Unbeatable Tic Tac Toe – Rule Based Algorithms

Continuing my work with Java, recently, I developed an unbeatable Tic Tac Toe game in Java.

Tic Tac Toe Tie Game

While you can find many such programs online, I think that I’m the only person to create the kinds of algorithms I have.

Coming from a database background, I implemented a number of database like structures in memory. An array list of remaining cells. A Decision Table. And a lookup table for intersections of runs.

Here’s how I did it.

——-

Many Event Handlers:

At first, I tried downloading a few programs, and modifying them. But they were buggy. I realized that in the entire GUI program, I didn’t know what line of code the program was actually on.

So, I implemented many event handlers. One for each button. Then another event handler on a dummy invisible label. When the button is clicked, the event handler sends the focus to the dummy label.

lblDummy.requestFocus();
lblDummy.grabFocus();

The event handler in the dummy label then handles the logic of the program.

—————

Analysis:

Some initial analysis of the Tic Tac Toe game revealed:
9 buttons
8 runs or ways to win the game
Two or more runs will intersect on a single button

—————

Prime Numbers:

Originally, I started with Strings of “X” and “O”. But then I had the idea of using prime numbers. 3 for X, and 5 for O. These numbers could now be added up very quickly. And the sum could indicate various states of the run.

All blank – Potential run: 0
One X or O – Win In Two Moves: 3 or 5
Two Xs or Two Os – Win Next Move: 6 or 10
Both an X and an O – Blocked: 8
Three X or three O – Win: 9 or 15
Other combinations of three (ie. X, X, O) – filled and blocked

—————

Decision Table:

Then I created a decision table, composed of an array of objects. One row for each potential run, and all the different possible states. Blame it on my database background.  🙂

 
--- Decision Table ---
Run Posn_1_2_3 
                    Total
                       Clear Row
                           Blocked 
                             Filled 
                                  X O WinNextMove 
                                          X O WinTwoMoves  
                                                  Button_1_2_3
                                                             X O Fork
  row1  0  0  3  |  3  0  0  0  | 0  0  | 1  0  | 1  2  3  | 1  0  
  row2  0  5  0  |  5  0  0  0  | 0  0  | 0  1  | 4  5  6  | 0  0  
  row3  3  0  0  |  3  0  0  0  | 0  0  | 1  0  | 7  8  9  | 1  0  
  col1  0  0  3  |  3  0  0  0  | 0  0  | 1  0  | 1  4  7  | 1  0  
  col2  0  5  0  |  5  0  0  0  | 0  0  | 0  1  | 2  5  8  | 0  0  
  col3  3  0  0  |  3  0  0  0  | 0  0  | 1  0  | 3  6  9  | 1  0  
 diag1  0  5  0  |  5  0  0  0  | 0  0  | 0  1  | 1  5  9  | 0  0  
 diag2  3  5  3  | 11  0  1  1  | 0  0  | 0  0  | 3  5  7  | 0  0  

After the decision table was made and populated, some decisions then became quite simple. A Win Next Move for Offense? Take it. A Win Next Move for defense? Block it.

—————

Intersection Table:

Another table I made was an intersection table, a two dimensional array.  Both the horizontal and vertical axis of the array contained all potential runs (3 rows, 3 columns, or 2 diagonals). In the body of the 2D array, is the intersecting cell (1 to 9). For instance, row 3 and column 2, intersect on cell 8.

1  2  3  
4  5  6  
7  8  9

One point to note is that rows never intersect with each other. Neither do columns. But the two diagonals intersect in the middle on cell 5.

—————

Remaining Cells:

Another object I made was an arraylist representing each cell. As each button was clicked or selected, it would be removed from the arraylist.

—————

Forks:

When I played Tic Tac Toe as a child, I discovered how to fork the opponent. One scenario would be to put an X in each corner, like this.

Tic Tac Toe Fork On Diagonals

In this scenario, the next move for X could be in either remaining corner. And each corner, would allow for a fork. X could win on a row, or a column.

Turns out that one tactic for O to prevent a fork, is to put an O in the side.  Like this.

   Move
X: 7		3		
O:	5		4	

 

Tic Tac Toe Block Diagonal Fork

 

This allows O to win in the next move, and force X to block the row, without taking either fork.  Easily seen by checking this online unbeatable Tic Tac Toe game.
http://mistupid.com/games/tictactoe.htm

I implemented this algorithm by looking for the intersection between the runs of
X_Win_in_Two_Moves and O_Win_in_Two_Moves.

In the example above, X_Win_in_Two_Moves was found in: row 1, row 3, column 1, and column 3. O_Win_in_Two_Moves was found in: row 2, and column 2.

So, the intersection of row 1 and column 2 is cell 4.

—————

Advanced Anti-Fork Algorithm:

Things were working fine, until I noticed that I could still beat the game with this scenario:

   Move:
X: 7		2		6	
O:	5		4		

 

Tic Tac Toe Fork 02

 

My original algorithm chose cell 1. However, this then allowed X to choose cell 9, attaining a fork on row 3, and column 3.

Tic Tac Toe Fork 02 Wrong Move

O could then only block one of the runs, and X won selecting either cell 3, or cell 8.

After some analysis, I came up with an algorithm to deal with this issue. The original algorithm looked at intersections between X_Win_in_Two_Moves and O_Win_in_Two_Moves.

In this new scenario, first, I looked at all intersections of X with X_Win_in_Two_Moves. So, at the start of move 6, X has three X_Win_in_Two_Moves:
row 1, row 3, and column 3.

And, X has two potential forks:
row 1 and column 3, on cell 3
and
row 3 and column 3 on cell 9.

But which one to block? As I did the algorithm, I tallied how many potential forks each run was involved with.

row 1:    1
row 3:    1
column 3:     2

Then, I started with the most popular runs, and worked down to the less popular runs. In this case, start with column 3, then look at row 1, and row 3.

Using column 3, look for an intersection with O_Win_in_Two_Moves. In this case, O’s only O_Win_in_Two_Moves is diagonal 1.

The intersection of diagonal 1, and column 3, is cell 9. Choose cell 9.

Tic Tac Toe Fork 02 – Correct Move

 

Following through to the conclusion, the end of the game will be a tie.

Tic Tac Toe Tie Game

 

So, I’m pretty pleased with the results. I’m not posting the code. But, if you implement the algorithms, please let me know. I’d like to hear about it.