Perft search speed bottleneck

[Patrice Duhamel]

hashmove: If a probe of the transposition table finds a hashmove, it is played and searched immediately before generating any moves; a hashmove is always valid.

I don't understand why the hashmove should be always valid ?

I'm testing the validity of the hashmove,
and killers because I try them before generating non capture moves.

Thanks.

[elcabesa]

hashmove: If a probe of the transposition table finds a hashmove, it is played and searched immediately before generating any moves; a hashmove is always valid.

I don't understand why the hashmove should be always valid ?

I'm testing the validity of the hashmove,
and killers because I try them before generating non capture moves.

Thanks.

hash move is saved only if it's legal so it shall be legal for the position when you probe it.
if it's not legal you had a hashkey collision but i think it should be a rare event

[Chan Rasjid]

Illegal moves that leave one's own king open to slider attack is not rare. I measured it. In late-middle or endgame, the percentage of illegal psuedo-legal moves may be 30/40%.

Then you were not using a dedicated evasion generator when in check.

I now have these confirmed these figures.

[d]r4k2/pp2qn1Q/n4b2/8/2B4p/5N1P/Pp3PPB/3R2K1 b - - 4 29

I compare the ratio of skip invalid moves over the number of valid moves searched, but only for non-qs nodes where there was a full generation/evasion.

It is 34.5% in the position above for a search to depth 5.

For the next 20 moves, the % were all mainly above 20% and some reaches 50%.

Best Regards,
Rasjid.

[syzygy]

hashmove: If a probe of the transposition table finds a hashmove, it is played and searched immediately before generating any moves; a hashmove is always valid.

I don't understand why the hashmove should be always valid ?

I'm testing the validity of the hashmove,
and killers because I try them before generating non capture moves.

Thanks.

hash move is saved only if it's legal so it shall be legal for the position when you probe it.
if it's not legal you had a hashkey collision but i think it should be a rare event

Collisions should be rare, but they do happen. If the validity of the hash move is not tested, you don't know if your program crashed due to a rare collision (which you will have to accept) or due to another kind of bug that you might want to fix.

[hgm]

But testing the validity of the hash move is a needlessly expensive fix for that. Usually it is much cheaper to make sure your engine cannot crash no matter what (from, to) pair you offer to MakeMove(). That once every 4 billion tree nodes it does something crazy won't result in any measurable effects.

Even testing if the from-square contains a piece of the side-to-move (or, indeed, any piece at all) is usually not needed. For safety I usually do remember what a Rook (or whatever happened to be in the corner) captured during castling, and restore it on UnMake(). That slows down castling a little (these are rare anyway), but still less than when I would have to test if they were legal.

What is usually more of a worry for me is whether the hash move delivers check. If I don't pass that information with the hash move, a checking hash move might not be extended.

[Chan Rasjid]

But testing the validity of the hash move is a needlessly expensive fix for that. Usually it is much cheaper to make sure your engine cannot crash no matter what (from, to) pair you offer to MakeMove(). That once every 4 billion tree nodes it does something crazy won't result in any measurable effects.

Even testing if the from-square contains a piece of the side-to-move (or, indeed, any piece at all) is usually not needed. For safety I usually do remember what a Rook (or whatever happened to be in the corner) captured during castling, and restore it on UnMake(). That slows down castling a little (these are rare anyway), but still less than when I would have to test if they were legal.

What is usually more of a worry for me is whether the hash move delivers check. If I don't pass that information with the hash move, a checking hash move might not be extended.

There you are!

The great authors of Ippolit, komodo have considered every possibility and leave the 16th bit of their move integer unused.

After a move is make() and the check info is available, this bit is set to mark a check move and would be saved in the TT if we save at least 16 bits.

Rasjid.

[syzygy]

But testing the validity of the hash move is a needlessly expensive fix for that. Usually it is much cheaper to make sure your engine cannot crash no matter what (from, to) pair you offer to MakeMove().

Whether that is cheaper depends on board and move representation and MakeMove() implementation. But I agree this is also a possibility.

[Sven]

I compare the ratio of skip invalid moves over the number of valid moves searched, but only for non-qs nodes where there was a full generation/evasion.

It is 34.5% in the position above for a search to depth 5.

I get 3.1% with my current engine. I also have kind of a "toy engine" that has no dedicated evasion generator. There I get about 55% illegal moves for the same position in full-width search nodes to depth 5.

I calculate "illegal moves / (legal moves + illegal moves)". If you want "illegal moves / legal moves" then my numbers would be about 3.2% and 122%.

You did not reply to Ronald's remark yet, so may I ask again: does your engine use an evasion generator for all positions where the moving side is in check? From your numbers it seems it doesn't.

Sven

[JarvisXerxes]

If the knight is pinned (pinned being a precalc bitboard that you will need later anyway), then just '&' this with the "pin ray' (the line between king and the knight, that the knight must stay on). Or you can go the pseudo-legal route and code a (complicated) function that determines if a pseudo=-legal move is legel *without* playing it.

the example is not so right. a pinned rook, queen bishop or pawn can moe only in the pin ray direction but a pinned knight can't move, it's even simpler.
if you have a pinned knight you can avoid to calculate his movement.

These are all sound advice. Thanks.
I did do some of the suggested optimizations, and apparently the speed is tripled. I guess I'm done with perft and need to move on to alpha-beta asap.

[syzygy]

I've now experimented a bit with efficiently checking legality before making the move, but I am still losing nps compared to simply playing/testing/undoing. My perft speed has gone through the roof, but that does not buy me anything useful.

With some more effort I finally got the "checking legality before making the move"-scheme slightly faster than my old play/test/undo scheme. I suspect though that some of the optimisations I found can also be applied to my old implementation.

I then went on to implement a full legal move generator. The pinned pieces part can be done quite efficiently, but when implementing the generation of legal king moves I became convinced that this scheme would be of no help for alpha/beta search.

To my surprise, the legal move generator does increase nps during alpha/beta...

I don't think going from pseudo-legal to legal should be high on anybody's list, but well, it is an interesting exercise.

My perft now beats hgm's qperft on my machine (12.31s vs 15.19s for perft 7 and 336.25s vs 410.49s for perft 8). Before switching to full legal move generation, my perft was still a bit slower.

My checks generator still only generates pseudo-legal moves, so those still have to be checked in my select_move().

It might be that I could get a further speed up by generating pseudo-legal king moves.