What is the best known speed of move generation?

[nczempin]

perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea.

Wow, I did not know that. Can you please finally lift the secret that everyone wants to know: What does "perft" actually stand for??

[smrf]

I agree with H.G.. If Perft (Performance Test) is done to validate a move generator's true performance, it should be done under realistic circumstances. That is to make use not only of the existence of a move but of all related necessary properties, e.g. if it would be a check threat or castling etc. - thus to prove that ability, it seems to be necessary to also provide statistics about that kind of information. SMIRF has done such a thing as an example, avoiding best move count results by intention, but providing a lot of move related information.

Reinhard.

[bob]

How do you weed out the _other_ illegal moves? perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea. And the idea was that a perft total counts _only_ legal moves. If you do as you say, you will make illegal moves at the last ply when a piece is pinned on your own king...

You can look at the code.
He clearly does not generate illegal moves of pinned pieces

Here is one of his comments:

"/* Pintest, starting from possible pinners in enemy slider list */
/* if aiming at King & 1 piece of us in between, park this piece */
/* on pin stack for rest of move generation, after generating its */
/* moves along the pin line. */"

It is clear that he counts only legal moves otherwise he could not get correct numbers.

OK. I did not look at his code and generally do not look at code of others due to a lack of time. If he generates legal moves that's fine. Sounds like a waste of time, but that's a different matter.

Perft has become quite distorted over the years. It was originally defined as "legal moves only, made _and_ unmade". This includes a _full_ make/unmake, not some stripped-down version, no hashed totals, just a tree-walk of legal moves to a fixed depth doing whatever you do for a normal search.

Somehow that has become badly corrupted...

No

This is not correct.

Sorry, but you don't get to redefine something _I_ defined first. Perft was designed with two goals. (1) enumerate a tree of legal moves to a fixed depth; (2) test performance (hence the name "perf from performance, and t from time) by measuring move generation and make/unmake speed. Full make/unmake, whatever it is you do in your actual program is what was intended to be done here.

The nonsense about hashing values and so forth is an OK experiment to try, but it is _not_ "perft" as I originally defined it back around 1988 in Cray Blitz, although nobody really paid any attention until after Crafty came along where it became a good move-generator test for correctness.

But that is _exactly_ what it was defined as being, not what it is getting twisted into today...


'quote]
Perft is simply a function to calculate the number of possible games with n moves.

It can be used as a tool to debug the move generator but it is not the only use.

Even if you do not make the last ply then it is still useful as debugging tool for the move generator because you clearly need to make moves earlier and if you have bugs in your makemove function then you will not get correct results.[/quote]

You can call that whatever you want, but it isn't "perft".

It can be also useful to debug your hash tables because if you have hash collisions because of bad numbers in the hash and use perft with hash then you are not going to get correct numbers.

Uri

The chances of that are almost zero. 10 plies is not enough to reach significant hash collisions unless your code is broken badly enough that the program won't run, and then perft is not the way to debug that at all.

[bob]

How do you weed out the _other_ illegal moves? perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea. And the idea was that a perft total counts _only_ legal moves. If you do as you say, you will make illegal moves at the last ply when a piece is pinned on your own king...

Such moves are not generated. It is far faster not to generate such moves in the first place, than generate them, and subsequently having to test _every_ move for not being pinned to the King. So you benefit in 3 ways: It saves the time of both generating _and_ testing illegal moves, and it saves on testing the legal moves.

I don't test for pinned anywhere. it is just something that works out easily when using bitboards... I certainly would not want to do this generating captures since it is a waste of time in the q-search... Making a capture with an absolute-pinned piece is a _low_ frequency event...

Perft has become quite distorted over the years. It was originally defined as "legal moves only, made _and_ unmade". This includes a _full_ make/unmake, not some stripped-down version, no hashed totals, just a tree-walk of legal moves to a fixed depth doing whatever you do for a normal search.

Somehow that has become badly corrupted...

I see it more as being credited for its full potential...

As Uri already pointed out, the numbers themselves are immensely useful for debugging move generation and tree walk. And usually only deep searches are able to set up the rare occasions that suffer from bugs. So obtaining the numbers is a non-negligible effort, and not obtaining in the most efficient way possible would be madness. Not making the moves unnecessarily saves about a factor 2, hashing on a deep perft might save you another factor 10..

Fine. But let me _again_ point out. "perft". "performance test". Originally defined in Cray Blitz, and then in Crafty in 1995. It was originally used after Crafty was originally released, as a way for others to (a) test move generator for correctness (it is easy to screw up en passant captures, promotions, etc) and (b) a way to measure the speed of the move generator and make/unmake code which also tests the data structures for efficiency as well.

Comparing two programs that do the computations differently is useless when time is measured... Yet everyone is doing that and it is wrong.

And, like I said, engines usually don't make the moves they generate in the end-leaves either. So for timing an engine under construction, Make / UnMake of the last ply would invite you to make completely wrong and counterproductive 'optimizations'.

Eh? Why don't you make/unmake moves in the last ply? I do, unless there are none generated to make...

[bob]

I agree with H.G.. If Perft (Performance Test) is done to validate a move generator's true performance, it should be done under realistic circumstances. That is to make use not only of the existence of a move but of all related necessary properties, e.g. if it would be a check threat or castling etc. - thus to prove that ability, it seems to be necessary to also provide statistics about that kind of information. SMIRF has done such a thing as an example, avoiding best move count results by intention, but providing a lot of move related information.

Reinhard.

I don't see how HG said what you are supposedly agreeing with. Many programs hash the move counts. We don't do that in a _real_ search. I make moves and unmake them in the last ply of search, unless I don't generate any moves in the first place and just return the static eval.

None of that makes any sense to me in the context of a "real search"...

[bob]

perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea.

Wow, I did not know that. Can you please finally lift the secret that everyone wants to know: What does "perft" actually stand for??

"performance test"... shortened to perft ala' unix...

[bob]

Almost none (with material + piece-square table differential eval only).

But you count nodes differently, of course. The perft(6) (without Make/UnMake) you would count as a 5-ply search, with 486k nodes. The 6th ply would merely be concluding that none of the generated moves is worth searching (i.e. not a capture, or futile).

Again I don't follow. Perft has _nothing_ to do with an alpha/beta search. There are no cutoffs. No evaluations. no extensions. No hashing. No repetitions. No 50-move rule and other drawing conditions. My move generation and make/unmake generally take less than 15% of the total search time when profiled... So the speed of perft doesn't even relate to the speed of the chess engine.

[hgm]

OK. I did not look at his code and generally do not look at code of others due to a lack of time.

This policy apparrently also applies to what people post here...

If he generates legal moves that's fine. Sounds like a waste of time, but that's a different matter.

... as it was clearly explained above that it actually saves a lot of time, and that it is the generation of such illegal moves that is a big time waster.

Sorry, but you don't get to redefine something _I_ defined first. Perft was designed with two goals. (1) enumerate a tree of legal moves to a fixed depth; (2) test performance (hence the name "perf from performance, and t from time) by measuring move generation and make/unmake speed. Full make/unmake, whatever it is you do in your actual program is what was intended to be done here.

Not redefine. Just implement it better. They want to test the performance of their engine, and thus they do the performance test to mimic the behavior of their engine as closely as possible. But it is still a performance test, as it fulfills exactly the functions you defined.

Fine. But let me _again_ point out. "perft". "performance test". Originally defined in Cray Blitz, and then in Crafty in 1995. It was originally used after Crafty was originally released, as a way for others to (a) test move generator for correctness (it is easy to screw up en passant captures, promotions, etc) and (b) a way to measure the speed of the move generator and make/unmake code which also tests the data structures for efficiency as well.

Comparing two programs that do the computations differently is useless when time is measured... Yet everyone is doing that and it is wrong.

Unless, of course, the programs that are being compared are doing it the same way. Then it doesn't matter so much which way this is.

Everyone is well aware of this, and this is why we always report if we are making the last ply, hashing counts, classifying moves, detecting checks...

And, like I said, engines usually don't make the moves they generate in the end-leaves either. So for timing an engine under construction, Make / UnMake of the last ply would invite you to make completely wrong and counterproductive 'optimizations'.

Eh? Why don't you make/unmake moves in the last ply? I do, unless there are none generated to make...

How do you know there are none generated to make? Wouldn't that be by running your move generator? I was under the impression that Crafty would not search bad captures in end leaves. So you must generate the captures, in order to subject them to see, and then _not_ make them...

Again I don't follow. Perft has _nothing_ to do with an alpha/beta search.

They are both tree walks. So "nothing" must be a relative notion here...

There are no cutoffs. No evaluations. no extensions. No hashing. No repetitions. No 50-move rule and other drawing conditions. My move generation and make/unmake generally take less than 15% of the total search time when profiled... So the speed of perft doesn't even relate to the speed of the chess engine.

None of the tasks you mention takes significant time. Except the hashing, but as you must have figured by now we already did this in the perft we were comparing with. And, knowing how much you value purity of the terms used, most of them really don't have anything to do with alpha-beta.

[nczempin]

perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea.

Wow, I did not know that. Can you please finally lift the secret that everyone wants to know: What does "perft" actually stand for??

"performance test"... shortened to perft ala' unix...

Well, that's what I always thought. But I remember that a while ago someone somewhere (sorry) asked where it came from, and no-one had a clue. Good that we know now.


I use it mainly to test the correctness of the move generation, so for that aspect the name is a bit misleading.

[smrf]

I agree with H.G.. If Perft (Performance Test) is done to validate a move generator's true performance, it should be done under realistic circumstances. That is to make use not only of the existence of a move but of all related necessary properties, e.g. if it would be a check threat or castling etc. - thus to prove that ability, it seems to be necessary to also provide statistics about that kind of information. SMIRF has done such a thing as an example, avoiding best move count results by intention, but providing a lot of move related information.

Reinhard.

I don't see how HG said what you are supposedly agreeing with. Many programs hash the move counts. We don't do that in a _real_ search. I make moves and unmake them in the last ply of search, unless I don't generate any moves in the first place and just return the static eval.

None of that makes any sense to me in the context of a "real search"...

This is strange to me. Even when a (that way) fast move generator has only a very small influence on an engine's final speed, it is a signifcant indicator for the usability of the move's themselves including their bundled information and thus also for the quality of the underlaying data structure. This is even more important if the tested move generator has been developed for a more abstract target, that is to generate moves for different geometries and piece sets like done in ChessV or SMIRF, where e.g. 8x8 and 10x8 Chess variants ar supported by unique move generators.

Reinhard.