Little bug Glaurung

[Rubinus]

Is missing randomize value for books in start engine! -> Engine plays identical variants!
for ph-book.bin:
white 1.e4 -> Ruy Lopez 5.d4
black 1.e4 d6 or Slav-Merano
If new game, then book variable, but first variant ever identical.


test here

Also 64 bit variant.

[Tord Romstad]

Is missing randomize value for books in start engine! -> Engine plays identical variants!
for ph-book.bin:
white 1.e4 -> Ruy Lopez 5.d4
black 1.e4 d6 or Slav-Merano
If new game, then book variable, but first variant ever identical.

Hello Pavel,

You are absolutely correct - thanks for pointing out this bug! I have fixed it in the current development version, and this bug fix will of course be included in Glaurung 2 - ε/3.

Thanks also for the tests you are running with Glaurung! I follow the results with great interest.

Tord

[Tord Romstad]

Also, as I pointed out weeks ago in WinBoard Forum, Glaurung does not show hash usage under Arena.

True, and in fact Glaurung 1.x also didn't until recently. I consider the display of hash saturation to be relatively unimportant, for two reasons:

1. 95% of the users (including myself) don't care at all.
2. 95% of those users who do care don't really know what the number means, even if they think they do.

The second item above deserves some explanation: Most non-programmers seem to believe that as long as the hash usage never gets close to 100%, everything is fine, and a bigger hash table would be useless. This is wrong. When a position is written to the hash table, it is written to an essentially random location, which may or may not be occupied by some previously searched position. The program does not search through the whole hash table looking for some empty place (this would take a lot of time).

The hash saturation should be thought of as the probability that the next position which is written to the hash table will have to overwrite some position previously examined in the same search. This means that the search is a lot more efficient when the hash table is 10% full than when it is 90% full. If the hash table is 90% full, there is a 90% probability that the next write to the hash table will be forced to delete some potentially useful information. This is why a bigger hash table is always better for most programs, as long as the whole table can be stored in RAM.

Tord

[PauloSoare]

Also, as I pointed out weeks ago in WinBoard Forum, Glaurung does not show hash usage under Arena.

True, and in fact Glaurung 1.x also didn't until recently. I consider the display of hash saturation to be relatively unimportant, for two reasons:

1. 95% of the users (including myself) don't care at all.
2. 95% of those users who do care don't really know what the number means, even if they think they do.

The second item above deserves some explanation: Most non-programmers seem to believe that as long as the hash usage never gets close to 100%, everything is fine, and a bigger hash table would be useless. This is wrong. When a position is written to the hash table, it is written to an essentially random location, which may or may not be occupied by some previously searched position. The program does not search through the whole hash table looking for some empty place (this would take a lot of time).

The hash saturation should be thought of as the probability that the next position which is written to the hash table will have to overwrite some position previously examined in the same search. This means that the search is a lot more efficient when the hash table is 10% full than when it is 90% full. If the hash table is 90% full, there is a 90% probability that the next write to the hash table will be forced to delete some potentially useful information. This is why a bigger hash table is always better for most programs, as long as the whole table can be stored in RAM.

Tord

Interesting explanation Tord, I was included in your number 2 item.
There are no way to optimize this?

Paulo Soares

[Uri Blass]

Also, as I pointed out weeks ago in WinBoard Forum, Glaurung does not show hash usage under Arena.

True, and in fact Glaurung 1.x also didn't until recently. I consider the display of hash saturation to be relatively unimportant, for two reasons:

1. 95% of the users (including myself) don't care at all.
2. 95% of those users who do care don't really know what the number means, even if they think they do.

The second item above deserves some explanation: Most non-programmers seem to believe that as long as the hash usage never gets close to 100%, everything is fine, and a bigger hash table would be useless. This is wrong. When a position is written to the hash table, it is written to an essentially random location, which may or may not be occupied by some previously searched position. The program does not search through the whole hash table looking for some empty place (this would take a lot of time).

The hash saturation should be thought of as the probability that the next position which is written to the hash table will have to overwrite some position previously examined in the same search. This means that the search is a lot more efficient when the hash table is 10% full than when it is 90% full. If the hash table is 90% full, there is a 90% probability that the next write to the hash table will be forced to delete some potentially useful information. This is why a bigger hash table is always better for most programs, as long as the whole table can be stored in RAM.

Tord

This is not exactly correct that the probability is 90% because even if the first try fails you may try second try but there is a constant limit to the number of tries so the probability is clearly more than 0.

Note also that the place of the position in the hash table is not exactly random number and I suspect that the probability that
the next write to the hash table will be forced to delete may be even 0 in the first writes when with random numbers it may be something like 1/(2^20).

I did not investigate this problem and it is possible to try to have a model for it based on results of millions of shallow searches.

Uri

[Tord Romstad]

Interesting explanation Tord,

Thanks!

I was included in your number 2 item.
There are no way to optimize this?

To some extent, there is: Most programs make some effort to keep the most valuable entries in the hash table, and try to overwrite only the less valuable entries when possible. Exactly how the value of an entry is measured depends on the program, but the most common and obvious way to do it is to regard the result of a deep search as more valuable than the result of a shallower search.

Such techniques help a little, but it is still very far from perfect.

Tord

[anst]

There are a lot of ways to optimize this - many books have been written about the subject. I am absolutely sure that Tord has a good solution to this - it may not be perfect, but as close to perfect as necessary. In the end the size of the hash table is what counts.

Regards
Andreas

[anst]

[quote="anst"]There are a lot of ways to optimize this - many books have been written about the subject. I am absolutely sure that Tord has a good solution to this - it may not be perfect, but as close to perfect as necessary. In the end the size of the hash table is what counts.
[/quote]

I stand corrected (See Tord's post)

Regards
Andreas

[Tord Romstad]

This is not exactly correct that the probability is 90%

True, it is not exactly correct. I was simplifying the argument considerably, for the benefit of non-technical readers.

Tord

[Tord Romstad]

I stand corrected (See Tord's post)

You were not really wrong, at least not with respect to hash tables in general. But the hash tables used by conventional chess programs are actually a very crude and primitive form of hash table. Most advanced techniques are unsuitable for a chess program, for performance reasons.

Tord