0x88 engines

[Zach Wegner]

Still on that anti-bitboard kick, eh Vincent?

[MattieShoes]

0x88 was 16x8 (or 8x16, it matters not) I believe. 10x12 would not allow the 0x88 scheme to work since the "8 bits" aren't necessarily OOB flags.

I'm trying to understand the advantage of 16x16 and I'm not getting it. Can anybody explain why 16x16 is better than 16x8? What additional capabilities does it offer over 16x8?

[hgm]

16x16 seems needlessly large for normal Chess.

Using the 0x8 bits as off-board indicators is not optimally efficient, though, as it represents an extra test your move generator has to do: even if the conclusion of this test is that the target square is on board, it still has to testif it is not occupied by a friendly piece. It is therefore more efficient to simply surround the board by a rim of ' border guard' pieces, that test as both white and black pieces. An off-board test then becomes completely redundant. To catch all Knight moves, there has to be a double layer of border guards. So this would make the board 12 ranks high.

The main importance of 16-wide 0x88 boards is not the easy testing for off-board moves, but the fact that there is no ambiguity if a move with a certain 'step vector' (difference between number of the from- and to-square) crosses the border or not. In theory a width of 15 is already enough for this, but this makes it more difficult to extract the file number from the square number. (Which can be useful in, e.g. testing for passers.) OTOH an odd width makes it easier to test for square color.
Using exactly double the width makes it possible to use the storage of board-size tables (like piece-square or Zobrist) that is skipped by the square numbering tables for other such tables, reducing the cache foortprint of your engine's kernel data.

[Dann Corbit]

0x88 was 16x8 (or 8x16, it matters not) I believe. 10x12 would not allow the 0x88 scheme to work since the "8 bits" aren't necessarily OOB flags.

I'm trying to understand the advantage of 16x16 and I'm not getting it. Can anybody explain why 16x16 is better than 16x8? What additional capabilities does it offer over 16x8?

The idea of all the "extra space" board representations is to reduce time spent for "Am I still on the board?" tests. See, for instance:
http://www.cis.uab.edu/hyatt/boardrep.html
http://chessprogramming.wikispaces.com/0x88

See Christophe Theron's remarks in this thread:
http://www.chesskb.com/Uwe/Forum.aspx/c ... /bitboards

which explains quite well why alternatives to 0x88 come out a bit better.

Which move generator is popular waxes and wanes with whichever chess engine is smoking at the time. I expect that most new engines will be bitboard since Rybka is currently king of the hill. When ChessTiger had the fastest move generator, the array approach gained popularity.

I expect that with 64 bit machines and compilers the bitboard method is just as good or better, but I do not have emprical evidence to prove it.

[MattieShoes]

I understand the advantages of of 0x88. What I've written uses the standard 16x8, 0x88 representation in fact. The first engine I wrote used 10x12. The main advantage of 0x88 over, 10x12 board is the very small, dense tables possible. A single 238 byte table can store a ton of information, and the 0x88 test is a minor additional bonus.

So from the thread, the advantage of 16x16 over 8x16 is eliminating the (target & 0x88) check in movegen before lookup and replacing it with a single lookup, which will be marginally faster on checks of squares on the board and marginally slower when checking squares off the board. The disadvantage is 256 bytes for the board instead of 128 bytes. Did I miss any other advantages of 16x16? I can believe it's faster, but I have a hard time imagining that alone would be significant in the scheme of things...

Regarding square color tests, i think I do

Code: Select all

(((sq >> 4) ^ sq) & 1)

Is there something better?

[Gerd Isenberg]

I understand the advantages of of 0x88. What I've written uses the standard 16x8, 0x88 representation in fact. The first engine I wrote used 10x12. The main advantage of 0x88 over, 10x12 board is the very small, dense tables possible. A single 238 byte table can store a ton of information, and the 0x88 test is a minor additional bonus.

So from the thread, the advantage of 16x16 over 8x16 is eliminating the (target & 0x88) check in movegen before lookup and replacing it with a single lookup, which will be marginally faster on checks of squares on the board and marginally slower when checking squares off the board. The disadvantage is 256 bytes for the board instead of 128 bytes. Did I miss any other advantages of 16x16? I can believe it's faster, but I have a hard time imagining that alone would be significant in the scheme of things...

Regarding square color tests, i think I do

Code: Select all

(((sq >> 4) ^ sq) & 1)

Is there something better?

Not really ...

Code: Select all

; 0x88 square in ecx
 mov eax, ecx
 shr eax, 4 
 xor eax, ecx
 and eax, 1

... may be a 64/128 byte lookup, depending whether you have 8*8 or 8*16 square coordinates.

Xor, add or sub the least significant one bits of file and rank index is fine. Since square a1 is black, and my enum for {white, black} is {0,1}, and i map square a1 to rank and file zero, I need one further leading or trailing xor 1.

With 0..63 coordinates, a 32-bit in-register lookup instead of the portable 64-bit in-register lookup works as well on x86, since 32-bit shift amount is implicitly modulo 32:

Code: Select all

int colorOfSquare (int square0_63) {
   return (0xAA55AA55 >> square0_63) & 1;
}

Code: Select all

; square 0..63 in ecx
 mov eax, 0xAA55AA55
 shr eax, cl
 and eax, 1

This is shorter but requires a variable shift on x86 via cl.

[hgm]

On an odd-width board you could simply do (sq & 1).

A point to note is that for boards with a rim of border guards, the extra size of the board is only needed for the actual playing board. All other board-size tables (e.g. piece-square or Zobrist) would not need the rim, as they would only be accessed for on-board squares, after the test on the move generator using the higher board that describes the current positon would have confirmed the toSquare is valid.

So 12x16 actualy makes for very compact tables, not wasting any space at all. In my engine HaQiKi D I have opted for a 16x20 board, so that it can handle actual playing areas of upto 10x10, with a 3-wide rim of border guards around it. But all other tables are 10x20 arrays, each contaning two logically independent tables. In variants that actually use the full 10x10 board this does not waste any space at all, except on the main board, which now needs border guards left and right (where you coud have the left and right rim overlap, and do with a 16x13 board), and 4 unused bytes between right rim and left rim for the next rank (into which I then map other int variables). Of course a 3-layer rim of boder guards is also more than is needed in most variants, as pieces that leap over a distance of 3 (such as Bison or Falcon) are not very common.

But the main board usually takes only a very small part of the space occupied by board-size tables. There is only a single such board, usually an array of characters. Even the PSTs occupy 13 times as much space, assuming 8 bytes is enough for them (and 52 times as much if they are 32-bit ints), and each piece type only has a single PST. (Usually Kings have extra PST for in the end-game, and passers use other PST than other Pawns.) And if you are not careful, the Zobrist randoms even occupy 104 times as much space, as they are 8 bytes each.

[Gerd Isenberg]

or with 0x88 squares ...

Code: Select all

int colorOfSquare (int x88square) {
   return (0x00AA0055 >> x88square) & 1;
}

[Robert Pope]

Thanks for all the good pointers. I felt like I was hitting a wall with Beaches, and just couldn't get over that "beginner" hump no matter what I tried. Partly that was movegen speed, partly my code was too messy to test ideas and probably had many bugs.

I'm hoping that using a simpler format and doing it properly, the next attempt will be easier to work with.

[MattieShoes]

I never even considered shifting by more bits than there are in the value... Clever solution
Should it run faster? I tested it in debug mode (otherwise, the compiler optimized away the entire loop!) and it was within a few percent, but I don't know if the fact it was running in debug mode makes any real difference here.