I am currently working on a tic tac toe auto-mover game. I have come upon a decent algorithm that allows the computer to easily build towards, and claim victory spots.
The problem however is that when the opponent is dangerously close to victory, the computer continues to build towards it’s own victory instead of blocking the opponents, is there any way the following algorithm can be optimized to counter that?
The algorithm works as follows:
-
Initialize a 3×3 integer array
-
Loop over all possible combinations on the board (0|0, 1|1, 0|2… e.tc).
-
If combination is a immediate victory, stop and return this position.
-
Else initiate a loop (That loops either 1000, 10000 or 100000 times, depending on difficulty)
- Continually move from both sides randomly till victory is achieved. If victory is by the computer, increment the score counter.
-
- Select the board position with the highest score
This algorithm works fine and can build towards victory (example:
·|x|o ·|x|o ·|x|o
·|·|· x|·|o x|x|o
·|·|· ·|·|· ·|·|o
However when confronted with a board like this
·|x|o
o|x|·
·|·|·
The optimal move should be to break x’s chain, but the computer builds towards raising it’s own chain i.e moving at 1|2 (The board is 3×3, indexes start from zero. So that’d be the second row’s third coloumn).
Is there any way to optimize this algorithm such that this weakness goes away?
Sure there is a way. Your problem is that your definition of “I win” is too narrow. As you’ve pointed out, a row of three is only a win for you if your opponent doesn’t already have one – therefore your metric must track potential rows achieved by you and your opponent, and avoid states in which they get a row completed first.
1
Tic-Tac-Toe is a solved game and quite ‘easy’ to fully program or expand (its even been done in books). Pre-programming the entire game is the optimal approach.
If you were working with a larger game (such as a 20,20,5 game (these all belong to a set of games known as m,n,k games – Tic-Tac-Toe can be described as 3,3,3)) then matters of min-max trees and optimizations on them come into play. For Tic-Tac-Toe, this is overkill.
Working with just 3,3,3; if the game is represented with 0 as the empty cell, +1 as X, and -1 as O, the board has some interesting properties:
·|x|o 0 | +1 | -1 o|x|· --> -1 | +1 | 0 ·|·|· 0 | 0 | 0
For each row, column, and diagonal, take the absolute value of the sum of the elements:
0
/
0 | +1 | -1 = 0
-1 | +1 | 0 = 0
0 | 0 | 0 = 0
= = =
1 2 1 1
Wherever there is a 2, you want to play in that remaining spot. If there are two or more spots that can be played into, chose the one that has the sign match your own. This way, you are always guaranteed to play to win or to block if possible.
This can be used as the basis for other heuristics. Spots that have a value of 0 are rather uninteresting in that they are either blocked ( x | o | . ) or uncontested ( . | . | .). The number of contested lines that pass through a given cell then would likely make it a better play.
- look if you could 1-move win : play this move
- look if you could prevent him last-move win : play this move
- look if you could 2-move win : play first of these 2 moves (which one could vary according to difficulty or which one prevent the other to win)
- look if you could prevent him to 2-move win : play first of these 2 moves (…)
- play anywhere
I’m not sure what you mean by
Else initiate a loop (That loops either 1000, 10000 or 100000 times, depending on difficulty)
It seems like you’re working with a rudimentary genetic algorithm; in this case, you need a better fitness function. In particular, for each possible outcome of the game (your “all combinations”),
- if the opponent can win in one move
should have a higher priority than
- you can win in one move
When you say
Continually move from both sides randomly till victory is achieved. If victory is by the computer, increment the score counter.
That randomly is your problem. Try to prevent it from happening.