Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Improvements in BF makes my MoveGen suck =(

Author: Christophe Theron

Date: 13:57:41 06/28/03

Go up one level in this thread


On June 27, 2003 at 15:16:27, Russell Reagan wrote:

>On June 27, 2003 at 15:02:40, Christophe Theron wrote:
>
>>Generating lists of moves in general is sub-optimal. It's much better to
>>generate move lists incrementally (moves should be generated on demand, a
>>complete list is never generated).
>
>How do you have good move ordering without knowing what all of the moves are?



Well that's part of the point. You need to work and find good move ordering
heuristics that do not imply building and sorting a move list.

I have made experiments for several years in my 16 bits program. This program
generated complete move lists and allowed me to test many move ordering
heuristics.

I then rewrote my program in 32 bits with an incremental move generator and move
ordering heuristics developped in the 16 bits program.

Actually the move generator and the move ordering heuristics are melted
together. That means that the move generator generates the moves in a special
order. Move ordering heuristics are not used to sort a list, but to generate
moves on the fly.

My move generator is quite complex. I think it's pointless to try to have the
fastest move generator. I could generate moves maybe 10 times faster, and even
if the move ordering was as good as the one I have now my program would not even
be 2% faster.

It's much better to work on incremental and smart move generation.

Techniques can involve accessing the hash table or buffering moves (there are
two moves that could be interesting to generate, so the move generator generates
both, decides which one should be emitted first and puts the second one in a
buffer so it will be generated at the next call).

Also there are some well-known cases where you are almost certain that the whole
move list is going to be searched. In this case the incremental move generator
can be smart enough to generate them all as quickly as possible, store them in a
buffer and pull them from the buffer one by one when needed. In this case it's
not incremental move generation anymore but the search part still sees it as
incremental. So it's not completely true to say that complete lists are never
generated as I wrote above.

The point about incremental move generation is to emit the next move to search
with the smallest possible effort, because the probability that you will not
need to generate the other ones is quite high. But generating the moves in a
sensible order is also very important and "smallest effort" must negociate a
compromise with "good move ordering".





> Do
>you have a cheaper function that detects statically whether a move is legal
>(say, get the hash move and statically detect if it is legal, rather than
>generating all moves and seeing if it is in the list)?



You focus too much on move legality. You should not care much about this. After
making a move, just call a function that checks for the legality of it. It's
very easy, you just have to look at your own king and see if it is in check.

Illegal moves are not common and so very few moves are going to be rejected.

The move generator can even help by filtering out some obviously illegal moves.
For example if you are in check you should write a special "out of check" move
generator because the general one is going to emit mostly illegal moves.




>IIRC, you use several forward pruning filters in Chess Tiger. How do you apply
>the filters if you don't have a complete move list?



Pruning is applied both during and after move generation.

Some moves a pruned before being generated (so they are not generated at all),
some other moves are generated and pruned after makemove.





>>I have the same opinion about attack tables, but it depends on what you are
>>doing.
>
>At what point would your opinion change about attack tables? Would an engine
>have to make significant use of them before you would prefer them over on the
>fly attack detection?



I can't answer to this question, which is too general.

All I can say is that I have absolutely no attack table in Chess Tiger. When I
need to know if X attacks Y I call a function that looks at the board and
determines if X can move to the square of Y. Naturally a great deal of
optimization has been applied to this function, and I would even say that the
basic data structure of Chess Tiger has been designed to help this optimization.

It can happen that during the evaluation of a single position I call this
function several times for the same X and Y, but it does not happen often and in
average I save a lot of computations over the method of building a complete
attack table and just looking up at the table to find out if X attacks Y.

But all of this is also dependant on the way you do your evaluation. It is also
possible to be efficient by building attack tables, but not up to the leaves.
But it's very tricky because you need to understand what parts of the table are
outdated, and also it's not that easy to decide a priori if a node is a leaf or
not without investigating the position, and in general you would need the attack
tables to determine this.





>In any case, your philosophy sounds interesting. It should keep my brain
>thinking for a bit :)



It's just the general idea. You then need to experiment yourself. But I think
that you already have some evidence of what I say. In a chess program -in
general- computations should be done on demand, not prepared before you even
know if you are going to use them.




    Christophe



This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.