Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: annoying en passant x-ray

Author: Sune Fischer

Date: 04:27:08 12/01/03

Go up one level in this thread


On December 01, 2003 at 04:16:46, Russell Reagan wrote:

>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.

In move generation there are two loops, the outer loop over the pieces and the
inner loop for the moves of that piece.

The clever thing about legal move generation is that you can move the legality
check out of the inner loop.

Currently I check 'em move by move as I play them, so that means in a fail low
my check would effectively be in the inner loop, argh!

> 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.

Not sure fillers are the fastest ways to find pins.

As you loop through the pieces you get their square, this square you look up in
a table to see what kind of geometric relation it has to the king.
This seems simple and quite fast to me.

>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).

I imagine it can get a little complicated, but the principle isn't hard to
understand :)

-S.



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.