{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T11:41:09Z","timestamp":1767181269573,"version":"build-2238731810"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1010358","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000}}],"reference-count":66,"publisher":"Public Library of Science (PLoS)","issue":"8","license":[{"start":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T00:00:00Z","timestamp":1660089600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["3081\/21"],"award-info":[{"award-number":["3081\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2185\/20"],"award-info":[{"award-number":["2185\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>People have limited computational resources, yet they make complex strategic decisions over enormous spaces of possibilities. How do people efficiently search spaces with combinatorially branching paths? Here, we study players\u2019 search strategies for a winning move in a \u201ck-in-a-row\u201d game. We find that players use scoring strategies to prune the search space and augment this pruning by a \u201cshutter\u201d heuristic that focuses the search on the paths emanating from their previous move. This strong pruning has its costs\u2014both computational simulations and behavioral data indicate that the shutter size is correlated with players\u2019 blindness to their opponent\u2019s winning moves. However, simulations of the search while varying the shutter size, complexity levels, noise levels, branching factor, and computational limitations indicate that despite its costs, a narrow shutter strategy is the dominant strategy for most of the parameter space. Finally, we show that in the presence of computational limitations, the shutter heuristic enhances the performance of deep learning networks in these end-game scenarios. Together, our findings suggest a novel adaptive heuristic that benefits search in a vast space of possibilities of a strategic game.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1010358","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T13:39:29Z","timestamp":1660138769000},"page":"e1010358","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":3,"title":["Adaptive search space pruning in complex strategic problems"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2303-3684","authenticated-orcid":true,"given":"Ofra","family":"Amir","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9468-5159","authenticated-orcid":true,"given":"Liron","family":"Tyomkin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6953-6589","authenticated-orcid":true,"given":"Yuval","family":"Hart","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,8,10]]},"reference":[{"issue":"5","key":"pcbi.1010358.ref001","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1037\/h0093599","article-title":"On problem-solving","volume":"58","author":"K Duncker","year":"1945","journal-title":"Psychological Monographs"},{"key":"pcbi.1010358.ref002","doi-asserted-by":"crossref","DOI":"10.1093\/oxfordhb\/9780199734689.001.0001","volume-title":"The Oxford Handbook of Thinking and Reasoning","author":"KJ Holyoak","year":"2012"},{"key":"pcbi.1010358.ref003","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511615771","volume-title":"The Psychology of Problem Solving","author":"JE Davidson","year":"2003"},{"key":"pcbi.1010358.ref004","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1017\/CBO9780511615771.010","volume-title":"The Psychology of Problem Solving","author":"N Schwarz","year":"2003"},{"issue":"3","key":"pcbi.1010358.ref005","doi-asserted-by":"crossref","first-page":"e1002410","DOI":"10.1371\/journal.pcbi.1002410","article-title":"Bonsai trees in your head: how the Pavlovian system sculpts goal-directed choices by pruning decision trees","volume":"8","author":"QJ Huys","year":"2012","journal-title":"PLoS computational biology"},{"issue":"10","key":"pcbi.1010358.ref006","doi-asserted-by":"crossref","first-page":"3098","DOI":"10.1073\/pnas.1414219112","article-title":"Interplay of approximate planning strategies","volume":"112","author":"QJ Huys","year":"2015","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"pcbi.1010358.ref007","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1146\/annurev-psych-120709-145346","article-title":"Heuristic Decision Making","volume":"62","author":"G Gigerenzer","year":"2011","journal-title":"Annual Review of Psychology"},{"issue":"45","key":"pcbi.1010358.ref008","doi-asserted-by":"crossref","first-page":"12868","DOI":"10.1073\/pnas.1609094113","article-title":"Adaptive integration of habits into depth-limited planning defines a habitual-goal\u2013directed spectrum","volume":"113","author":"M Keramati","year":"2016","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"pcbi.1010358.ref009","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/j.cognition.2015.07.004","article-title":"Children adapt their questions to achieve efficient search","volume":"143","author":"A Ruggeri","year":"2015","journal-title":"Cognition"},{"issue":"1","key":"pcbi.1010358.ref010","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1037\/a0021110","article-title":"Hypothesis generation, sparse categories, and the positive test strategy","volume":"118","author":"DJ Navarro","year":"2011","journal-title":"Psychological Review"},{"key":"pcbi.1010358.ref011","doi-asserted-by":"crossref","first-page":"103965","DOI":"10.1016\/j.cognition.2019.05.002","article-title":"Stepwise versus globally optimal search in children and adults","volume":"191","author":"B Meder","year":"2019","journal-title":"Cognition"},{"key":"pcbi.1010358.ref012","first-page":"271","volume-title":"Handbook of learning & cognitive processes: V. Human information","author":"HA Simon","year":"1978"},{"issue":"1","key":"pcbi.1010358.ref013","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1080\/03640210701802071","article-title":"A rational analysis of rule-based concept learning","volume":"32","author":"ND Goodman","year":"2008","journal-title":"Cognitive science"},{"issue":"4","key":"pcbi.1010358.ref014","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.cogdev.2012.07.005","article-title":"Theory learning as stochastic search in the language of thought","volume":"27","author":"TD Ullman","year":"2012","journal-title":"Cognitive Development"},{"issue":"2","key":"pcbi.1010358.ref015","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.cognition.2011.11.005","article-title":"Bootstrapping in a language of thought: A formal model of numerical concept learning","volume":"123","author":"ST Piantadosi","year":"2012","journal-title":"Cognition"},{"key":"pcbi.1010358.ref016","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.cogpsych.2017.05.006","article-title":"Learning physical parameters from dynamic scenes","volume":"104","author":"TD Ullman","year":"2018","journal-title":"Cognitive psychology"},{"issue":"1","key":"pcbi.1010358.ref017","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo Sampling Methods Using Markov Chains and Their Applications","volume":"57","author":"WK Hastings","year":"1970","journal-title":"Biometrika"},{"key":"pcbi.1010358.ref018","doi-asserted-by":"crossref","unstructured":"Schulz L. Finding New Facts; Thinking New Thoughts. In: Xu F, Kushnir T, editors. Advances in Child Development and Behavior. vol. 43 of Rational Constructivism in Cognitive Development. JAI; 2012. p. 269\u2013294. Available from: http:\/\/www.sciencedirect.com\/science\/article\/pii\/B9780123979193000101.","DOI":"10.1016\/B978-0-12-397919-3.00010-1"},{"issue":"7","key":"pcbi.1010358.ref019","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.tics.2012.06.004","article-title":"The origins of inquiry: inductive inference and exploration in early childhood","volume":"16","author":"L Schulz","year":"2012","journal-title":"Trends in Cognitive Sciences"},{"key":"pcbi.1010358.ref020","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.cogdev.2014.12.008","article-title":"Imagination and the generation of new ideas","volume":"34","author":"RW Magid","year":"2015","journal-title":"Cognitive Development"},{"issue":"6245","key":"pcbi.1010358.ref021","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1126\/science.aac6076","article-title":"Computational rationality: A converging paradigm for intelligence in brains, minds, and machines","volume":"349","author":"SJ Gershman","year":"2015","journal-title":"Science"},{"issue":"5","key":"pcbi.1010358.ref022","doi-asserted-by":"crossref","first-page":"e1002055","DOI":"10.1371\/journal.pcbi.1002055","article-title":"Speed\/accuracy trade-off between the habitual and the goal-directed processes","volume":"7","author":"M Keramati","year":"2011","journal-title":"PLoS computational biology"},{"issue":"3","key":"pcbi.1010358.ref023","doi-asserted-by":"crossref","first-page":"e1006827","DOI":"10.1371\/journal.pcbi.1006827","article-title":"Optimizing the depth and the direction of prospective planning using information values","volume":"15","author":"CE Sezener","year":"2019","journal-title":"PLoS computational biology"},{"key":"pcbi.1010358.ref024","volume-title":"Thought and choice in chess","author":"AD De Groot","year":"1978"},{"issue":"1","key":"pcbi.1010358.ref025","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0010-0285(73)90004-2","article-title":"Perception in chess","volume":"4","author":"WG Chase","year":"1973","journal-title":"Cognitive psychology"},{"issue":"7587","key":"pcbi.1010358.ref026","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1038\/nature16961","article-title":"Mastering the game of Go with deep neural networks and tree search","volume":"529","author":"D Silver","year":"2016","journal-title":"Nature"},{"key":"pcbi.1010358.ref027","doi-asserted-by":"crossref","unstructured":"van Opheusden B, Bnaya Z, Galbiati G, Ma WJ. Do People Think Like Computers? In: International conference on computers and games. Springer; 2016. p. 212\u2013224.","DOI":"10.1007\/978-3-319-50935-8_20"},{"key":"pcbi.1010358.ref028","unstructured":"van Opheusden B, Galbiati G, Bnaya Z, Li Y, Ma WJ. A computational model for decision tree search. In: COGSCI; 2017."},{"issue":"1","key":"pcbi.1010358.ref029","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0001-6918(91)90065-8","article-title":"Aspects of skilled imagery in blindfold chess","volume":"77","author":"P Saariluoma","year":"1991","journal-title":"Acta psychologica"},{"issue":"1","key":"pcbi.1010358.ref030","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1111\/j.1467-9280.1996.tb00666.x","article-title":"The roles of recognition processes and look-ahead search in time-constrained expert problem solving: Evidence from grand-master-level chess","volume":"7","author":"F Gobet","year":"1996","journal-title":"Psychological science"},{"issue":"4","key":"pcbi.1010358.ref031","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0004-3702(75)90019-3","article-title":"An analysis of alpha-beta pruning","volume":"6","author":"DE Knuth","year":"1975","journal-title":"Artificial intelligence"},{"key":"pcbi.1010358.ref032","volume-title":"The think aloud method: a practical approach to modelling cognitive processes","author":"M van Someren","year":"1994"},{"key":"pcbi.1010358.ref033","doi-asserted-by":"crossref","unstructured":"Dunbar K. Problem Solving. In: A Companion to Cognitive Science. Wiley; 2017. p. 289\u2013298. Available from: https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/9781405164535.ch20.","DOI":"10.1002\/9781405164535.ch20"},{"issue":"6022","key":"pcbi.1010358.ref034","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1126\/science.1192788","article-title":"How to grow a mind: Statistics, structure, and abstraction","volume":"331","author":"JB Tenenbaum","year":"2011","journal-title":"science"},{"key":"pcbi.1010358.ref035","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/j.visres.2015.03.004","article-title":"Discovering hierarchical motion structure","volume":"126","author":"SJ Gershman","year":"2016","journal-title":"Vision Research"},{"issue":"6","key":"pcbi.1010358.ref036","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1016\/j.conb.2012.05.008","article-title":"Hierarchical reinforcement learning and decision making","volume":"22","author":"MM Botvinick","year":"2012","journal-title":"Current Opinion in Neurobiology"},{"key":"pcbi.1010358.ref037","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.conb.2016.01.014","article-title":"Toward the neural implementation of structure learning","volume":"37","author":"DGR Tervo","year":"2016","journal-title":"Current opinion in neurobiology"},{"issue":"6","key":"pcbi.1010358.ref038","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1037\/rev0000075","article-title":"Strategy selection as rational metareasoning","volume":"124","author":"F Lieder","year":"2017","journal-title":"Psychological review"},{"key":"pcbi.1010358.ref039","unstructured":"Ullman T, Siegel M, Tenenbaum J, Gershman S. Coalescing the Vapors of Human Experience into a Viable and Meaningful Comprehension. In: Proceedings of the 38th Annual Meeting of the Cognitive Science Society; 2016. Available from: https:\/\/mindmodeling.org\/cogsci2016\/papers\/0264\/index.html."},{"key":"pcbi.1010358.ref040","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.cognition.2018.04.017","article-title":"Remembrance of inferences past: Amortization in human hypothesis generation","volume":"178","author":"I Dasgupta","year":"2018","journal-title":"Cognition"},{"key":"pcbi.1010358.ref041","volume-title":"Human judgments and optimality","author":"WR Reitman","year":"1964"},{"issue":"4","key":"pcbi.1010358.ref042","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1037\/0033-295X.101.4.608","article-title":"A rational analysis of the selection task as optimal data selection","volume":"101","author":"M Oaksford","year":"1994","journal-title":"Psychological Review"},{"issue":"9","key":"pcbi.1010358.ref043","doi-asserted-by":"crossref","first-page":"e1004501","DOI":"10.1371\/journal.pcbi.1004501","article-title":"Prospective optimization with limited resources","volume":"11","author":"J Snider","year":"2015","journal-title":"PLoS computational biology"},{"issue":"11","key":"pcbi.1010358.ref044","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1038\/s41593-018-0232-z","article-title":"Prioritized memory access explains planning and hippocampal replay","volume":"21","author":"MG Mattar","year":"2018","journal-title":"Nature neuroscience"},{"issue":"1","key":"pcbi.1010358.ref045","first-page":"161","article-title":"Theories of bounded rationality","volume":"1","author":"HA Simon","year":"1972","journal-title":"Decision and organization"},{"key":"pcbi.1010358.ref046","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1654.001.0001","volume-title":"Bounded rationality: The adaptive toolbox","author":"G Gigerenzer","year":"2002"},{"issue":"9","key":"pcbi.1010358.ref047","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1037\/0003-066X.58.9.697","article-title":"A perspective on judgment and choice: mapping bounded rationality","volume":"58","author":"D Kahneman","year":"2003","journal-title":"American psychologist"},{"issue":"2","key":"pcbi.1010358.ref048","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1023\/A:1009944326196","article-title":"Bounded rationality in individual decision making","volume":"1","author":"C Camerer","year":"1998","journal-title":"Experimental economics"},{"issue":"2","key":"pcbi.1010358.ref049","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1111\/tops.12142","article-title":"Rational use of cognitive resources: Levels of analysis between the computational and the algorithmic","volume":"7","author":"TL Griffiths","year":"2015","journal-title":"Topics in cognitive science"},{"issue":"2","key":"pcbi.1010358.ref050","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1111\/tops.12088","article-title":"Decision Theory with Resource-Bounded Agents","volume":"6","author":"JY Halpern","year":"2014","journal-title":"Topics in cognitive science"},{"key":"pcbi.1010358.ref051","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/j.jet.2014.04.007","article-title":"Algorithmic rationality: Game theory with costly computation","volume":"156","author":"JY Halpern","year":"2015","journal-title":"Journal of Economic Theory"},{"issue":"2","key":"pcbi.1010358.ref052","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0896-6273(02)00971-6","article-title":"Banburismus and the Brain: Decoding the Relationship between Sensory Stimuli, Decisions, and Reward","volume":"36","author":"JI Gold","year":"2002","journal-title":"Neuron"},{"issue":"3","key":"pcbi.1010358.ref053","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.tins.2004.01.006","article-title":"Psychology and neurobiology of simple decisions","volume":"27","author":"PL Smith","year":"2004","journal-title":"Trends in Neurosciences"},{"key":"pcbi.1010358.ref054","doi-asserted-by":"crossref","first-page":"e06678","DOI":"10.7554\/eLife.06678","article-title":"Tuning the speed-accuracy trade-off to maximize reward rate in multisensory decision-making","volume":"4","author":"J Drugowitsch","year":"2015","journal-title":"eLife"},{"issue":"12","key":"pcbi.1010358.ref055","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1038\/s41562-018-0467-4","article-title":"Generalization guides human exploration in vast decision spaces","volume":"2","author":"CM Wu","year":"2018","journal-title":"Nature Human Behaviour"},{"issue":"4","key":"pcbi.1010358.ref056","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1037\/0033-295X.112.4.979","article-title":"Finding useful questions: on Bayesian diagnosticity, probability, impact, and information gain","volume":"112","author":"JD Nelson","year":"2005","journal-title":"Psychological Review"},{"issue":"1","key":"pcbi.1010358.ref057","first-page":"427","article-title":"Adaptive submodularity: theory and applications in active learning and stochastic optimization","volume":"42","author":"D Golovin","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"10","key":"pcbi.1010358.ref058","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1162\/jocn_a_01263","article-title":"Planning Complexity Registers as a Cost in Metacontrol","volume":"30","author":"W Kool","year":"2018","journal-title":"Journal of Cognitive Neuroscience"},{"key":"pcbi.1010358.ref059","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/9781118920497.ch10","volume-title":"The Wiley handbook of cognitive control","author":"W Kool","year":"2017"},{"issue":"1","key":"pcbi.1010358.ref060","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1146\/annurev-neuro-072116-031526","article-title":"Toward a Rational and Mechanistic Account of Mental Effort","volume":"40","author":"A Shenhav","year":"2017","journal-title":"Annual Review of Neuroscience"},{"issue":"3","key":"pcbi.1010358.ref061","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.cognition.2010.10.001","article-title":"The double-edged sword of pedagogy: Instruction limits spontaneous exploration and discovery","volume":"120","author":"E Bonawitz","year":"2011","journal-title":"Cognition"},{"issue":"4","key":"pcbi.1010358.ref062","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.cogdev.2012.07.005","article-title":"Theory learning as stochastic search in the language of thought","volume":"27","author":"TD Ullman","year":"2012","journal-title":"Cognitive Development"},{"issue":"10","key":"pcbi.1010358.ref063","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/j.tics.2014.06.006","article-title":"Probabilistic models, learning algorithms, and response variability: Sampling in cognitive development","volume":"18","author":"E Bonawitz","year":"2014","journal-title":"Trends in cognitive sciences"},{"key":"pcbi.1010358.ref064","doi-asserted-by":"crossref","unstructured":"Dworkin L, Kearns M. From \u201cIn\u201d to \u201cOver\u201d: Behavioral Experiments on Whole-Network Computation. In: Third AAAI Conference on Human Computation and Crowdsourcing; 2015.","DOI":"10.1609\/hcomp.v3i1.13223"},{"key":"pcbi.1010358.ref065","volume-title":"Computers and intractability","author":"MR Garey","year":"2002"},{"key":"pcbi.1010358.ref066","unstructured":"Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:171201815. 2017;."}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1010358","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T02:30:07Z","timestamp":1676341807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1010358"}},"subtitle":[],"editor":[{"given":"Samuel J.","family":"Gershman","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,8,10]]},"references-count":66,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8,10]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1010358","relation":{},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,10]]}}}