Author: Russell Reagan
Date: 01:16:46 12/01/03
Go up one level in this thread
On November 30, 2003 at 19:43:00, Sune Fischer wrote: >No pun intended, but what is it that is so clever about legal move generation? > >It seems faster to put off the expensive legality check until the last moment >just before you make the move. >That way you save a lot of legality checking if/when you fail high. > >The only advantage that I can see, is that the move list might become 1-2 moves >shorter and therefore a bit faster to score and order, but for me the legality >checking of ~30 moves is more expensive. Hi Sune, I have tried implementing a 100% legal move generator in the past, and here are my thoughts. I think the main reason to do it would not be for speed, but for cleaner code, and to avoid any potential bugs that might arise from you forgetting to do your test after making a move. This probably isn't a very big deal either way. Just a matter of preference. I also think it is possible to write a 100% legal move generator that is almost no slower (maybe even faster) than a pseudo-legal generator. I'm comparing the overall effect on speed, not just the absolute time spent in the move generation function (IE I'm taking into account the time saved by not having to check for illegal moves being played). As Uri pointed out, you don't have to check that every move is legal, but that means that you have to have some information about pins ready to go, or efficiently computable. IIRC, Uri has attack tables, and Gerd uses the bitboard filling routines (KoggeStone), so they can detect pins pretty fast. If you used an 0x88-like system, a pseudo-legal generator is probably faster because the check to see if the move was legal is almost zero most of the time. Then again, Tord uses this kind of system, and he has a legal generator, so maybe he can tell us if there are some tricks he uses to keep legal move generation fast. The thing I didn't like about 100% legal move generators when I tried to write one was trying to manage all of the special cases, hoping I wasn't forgetting something, and trying to make it as fast as the pseudo-legal version. I gave up, but I believe it would not have been too hard if it was something I really wanted in my program (and therefore I would have had the patience to finish it).
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.