Daniel Shawul wrote:Bitboards are best for games like checkers. In orthodox chess they require some rotation or majic tables and become clumsy.
I disagree!
Bitboards are probably the most compact way to store true/false information about a set of squares. As a bonus, you can use rank/file/diagonal occupancy information as an index to a table of pre-computed move targets, but you don't have to. Depending on your mapping, rank occupancy is the easiest to get and file/diagonal occupancy are more difficult and require some bitwise manipulations. Not sure why you say that's better for checkers, it seems to me at best equally bad (if you're using a simple naive board representation as you do for chess) or worse (if you're using a denser representation that takes into account that only half the board is ever actually used).
Also when you do incremental, you need a sanity check for that move which is not that trivial. In some games it is just impossible to do that. There are so many tests you need to do, it is much easier generating all moves at once. Even for the hash table move this privilage could get screwed up when you go multi processor due to hash collisions.
Yes.
Personally, I haven't been able to get verification of moves to work well enough that it pays off. I may look at that again some time, more interesting things to do in the mean time.
If we only talk about orthodox chess evasions, I remeber I did gain some speed up for my old engine with piece list. I had to do some game specific in_check and pinned routines to achive that.
It probably helps that I'm not trying to be 100% correct: I just weed out things that I know I don't need to consider without even spending any time thinking about it. I still need to check generated moves for legality during the search.
I disagree!
Bitboards are probably the most compact way to store true/false information about a set of squares. As a bonus, you can use rank/file/diagonal occupancy information as an index to a table of pre-computed move targets, but you don't have to. Depending on your mapping, rank occupancy is the easiest to get and file/diagonal occupancy are more difficult and require some bitwise manipulations. Not sure why you say that's better for checkers, it seems to me at best equally bad (if you're using a simple naive board representation as you do for chess) or worse (if you're using a denser representation that takes into account that only half the board is ever actually used).
In checkers there are no sliders, which avoids the need for majic or rotatated bitboard tables. The international checkers variant has sliders so that is more like chess then. Even if it is 10x10, I *think* you can use bitboards since only 50 of them are used. But for chess variants with larger boards, how can you use bitboards effectively ? You need all the squares unlike checkers, and you have to use pairs of bitboards. Bitboards are winners in caputre move generation , mobility , attack_from_to , which will get lost once the boards size exceeds 64.
Sure bitboards are compact, but I honestly don't know how to use on boards larger than 64 _relevant_ squares. BTW when I say bitbaords , I meant only the 64 bit bitboard, not the file/rank/diagonal bitsets. I used that kind of bitsets in attack tables in the past even when I had purely piece list board representation. Please exuse my "insistance" (probably due to some ignorance on my side
I use the 'retrograde' type of computation when doing attacks. F.i checking if a square is attacked by a pawn in the retrograde way is much faster than looping through all the pawns to see if they attack the square. For spartan and other variants, there are such chances for pieces other than pawns. Maybe the same thing can work in the move generator as well. Also since captures are by far the most generated your MVV optimization can be a winner. But if you want to go ahead and sort them by SEE , other moves still have to generated. Also single reply extensions require you to generate all moves which I do not do now.
I guess it all depends on your strategy.
Surprising not generating any kind of evasions is my new strategy which is working fine rght now
I believe bitboards are ideally suited to checkers. A bitboard represents a piece of information about each square on the board with a single bit. Bitboards are most mentioned in relation to chess, but they don't fit in with a chess program as elegantly. (Note: I don't mean to imply they can't be good for chess. ) The sliding moves in chess aren't easily generated with bitboards, and there are more piece types, so you need more bitboards. Bitboards have also been used in Othello, though my own Pointy Stone doesn't use them. I don't see any drawbacks to using bitboards with checkers besides the added complication.
Daniel Shawul wrote:
In checkers there are no sliders, which avoids the need for majic or rotatated bitboard tables. The international checkers variant has sliders so that is more like chess then.
Right - I keep forgetting checkers has no sliders.
But for chess variants with larger boards, how can you use bitboards effectively ? You need all the squares unlike checkers, and you have to use pairs of bitboards. Bitboards are winners in caputre move generation , mobility , attack_from_to , which will get lost once the boards size exceeds 64.
Sure bitboards are compact, but I honestly don't know how to use on boards larger than 64 _relevant_ squares.
The simplest would be a 128 bit integer data type, but we don't have that. I use a tuple of 2 64 bit integers and define bit-wise operators on them (either through operator overloading in C++ or by explicit function calls hiding the internal representation in C). That's about it, really. Essentially the same as you would do for a 64 bit data type on 32-bit hardware. You lose some efficiency because you're not running natively on 128 bit hardware, but that doesn't make it unusable.
Note that I don't claim it's the most efficient way to do it, I don't know either way. But it does work.
Back in 1987 I wrote Spector, my first bitboard chess program and at first it did not have a move generator for check evasion. I read the Chess 4.x report by Slate and Atkin and they mentioned that their program had such an evasion generator, so I gave it a try and I saw a significant speed-up.
Bitboards can work well for other games. Long ago I wrote a Qubic (4x4x4 tic-tac-toe) that used 64-bit bitboards for location properties and 76-bit bitboards with each bit corresponding to one of the 76 possible wins.
sje wrote:Back in 1987 I wrote Spector, my first bitboard chess program and at first it did not have a move generator for check evasion. I read the Chess 4.x report by Slate and Atkin and they mentioned that their program had such an evasion generator, so I gave it a try and I saw a significant speed-up.
Bitboards can work well for other games. Long ago I wrote a Qubic (4x4x4 tic-tac-toe) that used 64-bit bitboards for location properties and 76-bit bitboards with each bit corresponding to one of the 76 possible wins.
What is the explanation for this "significant speed-up" ?
May be because I can mask (reduce) available "to" squares ?
selectany wrote:I can't understand what is the reasons for use of GenerateCheckEvesionsMoves as part of move generation.
Can I just use GenerateAllMoves and filter moves to only legal ones, by testing for check after probing (MakeMove/UnmakeMove) each generated move?
Only one reason (for me) might be if GenerateCheckEvesionsMove routine is faster than GenerateAllMoves one.
It is all about speed. If you generate "pseudo-legal moves" most are illegal when you are in check. You have to make a move, then test to see if it leaves you in check (which is an illegal move). If you only generate legal moves, you can avoid this "in-check test" completely. And if you like the one-legal-reply extension, this gives it to you easily since you know how many legal moves there are, not how many pseudo-legal moves there are...
selectany wrote:What is the explanation for this "significant speed-up" ?
May be because I can mask (reduce) available "to" squares ?
Yes, and if a program tracks sets of attacks to squares, then from-square selections can also be reduced.
Consider a typical middle game position that has 30 moves. With the king in check, the move count may drop to about five, so there's a speed-up by a factor of six.
sje wrote:Back in 1987 I wrote Spector, my first bitboard chess program and at first it did not have a move generator for check evasion. I read the Chess 4.x report by Slate and Atkin and they mentioned that their program had such an evasion generator, so I gave it a try and I saw a significant speed-up.
Bitboards can work well for other games. Long ago I wrote a Qubic (4x4x4 tic-tac-toe) that used 64-bit bitboards for location properties and 76-bit bitboards with each bit corresponding to one of the 76 possible wins.
What is the explanation for this "significant speed-up" ?
May be because I can mask (reduce) available "to" squares ?
If you generate pseudo-legal moves, most are illegal when you are in check. It takes effort to generate them. Then when you try to search one, you make the move, the legality check reveals it is illegal, you have to unmake it and go to the next move.
A legal move generator takes a bit more work to generate each individual move. But you generate fewer moves and do less work overall. But the big savings is that when you use this generator, you don't have to legality check each resulting position, saving all the illegal make/unmake operations, plus you never have to do the legality check at all. That is a significant savings.
