“What determines whether games are easy or difficult to solve? One very clear answer is how big the game is,” Bowling said.
Solvers have been making their way down the list. Tic-tac-toe is trivially solvable. Connect Four was first solved in 1988. Nine Men’s Morris in 1993. Go, on a 5×5 board, was solved in 2002, and checkers in 2007. As measured by state-space size, checkers is the most complex game yet solved.
The holy grails of this broad game-solving project are chess and go. By all accounts, their solution is unlikely in our lifetimes.
In 1965, Hans-Joachim Bremermann wrote that the “speed, memory, and processing capacity of any possible future computer equipment are limited by certain physical barriers: the light barrier, the quantum barrier, and the thermodynamical barrier. These limitations imply, for example, that no computer, however constructed, will ever be able to examine the entire tree of possible move sequences of the game of chess.”
