sje wrote:Consider the case where some randomness is desired in positional evaluation scores, perhaps changing the bottom two bits of a score. This means that the PRNG would be called many, many times in a search, so it needs to be fast.
To create a pseudo-random term in the evaluation, I derive it from the hash key itself. That can be done much cheaper than runing the presented PRNG, e.g. (hashKey ^ GAME_ID) * MAGIC >> 24 for an 8-bit random. Another advantage is that such a random term is actually consistent: if, in the same game, you reach the same position through two different paths, it will have the same evaluation.
hgm wrote:To create a pseudo-random term in the evaluation, I derive it from the hash key itself. That can be done much cheaper than runing the presented PRNG, e.g. (hashKey ^ GAME_ID) * MAGIC >> 24 for an 8-bit random. Another advantage is that such a random term is actually consistent: if, in the same game, you reach the same position through two different paths, it will have the same evaluation.
Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.
sje wrote:Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.
I could not imagine any. The only reason I would want to have a random evaluation term is to act as a poor-man's mobility eval. And there it would be a severe mistake to count yourself rich because there happen to be many paths to the only node that offers an escape from total disaster, because that node gets an independent random eval every time, making it seem as though there were many escapes.
But if I would need an independent random, I would use something like Reinhard. The periodicity of 2^32 would not worry me very much, as by the time it would start to repeat the generated values would be used to take completely different decisions (in other nodes of the tree, for trees that search other positons). In practice, only the state of the entire system (chess game state + random seed + opponent) matters.
sje wrote:Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.
I could not imagine any.
I can. Adjusting the bottom bit of a positional score independent of the position's hash could add variety to play. In fact, I'm fairly sure that this was done in some commercial dedicated units long ago; at least one unit with a Zilog z80 used the CPU's refresh register as the random source.
It will also add variety of play when it is done consistently. In fact this is how Joker gets its non-determinism.
Dedicated units long ago had no hash tables, so the consistecy was not that much of an issue. But with hash table I would not recommend it when there is no need for it. It just decreases search efficiency. The hash moves wik direct you to a node that had a high score the previous time, only to discover that this time that samenode is no good, because its random get recalculated.
sje wrote:Adjusting the bottom bit of a positional score independent of the position's hash could add variety to play. In fact, I'm fairly sure that this was done in some commercial dedicated units long ago; at least one unit with a Zilog z80 used the CPU's refresh register as the random source.
That still doesn't require a fast RNG. You can XOR the hash with a RN created at the beginning of the game. That is how MSCP randomizes its play.
That is exactly what GAME_ID in my expression stands for a random number created at the start of the game (from the millisec clock). The multiplication with MAGIC is to make sure that all bits of GAME_ID affect the random, and not just (say) the lowest 8 (so that it could only play 256 different games against a deterministic opponent).