Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Probability Discussions of probability theory

Reply
 
Thread Tools Display Modes
Old 04-13-2013, 05:42 PM   #1
pocketzeroes
veteran
 
Join Date: Aug 2010
Posts: 2,314
A simple randomized game

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

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.

Game ends when all squares are filled.

Now suppose the game is randomized so that every final game state is chosen as 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 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.

How bout for larger N?
pocketzeroes is offline   Reply With Quote
Old 04-13-2013, 08:03 PM   #2
Sherman
Carpal \'Tunnel
 
Sherman's Avatar
 
Join Date: Jun 2005
Location: Psychology Department
Posts: 7,764
Re: A simple randomized game

I do not understand how it is decided that a player wins. If black goes first, players take turns, and the game ends when all squares are filled, how is black ever going to have fewer squares than white? Obviously that must not be how the winner is decided.

So how do you decide who wins? Is it, "If the game matches this state, then black/white wins?"
Sherman is offline   Reply With Quote
Old 04-13-2013, 08:13 PM   #3
pocketzeroes
veteran
 
Join Date: Aug 2010
Posts: 2,314
Re: A simple randomized game

Quote:
Originally Posted by Sherman View Post
I do not understand how it is decided that a player wins. If black goes first, players take turns, and the game ends when all squares are filled, how is black ever going to have fewer squares than white? Obviously that must not be how the winner is decided.

So how do you decide who wins? Is it, "If the game matches this state, then black/white wins?"
Yes, take N=4. There are 6 possible final states: BBWW, BWBW, BWWB, WBBW, WBWB, WWBB.

So knowing each final state is win or lose, there are 2^6 = 64 possible games.

We randomly select one of these 64 games. What is the probability it is a win for black if both players play perfectly? I think it's 54/64... In other words, in 54 of the 64 possible games, black wins with perfect play. The other 10 white wins. But I'm not sure I did it right.
pocketzeroes is offline   Reply With Quote
Old 04-13-2013, 09:03 PM   #4
pocketzeroes
veteran
 
Join Date: Aug 2010
Posts: 2,314
Re: A simple randomized game

Note, taking account of symmetries, there are only 10 "unique" game classes for N=4.

I'll name games like this: "{BBWW, BWBW, BWWB}" is the game where black wins in each of the states listed.

The game {BBWW, WWBB} is symmetrically equivalent to {BWBW, WBWB}. You just permutate the board squares to get from one to the other. So if we find out one is a win/loss for black, we know the other has an equivalent evaluation. But they are both different than {BBWW, BWBW}.

As it happens, black loses the game {BBWW, WWBB}, but wins the game {BBWW, BWBW}.


White wins in only these classes.
{} (1 game)
{BBWW} (6 equivalent games), and
{BBWW, WWBB} (3 equivalent games).

Adding up the number of games in each class, we get 10. That's where the 54/64 win probability for black (and 10/64 for white) came from above.

Last edited by pocketzeroes; 04-13-2013 at 09:13 PM.
pocketzeroes is offline   Reply With Quote
Old 04-13-2013, 10:14 PM   #5
EvilSteve
 
EvilSteve's Avatar
 
Join Date: Mar 2006
Location: 2p2 afterlife
Posts: 13,198
Re: A simple randomized game

Number of final game states: F(n) = n choose (n div 2)
Where "div" signifies integer division, ie 6 div 2 = 7 div 2 = 3.
Number of ways to assign wins/losses to all the final states, ie the number of possible games: G(n) = 2 ^ F(n)

Code:
 n     F(n)       G(n)
 1       1          2
 2       2          4
 3       3          8
 4       6         64
 5      10      1,024
 6      20  1,048,576
And each game is a forced win for black if and only if there exists a first move which does not allow white to have a forced win. That's about all I've got so far.
EvilSteve is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 08:47 PM.


Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online