tic tac toe logic

the standard game of tic tac toe is played on a 3x3 board. this is the trivial case. the diagrams shown as examples apply to the trivial case. this method is appropriate for a game played on a larger board, hence the more generic definitions.

it is irrelevant whether both players are handled by the computer, or only one. each turn will see the definition of player and opponent switch, so if in the first turn the player is X and the opponent is O, then in the second turn the player will be O and the opponent X. in each turn the weight grid must be calculated anew.

the game grid

(1,1) | (1,2) | (1,3)
---------------------
(2,1) | (2,2) | (2,3)
---------------------
(3,1) | (3,2) | (3,3)

potential line cell (PL)

an empty cell which is on the same line as either an X or an O (not both on the same line), but if controlled by the same player (X if the other cells contain Xs, O if the other cells contain Os) will not finish the game

 X | PL| PL
-----------
   | PL|   
-----------
 O | PL| PL


in the above example (2,1) is on a line containing both X and O (1,3),(2,2),(3,3) are each found on distinct lines each containing one or the other

opponent's completion move cell (OC)

an empty cell which, if filled by the opponent will win him the game
   |   |   
-----------
 O | O | OC
-----------
   |   |   

in the above example the player is X

player's completion move cell (PC)

an empty cell which, if filled by the player will win him the game
   | X |   
-----------
   | PC|   
-----------
   | X |   

in the above example the player is X

the weights are calculated as follows:

+1

for a potential line cell

+10 (width * height + 1)

for an opponent's completion move cell (X)

+100 ((width * height + 1) ^ 2)

for the player's completion move cell (O)

the reasoning behind the weights is that we do not want the possibility, in the case of a larger grid, of a number of crossing potential lines (which are additive) to interfere with the priority of closing off an opponent's completion, or for a number of potential opponent completions to interfere with a player completion (winning the game). regardless of the size of the grid, (width * height + 1) and (width * height + 1)^2 will always be safe values. the basic method is fairly simple. we construct a weight grid with the same dimensions as the game grid to contain the weights, with each cell initialized to zero.

initial state for the turn
 game grid      weight grid
 X | X |         0 | 0 | 0 
-----------     -----------
   |   |         0 | 0 | 0 
-----------     -----------
 O |   |         0 | 0 | 0 

we then go over each line, modifying the line's cell's weights accordingly. in the figures below, it is player O's turn. if it was player X's turn, then cell (1,3) would be weighted 101 instead of 11 by the end of the process.

if the line contains more than one available cell, and contains either Os or Xs (in the trivial case, if the line contains exactly one filled cell), then any available cells are on the potential line, and their counterpart cells in the weight grid are each incremented by 1.

if the line contains exactly one available cell, and the rest of the line's cells are controlled by the opponent, then the available cell is incremented by (width * height + 1), or 10 in the trivial case.

if the line contains exactly one available cell, and the rest of the line's cells are controlled by the player, then the available cell is incremented by (width * height + 1)^2, or 100 in the trivial case.

row 1
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 0 | 0 
-----------     -----------
 O |   |         0 | 0 | 0 

row 2
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 0 | 0 
-----------     -----------
 O |   |         0 | 0 | 0 

row 3
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 0 | 0 
-----------     -----------
 O |   |         0 | 1 | 1 

column 1
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 0 | 0 
-----------     -----------
 O |   |         0 | 1 | 1 

column 2
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 1 | 0 
-----------     -----------
 O |   |         0 | 2 | 1 

column 3
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 1 | 0 
-----------     -----------
 O |   |         0 | 2 | 1 

diagonal 1
 game grid      weight grid
 X | X |         0 | 0 | 10
-----------     -----------
   |   |         0 | 2 | 0 
-----------     -----------
 O |   |         0 | 2 | 2 


diagonal 2
 game grid      weight grid
 X | X |         0 | 0 | 11
-----------     -----------
   |   |         0 | 3 | 0 
-----------     -----------
 O |   |         0 | 2 | 2 

once we have gone over each line (row, column, diagonal), we select the maximum weighted cell as the next move. in the case of a number of cells with the maximum weight, one can be selected at random.

we have now defined the computer's priorities as
1) finish the game by winning
2) prevent the opponent from winning
3) control the cell with the most completion options for either player

that was fun :)