Two expert and jaded tic-tac-toe players, after drawing for the n-th time, decided to add some randomness to their favorite game.

First, they used a coin to decide who would start. Then, that player would pick his initial move randomly. Next, the other player would also pick his answer randomly. Finally, from then on the game went on as usual, with each player playing in the best possible way.

For each player, what are the odds of winning, losing, or drawing?

(In reply to re(2): Solution by Penny)

My program has no set strategy, and I did not program it to detail if any of what you programmed is being followed.  It merely has a chooseMove function that tries every possible move, calling itself recursively to get the opponent's possible moves, etc., at each stage reporting back to the preceding caller whether that move for him was a winner or loser or led to a draw. At each level, if any move leads to a win, a loss is reported back to the caller.  If no move leads to a win, and some lead to losses and others to ties, then a tie is reported back to the caller.  If all moves lead to losses, a win is reported back to the caller (the other player).  Ultimately a win is recognized by 3 in a row and a tie by having no more empty spaces.

As the first two moves are in the preset sequence (all 12 possibilities), the outermost call is for the second player and therefore is reversed to make it a call for the first player.

Posted by Charlie on 2004-10-05 13:35:34