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.
At length 3, there are 3 possible active games: XXO, XOX, and XOO.
Following the decision tree below, Annabella (A) can always win.
Guaranteed wins are indicated with (***)
Case 1: XXO
-----------
A B A B A B A
X XX
X XX XXO XXOX XXOXX (A's mistake, A may now lose)
X XX XXO XXOX XXOXX XXOXXO (A is forced)
X XX XXO XXOX XXOXX XXOXXO XXOXXOO (A loses)
X XX XXO XXOX XXOXO (mistake by B)
X XX XXO XXOX XXOXO XXOXOO (A wins)
X XX XXO XXOO (A's right move)
X XX XXO XXOO XXOOX XXOOXX (B is forced; A's right move)
X XX XXO XXOO XXOOX XXOOXX XXOOXXO (B is forced)
X XX XXO XXOO XXOOX XXOOXX XXOOXXO XXOOXXOO (A wins) ***
X XX XXO XXOO XXOOX XXOOXO XXOOXOX (A's wrong move - A loses)
X XX XXO XXOO XXOOX XXOOXO XXOOXOO (A's wrong move - A loses)
Case 2: XOX
-----------
A B A B A B A
X XO XOX XOXX (A will win here with this move)
X XO XOX XOXX XOXXO XOXXOO (B is forced. A wins with O) ***
X XO XOX XOXX XOXXO XOXXOX (B is forced, A loses with X)
X XO XOX XOXX XOXXO XOXXOX XOXXOXO (A loses)
X XO XOX XOXO (A's mistake, may now lose)
X XO XOX XOXO XOXOO (right move by B)
X XO XOX XOXO XOXOO XOXOOX XOXOOXX (A forced; winning move by B)
X XO XOX XOXO XOXOO XOXOOX XOXOOXO (A forced, but mistake for B)
X XO XOX XOXO XOXOO XOXOOX XOXOOXO XOXOOXOX (A wins)
Case 3: XOO
-----------
A B A B A B A
X XO XOO (bad move for B; several ways for A to win)
X XO XOO XOOX XOOXX (A forced; one bad choice for B)
X XO XOO XOOX XOOXX XOOXXO (A forced)
X XO XOO XOOX XOOXX XOOXXO XOOXXOO (B forced)
X XO XOO XOOX XOOXX XOOXXO XOOXXOO XOOXXOOX (A forced and wins) ***
X XO XOO XOOX XOOXO XOOXOO (this choice for B lets A win with O) ***
X XO XOO XOOX XOOXO XOOXOX (this choice for B lets A win with X too) ***
Edited on May 22, 2023, 2:28 am
soln: decision tree
