I am programming AI for connect 4. To impress my teach I’m using bitboards and bitwise operations so that more moves can be evaluated in less time. The board is represented by a long (Java) type, one for each player. 0 is at the bottom left corner and it increased upward. It looks like this
. . . . . . .
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2 9 16 23 30 37 44
1 8 15 22 29 36 43
0 7 14 21 28 35 42
The blank row at the top prevent wrap-overs during shifts from matching any pattern.
I’m trying to come up with a bitwise algorithm to check for connect 3’s, where there is an EXTRA space next to the three pieces in a row so that the AI can potentially play
It is important that this method is able to COUNT the number of times this condition occurs.
I’m totally new to the bitwise idea but I’m thinking about doing it like this:
Take a connect 3 for example
1 1 1
shift right and do and
0 1 1 1
& 1 1 1 0
= 0 1 1 0
repeat
00110
&11100
=00100
and then generate a bitboard representing unoccupied spaces by doing AND to both the player’s boards and then doing NOT
and then shifting the 00100 from earlier 1 right and do AND against unoccupied space board and then shifting the result 4 left and do another AND against unoccupied space board. Finally do a bit count for each of the unoccupied AND operations. Repeat for horizontal vertical and two diagonals by shifting them by a differnt amount.
I think it’ll work but I feel like there is a much better way that I’m missing because I feel like this could be quite slow, and I’m not even sure if it works. What’s the conventional, fastest way to do this?
