TalkChess.com

Robert Pope wrote:

jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon

But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.

With a 64 bit key validation is not really necessary.

I have a move validation routine which I only use when I want to check if my transposition table is not malfunctioning.
Sometimes I let it run for an hour or so, and it never detects a single invalid move, and this is in a multithreaded search.
To be 100% on the save side you can of course make sure that an invalid move won't crash your engine.

Dann Corbit wrote:Was it the advice that was bad or the implementation of the advice?

Now, bitboards can be quite unnatural when you are not used to them yet.
But in the long run, I think that the advice was very good.
I guess that if you take your time and work through the issues, eventually you will be glad that you switched.

Look at the top ten on this list:
http://www.computerchess.org.uk/ccrl/4040/

Guess which of them are bitboard engines...
Answer:
All of them.

It's not a coincidence.

It is also true that array based engines can be very strong. But for 64 bit CPUs and 64 bit operating systems, bitboards are better.

Are you talking about using bitboards for move generation or bitboards for evaluation ? No need to tell me that bitboards are fine for detecting passed pawns.

Using bitboards for move generation was at least one month of misery with these stupid bit shifts that always shifted to the wrong direction.

Henk wrote:

Dann Corbit wrote:Was it the advice that was bad or the implementation of the advice?

Now, bitboards can be quite unnatural when you are not used to them yet.
But in the long run, I think that the advice was very good.
I guess that if you take your time and work through the issues, eventually you will be glad that you switched.

Look at the top ten on this list:
http://www.computerchess.org.uk/ccrl/4040/

Guess which of them are bitboard engines...
Answer:
All of them.

It's not a coincidence.

It is also true that array based engines can be very strong. But for 64 bit CPUs and 64 bit operating systems, bitboards are better.

Are you talking about using bitboards for move generation or bitboards for evaluation ? No need to tell me that bitboards are fine for detecting passed pawns.

Using bitboards for move generation was at least one month of misery with these stupid bit shifts that always shifted to the wrong direction.

The advantage of bitboards is mostly in evaluation.
Direction of shift will be wrong if you number your bits differently than the intention of the bitmap.

For instance, if you have a1 as bit 0 or bit a8 as zero, the math will clearly be different.

It seems that everyone is using magic bitboards now, which are even stranger looking than rotated bitboards. But since it is a perfect hash function, it is not surprising that it looks a little odd. Perfect hash functions always look a little odd, since you have to finagle the hash to have a distinct value for every known input. So the advice for perfect hash routines is to use an existing generator and just verify that the routines work and then use them (with proper credit as due, of course).

Joost Buijs wrote:

Robert Pope wrote:

jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon

But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.

With a 64 bit key validation is not really necessary.

I have a move validation routine which I only use when I want to check if my transposition table is not malfunctioning.
Sometimes I let it run for an hour or so, and it never detects a single invalid move, and this is in a multithreaded search.
To be 100% on the save side you can of course make sure that an invalid move won't crash your engine.

You HAVE to have collisions. No way to compress all possible chess positions into 64 bits. So collisions will happen. If they can crash your engine or corrupt things, a legality check is required.

bob wrote:

Joost Buijs wrote:

Robert Pope wrote:

jdart wrote:Nobody should be doing 1). If you have a hash table, you probe it first, before movegen. That is not complicated.

--Jon

But how do you know the probe returned a legal move? Stronger engines will have special validation routines, but younger engines often do a movegen and then see if the probe is in the movelist.

With a 64 bit key validation is not really necessary.

I have a move validation routine which I only use when I want to check if my transposition table is not malfunctioning.
Sometimes I let it run for an hour or so, and it never detects a single invalid move, and this is in a multithreaded search.
To be 100% on the save side you can of course make sure that an invalid move won't crash your engine.

You HAVE to have collisions. No way to compress all possible chess positions into 64 bits. So collisions will happen. If they can crash your engine or corrupt things, a legality check is required.

Of course you will have collisions, but with a 64 bit key they occur so infrequently that the chance they will alter the outcome of the search is virtually zero.
When your engine is susceptible to crash or corrupt things on an invalid move it can be a problem, however you don't need a full legality check to solve this.

To check again i just let my engine run on 16 threads for over two hours with the move validation routine enabled and it didn't find a single invalid move from the transposition table.
This doesn't mean that there were no collisions though, it is possible that there are different positions mapping to the same key where the same stored move is valid.

The frequency of collisions is so low that they are almost undetectable.
When you see a higher number of collisions it probably means a bug or a race condition in the transposition table code.

Anyways I don't think this is something to worry about.

I just make sure that the engine does not crash, no matter what move it finds in the hash table. If it wants to capture an own piece with an empty square? Fine, why would that be a problem? Just do it. The only extra code I needed was when MakeMove performs a castling. Then I also have to save and restore the piece that was captured by the Rook (or by whatever was standing on the square where the Rook was expected). As castlings are rare, the overhead is immesurably small.

More dirty is that in my younger engines, when the hash move fails low, I don't even bother to remove it from the move list after generation. Just search it again. This should be a guaranteed hash hit to an already cached hash entry, and the involved overhead could even be smaller than having to check for every move if it happens to be the already-searched hash move (in order to skip it). If you program it cleverly you can do key calculation and hash probe even before MakeMove(), so that you can skip the Make/recursion/UnMake. Just like you would when the move created a repetition (which you would check even before the hash probe).

hgm wrote:I just make sure that the engine does not crash, no matter what move it finds in the hash table. If it wants to capture an own piece with an empty square? Fine, why would that be a problem? Just do it.

From a professional software developer's point of view that is horrible
Imho code must be correct.

flok wrote:

hgm wrote:I just make sure that the engine does not crash, no matter what move it finds in the hash table. If it wants to capture an own piece with an empty square? Fine, why would that be a problem? Just do it.

From a professional software developer's point of view that is horrible
Imho code must be correct.

If you are professional software developer and you do chess programming you probably first have to write a zillion test cases. Not much fun.

bob wrote:You HAVE to have collisions. No way to compress all possible chess positions into 64 bits. So collisions will happen. If they can crash your engine or corrupt things, a legality check is required.

Assuming you mean "false positives", then such could indeed crash an engine which didn't use a validity test.

UNLESS the probability of a false positive is much less than the probability of error due to random cosmic ray impact. In Symbolic and Oscar, the transposition table entries all use 128 bit signatures -- and so there is no validity test. Yes, this eats space. But it also reduces time as no post-fetch test needs to be run. Further, a post-fetch test works only if a move is fetched and not just a score or a node count.