Effective learning often involves actively querying the environment for information that disambiguates potential hypotheses. However, the space of observations available in any situation can vary greatly in potential "informativeness." In this report, we study participants' ability to gauge the information value of potential observations in a learning task based on the children's game Battleship. Participants selected observations to disambiguate between a large number of potential game configurations subject to information-collection costs and penalties for making errors in a test phase. An "ideal-learner" model is developed to quantify the utility of possible observations in terms of the expected gain in points from knowing the outcome of that observation. The model was used as a tool for both measuring search efficiency, and for classifying various types of information collection decisions. We find that participants are generally effective at maximizing gain relative to their current state of knowledge and the constraints of the task. In addition, search behavior shifts between an slower, but more efficient "exploitive" mode of local search and a faster, less efficient pattern of "exploration."