In this Tic-Tac-Toe game your opponent is an unbeatable A.I. player.
It’s impossible to win.
MiniMax
A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent’s possible following moves.
Pseudo code:
function minimax(node, currentPlayer) {
if (isLeaf(node)){
return heuristic(node);
}
var value;
var children= getChildren(node);
var childrenCount= children.length;
if (currentPlayer == 'O') {
value = -inf;
for (var i = 0; i < childrenCount; i++) {
value = Math.max(value, minimax(children[i], 'X'));
}
} else if (currentPlayer == 'X') {
value = +inf;
for (var i = 0; i < childrenCount; i++) {
value = Math.min(value, minimax(children[i], 'O'));
}
}
return value;
}
Bit-logic and bitwise operators
1 – The positions
Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level, that’s why I am using it for this game wich is client side.
We have a 3×3 board in this game, so 9 squares. Each square is numbered from 0 to 8 as below:
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
This board can be displayed in a single line:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
And then reversed:
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Each number corresponds to the position of a bit in an integer.
For example the number 10 in decimal which equals 1010 in binary
(10)10 = (1010)2 :
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
Considering that this integer 10 represents the positions of the player X in the board we finally have the following result
All the positions of the player X and O can now be stored in only 2 integers.
int positionsX = 0;
int positionsO = 0;
2 – Perfom a move
Knowing that the bits in an integer are power of 2, we have all these values :
(000000001)2 = (1)10 = 20
(000000010)2 = (2)10 = 21
(000000100)2 = (4)10 = 22
(000001000)2 = (8)10 = 23
(000010000)2 = (16)10 = 24
(000100000)2 = (32)10 = 25
(001000000)2 = (64)10 = 26
(010000000)2 = (128)10 = 27
(100000000)2 = (256)10 = 28
To perform a move, a simple bitwise operator OR does all the job. Knowing the number of the destination square and its power of 2:
int positionX = 2;
positionX | 256 → 258
000000010 | 100000000 → 100000010
3 – How do I know if someone has won? Easy!
There is 8 ways to win with 3 symbols in a row.
We can encode these 8 states in 8 integers as we saw before. Here are the magic numbers :
var winning = {7, 56, 448, 73, 146, 292, 273, 84}
Now the operator AND does all the job.
For each winning integers if the operation AND between it and the positions of the player results itself then the player won.
Example:
positionX = (15)10 = (000001111)2
(7)10 = (000000111)2
15 & 7 = 7
The player X won!