Thermostat Algorithm

[rjgibert]

Okay, here's a simple idea of applying the basic operation of a thermostat to computer chess. It has many uses, but I will use null move pruning as an example. Note that many error prone time saving ideas can be regulated in this fashion.

About , say for example, 1% of the time, after a nullmove would produce a cutoff, you would also run a regular search to compare the result and compute an error rate for nullmove. You can think of this as verified nullmove as a sampling method applied sporadically to compute an error rate.

If the error rate rises above a certain threshold, then nullmove's R factor is decreased. If the error rate falls below a certain threshold, then R is increased. This is analogous to the operation of a thermostat where error rate takes the place of temperature.

This idea is half-baked and untested. I thought I'd just throw it out there to see what you guys make of it.

[mjlef]

I have tried this a number of ways. One way was seeing how many moves should be searched to full depth in Late Move Reductions. The idea being that in the opening and midgame, where more moves are available you might need to search a different number of moves fully thatn say in an endgame, or in some tricky position where move ordering heuristics fail more. The search notes the move number for each fail high, and counts them. Then the program user can specify a success rate. For example, if someone specified say 99% success in searching a best move to full depth, the program merely figures out what N moves should be based on the staticstics so far. Does it work? I am not sure. But it was certainly not bad and in it did dynamically change N based on game stage and position. In my crude implementation, I just counted the number of times each Nth ordered move failed high, then for the success margin, just adding count[1]...count[x] until the ratio of the total counts to count[x] to the number of positions counted was > the desired success rate. I did this every thousand nodes or so, but it could even be done dymically with each node pretty fast.

Mark

[Tony]

I liked the adjustability, but I never got it really stable. The problem was when things started to go wrong (ie root fail low)

It is still on my todo list though. Specially for some dynamic adjustments when you're behind in material (start an almost woodonly search).

Tony

[rjgibert]

Specially for some dynamic adjustments...

This seems to imply you intend to use it on more than one thing. Be careful. They must be independent of each other. If they are not, I would expect you could get some weird interaction. In fact, I wouldn't generally expect it to work at all, because if it did, it would imply solving a very difficult type of problem in very simple way and that is just too good to be true.

Adjusting more than one interdependent parameters at a time (or even one at a time in sequence) requires a much more sophisticated algorithm to be stable.

BTW, this also applies to how some people manually tune their chess programs too. They can spend a lot of their time biting their own tail without realizing it.

[rjgibert]

Yes, this idea has many incarnations. I was curious as to why nobody mentioned it before. Or perhaps they did, but I did not recognize it. It's simple and if used carefully, ought to work with the right application.

BTW, A possible problem with using it with null move is that R is possibly too coarse a parameter. Perhaps a program that makes significant use of fractional depths would be a better fit if an R = 2.8 or whatever was something that made sense in such a program.

[Harald Johnsen]

Yes, this idea has many incarnations. I was curious as to why nobody mentioned it before. Or perhaps they did, but I did not recognize it. It's simple and if used carefully, ought to work with the right application.
...

I see here the same 'problem' that there is with history numbers (or relative history numbers).
1) You get a global search result and you try to apply it to a local subtree. It can work or not, but you'll never know (the verification that you do is only valid where you do it)
2) The term that you compute affects the result. You can not do two consecutive search and get the same result
3) it's difficult to debug because you can not predict what will happen in the search.

HJ.