Sunday 27 June 2010

Taking turns fairly

In most turn based games, players alternate ABABABAB..., such as in chess. It's not exactly fair though, because the first player is one move ahead of their opponent half the time. Or to put it another way, player B alternates between being behind one move, and being on a equal number of moves. That's why white tends to win more often in chess. In other games, such as hex, it can be proven that this gives the first player a 'winning strategy'. This is game-theory speak to mean that there exists a way of playing that can guarantee a player a win, regardless of the opponent's strategy.

In tennis tie-breakers, this is improved slightly to ABBAABBA..., so that B is ahead just as often as A. I think this works well because the results of a previous point have almost no effect on future play, other than perhaps the psychological effect of the score. This is not the case in a game like chess however, because giving a player 2 turns in a row probably leads to an easy early win to one of the players (I need to check this).

I was thinking though, this is still not perfect, because although player B is ahead by 1 turn equally as often as A, if you look at the tally not of the number of moves, but the tally of the number of times a player is ahead by a move, B is always behind or equal. So in the sequence above, after 8 moves, both players have been ahead of the other player twice, but A was always equal or ahead by one on that count. (eg after 5 moves A had been ahead twice to B's once, but then after 7 moves B catches up to be ahead twice, so the tally is at 2-2).

So I came up with this sequence:
ABBABAABBAABABBABAABABBAABBABAAB..., which I think balances it out.
The algorithm is this:
1. Start with player A
2. After turn 2^n, play the opposite of all moves so far.

If I put commas every 2^n, it might be clearer:
A,B,BA,BAAB,BAABABBA,BAABABBAABBABAAB, ...

I think that this will balance out all 'n-tallies'. The n-tally is the number of times a player is ahead on the n-1 tally. The 1-tally is just the number of moves so far.

I guess that there is still some slight advantage to player A, but that this has been diminished as much as possible.

I can see though that in the game of 2x2 hex, it just gives a winning strategy to player B. I wonder however, if there are some nontrivial games that it changes the game from a first player win to a forceable draw.

In practice of course, the big drawback would be remembering whose turn it is. Unless someone made a cool digital watch with it programmed in.

-----

Postscript: Thanks to Prof Alan Knutson of Cornell who pointed out to me subsequently that this sequence has been known for a while. An interesting recent article about it is here:
http://www.guardian.co.uk/education/2010/jul/13/perfect-coffee-improbable-research