random evaluation perturbation factor

[smcracraft]

For evaluated terminal and non-terminal nodes in the tree, what randomization factor is reasonable (as a percentage of a pawn's value) to add to the evaluation returned? 1% of a pawn? 5%? 10%? What is the most popular?

[Ferdy]

For evaluated terminal and non-terminal nodes in the tree, what randomization factor is reasonable (as a percentage of a pawn's value) to add to the evaluation returned? 1% of a pawn? 5%? 10%? What is the most popular?

I think it depends on the engine, there are engines that are not sensitive to eval changes. Also depends on the current score. But of course testing is better to find out the best factor.

[brtzsnr]

I've genuinely never heard of this before, except maybe in the context of skill levels. Why do you want to add a small random value to your score?

[hgm]

I do that in Joker. One reason is to randomize play. The other is the 'Beal effect', that it makes you go for lines that have as many approximately equivalent alternatives as possible, rather than one where you can only escape one way. Because the best random addition of a large group is likely better than on a single try.

E.g. suppose you want to go with a Knight from b1 to c4, in a 3-ply search. You can do it over a3 or d2. But on a3 you are committed to c4, on d2 you could also go to f3. (Say e4 is occupied.) But your evaluation tells you that being on c4 is 2 centi-Pawn better than being on f3. So you go for that. Now minimax does not care how you do it; it sees that you can always reach c4 in 3 ply. So it takes either of them with 50% probability.

If you randomly add 0-9 cP to the eval, the chances that f3 looks better than c4 are 28%, in which case you would always make the first move to d2. The remaing 72% is split equally between a3 and d2, so you have 64% chance to move to d2, and only 36% to move to a3. The fact that you have an alternative from d2 draws you to it with extra probability. By the time you have to make the second step, the evaluations in these positions are no longer relevant, as you know can see ahead further, and it is the evaluations (and randomizations) at the new horizon that matter. So if you were on d2 you do what seems best on the basis of the new information. Perhaps going to c4 now seems 30 cP worse than going to f3, so you go to f3. If you had been on a3, however...

I usually derive the random addition from the hash key, and a value set at the start of the game, so that within a game the randomization is reproducible. That way it would count reaching the same final position through two different path (if not caught by the TT) in itself as having two options. Besides, it is a cheap way to generate a pseudo-random number. Like (int)hashKey*startTime >> 27 to get an addition from -16 to +15.

[D Sceviour]

By the 'Beal effect' are you referring to "Random Evaluations in Chess", Don F. Beal and Michael C. Smith, ICCA Journal [17(1):3-9], March 1994? Is a text available for that publication?

[hgm]

Indeed. I have never seen the text, but Bob Hyatt once mentioned the effect. It is still on my list of fun things to do to build an engine based entirely on that effect, in order to populate the low end of the Elo spectrum. It is a bit tricky how to handle checkmate, however. If you handle it the usual way, with a mate score, you get a very unbalanced engine, which plays like an idiot, and then suddenly announces a perfect mate in 6 (when playing against another idiot). Then it is very obvious the engine with the larger search depth will win, as the one with the lower search depth will more often accidentally walk into its 'mate recognition zone'.

So what I plan to do is also recognize the mate through the Beal effect: the engine will not stop searching when the King is captured, but a side with no Kings can only play null moves. (This incidentally, is very much like how royalty is treated in Chieftain Chess: each royal piece, called a Chieftain there, is an activator for your pieces, so that you can do as many moves as you have Chieftains, and naturally lose when you lost your last Chieftain!) That would give the side that captured the King a huge number of leafs in that sup tree to pick from, the opponent being unable to steer it away from the richest pickings. And the deeper the sub-tree after the mate, the more leaves to pick a favorable score from, so the better the score of the move that captured the King. So it will try to mate quickly rather than late, if it has the choice.

One should have a very fine-grained random, however, to make sure that the best eval in a tree with ten million leaves is on average better than that with a million leaves.

[D Sceviour]

I noticed the effect some time ago and that a small random score of +/- 5 did increase elo (based on 100 centipawns). However, it was turned off because it badly interferes with debugging static evaluated positions. The effect of a random score on mate distance pruning should be predictably disastrous. It may be suspected that mate scores should be exempt from randomization.

[hgm]

A random term in the evaluation cannot affect mate scores, as mate scores do not use the evaluation at all. You must be talking about something entirely different, namely adding a random number to each move score in the root. This indeed should not be done for mate scores.

[D Sceviour]

A random term in the evaluation cannot affect mate scores, as mate scores do not use the evaluation at all.

Yes.

You must be talking about something entirely different, namely adding a random number to each move score in the root.

No, the random +/- 5 is added in quiescence evaluation.

This indeed should not be done for mate scores.

Yes.

[hgm]

Well, you can also do that for mate scores. Because then the quiescence evaluation is not used, and what you add to something that is not used has no effect.