18 August 2009

Stochastic Duels: Part 1

Picking up where I left off (more or less) in the introduction, consider the following simple game -

Some definitions:
This game is played in turns. Players firing at each other once each turn with a fixed probability of hitting the other. The game is over when one (or both) players are hit. If neither player has been hit, the game continues for another turn.

A and B are shorthand for the first and second players,
pA = probability player A will hit,
pB = probability player B will hit,
pA and pB are between 0 and 1.

qA = 1 – pA = probability player A will miss,
qB = 1 – pB = probability player B will miss,
and Q = qA*qB = probability both players miss (which I will need later).

And a bit of statistical probability notation; read “P[event | condition]” as “The probability of the event given the condition”, and "|" is read as "given" (but there might not always be a condition.) So “P[player A wins | game lasts one turn]” should be read as “The probability that player A wins given the game lasts one turn”. I’m going to work out P[player A wins], which is the overall probability of player A winning in any number of turns. Later on I'll put pA and pB inside the brackets so the descriptions are not so wordy.

On the first turn of play there are four possible outcomes, and probabilities of each outcome:
1) Player A hits and player B misses, (probability =) pA*qB
2) Player A misses and player B hits, qA*pB
3) Player A hits and player B hits, pA*pB (a draw)
4) Both players miss, qA*qB = Q.

Using the notation described above, outcome (1) is
P[player A wins | 1 turn] = pA*qB.
If neither player hits, outcome 4) above, the game goes on for another round.
Turn 2 looks similar to round 1, but the probably of no hits (Q) in round one is carried forward:

1) Player A hits and player B misses, (probability =) Q*pA*qB
2) Player A misses and player B hits, Q*qA*pB
3) Player A hits and player B hits, Q*pA*pB
4) Both players miss, Q*qA*qB = Q*Q = Q^2 (Q squared).

I will focus on the probability of player A winning (outcome 1) so this doesn’t get too tedious. If a game with one or two turns the probability of player A winning is the probability of winning in the first round plus the probability of winning in the second turn (if there is a second turn), which is:

P[ player A wins | 2 turns] = pA*qB + Q*pA*qB

Now if we carry this out to three turns, the probability of player A winning is:

P[ player A wins | 3 turns] = pA*qB + Q*pA*qB + (Q^2)*pA*qB

And four turns

P[ player A wins | 4 turns] = pA*qB + Q* pA*qB + (Q^2)* pA*qB + (Q^3)*pA*qB

If you see the pattern here, each turn a new tern is added on with Q to-the-power-of-X where X increase by one each term. And now the BIG leap: N turns ...

P[ player A wins | N turns] = pA*qB + Q*pA*qB + (Q^2)*pA*qB + Q^3)*pA*qB + … + (Q^N)*pA*qB

Where the ellipsis “…” assumes that I have filled in all the terms between 4 turns and N turns. With a bit of algebra this becomes

P[ player A wins | N turns] = pA*qB*(1 + Q + Q^2 + Q^3 + … + Q^N)

And if have studied calculus you may recognize the sum of terms in parentheses as a geometric series. If you don’t, that’s OK too; the point is there is a solution for this sum in a simple formula. As N gets larger the sum gets very close to 1/(1-Q), and as N goes to infinity the sum is exactly equal to 1/(1-Q). Therefore:

P[ player A wins ] = pA*qB/(1-Q)

And in a similar way we can calculate the probability of the other outcomes, which are

P[ player B wins ] = qA*pB/(1-Q) and
P[ “Draw” ] = pA*pB/(1-Q)

Examples:

P[ player A wins | pA=0.4 , pB=0.3 ] = 0.4828
P[ player B wins | pA=0.4 , pB=0.3 ] = 0.3103
P[ “Draw” | pA=0.4 , pB=0.3 ] = 0.2069

and the three probabilities should total to 1.o (maybe some rounding error).

P[ player A wins | pA=0.6 , pB=0.6 ] = 0.2857
P[ player B wins | pA=0.6 , pB=0.6 ] = 0.2857
P[ “Draw” | pA=0.6 , pB=0.6 ] = 0.4286

when pA = pB the probability of a draw gets large as pA and pB get bigger.

P[ player A wins | pA=0.1 , pB=0.05 ] = 0.5028
P[ player B wins | pA=0.1 , pB=0.05 ] = 0.4475
P[ “Draw” | pA=0.1 , pB=0.05 ] = 0.0497

I created a simple Google Spreadsheet which you can be use to try this for yourself.:

One more tidbit: The odds ratio that player A will win is:
P[ player A wins ] / P[ player B wins ].

In the next part I will consider the situation where one player has a range advantage, but the other moves faster.

[Update: I changed notation in an effort to improve readability, Players 1 and 2 are now A and B, p1 and p2 are now pA and pB, etc.]
GBR Giant Battling Robots Favicon

No comments: