of 1000 euros, available through 2012, for any computer program that could beat him in even one game of a ten-game match. For many years, computer programs lagged far behind human players. However, since 2010 several Havannah-playing programs have applied Monte Carlo tree search techniques resulting in some notable improvement in playing strength. The "Havannah Challenge 2012" was held October 15–19, 2012 during which Freeling played ten games against three of the strongest Havannah-playing programs available, playing (at least) one game as black and one as white against each opponent. Freeling lost the challenge when he had to resign a game with white against the Lajkonik program. Until 2019, the best humans were still by far stronger than computers. However, MetaTotoro, based on Polygames (an open-source project, initially developed by Facebook Artificial Intelligence Research and several universities), won four times in a row on the board of size 8 against the human player with the best ELO rank on LittleGolem, who was also the winner of various tournaments. This result was achieved by the same program as the one used for beating best humans at Hex. It is a zero-learning based algorithm, as in AlphaZero, but with novelties: boardsize invariance thanks to fully convolutional neural networks (as in U-Net) and global pooling. This allows growing architectures, meaning the program can learn on a small board, and then extrapolate on a large board. Computational complexity Solving Havannah is PSPACE-complete with respect to the size of the input graph. The proof is by a reduction from generalized geography and is based on using ring-threats to represent the geography graph. In detail, since Lichtenstein and Sipser have proved that generalized geography remained PSPACE-hard even if the graph is only bipartite and of degree at most 3, it only remains to construct an equivalent Havannah position from such a graph, which is accomplished by constructing various gadgets in Havannah. Reviews Jeux & Stratégie #9 References External links Official site MindSports.nl Havannah article on Sensei's Library Board games introduced in 1981 Abstract strategy games Connection games Ravensburger games