)good alternative to standard bitboard/legal move detection.
Here is how the system works:
Normally a chess game needs to generate a list of legal moves for a given position. An illegal move is one that would put the king in check. Knowing whether a move is legal or not requires you to scan the board, figure out where each piece can attack, and determine if one of those attacks is on the king''s square. Knowing the is critical.
"Scanning the board" is where we make our first change. We skip it. Why? Because MOST of the information we actually need will become available in due-process (through the natural course of programs execution).
So for now we assume most moves are valid. This is a good assumption, because as it turns out, the only time it''s neccesary to verify a moves is when it results in the capture of a king.
Most moves DON''T result in a kings capture, so checking their validity is not necessary. When more moves do result in a kings capture, the tree is going to do lots of pruning anyway! This is how we save-- by doing more processing than normal, but only when it needs doing.
i.e.: I move (A), the my opponent moves (B) and captures my king
If B did not result in a capture, then there is no need to verify A. If it did then we must do some extra work.
To accomplish this we need to add a check to our MinMax / AlphaBeta / Whatever algortithm.
As you enter the funtion, generate a list of legal moves (as you normally would). Then check each move to see if it results in a king capture (you would normally do this too, I hope). If a king capture occures, then call our new Verify function, and pass the PREVIOUS move (A)to it (not the ones you just generated (B)).
Verify does three things.
1. Using this board data you passed, construct a copy of the board previous to that (A-1). (Not a problem if you remember details about the last move in your gameboard structure).
2. Using the new board (A-1), let the side who did the capture (white in our example) move again. If any of these moves results in the kings capture, then the black king must be in checkmate, so there is no need to do any more processing. Quit.
3. If in 2, no moves resulted in a capture: Using the new board (A-1), create a list of moves for the side that was captured (black). For each of these, create a list of moves for the side that did the capturing(white). If for every black move, there is a resulting king capture by white, then the board is in a stalemate position. But, if ONE or more of these results in a move where the king isn''t captured, the move is ILLEGAL, and we can stop all processing.
Thats it. If coded properly it will only do maximum work if move results in a stalemate (very rare).
The only time there is waste is when a king is captured. We end up exploring just one move extra (by move I mean move, not ply) in the main loop IF a capture occures, and a maximum of two ply, minimum of 1 move, extra if move is illegal or a stalemate.
This is much faster than checking EVERY move to see if it''s legal. There is lots of room for optimizing (like sorting moves, so king captures appear first, during move generation).
Please let me know what you think.. I''m sure this has been tried before. It''s really easy to implement.
Will
New Chess game tree
October 17, 2002 12:29 PM
I''ve recently completed the guts of a new chess engine that''s been in the works for a few weeks.
What makes it interesting is the way in which I generate moves. No bitboards, no extra data structures to see what squares are safe, etc.. In fact, aside from the basic movement rules, there is no legal-move detection at move generation time.
This means that it''s much faster than your _standard_ run-of-the-mill Chess game tree. (I mean this only in terms of valid move generation)
I''m posting for two reasons. One is to see if anyone else has heard of or used this method in the past (are there better ways?). And the other is to let people know that there is at least one ( )good alternative to standard bitboard/legal move detection.
Here is how the system works:
Normally a chess game needs to generate a list of legal moves for a given position. An illegal move is one that would put the king in check. Knowing whether a move is legal or not requires you to scan the board, figure out where each piece can attack, and determine if one of those attacks is on the king''s square. Knowing the is critical.
"Scanning the board" is where we make our first change. We skip it. Why? Because MOST of the information we actually need will become available in due-process (through the natural course of programs execution).
So for now we assume most moves are valid. This is a good assumption, because as it turns out, the only time it''s neccesary to verify a moves is when it results in the capture of a king.
Most moves DON''T result in a kings capture, so checking their validity is not necessary. When more moves do result in a kings capture, the tree is going to do lots of pruning anyway! This is how we save-- by doing more processing than normal, but only when it needs doing.
i.e.: I move (A), the my opponent moves (B) and captures my king
If B did not result in a capture, then there is no need to verify A. If it did then we must do some extra work.
To accomplish this we need to add a check to our MinMax / AlphaBeta / Whatever algortithm.
As you enter the funtion, generate a list of legal moves (as you normally would). Then check each move to see if it results in a king capture (you would normally do this too, I hope). If a king capture occures, then call our new Verify function, and pass the PREVIOUS move (A)to it (not the ones you just generated (B)).
Verify does three things.
1. Using this board data you passed, construct a copy of the board previous to that (A-1). (Not a problem if you remember details about the last move in your gameboard structure).
2. Using the new board (A-1), let the side who did the capture (white in our example) move again. If any of these moves results in the kings capture, then the black king must be in checkmate, so there is no need to do any more processing. Quit.
3. If in 2, no moves resulted in a capture: Using the new board (A-1), create a list of moves for the side that was captured (black). For each of these, create a list of moves for the side that did the capturing(white). If for every black move, there is a resulting king capture by white, then the board is in a stalemate position. But, if ONE or more of these results in a move where the king isn''t captured, the move is ILLEGAL, and we can stop all processing.
Thats it. If coded properly it will only do maximum work if move results in a stalemate (very rare).
The only time there is waste is when a king is captured. We end up exploring just one move extra (by move I mean move, not ply) in the main loop IF a capture occures, and a maximum of two ply, minimum of 1 move, extra if move is illegal or a stalemate.
This is much faster than checking EVERY move to see if it''s legal. There is lots of room for optimizing (like sorting moves, so king captures appear first, during move generation).
Please let me know what you think.. I''m sure this has been tried before. It''s really easy to implement.
Will
)good alternative to standard bitboard/legal move detection.
Here is how the system works:
Normally a chess game needs to generate a list of legal moves for a given position. An illegal move is one that would put the king in check. Knowing whether a move is legal or not requires you to scan the board, figure out where each piece can attack, and determine if one of those attacks is on the king''s square. Knowing the is critical.
"Scanning the board" is where we make our first change. We skip it. Why? Because MOST of the information we actually need will become available in due-process (through the natural course of programs execution).
So for now we assume most moves are valid. This is a good assumption, because as it turns out, the only time it''s neccesary to verify a moves is when it results in the capture of a king.
Most moves DON''T result in a kings capture, so checking their validity is not necessary. When more moves do result in a kings capture, the tree is going to do lots of pruning anyway! This is how we save-- by doing more processing than normal, but only when it needs doing.
i.e.: I move (A), the my opponent moves (B) and captures my king
If B did not result in a capture, then there is no need to verify A. If it did then we must do some extra work.
To accomplish this we need to add a check to our MinMax / AlphaBeta / Whatever algortithm.
As you enter the funtion, generate a list of legal moves (as you normally would). Then check each move to see if it results in a king capture (you would normally do this too, I hope). If a king capture occures, then call our new Verify function, and pass the PREVIOUS move (A)to it (not the ones you just generated (B)).
Verify does three things.
1. Using this board data you passed, construct a copy of the board previous to that (A-1). (Not a problem if you remember details about the last move in your gameboard structure).
2. Using the new board (A-1), let the side who did the capture (white in our example) move again. If any of these moves results in the kings capture, then the black king must be in checkmate, so there is no need to do any more processing. Quit.
3. If in 2, no moves resulted in a capture: Using the new board (A-1), create a list of moves for the side that was captured (black). For each of these, create a list of moves for the side that did the capturing(white). If for every black move, there is a resulting king capture by white, then the board is in a stalemate position. But, if ONE or more of these results in a move where the king isn''t captured, the move is ILLEGAL, and we can stop all processing.
Thats it. If coded properly it will only do maximum work if move results in a stalemate (very rare).
The only time there is waste is when a king is captured. We end up exploring just one move extra (by move I mean move, not ply) in the main loop IF a capture occures, and a maximum of two ply, minimum of 1 move, extra if move is illegal or a stalemate.
This is much faster than checking EVERY move to see if it''s legal. There is lots of room for optimizing (like sorting moves, so king captures appear first, during move generation).
Please let me know what you think.. I''m sure this has been tried before. It''s really easy to implement.
Will
------------------http://www.nentari.com
21,607
October 21, 2002 05:07 PM
First of all, congratulations for having a chess engine up and running. The hardest part in making a good chess program is getting started.
Now the bad news: You are not discovering any new alternatives to legal-move detection. Sorry.
Actually, it goes the other way around. Old programs (including mine) used to do it your way. But adding information about threats, or being able to find them fast (like using bitboards) turns out to be important for speeding up the evaluation. So if you have a non-trivial evaluation function, you have to do the work anyway. Legal-move detection is faster under those circumstances.
Also, there are situations where lots of moves are illegal (for instance, after a check). And trees in which that happens often are the most critical in a game, because they can lead to check-mate! If your program slows down exactly at the hotest moments in a game, you are doomed. At least, you should make a specific routine to avoid checks.
Your scheme is still usable. I would recommend that you make your move generation more or less independant of the rest of the game, so you can test what is fastest for your program.
Now the bad news: You are not discovering any new alternatives to legal-move detection. Sorry.
Actually, it goes the other way around. Old programs (including mine) used to do it your way. But adding information about threats, or being able to find them fast (like using bitboards) turns out to be important for speeding up the evaluation. So if you have a non-trivial evaluation function, you have to do the work anyway. Legal-move detection is faster under those circumstances.
Also, there are situations where lots of moves are illegal (for instance, after a check). And trees in which that happens often are the most critical in a game, because they can lead to check-mate! If your program slows down exactly at the hotest moments in a game, you are doomed. At least, you should make a specific routine to avoid checks.
Your scheme is still usable. I would recommend that you make your move generation more or less independant of the rest of the game, so you can test what is fastest for your program.
October 22, 2002 10:47 AM
Thanks for the post. It was a lot of work getting this chess engine running. My wife thought I was loosing it.
I was under the assumption that, even with bitboards, it is still necessary to recalculate which squares are under attack for every move. If this is correct, that is almost the equivilant of doing an extra ply of moves for every move (except illegal moves). Is this correct?
I didn''t take in to account implementing any kind of complicated evaluation. Terms that can be measured quickly (material advantage, pawn structure, and a few other rules) are not a problem, but I see what you''re saying-- in my engine there would need to be a lot of recalculation for more complex terms.
Thanks,
Will
It was a lot of work getting this chess engine running. My wife thought I was loosing it. I was under the assumption that, even with bitboards, it is still necessary to recalculate which squares are under attack for every move. If this is correct, that is almost the equivilant of doing an extra ply of moves for every move (except illegal moves). Is this correct?
I didn''t take in to account implementing any kind of complicated evaluation. Terms that can be measured quickly (material advantage, pawn structure, and a few other rules) are not a problem, but I see what you''re saying-- in my engine there would need to be a lot of recalculation for more complex terms.
Thanks,
Will
------------------http://www.nentari.com
October 25, 2002 08:25 PM
As far as I understand (I am pretty new to AI programming so forgive me is my explanations are clueless...), with bitboards, you don''t need to recalculate the controlled squares (or legal moves) after each move as if you had no informations at all about it.
Let''s say for instance you moved a rook without capture.
You take your previous bitboard, remove from them the flags on squares indicating that they were controlled by the rook at its old position, and add flags on the new squares controlled by the rook. You also need to do a few extra things of course, like extend the controlled squares of long range pieces that were defneding or attacking the rook, and if you captured something, remove the flags for the controlled squares from the captured piece. You also must identify pinnings possibly caused or destroyed by your rook move, and remove or add flags for squares controlled by the unpinned or newly pinned piece. If your bitboard datas include xrays (for instance if you have a rook on a1 and a rook on b1, c1 is controlled by the b1 rook and is xrayed by the a1 rook through b1, the extension of lines and pinning/unpinning are easily detected from your previous bitboard data.
At least that''s what I am doing for my shogi program (even though there are few long range pieces in shogi), and I think it fastens a lot the legalmove detections without requiring really complex coding. The update of my bitoard is done with very few loops, and the geting of legalmove just requires me one loop over the 81 squares to get each piece who can go to that square (+ adding the drop piece movements, but these don''t exist in classic chess).
David Antonini
Let''s say for instance you moved a rook without capture.
You take your previous bitboard, remove from them the flags on squares indicating that they were controlled by the rook at its old position, and add flags on the new squares controlled by the rook. You also need to do a few extra things of course, like extend the controlled squares of long range pieces that were defneding or attacking the rook, and if you captured something, remove the flags for the controlled squares from the captured piece. You also must identify pinnings possibly caused or destroyed by your rook move, and remove or add flags for squares controlled by the unpinned or newly pinned piece. If your bitboard datas include xrays (for instance if you have a rook on a1 and a rook on b1, c1 is controlled by the b1 rook and is xrayed by the a1 rook through b1, the extension of lines and pinning/unpinning are easily detected from your previous bitboard data.
At least that''s what I am doing for my shogi program (even though there are few long range pieces in shogi), and I think it fastens a lot the legalmove detections without requiring really complex coding. The update of my bitoard is done with very few loops, and the geting of legalmove just requires me one loop over the 81 squares to get each piece who can go to that square (+ adding the drop piece movements, but these don''t exist in classic chess).
David Antonini
122
October 28, 2002 12:14 AM
Ugh... I was writing a long explanation on how to detect legal move rooks with a bitboard (without any loop, just a few binary rotaions, |, & and ~) and the message posting window just closed for some reason....
Anyway check this link, though less detailed (and not giving an algorithm for bitboard roation), it explains it well too.
http://www.ast.cam.ac.uk/~cmf/chess/theory.html#bitboards
After rereading your post I understood better what you meant though. You do not verify if a move leaves the king en prise, but you have somehow to test collisions for long range pieces when generating your move list (to avoid having rooks jump above pieces). So I would certainly advise you to use bitboards, as it fastens up A LOT this task : no loop needed at all, except maybe to update the rotated boards after a move has been played. And even more important, everything is done with binary operations on 64bites unsigned integers (wich are done extremely fast).
About the fact of considering as legal the moves that leave the king en prise, I think most top programs proceed that way already, except when the verification is needed (i.e quiescent search at lowest parts of tree). For the rest they consider that the brute force gained by not having to detect absolute pins is more important than the fact of generating a few less moves. So nothing new I am affraid, sorry.
If you need more explanations on bitboards, you can mail me at sigloxx@cybercable.fr (I won''t retry posting my explanations here to see my message closed again
)
David Antonini
Anyway check this link, though less detailed (and not giving an algorithm for bitboard roation), it explains it well too.
http://www.ast.cam.ac.uk/~cmf/chess/theory.html#bitboards
After rereading your post I understood better what you meant though. You do not verify if a move leaves the king en prise, but you have somehow to test collisions for long range pieces when generating your move list (to avoid having rooks jump above pieces). So I would certainly advise you to use bitboards, as it fastens up A LOT this task : no loop needed at all, except maybe to update the rotated boards after a move has been played. And even more important, everything is done with binary operations on 64bites unsigned integers (wich are done extremely fast).
About the fact of considering as legal the moves that leave the king en prise, I think most top programs proceed that way already, except when the verification is needed (i.e quiescent search at lowest parts of tree). For the rest they consider that the brute force gained by not having to detect absolute pins is more important than the fact of generating a few less moves. So nothing new I am affraid, sorry
.If you need more explanations on bitboards, you can mail me at sigloxx@cybercable.fr (I won''t retry posting my explanations here to see my message closed again
)David Antonini
David Antonini.
October 28, 2002 09:40 AM
Maybe I''ll go back and rewrite the move generator to use bitboards, just for the sake of comparision. It''s not so much bitboards that I considered slow, it was the legal move detection.
I was pretty sure this method has been used elsewhere; but like I said I''ve been unable of finding any documentation that describes it.
Thanks for the info,
Will
I was pretty sure this method has been used elsewhere; but like I said I''ve been unable of finding any documentation that describes it.
Thanks for the info,
Will
------------------http://www.nentari.com
118
November 01, 2002 10:50 PM
David,
I believe that the amount of work you would have to do to take care of all of the special cases would take as much time or longer than it would to generate the moves from scratch.
I have fiddled around before with generating 100% legal moves (IE I tried to detect pins) and that alone was complicated enough to cause a slowdown. Detecting it a knight is pinned is easy. But what about when a bishop is pinned? It might still be able to move in two directions, so you still have some checking to do. It''s not impossible, but it certainly seems much more bug prone. Imagine if you overlooked some obscure case and your program played an illegal move in a crucial game...
I''ve recently experimented with some attack generation methods that might prove useful for this method, but I still think incremental move generation isn''t going to cause great speed improvements. Even if it is an improvement, it probably won''t be that significant in the scope of the entire program. I think I''ll play with it though. I''d like to be able to generate 100% legal moves instead of having to check if it was actually legal at the next ply.
Contrary to what many people think, move generation is not where a good chess engine will spend most of it''s time. Evaluation is usually where the majority of time is spent.
Russell
I believe that the amount of work you would have to do to take care of all of the special cases would take as much time or longer than it would to generate the moves from scratch.
I have fiddled around before with generating 100% legal moves (IE I tried to detect pins) and that alone was complicated enough to cause a slowdown. Detecting it a knight is pinned is easy. But what about when a bishop is pinned? It might still be able to move in two directions, so you still have some checking to do. It''s not impossible, but it certainly seems much more bug prone. Imagine if you overlooked some obscure case and your program played an illegal move in a crucial game...
I''ve recently experimented with some attack generation methods that might prove useful for this method, but I still think incremental move generation isn''t going to cause great speed improvements. Even if it is an improvement, it probably won''t be that significant in the scope of the entire program. I think I''ll play with it though. I''d like to be able to generate 100% legal moves instead of having to check if it was actually legal at the next ply.
Contrary to what many people think, move generation is not where a good chess engine will spend most of it''s time. Evaluation is usually where the majority of time is spent.
Russell
122
November 02, 2002 12:07 AM
Thanks for the advice, Russel .
I gave up too the idea of checking if a move leaves king en prise, so no use for checking pins. Anyway the quiescent search will find king captures.
And all the "legal moves" in a given position are actually generated by the evaluation function itself now (and are probably a small part of it indeed, speedwise), as my evaluation needs to know wich squares are controlled by who.
In fact as I wanted to do this program in javascript, the BIG slowing factor is arrays or objects definition, it seems... defining a new object within the search is out of question it seems and I am going to have to use a lot of global variables (well I already do, my program barely looks like a program now).
I wonder how IE stocks personal objects in memory... I even had to give up the idea of pre-generating legal movements bitboards for all squares a rook or bishop might be on, as creating a few arrays of 9*512 objects of 3 32bytes integers (bitboards for a 9x9 board with a language that doesn''t admit 64 unsigned integers) was making my comp swap on the hard drive... (at least with IE5.5, NS6 seems to use less memory to stock objects).
I just pre-generated them for one file, depending on the occupancy, and I make bitboards rotations during the legal move generation.. This doesn''t seem to slow me too much compared to the time taken when stocking data in the tree. I wanted to stock the new positions (an object with the bitboards for each pieces and the bitboards for white and black pieces) at each depth, to not have to "undo" moves. I guess I will have to undo moves).
Anyone interested can download the actual sources at 9*9 board bitboards utilities and Main part. The main part is VERY chaotic at the moment (a mix of bitboard use and of my first try without bitboards), but you can find the actual evaluation function there (GiveEvaluation() ). It still obviously requires a lot of optimization (evaluating 1000 times the starting position takes over 30 seconds, when I hope to reach 1 or 2 seconds).
David Antonini
.I gave up too the idea of checking if a move leaves king en prise, so no use for checking pins. Anyway the quiescent search will find king captures.
And all the "legal moves" in a given position are actually generated by the evaluation function itself now (and are probably a small part of it indeed, speedwise), as my evaluation needs to know wich squares are controlled by who.
In fact as I wanted to do this program in javascript, the BIG slowing factor is arrays or objects definition, it seems... defining a new object within the search is out of question it seems and I am going to have to use a lot of global variables (well I already do, my program barely looks like a program now
).I wonder how IE stocks personal objects in memory... I even had to give up the idea of pre-generating legal movements bitboards for all squares a rook or bishop might be on, as creating a few arrays of 9*512 objects of 3 32bytes integers (bitboards for a 9x9 board with a language that doesn''t admit 64 unsigned integers) was making my comp swap on the hard drive... (at least with IE5.5, NS6 seems to use less memory to stock objects).
I just pre-generated them for one file, depending on the occupancy, and I make bitboards rotations during the legal move generation.. This doesn''t seem to slow me too much compared to the time taken when stocking data in the tree. I wanted to stock the new positions (an object with the bitboards for each pieces and the bitboards for white and black pieces) at each depth, to not have to "undo" moves. I guess I will have to undo moves
).Anyone interested can download the actual sources at 9*9 board bitboards utilities and Main part. The main part is VERY chaotic at the moment (a mix of bitboard use and of my first try without bitboards), but you can find the actual evaluation function there (GiveEvaluation() ). It still obviously requires a lot of optimization (evaluating 1000 times the starting position takes over 30 seconds, when I hope to reach 1 or 2 seconds).
David Antonini
David Antonini.
122
November 02, 2002 12:25 AM
David Antonini.
118
November 02, 2002 08:58 AM
Another myth I think a lot of people believe is that bitboards are the most popular board representation. It''s not true. It''s actually only becomming more popular now, but 0x88 board representation is by far the most popular I believe.
I use bitboards though, and I don''t know if using a non-compiled language for bitboards is a good idea. The reason bitboards are fast enough is because they can make use of fast "least significant 1 bit" functions, making use of the bsf/bsr ASM instructions. The language you use has to have support for inline assembly, or linking of an external assembly. I think finding the location of bits in java or javascript (or any other interpreted language) is going to be quite a bit slower than using bsf/bsr.<br><br>Russell
I use bitboards though, and I don''t know if using a non-compiled language for bitboards is a good idea. The reason bitboards are fast enough is because they can make use of fast "least significant 1 bit" functions, making use of the bsf/bsr ASM instructions. The language you use has to have support for inline assembly, or linking of an external assembly. I think finding the location of bits in java or javascript (or any other interpreted language) is going to be quite a bit slower than using bsf/bsr.<br><br>Russell
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
