bitboard algorithm needed

[Daniel Shawul]

I am working on a montecarlo simulator for an 8x8 hex game on GPU. Everything is ok so far except for one problem regarding terminal leaf evaluation. Once the random games are complete and the board is full of stones, we need to evaluate who won. For Hex, white wins if there is a path connecting the bottom raw (rank 0) with the top raw(rank 7). I am using a bitboard shifting to find a path...

Code: Select all

U64 m = (wpawns & UINT64(0x00000000000000ff));
for(int i = 0;i < 7;i++)
	m = (((m << 8) | ((m << 9) & UINT64(0x7f7f7f7f7f7f7f7f))) & wpawns);

if(m) wins++;

We start from the bottom raw and shift up and right-up to see if we have connecting stones. This is done 7 times and if m is non-zero white wins other wise black wins(no draws). The problem is when we have connected pawns on the same rank. In this case I need to check also squares to the left and right. For instance on rank 4, if m has only one bit at file A but there are pawns on the same rank that connect to the pawn on file A, then those pawns need to be "ORed" to m, so that we go on from there. The obvious method I can think of is to shift m by 1 to 7 to the left and right and include bits connected to existing bits in m. This sounds very costly to me and I was wondering if there is a better way.

Please feel free to ask if anything is unclear.

[bob]

Define "path"? vertical? Or vertical/horizontal? Or are diagonal paths also included?

[Daniel Shawul]

The path is from a Hex board
http://en.wikipedia.org/wiki/File:Hex_board_11x11.svg
The moves are +1, -1,+8,+9,-7,-8

Code: Select all

             +8  +9
         -1   C    +1
         -7  -8

What I need is how to convert
Say m is
X0000000
and we have pawns
XXX00X00
How to get result ?
XXX00000

I was planning to add something like this at each step of the loop above

Code: Select all

r = m

//left shift
do {
   t = (((r<<1) &~FILEA) & wpawns);
   r |= t;
} while(t)

//and for the right
do {
   t = (((r>>1) & ~FILEH) & wpawns);
   r |= t;
} while(t)

[mjlef]

When I programmed Hex in a non-bitmap form I did it this way.

I assign numbers to the board edges. 1-2-3-4, to for groups
connecting 1 to 3 is a win for white, and 2 to 4 is a win for black
any piece put on the board assumes the group number of the piece or board edge next to it. If nothing is next to it it gets a group number of 0.
whenever a piece touches an edge it gets the group number of that edge, and if any zero groups are also touching the new piece, the group numbers for all pieces that were 0 before are changed.

So this makes it very easy to see if any move immediately causes a win since it is fast to see if the groups are connected.

The basic idea is instead of trying to calculate if a path is available at the end of the tree, just incrementally update as much as you can with each piece drop.

[Edmund]

what do you think of a precomputed table[256][256] that for every possible bottom/top row configuration tells the resulting top row.

If you had the chance to build the movegeneration to work from left to right you might try using the o^(o-2r) trick http://chessprogramming.wikispaces.com/ ... king+Piece

Another approach would be something like:

Code: Select all

U64 m = (wpawns & UINT64(0x00000000000000ff));
for(;m;) {
   m = ((m << 1) | (m >> 1) | (m << 8) | (m << 9)) & wpawns;
   if(m & 0xff00000000000000) wins++; 
}

Furthermore you can get better parallelization by starting off from row 0 and row 7 simultaneously, because this reduces dependency.

I don't know hex enough, but wouldn't it be possible for a line not only to move sideways but also backwards?

[Daniel Shawul]

Precomputed is a no no since I am doing it on GPU. Right now I am doing all the calculations on the register. I don't want to even use shared mem. I chose HEX 8x8 to use bitboards. makemove,move generation and everything is very easy and lightweight. It is about 100 lines of code total to do a montecarlo on the root board.

Another approach would be something like:
Code:
U64 m = (wpawns & UINT64(0x00000000000000ff));
for(;m;) {
m = ((m << 1) | (m >> 1) | (m << 8) | (m << 9)) & wpawns;
if(m & 0xff00000000000000) wins++;
}

I think I will using something like that once I correct the shifts ~FILEA and ~FILEH. I will just do it 7 times anyway since unrolled code is much better for the GPU.

Furthermore you can get better parallelization by starting off from row 0 and row 7 simultaneously, because this reduces dependency.

I don't know hex enough, but wouldn't it be possible for a line not only to move sideways but also backwards?

Good point. Yes it can move backwards too so I guess I will have to add -7 and -8 to the mix.

[Edmund]

Precomputed is a no no since I am doing it on GPU. Right now I am doing all the calculations on the register. I don't want to even use shared mem. I chose HEX 8x8 to use bitboards. makemove,move generation and everything is very easy and lightweight. It is about 100 lines of code total to do a montecarlo on the root board.

Another approach would be something like:
Code:
U64 m = (wpawns & UINT64(0x00000000000000ff));
for(;m;) {
m = ((m << 1) | (m >> 1) | (m << 8) | (m << 9)) & wpawns;
if(m & 0xff00000000000000) wins++;
}

I think I will using something like that once I correct the shifts ~FILEA and ~FILEH. I will just do it 7 times anyway since unrolled code is much better for the GPU.

Furthermore you can get better parallelization by starting off from row 0 and row 7 simultaneously, because this reduces dependency.

I don't know hex enough, but wouldn't it be possible for a line not only to move sideways but also backwards?

Good point. Yes it can move backwards too so I guess I will have to add -7 and -8 to the mix.

Unrolling this one seems costly. It appears to me, the maximum number of steps is 30.
P7/P2PPPPP/P1P4P/P1PPPP1P/P4P1P/P1PP1P1P/PP1PP2P/7P w - - 0 1

btw there is a mistake in my previous posted code. The way the loop is constructed one has to check for m != old m and not m != 0.

[Daniel Shawul]

Unrolling this one seems costly. It appears to me, the maximum number of steps is 30.
[d]P7/P2PPPPP/P1P4P/P1PPPP1P/P4P1P/P1PP1P1P/PP1PP2P/7P w - - 0 1

btw there is a mistake in my previous posted code. The way the loop is constructed one has to check for m != old m and not m != 0.

Yes that maybe the longest but I am not sure since the Hex board is difficult to visualize when deformed.

I tested the following code that do not consider backward moves

Code: Select all

      U64 m = (wpawns & UINT64(0x00000000000000ff)),oldm;
		print_bitboard(m);
		do {
			oldm = m;
			m = (((m << 8) | 
				 (((m << 9) | (m << 1)) & UINT64(0x7f7f7f7f7f7f7f7f)) | 
				 ((m >> 1) & UINT64(0xfefefefefefefefe))) 
				 & wpawns);

			print_bitboard(m);

			if(m & UINT64(0xff00000000000000)) {
				wins++;
				break;
			}
			
		} while(m != oldm);

It detects the following position as a win but I am not sure if it is doing the right thing. Here is a step by step output. Do you think it is working correctly ?

Code: Select all

0 1 1 1 0 0 1 1
0 0 1 1 0 0 1 1
0 0 0 0 0 1 0 1
1 0 0 1 1 0 1 0
1 1 1 1 1 0 0 0
1 1 0 0 0 0 0 1
1 1 0 1 0 0 1 1
1 1 0 0 0 1 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
1 1 0 0 0 0 1 1
0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 1 0
1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 1 0
1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0
1 1 1 1 1 0 0 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 1 0
1 0 0 0 0 0 0 0

0 1 1 1 0 0 1 1
0 0 1 1 0 0 1 1
0 0 0 0 0 1 0 1
1 0 0 1 1 0 1 0
1 1 1 1 1 0 0 0
1 1 0 0 0 0 0 1
1 1 0 1 0 0 1 1
1 1 0 0 0 1 0 1
wins : 1
Press any key to continue . . .

[Daniel Shawul]

I am having more doubts now. I tried your position which should require 30 shifts but the algorithm needed only about 10 and it still says a win. I have included backward moves for this version

Code: Select all

      U64 m = (wpawns & UINT64(0x00000000000000ff)),oldm;
		do {
			oldm = m;
			m =((((m << 8) | (m >> 8)) | 
				 (((m << 9) | (m << 1)) & UINT64(0x7f7f7f7f7f7f7f7f)) | 
				 (((m >> 7) | (m >> 1)) & UINT64(0xfefefefefefefefe))) 
				 & wpawns);

			if(m & UINT64(0xff00000000000000)) {
				wins++;
				break;
			}
			
		} while(m != oldm);

The position is 0x809fa1bd85b5c901

Code: Select all

1 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1
1 0 1 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 0 0 0 1 0 1
1 0 1 1 0 1 0 1
1 1 0 0 1 0 0 1
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0
1 0 0 0 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1
1 0 1 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 0 0 0 1 0 1
1 0 1 1 0 1 0 1
1 1 0 0 1 0 0 1
0 0 0 0 0 0 0 1
wins : 1
Press any key to continue . . .

[Edmund]

I think the shifts got mixed up. Moving top right you need m << 7

Code: Select all

      U64 m = (wpawns & UINT64(0x00000000000000ff)),oldm; 
      print_bitboard(m); 
      do { 
         oldm = m; 
         m = (((m << 8) | 
             (((m << 7) | (m >> 1)) & UINT64(0x7f7f7f7f7f7f7f7f)) | 
             ((m << 1) & UINT64(0xfefefefefefefefe))) 
             & wpawns); 

         print_bitboard(m); 

         if(m & UINT64(0xff00000000000000)) { 
            wins++; 
            break; 
         } 
          
      } while(m != oldm);