Can someone explain what advantage there is to...

[bob]

Not sure why you would need a TT to calculate perft, but if you do need one, perft(8) has ~40% chance of having a collision with a 64-bit key. Perft(13) will have a collision rate of about 0.1. Having 10% of your entries over-written doesn't sound like a usable system to me!

I don't think that is correctly calculated. That you have a key collision somewhere inside the tree is irrelevant if the two colliding positions would never try to be in the hash table at the same time. Which they wouldn't, if your hash table is far smaller than the number of unique positions in the tree.

But it is obvious that perft is a much more demanding task than minimax. The mininmax result is unlikely to be affected even if 0.1% of the hash probes returns a result from a wrong position, according to Bob Hyatt. A perft result would already be wrong if there is a single mixup anywhere in the tree.

I think the important factors for collisions in a TT are the key size and the number of entries stored. These factor along with the quality of the hash function are what is important.

I think a collision rate for 10% is too high even for minimax trees. I think Bob would agree if you ask him. My personal choice is that 10^-5 is about the limit. Collisions more often than this are likely to change moves often enough to impact the programs rating. I would note that just because a collision has occurred isn't an indication that this will have any effect on the program. For this to effect it's execution it must first be accessed, then be of the proper depth, within bounds, and contain a legal move. Even then there is no guarantee that it will affect the move. But if it happens often enough, eventually it will. Then the programs performance will begin to degrade.

Your right, perft() is much more demanding. It demands perfection if I understand its purpose. Which makes me wonder why anyone would use a hash function. They, by definitions, can return inaccurate data. It would be much better to store the data in an unambiguous form.

Regards,

Zen

All I can say is that there is theory and there is reality. In reality, a program can withstand a very large rate of actual false matches. But in theory, it "feels wrong" to allow this to grow beyond the level that one can provide with 64 bit signatures...

But it is nice to know that even if you somehow break something, it likely won't hurt anything but some efficiency points...

So far as I know, perft was something that I added to Crafty back in 1995, as a method for debugging the bit board stuff when I started. I intended it to be nothing more than a simple sanity check when I made a significant move generator change. I then modified it to be a more general debugging tool that included a simple depth-first fixed-depth search that would walk a tree to a specific depth and sum the nodes. It worked quite well. I then began to use it to tweak performance, but my usage was solely to improve the speed of Make()/Unmake()/GenerateMoves(). If I improved the perft speed, the program would be stronger.

But as the word spread, others took it as a challenge to beat Crafty's perft speeds, for whatever reason. But not just by having a faster move generator or a faster make/unmake, but by resorting to other performance tweaks like hashing to avoid walking the same part of the generated tree more than once. I never got into this aspect of this, and don't begin to claim that I was the first to use this. I was the first that I knew of, however. And when I released the Crafty source back in 1995, it generated a lot of buzz (the perft idea) and spawned development of positions that produced the largest trees with the shallowest tree (an ICC member KiwiPete had one of the best-known positions that fit this description.) But the bottom line is all the hashing and stuff really is a pointless optimization of a not very useful debugging tool that I have not used myself in a LONG time... Even though the code has always been in Crafty..

Nice story! Amazing how things take on a life of their own isn't it! I'm sure it could still server the purpose you wrote if for should you decide to change the move generator in the future. In the mean time I was wondering, which version of crafty has the fastest move generator? The reason I was wondering was I was thinking about a modified MC play-out. I know there hasn't been much success with this in chess due to it's highly tactical nature but I had a few idea's that I though might change this situation and a very fast move generator wouldn't hurt in this regard. Also has anyone tried an incrementally updating move generator to increase speed?

Regards,

Forrest

The move generator speed has not changed in something like 20 years now, in terms of speed. Rotated bit boards in 1996 or so was a definite boost. I didn't find any speedup when I converted to magic a few years ago, just a very slightly faster Make/Unmake time due to the elimination of the rotated bit boards, but the generation was slightly slower due to the really large table lookups. The newer the Crafty version, however, the faster the overall search is as it has been slowly optimized for speed over the years...

[syzygy]

For key mod p to work well, it's not necessary that p be prime. But p should be odd (and so coprime with 2^N) so that all N bits of the key get a chance to contribute to the entry address generation.

Why should p be odd? In most chess engines p is a power of 2 and that works just fine. It has the benefit that key mod p is very easy and cheap to compute.

[hgm]

The point is of course that there is no advantage in having all bits contribute to the address. The Zobrist method causes a nice homogeneous distriution of keys, so you will never get in a situation where you have a large number of different keys that happen to be all the same in the bits that you use for deriving the index, and differ only in signature. Things like that are only important if you would have a simplistic primary key, e.g. a concatenation of square numbers (if there were only 10 pieces on an 8x8 board and a 64-bit key). What is important is that changing the occupant of every square contributes to every bit of the index, and Zobrist hashing nicely takes care of that.

In fact it is very advantageous to have not all bits contribute, because you can then intentionally focus accesses into the same bucket. E.g. most people use a stm key that does not affect the bucket index, so that after null move you have a guaranteed cache hit during the hash probe.

[AlvaroBegue]

For key mod p to work well, it's not necessary that p be prime. But p should be odd (and so coprime with 2^N) so that all N bits of the key get a chance to contribute to the entry address generation.

Why should p be odd? In most chess engines p is a power of 2 and that works just fine. It has the benefit that key mod p is very easy and cheap to compute.

Using a prime p or an odd p are attempts at hiding the deficiencies of the hash function. If you have a decent hash function, you can use any table size you like. I use powers of 2 myself.

[sje]

The point is of course that there is no advantage in having all bits contribute to the address. The Zobrist method causes a nice homogeneous distriution of keys, so you will never get in a situation where you have a large number of different keys that happen to be all the same in the bits that you use for deriving the index, and differ only in signature. Things like that are only important if you would have a simplistic primary key, e.g. a concatenation of square numbers (if there were only 10 pieces on an 8x8 board and a 64-bit key). What is important is that changing the occupant of every square contributes to every bit of the index, and Zobrist hashing nicely takes care of that.

While unlikely, it is still possible to have unwanted cross-key correlation for a given bit position. Maybe several bit positions. Having correlated positions reduces dispersion, a bad thing. But using key mod p with coprime(p, 2^N) is guaranteed to take advantage of all non correlated bit positions, not just those in an M bit (M < N) mask.

Consider the case where p in key mod p has one or more factors of two. Each such factor effectively tosses away a bit in key. And this reduces dispersal, which is not what you want.

[sje]

Further testing has again shown no measurable difference between masking and modulus. In all cases, the time taken by accessing uncached memory overwhelms the time taken by generating element addresses.

That being said, there are still some advantages to have the transposition table length be a power of two. First, it may be simpler to specify as a command line argument as is done with Oscar. Second, it makes it simpler to divide the table into spinlocked regions for multithreaded access.

The big advantage of using key mod p is that allows tuning the table size for better utilization of available memory. This is perhaps not too important in a chess program where doubling the table entry count adds usually less than 10 elo strength. But with perft(), there can be significant differences in running time with relatively smaller table entry count adjustments.