bitboard algorithm needed

[Daniel Shawul]

try replacing 7 by 9 that should fix the other bug

Indeed 7 should not have been used at all. I thought you were talking about your original suggestion shown below.

Code: Select all

then again on 19,22 you are correctly moving top-right

Code:
             ((&#40;m << 9&#41; | &#40;m << 1&#41;) & UINT64&#40;0xfefefefefefefefe&#41;) |
             ((&#40;m >> 7&#41; | &#40;m >> 1&#41;) & UINT64&#40;0x7f7f7f7f7f7f7f7f&#41;))


should be replaced by

Code&#58;
             ((&#40;m >> 7&#41; | &#40;m << 1&#41;) & UINT64&#40;0xfefefefefefefefe&#41;) |
             ((&#40;m << 9&#41; | &#40;m >> 1&#41;) & UINT64&#40;0x7f7f7f7f7f7f7f7f&#41;)) 

Well after a little brain twist I managed to see the HEX board's shifts which do not need a 7

Code: Select all

 ((&#40;m << 9&#41; | &#40;m << 1&#41;) & UINT64&#40;0xfefefefefefefefe&#41;) |
 ((&#40;m >> 9&#41; | &#40;m >> 1&#41;) & UINT64&#40;0x7f7f7f7f7f7f7f7f&#41;))

The moves are (+8,-8)vertical (+1,+9)right, (-1,-9)left

What was complicating the test was that all the positions we have been testing like this one 0x809fa1bd85b5c901 you brought up with the longest length 30 unit is actually not won. It breaks at the 14th pawn or so because it required a shift 7.
I will do more tests and see if anything comes up.

Code: Select all

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

1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 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 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0

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

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

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

5.
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
1 0 0 0 0 0 0 0

6.
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
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

7.
0 0 0 0 0 0 0 0
1 1 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
1 0 0 0 0 0 0 0

8.
0 0 0 0 0 0 0 0
1 1 1 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
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

9.
0 0 0 0 0 0 0 0
1 1 1 1 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 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

10.
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
1 0 0 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 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

11.
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 0 0 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 0 0
1 0 0 0 0 0 0 0

12.
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 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 0 0

13.
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0

14.
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0

wins : 0
Press any key to continue . . .

[Daniel Shawul]

I think it is correct now. It doesn't hang threads and also produces reasonable results. From 1000000 random games I am getting 500881 (about half of the games) won for white. Previously the ratio was about 30% which was bad. The first player has an advantage but I doubt the monte-carlo method would sustain that advantage through out the game. So 50% result is very reasonable.

To summarize here is the working code.

Code: Select all

      U64 m = (wpawns & UINT64(0x00000000000000ff)),oldm;
		do {
			oldm = m;
			m |=(((&#40;m << 8&#41; | &#40;m >> 8&#41;) | 
				  ((&#40;m << 9&#41; | &#40;m << 1&#41;) & UINT64&#40;0xfefefefefefefefe&#41;) | 
				  ((&#40;m >> 9&#41; | &#40;m >> 1&#41;) & UINT64&#40;0x7f7f7f7f7f7f7f7f&#41;)) 
				 & wpawns
				);
			if&#40;m & UINT64&#40;0xff00000000000000&#41;) &#123;
				wins++;
				break;
			&#125;
		&#125; while&#40;m != oldm&#41;;

[Edmund]

well done, daniel
personally I have to admit I was a little confused by your board-representation at the beginning. I am used to h1=2^0 and forgot scorpio was using a1=2^0.

Anyway, as I said before you should definitly also test the flooding from two sides and make speed comparisons.

regards
Edmund

[Daniel Shawul]

well done, daniel
personally I have to admit I was a little confused by your board-representation at the beginning. I am used to h1=2^0 and forgot scorpio was using a1=2^0.

Anyway, as I said before you should definitly also test the flooding from two sides and make speed comparisons.

regards
Edmund

Thanks for the help!

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

I can not use the table approach for obvious reasons. I don't think I can use the second trick either because the move generation is a random move picker. It picks uniformly from empty squares and makes moves until the board is full. Later I may add heuristics to pick the best available moves first (move sorting). Playing a full game may be as costly as one evaluation! So I may need to do optimization later but now I want to concentrate on devising a way to grow a tree on the gpu and do more simulations on promising nodes.
On an NVIDIA Quadro FX3700 workstation gpu, I am measureing at least a 20x speed up.

Code: Select all

GPU spec
14mp
1.25GHZ
8k registers per mp
16k shared mem per mp

CPU clock rate is 3GHZ so I was expecting a speed up of (1.25/3) * 14 * 8 = 46 but I am only getting half of that. Maybe it is because it is not a dedicated compute device ? I don't know, but still I think the result is satisfactory.