Human planning in large state spaces

As AlphaZero has revolutionized the AI of planning in large state spaces, our lack of understanding of how humans plan when the number of possible futures is combinatorially large has come into stark contrast. The strand of psychology that tries to understand human chess play once seemed promising but is now virtually extinct. Instead, most computational cognitive scientists favor extremely simple planning tasks; I will argue that this is a mistake. I will show that it is possible to study human planning in tasks of intermediate complexity while maintaining experimental tractability and computational modelability. I will describe a series of experiments in my lab, mainly on a game we call four-in-a-row — a variant of tic-tac-toe and Go Moku. I will describe a computational model of human play, inspired by best-first search and fitted to human moves using inverse binomial sampling and Bayesian Adaptive Direct Search. This model predicts moves in unseen positions, decisions in unseen tasks, eye fixation patterns, mouse movements, and response times. The model allows us to computationally characterize the effects of expertise and time pressure, as well as the balance between model-based and model-free systems. More broadly, studying human planning in tasks of intermediate complexity in conjunction with AI-inspired algorithms might open up a new direction in cognitive science and might make comparisons between human and machine intelligence less strained.