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:
- 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.
- 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.
- Board symmetry. Discussed further in this question.