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:


*

*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.
 A: 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.
A: 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.
