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 2i 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!"


3,160 4 18