Check Win algorithm for Gomoku with BitBoards

[patishi]

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:

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:

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

[oogabooga]

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?

[patishi]

The board is an array ,holding 15 16-bit words (short type) for each player:

short board[2][15] ;

so,when a player plays on a certain square, I mark that certain bit on HIS Bit Board like this:

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).

[Adak]

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