This project implements a strong solution of the board game pentago, which means that perfect play can be efficiently computed starting from any position. The results can be explored at https://perfect-pentago.net. The associated paper is Irving 2014, Pentago is a first-player win.

In the quest towards a strong solution, a total of five separate engines were implemented, three forward tree search engines and two backwards endgame engines. The final strong solution uses only the backwards engines, but the strongest forward engine was essential in developing and testing the backwards engines. Descriptions of the various engines are given below.

The easiest interface to the strong solution is the website at https://perfect-pentago.net, implemented in the web directory. Positions with 17 or fewer stones are looked up in a 3.7 TB database using a minimal node.js server (web/server). Positions with 18 or more stones are solved from scratch in the client, using small-scale backwards engine compiled to WebAssembly.

The pentago code is released under a BSD license, and the 3.7 TB data set is released into the public domain for anyone who wants to tinker around: please contact me if you want access to the raw data!

For background on the complexity of pentago and the applicability of a variety of solution algorithms, see Niklas Buscher's 2011 thesis "On Solving Pentago", which analyzed the game but did not solve it. Irving 2014 documents the strong solution in paper form.

Dependencies

The code is C++, with node.js for the backend server. The main dependencies are

• bazel: Build system
• mpi: OpenMPI, MPICH2, etc.
• node.js >= 8.9: Asynchronous javascript framework

Bazel handles a few extra dependencies automatically (see MODULE.bazel for details).

Installation

On Mac:

brew install bazel openmpi node llvm

On Ubuntu:

sudo apt-get install libopenmpi-dev

Then build and test:

# Build and test C++
bazel test -c opt --copt=-march=native ...
# Build and test node.js server
cd web/server
npm install
node unit.js all
# Build frontend webpage
cd web/client
make public

Website

The website https://perfect-pentago.net is a static Firebase frontend that talks to a node.js Google Cloud Function. To test and deploy the server:

cd web/server
node unit.js all
./deploy

To deploy the client:

cd pentago/web/client
npm install
make
(cd src && node unit.js)
npm run deploy
# If there is an error like 'resolving hosting target of a site with no site name...', do
firebase logout
firebase login

Algorithm summary

Forward engines

The first forward engine was a naive alpha-beta tree search code, plus a few pentago specific optimizations. Performance was dismal: the code reached only to 4 or 5 ply (here one ply means the combination of stone placement and quadrant rotation). The problem was branching factor, which starts out at a frightening 288 possible first moves (36 empty spots times 8 rotations).

Based on a belief that pentago was likely a tie (wrong!), I modified the solver so that the second player always reversed the rotation of the first player. This can't be any better for the second player, so if the result was a tie the game would be solved. Unfortunately, this "simple" solver declared the game to be a first-player win after 15 moves, providing no information about the real value of the game.

The key to the speed of the simple solver was eliminating the branching factor due to rotations. The final forward solver accomplished the same thing without weakening the second player. Instead of computing the value of one board at a time, this "super" solver operated on 256 different rotated version of a given board in parallel using SSE instructions. This also allowed the transposition tables to take advantage of the full 2048 element symmetry group of all global+local transpositions. With rotations eliminated, the supersolver managed to compute out to 17 ply, declaring the game up to that point a tie. See pentago/search/superengine.{h,cpp} for the core algorithm.

Parallelizing the engine would get further, but I still thought the game was a tie, and no forward engine would reach all the way to move 36. The similar games gomoku and renju were solved using threat space search, but it was unclear how to combine this technique with a rotation abstracted solver. So much for going forward.

A massively parallel backward engine

What about backward? Typically, backward (or retrograde) analyses are used to solve convergent games, where the number of positions decreases towards the end of the game. The canonical examples are chess and checkers, where fewer pieces near the end mean fewer positions. Pentago is divergent: the number of positions increases exponentially all the way to ply 24, but the total number of positions is only