Bitboards / move generation on larger boards

[Greg Strong]

Since we're talking about bitboard techniques (such as magic bitboards and hyperbola quintessence) anyway, I'd like to take the opportunity to throw another variable into the discussion...

Chess variants with larger boards, in particular the 80-square 10x8, being as it seems to be the most common right now. ChessV uses rotated bitboards, and has a BitBoard96 class that allocates a 64-bit and a 32-bit value so it's capable of handling any board with up to 96 squares. (And there's also a BitBoard128 class for even larger boards.) It all works fine, but I'm now in the process of doing a complete re-write of ChessV, and I'm wondering if other techniques should be considered. The use of 128-bit SSE registers is appealing, and certainly useful for some aspects, but it has limitations - for example, you can't shift an entire 128-bit register by an arbitrary number of bits, nor can you perform any arithmetic with any values larger than 64 bits.

Anyone have any ideas they want to kick around?

[Gerd Isenberg]

Since we're talking about bitboard techniques (such as magic bitboards and hyperbola quintessence) anyway, I'd like to take the opportunity to throw another variable into the discussion...

Chess variants with larger boards, in particular the 80-square 10x8, being as it seems to be the most common right now. ChessV uses rotated bitboards, and has a BitBoard96 class that allocates a 64-bit and a 32-bit value so it's capable of handling any board with up to 96 squares. (And there's also a BitBoard128 class for even larger boards.) It all works fine, but I'm now in the process of doing a complete re-write of ChessV, and I'm wondering if other techniques should be considered. The use of 128-bit SSE registers is appealing, and certainly useful for some aspects, but it has limitations - for example, you can't shift an entire 128-bit register by an arbitrary number of bits, nor can you perform any arithmetic with any values larger than 64 bits.

Anyone have any ideas they want to kick around?

I think those board sizes are the domain of mailbox approaches, specially for "variable" board sizes. For 10x8 you may use 128-bit xmm-registers. With the right mapping, one step shift is a combination of (left/right) bit-shift and byte-shift. So you may use something like this (saving the wrap ands), but replace bitwise shift 8 by byte-wise shift one. So quite nice for pawn attacks and dump-9 fill.

[hgm]

H Gregory! Good to hear you are again working on Chess V. I hope you still plan to make it WB compatible! We have an ICS that can handle Capablanca variants now too, to which WinBoard is client.

I would recomend mailbox. (But I would also recommend that for 8x8, so no surprise there. ) But if you want to try something new, you could try the following: make the board representation a collection of rays, 4 rays through each square. Even for 10-size boards and on a 32-it machine, this would give you 3 bits per square. For each square and direction you could tabulate which ray corresponds to it, plus a bit mask that indicates which bits would correspond to that square. To update the board, you would only have to update the rays that go through the from and the to squares. You could update information on what is on the square (e.g. if it moves along the ray, and if so, which color it has) in the same operation. If you use one of the 3 bits you have for each square as 'occupied' bit, and store all the 'occupied' bits contiguously, you could use those bits for tabe-lookups of bitmaps of reachable squares along the ray.

[smrf]

Greg, fine to read about your redesigning approach. My program Octopus still is waiting to be seriously started as a rewritten SMIRF - because first I am working out a pure combinatorical approach for solving exactly all type symmetric TSPs up to about 35 nodes (using a single PC CPU thread). This will be done during this month.

I suggest not to use any bitboard approach, not only because it is not matching convincingly the 10x8 geometry, but also because a mailbox based approach combined with some other binary tricks is far superiour. Despite of the fact, that move generation is only a minor relevant part for the quality of a resulting chess engine, it is not fine to find a self written generator to be of only second class efficiency.

[Tord Romstad]

Since we're talking about bitboard techniques (such as magic bitboards and hyperbola quintessence) anyway, I'd like to take the opportunity to throw another variable into the discussion...

Chess variants with larger boards, in particular the 80-square 10x8, being as it seems to be the most common right now.

I am fairly sure 9x9 and 10x9 are by far the most common bigger board sizes, but the problems are of course similar in all cases: No built-in support for bigger integers than 64 bit in common low-level languages, and much bigger sizes for lookup tables. I am very skeptical that bitboards are the best way to go for boards bigger than 8x8, but I know that several of the top shogi programs use bitboards, so they can't be too bad.

I have a 9x9 bitboard sliding attack generator for shogi, but I am not sure how efficient it is.

Tord

[Greg Strong]

H Gregory! Good to hear you are again working on Chess V. I hope you still plan to make it WB compatible! We have an ICS that can handle Capablanca variants now too, to which WinBoard is client.

Awesome. It'll definitely be WB compatible. In fact, in the beginning, that'll be the only way to use it. One of the big short-comings of ChessV is the inability to do any kind of automated tournament. Of course, when I started writing it, there wasn't much else out there to pittit against. I hope more CV-capable engines emerge.

I would recomend mailbox. (But I would also recommend that for 8x8, so no surprise there. ) But if you want to try something new, you could try the following: make the board representation a collection of rays, 4 rays through each square. Even for 10-size boards and on a 32-it machine, this would give you 3 bits per square. For each square and direction you could tabulate which ray corresponds to it, plus a bit mask that indicates which bits would correspond to that square. To update the board, you would only have to update the rays that go through the from and the to squares. You could update information on what is on the square (e.g. if it moves along the ray, and if so, which color it has) in the same operation. If you use one of the 3 bits you have for each square as 'occupied' bit, and store all the 'occupied' bits contiguously, you could use those bits for tabe-lookups of bitmaps of reachable squares along the ray.

What you have here sounds interesting, but I'm having difficulty comprehending. It sounds like, in addition to being able to handle different board sizes, it could also be extended to support pieces that slide in different directions (like Knight-riders) which quickly becomes infeasable with rotated bitboards because you have to maintain a lot more differently-rotated blocker arrays. I'm going to try reading it again and see if I can figure out what you mean...

[Greg Strong]

Greg, fine to read about your redesigning approach. My program Octopus still is waiting to be seriously started as a rewritten SMIRF - because first I am working out a pure combinatorical approach for solving exactly all type symmetric TSPs up to about 35 nodes (using a single PC CPU thread). This will be done during this month.

I suggest not to use any bitboard approach, not only because it is not matching convincingly the 10x8 geometry, but also because a mailbox based approach combined with some other binary tricks is far superiour. Despite of the fact, that move generation is only a minor relevant part for the quality of a resulting chess engine, it is not fine to find a self written generator to be of only second class efficiency.

Thanks. I'm also glad to hear that you're still in the CV-engine "game." You are correct that getting the fastest possible move generation isn't so important as to be worth spending all one's time on... It is just an interesting thing to play with.

[Greg Strong]

I think those board sizes are the domain of mailbox approaches, specially for "variable" board sizes. For 10x8 you may use 128-bit xmm-registers. With the right mapping, one step shift is a combination of (left/right) bit-shift and byte-shift. So you may use something like this (saving the wrap ands), but replace bitwise shift 8 by byte-wise shift one. So quite nice for pawn attacks and dump-9 fill.

Thanks, that page has a lot of good material on it. Actually, I've been spending quite a lot of time reading the various bitboard and bit-twiddling pages on the Wiki (mostly written by you, I believe.) That, along with some of the other great material on that site, is largely responsible for motivating me to get moving again...

I think the XMM registers have a lot of potential for 10x8 and even 12x8. I've come up with a super-fast way to find passed pawns, isolated pawns, backward pawns, and knight outposts on those board using them. I'll be sure to post the relevant code as soon as it's all written and tested. I think it might be really good for standard 8x8 also. It depends on a couple of unusual approaches, though...

For one thing, you need to map the squares so that the bits of a file are stored together, not the bits of a rank. This makes sense to me for a couple of reasons. (1) Since the SSE2 instructions can operate on arrays of bytes, and an entire file on a 10x8 board fits into a byte whereas a rank does not. And (2) finding all these pawn properties requires examing files, not ranks.

For another thing, you don't start at the first bit. You actually leave space for an extra non-existant file on each side of the board so that you don't have to handle the edge pawns as special cases. Since you've got 128 bits (16 bytes) to play with, there's plenty of room.

The only other catch is that you need to keep two extra 128-bit values, one for each side, but if you update them incrementally when a pawn moves, this is not expensive compared to the time it saves in evaluation. These values have the bits set of the back-most pawn on each file and all the squares behind it. For empty files, including the phantom files off the edge of the board, all the bits are set.

I can start posting pseudo-code if anyone's actually interested ...

[Gerd Isenberg]

I think those board sizes are the domain of mailbox approaches, specially for "variable" board sizes. For 10x8 you may use 128-bit xmm-registers. With the right mapping, one step shift is a combination of (left/right) bit-shift and byte-shift. So you may use something like this (saving the wrap ands), but replace bitwise shift 8 by byte-wise shift one. So quite nice for pawn attacks and dump-9 fill.

Thanks, that page has a lot of good material on it. Actually, I've been spending quite a lot of time reading the various bitboard and bit-twiddling pages on the Wiki (mostly written by you, I believe.) That, along with some of the other great material on that site, is largely responsible for motivating me to get moving again...

I think the XMM registers have a lot of potential for 10x8 and even 12x8. I've come up with a super-fast way to find passed pawns, isolated pawns, backward pawns, and knight outposts on those board using them. I'll be sure to post the relevant code as soon as it's all written and tested. I think it might be really good for standard 8x8 also. It depends on a couple of unusual approaches, though...

For one thing, you need to map the squares so that the bits of a file are stored together, not the bits of a rank. This makes sense to me for a couple of reasons. (1) Since the SSE2 instructions can operate on arrays of bytes, and an entire file on a 10x8 board fits into a byte whereas a rank does not. And (2) finding all these pawn properties requires examing files, not ranks.

For another thing, you don't start at the first bit. You actually leave space for an extra non-existant file on each side of the board so that you don't have to handle the edge pawns as special cases. Since you've got 128 bits (16 bytes) to play with, there's plenty of room.

The only other catch is that you need to keep two extra 128-bit values, one for each side, but if you update them incrementally when a pawn moves, this is not expensive compared to the time it saves in evaluation. These values have the bits set of the back-most pawn on each file and all the squares behind it. For empty files, including the phantom files off the edge of the board, all the bits are set.

I can start posting pseudo-code if anyone's actually interested ...

Yes, please post it. I guess pawn pattern can be done based on kogge-stone fills and spans. Of course with 8 ranks and up to 16 files one may also map one rank to one of eight 16-bit words. Then an up/down shift can be done 128-bit shifts with two bytes, while the left/right board shift might be done by word wise shifts.

[Gerd Isenberg]

The only other catch is that you need to keep two extra 128-bit values, one for each side, but if you update them incrementally when a pawn moves, this is not expensive compared to the time it saves in evaluation. These values have the bits set of the back-most pawn on each file and all the squares behind it. For empty files, including the phantom files off the edge of the board, all the bits are set.

Ahh, I understand now, so you can get spans by simple byte-wise SIMD one's decrement or negate. Interesting!