# 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!"
```

This is quite an elegant solution. The only thing I would worry about is future maintainability (sorry I can't spell). What if someone down the road comes in and can't understand what the code is doing because they are not very well versed in bit wise operations? for tic-tax-toe this might be fine because I can't see a feature that would change the conditions of winning but what about for larger projects? I think that while it would be fine for the fresco decamp.com zip lines using bit wise operations in other places really only make since when absolutely necessary.

hey Sean, Thanks for the comment. Mostly I figured this would be nice to put in as a testament of my coding abilities in case I use these pens as a part in future portfolios. These techniques are more common in high performance computing. (lattice gases come to mind) So all in all its just a case of "lets do it, because we can" :-)

I really enjoyed this read. Thank you. Keep it up! Nice visual explanation, too, with the clever use of those tables.

Return 1 & 1 = 0? The correct would not be 1 & 1 = 1?