Computer Chess Club Archives


Search

Terms

Messages

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

Author: Albert Bertilsson

Date: 00:49:57 06/28/03

Go up one level in this thread


On June 27, 2003 at 20:04:29, Uri Blass wrote:

>On June 27, 2003 at 19:48:44, Sune Fischer wrote:
>
>>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
>>>>off-road rally.
>>>
>>>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.
>
>And this is also counter productive for perft because if you have fast
>make move then you cannot use attack tables for faster move generation.
>
>I believe that this is the reason that Movei was faster than Sharp in
>calculating perft.

I think you're right, there are some places in the movegeneration that I know
would be done faster if Sharper had attacktables. The main reason that Sharper
doesn't use attacktables yet is that I:
1. Don't know how I want the tables to look (what I need to get from them when
ordering moves etc.
2. I don't have a good idéa of how to generate them efficiently.

I think the main point about studying perft times is that when isolating the
problem of how to generate and make moves you question what data is needed and
how to represent it. Good board representation should make fast move generation
easy!

Also it's really good to have perft to compare with, Sharper still lags behind
Movei, and that tells me I have missed some clever things in the board
representation.
>
> IMO it's very clear that it makes little sense to optimize a
>>makemove+movegen without considering the remaining program.
>
>I agree but I think that the difference between the things is not big.
>
>>
>>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.
>
>Yes but for calculating perft the speed of the move generator is also important
>and if I make my makemove slower then I can make my movegen faster.
>
>for perft 2 I make only the legal moves in one ply but generates the legal moves
>of all the games of 2 plies.
>
>>
>>>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.
>
>
>No
>It is better for you not to make the last ply but only generate legal moves.
>
>
> 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.
>
>In real perft I also do not make most of the moves that I generate so
>you see that for me it is similiar.
>
>Uri



This page took 0 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.