Perft as a Measure of Speed...

[Steve Maughan]

Maverick's perft routine is nearly complete. Here's a blog post where I discuss the merits of perft times as a measure of speed:

http://www.chessprogramming.net/compute ... important/

Steve

[CRoberson]

The probability that the speed of perft is very important decreases with the amount of CPU time required by the position evaluator per position.

The point being ROI (return on investment): there is a point when extra work is almost irrelevant. In the case you blogged about, a 4.3x speed up is certainly a big improvement, but you have to remember Amdahl's law when it comes to overall speed up.

If an engine is a basic piece counter then move gen can be the bottleneck, thus effort there pays off. If the eval is very full of heuristics then move gen may not be an issue. Also, there are techniques in the search that delay move gen until necessary. Such techniques reduce the impact of a slow or fast move gen.

[Evert]

Perft speed is a poor metric for determining overall speed. There are two reasons for this: 1. move generation is unlikely to be the bottleneck during the search and 2. during perft you fill up the CPU cache with move generation data; during the normal search you have the transposition table and evaluation function competing for the cache as well, so move generation will be less efficient than it is during perft.

Still, it can never hurt you to generate moves efficiently. Just beware that what looks good for perft may actually be worse for the search (I've seen one or two changes that looked like good performance enhancers for perft but that actually slowed down the main search, mainly having to do with legality testing).

[Steve Maughan]

Hi Evert & Charles,

I agree. In absolute terms move generation is rarely the bottleneck in a mature program.

However, I think you miss the point I make in the blog post. One of the most costly activities of the evaluation function is assessing such elements as mobility. If you have a fast perft then you are also likely to be able to quickly evaluate such terms i.e. perft speed is likely to be correlated to overall speed, all things being equal. So I believe perft speed is a valid measure of the quality of the underlying framework.

Best,

Steve

[Evert]

However, I think you miss the point I make in the blog post. One of the most costly activities of the evaluation function is assessing such elements as mobility. If you have a fast perft then you are also likely to be able to quickly evaluate such terms i.e. perft speed is likely to be correlated to overall speed, all things being equal. So I believe perft speed is a valid measure of the quality of the underlying framework.

I didn't miss it, I disagreed with it.

The relevant question is: what dominates the time it takes to calculate perft? There are three likely candidates: the cost of generating the moves themselves, the cost of make/unmake and the cost of testing for legality. Only the first of these is an issue for calculating mobility (and even then the impact is reduced compared to move generation, since you only need to bulk-count the bitboard as opposed to serialise it to generate a move list).
I would claim (with some reasoning but no direct measurement) that the cost of perft is dominated by the latter two rather than on the first one. The reason I say that is that perft speed is increased dramatically if you have a legal move generator and can do bulk counting of moves at the leaves (skipping make/unmake and the legality test), and also that perft becomes much faster if you skip the legality test (the results are wrong, of course): the in-check test is relatively expensive.

This is also why legal move generators are better for perft than pseudo-legal move generators. During the search I think this is not so clear, but what I think is clear is that this is not a difference that is worth 100s of elo points one way or the other. Calculating mobility using a legal move generator in positions where the side to move is in check is probably wrong, but then again, the static evaluation is likely to be wrong in those positions anyway (the position is not "quiet").

[Steve Maughan]

Hi Evert,

You make some good point. I think perft times are only comparable if you're comparing apples-to-apples i.e. legal move gen vs. legal move gen.

Let me ask you this - I have two frameworks, Monarch which is letterbox based and Maverick which is based on magic bitboard. Monarch's pseudo legal move generation perft time for the position I used was x4.3 slower than Maverick's time. Do you think it will be "easier" to write a strong program using the core code from Maverick or Monarch (ignoring the fact that bitboards will probably be more useful in the evaluation)?

I think it's clear. Maverick is the better framework.

I guess I'm trying to think of this from the perspective of the person who has never written a chess engine before. In their case I believe perft is a *huge* milestone.

Firstly a perft routine which gives the correct move count over a series of position is likely to have bug free move generation, make and unmake code. This is a great achievement. If you can get this far you can probably create a working chess program.

And secondly, I think if we provide some apples to apples comparisons, the speed of the perft is something which can be used as a yardstick for the quality of the underlying structure.

Of course once you have a working chess program the perft speed is not relevant. But from the newbie's perspective, they are not sure how good their code / structure is. They are seeking some validation for their work and I think perft can provide this.

Best,

Steve

[Evert]

You make some good point. I think perft times are only comparable if you're comparing apples-to-apples i.e. legal move gen vs. legal move gen.

Indeed. Also whether counts are hashed or not.

Let me ask you this - I have two frameworks, Monarch which is letterbox based and Maverick which is based on magic bitboard. Monarch's pseudo legal move generation perft time for the position I used was x4.3 slower than Maverick's time. Do you think it will be "easier" to write a strong program using the core code from Maverick or Monarch (ignoring the fact that bitboards will probably be more useful in the evaluation)?

I think it's clear. Maverick is the better framework.

Quite possibly. I'm not sure I could accurately predict that from just the perft data though. It's your code and you're more familiar with it and how it can grow.

I guess I'm trying to think of this from the perspective of the person who has never written a chess engine before. In their case I believe perft is a *huge* milestone.

Certainly. Don't get me wrong: I'm not trying to say that perft results are not important - far from it. I'm just saying that perft times alone are not a good indication of (potential) playing strength. It simply measures something very different.

It is probably fair to say that, all other things being equal, the engine with the fastest perft will be the strongest. One caveat: I am not 100% sure if this is true if the efficient perft derives from legal move generation.
In practice, comparing different programs, all other things are not equal of course and it becomes much harder to make quantitative statements.

Firstly a perft routine which gives the correct move count over a series of position is likely to have bug free move generation, make and unmake code. This is a great achievement. If you can get this far you can probably create a working chess program.

Yes, having a working (and correct) move generator is the first thing you have to get right, and already quite complicated.
By the way, be sure to test against the positions posted here: http://www.talkchess.com/forum/viewtopic.php?t=47318
They'll help you find obscure or non-obvious bugs.
(EDIT: oh, I see you've posted in that thread, so you probably have all those already).

And secondly, I think if we provide some apples to apples comparisons, the speed of the perft is something which can be used as a yardstick for the quality of the underlying structure.

See, this I'm not so sure about. There are things that help during search and hurt during perft and vice versa. You want to accept changes that do the former, but not the latter.
Your perft speed needs to be "good enough". It does not need to be "as good as it can be". Afterall, you can always go back and improve it later.

[hgm]

I have two frameworks, Monarch which is letterbox based and Maverick which is based on magic bitboard. Monarch's pseudo legal move generation perft time for the position I used was x4.3 slower than Maverick's time.

Then Monarch must be very slow for other reasons than the basic data structure. In general mailbox perfts are hardly slower than bitboard perfts. In fact, when you would make/unmake the final ply, I would be very surprised if bitboard could compete at all. MakeMove is quite expensive with bitboards.

[Steve Maughan]

Hi H G,

[...]Then Monarch must be very slow for other reasons than the basic data structure. In general mailbox perfts are hardly slower than bitboard perfts. In fact, when you would make/unmake the final ply, I would be very surprised if bitboard could compete at all. MakeMove is quite expensive with bitboards.

Maybe. It's been a while since I worked on it but I didn't think of it as super slow. It does about 1 million nodes / sec when playing real chess. I was expecting Maverick to be faster at perft but not my a factor of x4.

Anyway Maverick is good enough.

Best,

Steve

[AlvaroBegue]

[...] MakeMove is quite expensive with bitboards.

Really? How is MakeMove with a different representation any faster?

(Note about tone: These are honest questions. I believe what you are saying, but I am just expressing surprise because this doesn't match my intuition.)