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
- +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)
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 :)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.