3

I am trying to find a quick and fast way to check for alignment of 5 bits in a 6x6 board in all directions (diagonal, horizontal, vertical). The board is represented as a bitboard as they are very fast.

The bitboard is like this:

00 01 02 03 04 05   
06 07 08 09 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35

Some examples of alignment:

// Vertical Alignment
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 0 0 0 0 0 

// Diagonal Alignment
0 0 0 0 0 0   
0 0 0 0 0 1   
0 0 0 0 1 0   
0 0 0 1 0 0   
0 0 1 0 0 0   
0 1 0 0 0 0

I have tried looping through every possible bitboard winning position and checked if ((winningPosition & currentPosition) != 0) as I have seen that in many tic tac toe implementations of bitboards. The issue here is that this implementation is very slow compared to other solutions I have seen for other games such as connect four (https://spin.atomicobject.com/2017/07/08/game-playing-ai-bitboards/)

vvvvv
  • 25,404
  • 19
  • 49
  • 81
JackRubiralta
  • 84
  • 9

1 Answers1

3

Some tests could be grouped together.

For example, let's say the board is called x, then m = x & (x >> 1) & (x >> 2) & (x >> 3) & (x >> 4) computes a mask where every bit indicates whether it is the start of 5 horizontally-consecutive set bits (including ranges that wrap across different rows). If m has any of the bits in the first two columns set, then that means that that bit is the first bit of a winning position. That's a cheap test: (m & 0b000011000011000011000011000011000011) != 0. Together that takes care of checking 12 winning positions in 10 operations.

The same approach can be used for vertical alignment, but the shift amounts become 6, 12, 18, 24 instead of 1, 2, 3, 4 and the mask becomes 0b000000000000000000000000111111111111.

The same approach can also be used for the diagonals,

  • shift amounts of 7, 14, 21, 28 with a mask of 0b000011000011
  • shift amounts of 5, 10, 15, 20 with a mask of 0b110000110000

But there are only 8 diagonal winning positions and it ends up costing 20 operations to check them this way, which isn't that good. It may still help thanks to reducing the number of checks even though it's more operations, but it may also not help, or be worse.

The number of checks can be reduced to 1 if you prefer, by ORing together the winning-position bits and doing just one != 0.

harold
  • 61,398
  • 6
  • 86
  • 164