http://forumserver.twoplustwo.com/25/pr ... e-1321490/

I figure somebody must've thought of this question before me...

**PROBLEM**

-----------------------------------------------------------------

Simple two-player turn based game --

**Board**: A board consists of N squares.

**Players**: There are two players, black and white, each have pieces/checkers of their own color.

**Turn**: A player takes a turn by placing one of their pieces onto a board square. Black goes first.

**The game ends when all squares are filled.**

Now suppose the game is randomized so that every final game state is assigned as either a win for black or white with equal probability.

Given that both players have complete information about the game and final states, what is the probability that this game is a win for black for board size N with perfect play?

----------------------------------------------------------

Examples:

N = 1: Obviously probability of black win is 1/2.

N = 2: The only way it's a loss for black is if both final states are a win for white. Therefore, probability is 3/4 that black wins.

N = 3: Now there are 3 final states. BBW. BWB. And WBB. So there are 2^3 = 8 possible games. Black wins in all of the games where 2 out of 3 or 3 out of 3 of the final states are black wins. So probability is 1/2 that it's a black win.

After a little bit of work, I find that for N=4, the answer is 54/64.

How bout for larger N?

I wrote a simple program that can solve it for N=[1 to 6], but beyond that it begins to become intractable with brute force.