Unbeatable Tic Tac Toe

11 Mar 2013

I have been given the task to write a program that allows a user to play a game of Tic Tac Toe against the computer -- but the user must not ever win. In planning out the program I have begun some brainstorming:

1. User interface - command line, user will be prompted to give the place on a 9-square grid for their next move

2. What functions are necessary?

  • Print the board
  • User makes move
  • Computer makes a move
  • Computer decides best move (finds a win, blocks a win, or prepares to win)
  • Compare triples (up, down, left, right, diagonal up, diagonal down)
  • Convert triples to be compared mathematically (i.e. x=-1, o=1; take sum of all triples, optimize move based on highest or lowest triples sum, except if all three squares are filled). I have a feeling this won't be specific enough though.

3. Data structure

  • Board will be represented to computer as string of numbers 1-9
  • 123, 456, 789, 159, 147, 258, 369, 357 are the eight possible winning triples
  •  In order to use the triples, we must find them first. Given a string "_ox__oo_x" we should have the triples _ox, __o, o_x, __x, __o, o__, xox, and xoo, respectively.

4. Strategy (this is straight from Wikipedia, so it could be wrong):

Player wins if first possible move is chosen from the following list:

  • Win - if there are two in a row of your kind, you can place a third to make three
  • Block - if opponent has two in a row, you can place one to block the opponent
  • Fork - create an opportunity with two threats to win
  • Block a fork - two options. 1) create two in a row to force opponent to defend, so long as opponent does not create a fork by responding. 2) if opponent can fork, block opponent's fork from happening
  • Center - player marks the center
  • Opposite Corner - if opponent is in the corner, player marks opposite corner
  • Empty Corner - player marks a corner square
  • Empty side: player marks a middle square on any of the sides

5. End Game

  • In order to win a game of Tic Tac Toe a player must set up a play such that no matter what the opponent does, the player will be able to connect three boxes in a row. Thus, the computer AI will need to make a move that sets up two triples that can be completed on the next turn so that even if the opponent blocks one of the triples, the other can still be completed.

Next steps: design and build a game board so that two human opponents can play against one another.