Can someone explain what advantage there is to...

[sje]

Just a single test run can be more revealing than a thousand prognostications.

A expected, Oscar says that using modulus vs masking has no measurable effect on running time.

Like a small insect which falls into a big boiling stew pot, the effect of an extra modulus/division is "lost in the sauce" when looking at the big picture. Any modern CPU which costs more than a bottle of 80 proof Old Rot-Gut will find something productive to do while waiting for a pipeline to squeeze out a quotient.

[Zenmastur]

Symbolic's default book has 481,583 entries.

Hmmm...

Sounds like a pretty loose book to me but this is off topic so...

Collisions happen all the time. They aren't much of a problem. False positive matches can be a problem, and this problem is greatly mitigated by long signatures. Symbolic (and Oscar) use 128 bit signatures, and this drives the probability of a false positive to practically nothing.

Collisions happen all the time. They aren't much of a problem and yet you seem to go to a rather extreme measure to avoid them.

First, are we talking about a chess playing program or a perft program or both or a single program that has both capabilities.

Next, I'm wondering which is the case:

A.) Collisions happen all the time and aren't much of a problem.

or

B.) You use 128 signatures.

I doubt that both A and B can be true with current hardware since in order to have a 40% chance of having one collision in a TT with a 128-bit key (i.e. collision rate of ~2e-20) implies you are storing at least 128 Exabytes. Seems improbable to me.

Sounds to me like you should do more research before you begin coding!

The use of a prime is a tradition first employed with the idea that a relatively large prime is unlikely to accidentally be a dominating factor of the signature generation function.

http://stackoverflow.com/questions/1145 ... er-modulus

That's fine if you are using a polynomial hashing function. I doubt that it will have a significant effect when using Zorbist keys. In fact, I think that I can show that a composite with many factors but only two different prime factors will work just fine. i.e. P1^n*P2 where P1=2 and P2 > sqrt(modulas)

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.

How do you get those numbers?

I looked them up in a table. The first table uses the formula 1-EXP(-Q^2/(2*P)) if I recall. Not sure of the formula used for the second table.

Having 10% of your entries over-written doesn't sound like a usable system to me!

Why?

Because 10% of the entries have a 50% chance (or greater) of returning the wrong data.

Regards,

Forrest

[sje]

You need to first understand the difference between the terms collision and false positive.

A collision is when two or more different keys map onto the same table address.

A false positive is when a probe of the table returns an entry with a matching key but the match is erroneous because of the same key mapping onto two different sets of data.

[hgm]

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.

[Volker Annuss]

Divisions take some 30 clock cycles, compared to 1-3 for shifts and multiplies. And this is not only latency, but even the throughput is only 1 per 30 cycles, as the divide unit is not pipelined.

But I guess you could pre-calculate (1<<N)/size, so that you can do the modulo as key - ((((1<<N)/size)*key)>>N)*size with sufficiently large N to not lose precision.

I would be surprised if an optimizer would be smart enough to do that, though, if you just write key%size.

Just do

Code: Select all

((key >> 32) * size) >> 32

[Zenmastur]

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

[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..

[Zenmastur]

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

[tpetzke]

perft is a very nice debugging mechanism. I'm sure it helped a lot of developers to fix their move generators.

Those are complicated and I'm almost certain that you can't write a bug-free one from scratch without such a test method.

I do have an option in iCE to also my transposition table to hash results from sub trees. The main purpose of it is not to speed up perft (which it does as a side effect) but a quick sanity check for my transposition table. Do I get the correct numbers out that I'm putting in.

[Evert]

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..

While I've only ever used perft as a debugging tool (although the starting position is a very poor one to use for that, so I have specific positions for different aspects of the move generator), I don't think that's what people who take up the challenge of writing very fast perft-generators are primarily interested in (certainly not people who try to calculate perft(10) or larger). Rather, they're interested in a very different question: how many positions are reachable in N moves, starting from the starting position? Not something I've ever wondered about myself (I find the number of unique positions a bit more interesting), but if it amuses someone to work that out, good for them.