Key collision handling

[Zlaire]

How many moves per node on average you try ? 5, 10 or 15 ?

For me, > 25% of positions have a hash move. For the normal program, I'd expect it to be over 10% for LOWER position hits.

You're referring to the same occurrence as "very common" and "very rarely".

I guess it's in the eye of the beholder.

I can measure it to get exact numbers if you are curious...

The ratio of validation cost + validation occurrence / expected key collision hit and would be an interesting number.

But I guess that would have to be weighed against pretty much losing a game with the lack of validation for every collision.

[hgm]

You should distinguish length of the hash key, and length of the part of it that is stored in the TT (the signature). With a 32 bit signature, every hash probe has a 1 in 2^32 = 1/4G probability of accidentally matching the stored signature. So if you search 1Mnps it will happen once every hour or so. (How many games that is depends on your TC.) Not every accidental hit might contain an illegal move, and not every illegal move will make you crash.

You can store more bits to reduce the probablilty, but this will also cause a slowdown, and an effectively smaller has table.

The best solution would be to make sure the engine does never crash, no matter how illegal the move is. E.g. in Spartacus' MakeMove castling also saves the piece that is captured by the Rook, to restore it on UnMake, just in case. It is not even clear if this would always cost anything, in terms of performance. E.g. if the problem is that moving an empty square causes a crash because pos[EMPTY] or pieceValue[EMPTY] are out of bounds for those arrays, just enlarge the arrays so that it gets within bounds. If it unconditionally uses pos[KING] as a square number, which is again used as an index of a mailbox board or in a table of bitboards, just define the value you use for pos[piece] in the piece list to indicate a piece is captured such that it does map into an extension of the board or table where it retrieves something harmless. Then you will be resistent to the King being captured.

[bob]

How many moves per node on average you try ? 5, 10 or 15 ?

For me, > 25% of positions have a hash move. For the normal program, I'd expect it to be over 10% for LOWER position hits.

You're referring to the same occurrence as "very common" and "very rarely".

I guess it's in the eye of the beholder.

I can measure it to get exact numbers if you are curious...

The ratio of validation cost + validation occurrence / expected key collision hit and would be an interesting number.

But I guess that would have to be weighed against pretty much losing a game with the lack of validation for every collision.

In my code, a bad move can cause problems. For example, pull a o-o move out of its hat and play it after it has already castled, and I can end up with 2 kings. Since I don't do copy-make, but rather use make/unmake, I'd be dead at that point. Hence I have to validate any move before playing it (I don't care about being in check sort of legality, I can deal with that easily, I am talking about moving a piece that is not actually on the square, so that when I make the move, I "create" the piece, and when I unmake the move, the piece goes back to where I thought it was, (but it really was not there))...

[Desperado]

In Stockfish we validate and check for legality the TT move before to try it.

Isn't that costly for something that happens very rarely?

I guess my approach of researching on exception fails on the fact that not every illegal move is guaranteed to trigger an exception, so some (most) of the time the engine gets the move completely messed up.

But still, if you get it once every 1000 games (which seems like a lot, even with smp), it means you unnecessarily slow the engine down the other 999.

Hello Jonatan,

*
i bet there are countless places where you can speedup,optimize your
engine much more significant than at this point.

*
optimizing for the costs of misbehaviour will give you hard times
when debugging your algorithms

*
optimizing for the costs of basic functionality (to risk crashes...),
should at least double your speed , which it certainly doesnt do!
So, basic functionality should never be traded for anything (imho).

*
Really, the best thing you can do is to always validate not-generated
moves (transmoves,killers...) against the current board and
check them for legality.

cheers, Michael

[sje]

A 32 bit hash may be suitable for repetition detection, but not for much else. I use a 128 bit hash in Symbolic's big-perft mode and have seen less than a two percent slowdown vs a 64 bit hash. (I'd recommend the 64 bit hash for most purposes.)

Also, it can be a good idea to have a heavily optimized, legal moves only move generator, even if this costs more time for execute/retract operations. The idea is to generate all of the moves at each full width node and then scan these for matches for the PV moves, transposition moves, killers, etc. This simplifies the move ordering code and also ensures that a false positive match will never crash the program because the program can never select an illegal move from the list. Note that at all of the ALL-flavor nodes, all of the moves have to be generated anyway while at the CUT-flavor nodes, a good move ordering is needed (so all the moves should be present). This also gives faster checkmate and stalemate detection.

[hgm]

Well, for search (rather than perft) in practice a 10-bit signature might already be good enough...

[Evert]

Also, it can be a good idea to have a heavily optimized, legal moves only move generator, even if this costs more time for execute/retract operations. The idea is to generate all of the moves at each full width node and then scan these for matches for the PV moves, transposition moves, killers, etc. This simplifies the move ordering code and also ensures that a false positive match will never crash the program because the program can never select an illegal move from the list.

Note that you don't actually need a legal move generator for that, pseudo-legal will do just fine. I do this in Jazz (in in Sjaak, in fact).

[hgm]

Also, it can be a good idea to have a heavily optimized, legal moves only move generator, even if this costs more time for execute/retract operations. The idea is to generate all of the moves at each full width node and then scan these for matches for the PV moves, transposition moves, killers, etc. This simplifies the move ordering code and also ensures that a false positive match will never crash the program because the program can never select an illegal move from the list.

Note that you don't actually need a legal move generator for that, pseudo-legal will do just fine. I do this in Jazz (in in Sjaak, in fact).

Indeed, I do that in HaQiKi D too. It should always be harmless to play something the move generator would generate, or youwould crash very quickly indeed even without hash or killers.

It takes a lot of time to scan the move list, though, and move-gen time was wasted when the hash move produces a cutoff (as it usually does). So in Spartacus I play the hash move before generating anything, and the only test I do on its validity is to check that there is a piece of myself on the from-square. Because collissions are so rare that is good enough. Killers eedmuchmore testing, though; I do make sure that they are pseudo-legal and non-captures non-major promotions. (This produced a terrible bug when I changed the move encoding for special moves, because double-pushes are considered special; after the change the double-pushes were no longer tested for being non-captures, and as double-pushes are frequently killers this gave rise to lots of phantom lines in the tree, where the 'killer' killed very efficiently indeed...)

[tpetzke]

Hi Jonatan,

I'm surprised it takes a 1000 games to see a collision with 32 bit. I once used a hashing with 40 bits for a special hashing in qSearch. I used the lower 20 bits of the 64 bit key to address the cache slot and in the slot I saved the 20 upper bits of the 64 bit key for verification.

I had a collision in almost every game when I measured. Not every game crashed, sometimes I was lucky and the collision produced a hash move that was accidentally legal.

I did not have any problems with the main hash table and a 64 bit signature even without legal check of the move. I added it anyway because it felt right.

Thomas...

[hgm]

Well, with 20 bit signature you expect a collission every 1 million probes. Even more if you look into more entries for 1 probe. So that would be more than 1/sec. But the point is how likely it is a wrong hash move would crash your program. If illegal moves per se are no problem (and why would they, e.g. if I move a Bishop from f1 to f4, who cares?), but you only crash when the King gets captured, the chances are quite low. Because not many hash moves in the tree will move to squares around the opponent King.