Annabella and Bruce are playing "Almost Tic-Tac-Toe", in which an X is written on a line, and each player takes turns adding either a X or an O, in accordance with their choice.
Annabella goes first, and the goal is to avoid a sequence of three evenly spaced X's or O's; and the first person to do so loses. For instance, if the letters are XOXXOX, then Bruce has to put O because XOXXOXX is a losing position. Then, Annabella will lose because both XOXXOXOX and XOXXOXOO are losing positions.
Assuming that both of them play optimally after Annabella's first move, who wins if she starts putting down a second X on the line next to the initial one? What if she starts with an O?
Explain each of your answers with valid reasoning.
Let's say the "length" of the game is the length of the character string. The game must end by length 9 because (by inspection) all strings of length 9 have 3 repeats, i.e., the 9th letter cause its writer a loss.
Again by inspection, there are only 3 games still with no winner that are 8 in length are:
XXOOXXOO XOOXXOOX and XOXOOXOX. So either an XX or an XO beginning can win.
So, How can these arise?
Here are all the possible games:
X XO XOO
X XX XXO XXOO
X XO XOX XOXO XOXOO
X XX
X XO XOO XOOX XOOXO XOOXOO
X XX XXO XXOX XXOXO XXOXOO
X XO XOX XOXX XOXXO XOXXOO
X XX XXO XXOO XXOOX XXOOXO XXOOXOO
X XO XOX XOXO
X XO XOO XOOX XOOXX XOOXXO XOOXXOO
X XX XXO XXOX XXOXX XXOXXO XXOXXOO
X XO XOX XOXX
X XO XOX XOXO XOXOO XOXOOX XOXOOXO
X XO XOO XOOX XOOXO XOOXOX
X XX XXO XXOX XXOXO
X XO XOX XOXX XOXXO XOXXOX XOXXOXO
X XX XXO XXOO XXOOX XXOOXX XXOOXXO XXOOXXOO
X XO XOO XOOX XOOXX
X XX XXO XXOX XXOXX
X XX XXO XXOO XXOOX XXOOXO XXOOXOX
X XO XOO XOOX XOOXX XOOXXO
X XX XXO XXOX XXOXX XXOXXO
X XO XOX XOXO XOXOO XOXOOX XOXOOXX
X XO XOX XOXX XOXXO XOXXOX
X XX XXO XXOO XXOOX XXOOXX
X XO XOO XOOX XOOXX XOOXXO XOOXXOO XOOXXOOX
X XO XOX XOXO XOXOO XOXOOX XOXOOXO XOXOOXOX
X XX XXO XXOO XXOOX XXOOXX XXOOXXO
These may be sorted (TBD) to make a decision tree that
plots a foolproof route to one of the three length 8
winners for Annabella.
a start
