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:

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}= 2^{0}

(000000010)_{2 = }(2)_{10}= 2^{1}

(000000100)_{2 = }(4)_{10}= 2^{2}

(000001000)_{2 = }(8)_{10}= 2^{3}

(000010000)_{2 = }(16)_{10}= 2^{4}

(000100000)_{2 = }(32)_{10}= 2^{5}

(001000000)_{2 =}(64)_{10}= 2^{6}

(010000000)_{2 = }(128)_{10}= 2^{7}

(100000000)_{2 = }(256)_{10}= 2^{8}

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!