Adaptive search space pruning in complex strategic problems

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’ search strategies for a winning move in a “k-in-a-row” game. We find that players use scoring strategies to prune the search space and augment this pruning by a “shutter” heuristic that focuses the search on the paths emanating from their previous move. This strong pruning has its costs—both computational simulations and behavioral data indicate that the shutter size is correlated with players’ blindness to their opponent’s 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.Author summary: Search problems usually have a common trade-off between accuracy and computational resources; Finding the best solution usually requires an exhaustive search, while limiting computations usually decreases the quality of solutions. Yet, humans provide high-quality solutions for complex problems despite having limited computational resources. How do they do that? Here, we analyze people’s behavior in a strategic game of “k-in-a-row” that has an enormous space of possibilities. We find that people strongly prune the search space by using scoring strategies to evaluate each possibility and augment this pruning with a shutter heuristic that limits their search to the possible winning paths from their last move. Similar to other adaptive heuristics, the shutter heuristic provides a strong reduction in the computations the searcher needs to carry out while maintaining on par accuracy rates. Finally, this adaptive heuristic generalizes to the performance of deep learning networks when playing with limited computational resources.