# Pentago is a First Player Win: Strongly Solving a Game Using Parallel In-Core Retrograde Analysis

arXiv: https://arxiv.org/abs/1404.0743 · HTML: https://mlsanity.com/paper/1404.0743/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2014.

## Built on by (most cited first, 1 of 1)

- [Scaling Laws for a Multi-Agent Reinforcement Learning Model](https://mlsanity.com/paper/2210.00849/) (2022)

## Abstract (arXiv)

We present a strong solution of the board game pentago, computed using exhaustive parallel retrograde analysis in 4 hours on 98304 (3 × 215) threads of NERSC's Cray Edison. At 3.0 × 1015 states, pentago is the largest divergent game solved to date by two orders of magnitude, and the only example of a nontrivial divergent game solved using retrograde analysis. Unlike previous retrograde analyses, our computation was performed entirely in-core, writing only a small portion of the results to disk; an out-of-core implementation would have been much slower. Symmetry was used to reduce branching factor and exploit instruction level parallelism. Despite a theoretically embarrassingly parallel structure, asynchronous message passing was required to fit the computation into available RAM, causing latency problems on an older Cray machine. All code and data for the project are open source, together with a website which combines database lookup and on-the-fly computation to interactively explore the strong solution.