# Using bit-logic to keep track of a tic-tac-toe game

Everybody knows tic tac toe. We have a 3x3 play field like below, I started counting from 0 for a reason. We'll see that below.

0 | 1 | 2 |

3 | 4 | 5 |

6 | 7 | 8 |

Let us transform the grid to a single line.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

- | - | - | - | - | - | - | - | - |

For simplicity we look at one player. (the other is completely analogous) If a position in the grid is not occupied, we assign a value of zero (0) to it.

If we place an X in position 2, then we assign a 1 to this position.

So the empty state is 000 000 000 (added spaces for simplicity) Binary is read from right to left.

Let us label the bits (digits in a binary number) in a way similar to the grid.

8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

- | - | - | - | - | - | - | - | - |

You may wonder why I reversed the order here.
That's because the bit at position *i* has value *2 ^{i}* when converting to decimal.
That's also the reason why we wrote the indices starting from 0.
The rightmost bit is worth 1 in decimal (otherwise we couldn't make odd numbers)

Let me give a quick example of the conversion to decimal with 4 bits (brackets with a subscript denote the base of our number)

(0010)_{2} = (0*8 + 0*4 + 1*2 + 0*1)_{10} = (2)_{10}

(1010)_{2} = (1*8 + 0*4 + 1*2 + 0*1)_{10} = (10)_{10}

So with a certain playfield we can associate a single, unique number.

Let me consider 2 states, one that hasn't got 3-in-a-row and one that has.(both have the same amount of occupied cells)

## No winning combo(A)

- | - | X |

- | X | X |

- | X | - |

## Winning combo(B)

- | - | X |

- | X |
X |

X |
- |

Okay we now have two examples lets write them in the alternative notation (A) and (B) are the "states" of the board

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |

(A) | - | - | X | - | X | X | - | X | - |

(B) | - | - | X |
- | X |
X | X |
- | - |

So it's clear that these are the same as the grids. But we can also guess the close relation to binary strings. Lets do that now. Whenever a cell is occupied with an X we put a 1 in our binary string.

8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |

(A) | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |

(B) | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |

How can we exploit this "notation"? Well we have the winning combo in (B) with cell 2, 4 and 6 occupied. Lets look at the string that has only these cells occupied (call it (W) to signify a winning combo)

8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |

(W) | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |

# The big claim

I claim that we can check if a configuration has 3-in-a-row by using the bitwise AND operation.

Bitwise AND (&) is an operation on 2 strings, "comparing" them one bit at a time. An example

1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |

& | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |

= | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |

Here we used following properties

- 0 & 0 = 0
- 0 & 1 = 0
- 1 & 0 = 0
- 1 & 1 = 0

Lets see what we get when we use the bitwise AND on (A) and (W)

(A) | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | |

(W) | & | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |

= | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |

Now lets see what happens for (B) and (W)

(B) | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | |

(W) | & | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |

= | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |

Something magical must have happened.

# B & W = W !!!

This is the power of our bitwise operations. You can check that this holds for each winning combination. In our script we can use a test like the following pseudo code

` ````
for(var combo in winningCombos)
if(currentState & combo === combo)
"You have won!"
```