A randomized game

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
grovert
Posts: 5
Joined: Sun Apr 14, 2013 5:39 pm

A randomized game

Post by grovert » Sun Apr 14, 2013 5:52 pm

I originally posted this question here:
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.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: A randomized game

Post by thundre » Mon Apr 15, 2013 1:07 pm

I'm curious about your results up to N=6. Does it look like the probability converges?

Some notes which you've probably thought of but might be new to others reading this:

There are N! possible sequences of play.
There are C(N,N/2) end states.
There are 2C(N,N/2) end state sets which determine strategy.

On a move with an even number of choices, a player eliminates half of the potential end states. If the number of choices is odd, it's less. floor(n/2)/n
Image

grovert
Posts: 5
Joined: Sun Apr 14, 2013 5:39 pm

Re: A randomized game

Post by grovert » Mon Apr 15, 2013 11:51 pm

N=1 -- p = 1/2 = .5
N=2 -- p = 3/4 = .75
N=3 -- p = 4/8 = .5
N=4 -- p = 54/64 ~= .844
N=5 -- p = 476/1024 ~= .465
N=6 -- p = 964428/1048576 ~= .920

Looks like that as N increases, p approaches 1 for even N, and (probably) 0 for odd N.

grovert
Posts: 5
Joined: Sun Apr 14, 2013 5:39 pm

Re: A randomized game

Post by grovert » Tue Apr 16, 2013 12:05 am

An easier problem is as follows:
-- The game is same as the first post, except a final state is determined by the move list. E.g., for N=4, the game with move sequence 1-2-3-4 is different than 3-4-1-2 even though both would yield board states "BWBW" as the first game is defined.
-- Each final state is assigned a win for black with probability b.

Now the recurrence is straightforward
N=1 -- p(1) = b
N=2 -- p(2) = 1 - p(1)^2
N=3 -- p(3) = 1 - p(2)^3
...
p(1) = b
p(N) = 1 - p(N-1)^N

It's interesting to see that the asymptotic behavior changes near b = 0.588 (looks like an irrational). For b less than this value, p(N) approaches 1 for even N, and 0 for odd N. For b greater than that value, p(N) approaches 0 for even N, and 0 for odd N. I was curious if this number pops up anywhere else.

grovert
Posts: 5
Joined: Sun Apr 14, 2013 5:39 pm

Re: A randomized game

Post by grovert » Tue Apr 16, 2013 12:19 am

Another interesting "Project Euler"ish thing that popped up from the problem in my first post.

For N=4, there are 2^(C(4,2)) = 2^6 = 64 possible games. But there are only 10 unique classes of games.

We can define a game as the set of winning states for black. So, {BBWW}, {}, {BWBW}, and {BWBW, BWWB, WWBB} are all different games. However, {BBWW} is symmetrically equivalent to {BWBW} in that permutating board spaces will transform one to the other. Similarly {BBWW, BWBW}~={BWWB, WBWB}. But {BBWW, BWBW} is not equivalent to {BWWB, WBBW}.

White wins the game {BBWW, WWBB}, but loses the game {BBWW, BWBW}.

White wins only these games:
{} (1 equivalent game)
{BBWW} (6 equivalent games)
{BBWW, WWBB} (3 equivalent games)
==> white wins 10/64 games. Black wins 54/64 games.

For larger N, how do we enumerate unique games? How many game classes exist for a given N?

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: A randomized game

Post by thundre » Tue Apr 16, 2013 1:09 pm

grovert wrote:For N=4, there are 2^(C(4,2)) = 2^6 = 64 possible games. But there are only 10 unique classes of games.
I see what you mean. I'll try to enumerate the classes.

0. Black wins all 6 outcomes, 1 case.
1. White wins one specific outcome, 6 cases.
2A. White wins two outcomes which are opposites of each other, e.g. {BWBW,WBWB}, 3 cases.
2B. White wins two outcomes which intersect in one BW pair and are opposites in another, 12 cases.
3A. White wins three outcomes which intersect in a common W square, e.g. {WBBW, WBWB, WWBB}, 4 cases.
3B. White wins three outcomes which form a triangle -- all pairwise intersections contain exactly one W, e.g. {WWBB, WBWB, BWWB}, 4 cases.
3C. White wins three outcomes, two of which are opposites of each other, 12 cases.
4A. Black wins two outcomes which are opposites of each other, e.g. {BWBW,WBWB}, 3 cases.
4B. Black wins two outcomes which intersect in one BW pair and are opposites in another, 12 cases.
5. Black wins one specific outcome, 6 cases.
6. White wins all 6 outcomes, 1 case.
Image

grovert
Posts: 5
Joined: Sun Apr 14, 2013 5:39 pm

Re: A randomized game

Post by grovert » Tue Apr 16, 2013 3:33 pm

thundre wrote:
grovert wrote:For N=4, there are 2^(C(4,2)) = 2^6 = 64 possible games. But there are only 10 unique classes of games.
I see what you mean. I'll try to enumerate the classes.
Oops... That's 11. Looks like I counted wrong.

Post Reply