Results 1 to 2 of 2
May 5th, 2012, 01:50 AM #1jeremy5561n/aGuest
Connect 4 Bitboard Connect 3 threatmap generation
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
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?
May 25th, 2012, 09:29 AM #28Registered User
Your approach just might work, and kudos for trying something different.
This approach is simplest for going left to right: shift right to remove trailing bits, AND bits with 1111, assign score based on whether the result is 0, 1, 2, or 4.
Down and diagonal are a little trickier: shift right to remove trailing bits, shift left onto a new number, shift right again to get up to the next row, shift left onto the new number, shift right, shift left, shift right, then shift left again. Now AND the new number with 1111 and assign score based on whether result is 0, 1, 2, or 4.
I programmed a Connect 4 AI in my early days and used Strings to store chip positions. Whatever you do, do NOT use Strings!