The forums have permanently moved to forum.kirupa.com. This forum will be kept around in read-only mode for archival purposes. To learn how to continue using your existing account on the new forums, check out this thread.


Results 1 to 2 of 2

Thread: Connect 4 Bitboard Connect 3 threatmap generation

  1. #1
    jeremy5561
    n/a
    posts
    Guest

    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

    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?

  2. #2
    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!

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012