Computer Chess Club Archives

Messages

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

Author: Sune Fischer

Date: 16:48:44 06/27/03

Go up one level in this thread

On June 27, 2003 at 19:04:04, Steve Maughan wrote:

>Sune,
>
>>Perft is no good speed indicator anyway, not even for a move gen.
>>The perft tree is so different from the chess tree.
>>
>>Optimizing for perft is basicly like building a formula 1 car to use for
>
>I don't agree.  Perft is *quite* a good thing to optimize.  There are really
>four fundamental foundations of a good chess program -
>
>1) Evaluation
>2) Move Ordering
>3) Make / Unmake moves
>4) Generate Moves

This "box" thinking is not optimal I think.
It is better to think like this:

strength = engine(eval,moveordering,make/unmake,genmoves,...);

There is no reason why you shouldn't be mixing them, like e.g. in Rebel.

>There are of course other elements (e.g. extension) but these four elements IMO
>are the key elements.  Perft directly measures the performance of the last two
>elements.  Some would say that the speed of move generation is not that
>important and this is true to a certain extent since time spent in the GenMove
>routine is often less than 10%.  However, if you can generate moves quickly you
>will most likely also be able to generate mobility quickly - an element of the
>evaluation function.  So I would argue that perft goes some way to measuring
>three out of the four factors I've listed.

I can't think if a simple analogy here, so I will give you a mathematical
example.

Find the maximum of f(x,y) for x,y in [some interval].
You can think of x as move generator and y as eval.

If you know that f(x,y)=g(x)+h(y) for some functions g and h, then you can find
max for f by maximixing g and h.

However you do not know such functions exist, and there is no reason to believe
they would. In my experience hybrid functions tend to be the most powerful
solutions.

If you are determained to get the fastest possible make move, then that excludes
the use of attack tables, this will come back to haunt you in the search and the
eval. IMO it's very clear that it makes little sense to optimize a
makemove+movegen without considering the remaining program.

Suppose you use 50% of the time in eval and 20% in makemove+movegen, now you
slow down makemove a factor two but speed up eval also by a factor two.
Would you not think of this as a good decision? I would.

>It's other advantage is that you can't cheat with perft - i.e. for any given
>position there is a certain number of nodes that represent perft 5.  This is in
>contrast to Node Per Second where it's not clear what constitutes a node.  So
>you can see and objectively measure your perft times against other engines.

Yes nps doesn't compare, you can't compare speeds that simple in chess progs,
the best you can do is time to solution, or of course play matches.

What is really misleading about perft, is the topology of the search space.
It is very artificial compared to a realistic tree. You know in perft that you
will be needing all the moves you generate, you never generate a wasted move.
If you optimize for this, you are setting up your engine to go fast on the wrong
track. I make/ummake moves at the last ply in perft, that means my genmove takes
only 10-15%, the remaining 85% is pure make/unmake, as can be seen in a profile.

If I wanted a fast perft I'd only have to optimize my makemove, if I could move
the big load into genmove I'd go a lot faster. However in a *real* search you
don't get to make all the moves you generate, so that means the genmoves would
profile-wise be just as important as makemove, perhaps.
So you see, me optimizing for perft would cause me to optimize makemove, which
might not yield any speedup in a real search at all.

-S.

>Regards,
>
>Steve