Insight: the best evaluator depends on the search depth

[ddyer]

I've been experimenting with a genetic algorithm to improve the evaluator for my Hive
implementation, and because I wanted fast results, my simulated games were run with
a 1-ply search; Ie; using the evaluation directly, without any deeper search.

After various experimentation, I developed a procedure that ran the learned parameters
against the benchmark hand-tuned parameters; breeding better parameters etc, and
eventually reached an 75-85% win rate against the benchmark.

Plugging these parameters into the live program, and much to my surprise, the
learned parameters performed poorly, never winning against the benchmark parameters.
After a while, I re-ran the rollout with 2-ply search, and found the evolved parameters
performed at a 35-45% win rate. Same parameters, 2 ply instead of 1 ply, half the win rate.

I'm still mentally waving my hands to explain this, but the takeaway is that for a given
algorithm, the search depth interacts in more than obvious ways. A progressive search
should not necessarily use the same evaluation as the search deepens, and the common
practice of using the evaluator to pre-order the search tree might be more effective if
a different evaluation is used depending on the depth.

[Rémi Coulom]

Interesting.

Do you evaluate all the leaves at the same depth? Inconsistencies between odd and even plies might explain why a one-ply search works better.

[ddyer]

The depth is fixed, but maybe you missed the point. For the same pair of evaluators, the one
tuned to win at 1-ply does much worse if the search is deeper. For the actual evaluators I was testing,
the actual playing depth is 5 or 6 ply, and it just didn't work to use a 1-ply search as a proxy to select
the best evaluation.