Check Win algorithm for Gomoku with BitBoards

This is a discussion on Check Win algorithm for Gomoku with BitBoards within the Game Programming forums, part of the General Programming Boards category; I am working on a gomoku engine. I am using 15 16-bit words,one for each row (15x15 board). The board ...

  1. #1
    Registered User
    Join Date
    Aug 2013
    Posts
    55

    Check Win algorithm for Gomoku with BitBoards

    I am working on a gomoku engine. I am using 15 16-bit words,one for each row (15x15 board). The board looks like this if it was an array: (starting from the bottom and up,right to left)

    ...29 28 27 26 25 24 23 22 21 20 19 18 17 16 15
    14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
    etc.

    In Gomoku, A win must be 5 consecutive marks and not more, more than 5 is called an "overline" and is not considered as a win.
    So I am trying to find an algorithm that check if there is a win.

    The best idea i found so far is doing a bit masking on each 7 (or 6 on the edges) bit-sequence with this bit pattern that represents a win: 0111110
    this should be done for the whole row,columns and diagonals that relevant to a certain move (I always have a reference to the last move that was played).
    But The problem with this approach, is that for the columns and the diagonals, I need to "construct" a temporary Bit-set that is similar to how a row looks like but only with the bits of the column /diagonal instead. something like:
    Code:
    short y = 0;
    int col = lastMove%15;
    short mask = 1;
    
    for(int i = 0; i < 15; i++){
         y |= (board[color][i] >> col & mask) << i;
    }
    And after I did that, i can start do the win pattern recognizing to see if that cartain column contains a win:
    Code:
    short overline = 127;
    short win = 62;
     for(int i = 0; i <= 9; i++){
            y >>= i;
            if((y & overline) == win){
                return color+1;
            }
        }
    
    Any one got a better idea? cause mine is really slow and clumsy
    Last edited by patishi; 09-18-2013 at 05:00 PM.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I could be missing something here, but how can you represent a board "square" (or intersection or whatever) with a single bit? Doesn't it have 3 states: empty, black, white?


    Actually, is there any real advantage in representing the board minimally with bits?
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Aug 2013
    Posts
    55
    The board is an array ,holding 15 16-bit words (short type) for each player:
    Code:
    short board[2][15] ;
    so,when a player plays on a certain square, I mark that certain bit on HIS Bit Board like this:
    Code:
    board[player][row] ^= (short)1 << col ;
    A 1 bit means that that player have a mark on this square, and 0 means that he doesn't

    Initialy i used an array for the board, but i figured out that for the evaluation function, I will have to do a pattern recognition for threats detection, and this will be much (much!) faster using bitBoards and bit masking than to iterate through a certain line on the board and do a lot of checks (IF'S and ELSE's). what i can do with a bunch of checks, i can do in one single & operation and see if the result is equal to a certain pattern (a win pattern or a threat pattern for example).

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have discovered the secret of Crafty (the Chess program). It's open source, written by a former World Chess Champion team, and it uses bit boards just as you've described them.

    Only problem learning from Crafty, is that since it was originally written to run on a Cray computer, it has bits in a different order (Big Indian iirc). The author is all over at talkchess.com (and sometimes at openchess.com. He's a CS professor, and loves computer chess and his bit boards. (Don't mention anything about clones, however!).

    OpenChess • Index page
    TalkChess.com :: Index

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Check to check string for a series of characters
    By robi in forum C Programming
    Replies: 1
    Last Post: 02-28-2012, 04:42 PM
  2. Replies: 12
    Last Post: 06-06-2005, 05:45 AM
  3. Net GoMoku
    By LuckY in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 07-15-2004, 10:01 PM
  4. Help me: GoMoku AI Logic
    By LuckY in forum Game Programming
    Replies: 0
    Last Post: 03-10-2003, 03:26 PM
  5. my grandfather's chess algorithm can beat your grandfather's chess algorithm...
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 08-17-2001, 06:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21