# Counting board states in a game?

I'd like to count the number of board states possible in the game Pentago. It's similar to tic-tac-toe, only the object is it get 5 in a row on a 6x6 board. I've created a strong AI for the game, but I'm wondering if the number of possible game states is low enough that the game can be "solved" completely.

My question then, is how many unique board states are possible? What techniques might I use in estimating the number of possible board states?

My best estimate is the obvious observation that since each board space can be one of three states, that there are less than 3^36 possible board states. I know the answer is much lower, because you can't have a board filled entirely of back marbles (players use black and white marbles; the equivalent of X and O in tic-tac-toe). I can think of 3 constraints which limit the possible board states:

1. There must be a nearly equal number of white and black marbles on the board. Since marbles are never removed there cannot be 6 black marbles and 1 white marble.
2. There can't be several sets of 5 marbles in a row. I suppose you could have 4 sets of 6 in a row if a player lined everything up just right so his final move game him six in a row vertically, horizontally and diagonally in both direction.
3. Board symmetry. Discussed further in this question.

Without counting symmetries or the 5-in-a-row constraints, the number of states consisting of $k$ black and $k$ white marbles is $\frac{36!}{k! k! (36-2k)!}$ for $0 \le k \le 18$, and the number of states consisting of $k+1$ black and $k$ white (I'm assuming black goes first) is $\frac{36!}{(k+1)! k! (36-2k-1)!}$ for $0 \le k \le 17$. The total is $24072650378629801$. Rather large for a "brute force" computation.

• The five in a row constraint should narrow that number down some... but probably still outside the range of brute force. – recursion.ninja Aug 16 '13 at 23:54
• Your $2.4\times 10^{16}$ is marginally less than $8$ times the $3,009,081,623,421,550$ given at perfect-pentago.net/details.html . This $8$ makes sense, if you think of symmetries of a square, though it is affected by self-symmetric positions and 5-in-a-row constraints. In practice, they back calculated all the positions for a given number of stones but threw them away after each level, only holding the positions up to $18$ stones in a permanent database – Henry Apr 6 '17 at 8:13

The number of possible states is huge. However, if by "solve" you mean "construct an AI which always draws as the second player" (as the game is almost definitely a draw given optimal play), it should be feasible.

Suppose you have a program which can usually guess a non-losing move quickly. This is probably easy, as in this game there won't be many losing moves which won't be punished immediately. Then you'll only have to examine multiple options for your opponent's moves, not for your own. As a result, you might be able to get by only examining about the square root of the total number of possible positions.

The other answer gives 24072650378629801 as an upper bound. The square root of this is about 150 million positions. This is a heck of a lot, but depending on your available resources and time, you could do it.

However, this program will only be able to draw as the second player- it takes a lot more work to be able to punish suboptimal play by the first player. You'd basically have to do everything that I just described, but from the first player's perspective, and on every single one of the 150 million positions. Memoization will be absolutely key if you want to attempt this. However, even this is probably possible too with enough computer resources - after all, they solved checkers, didn't they?

But for sanity purposes, you might just want to let your strong AI take over - for a small board, it's almost certainly good enough for any practical matter.

• Why are you so confident that it's a draw? Connect-Four is a first-player win with optimal play... – mjqxxxx Dec 31 '11 at 0:55
• Wikipedia says this game is a first-player win on a 15 by 15 board - it cites a reference and everything - and I figured that if it were a first-player win on a smaller board, then that would be a stronger result, someone would have figured it out sooner especially if it were as small as 6 by 6, and Wikipedia would have cited that instead. – Lopsy Dec 31 '11 at 1:02
• @Lopsy: This question is about Pentago, not Gomoku (i.e. “Five in a Row”). Moreover, the analysis of the latter (on a standard $15\times 15$ board) does not imply anything about the game played on a smaller board. – David Bevan Jan 1 '12 at 17:10
• Yikes - I had assumed from the original post's wording that there was no other difference between Pentago and Gomoku. Apologies. If it turns out that Pentago is a first-player win, though, then I believe my answer with "always draws as the second player" replaced with "always wins as the first player" still stands in principle, albeit with extra programming work and computation power necessary to pull it off. – Lopsy Jan 1 '12 at 21:33
• Wikipedia noted in January 2014 that it had been strongly solved for a first player win, pointing at perfect-pentago.net/details.html – Henry Apr 6 '17 at 7:50