Insight: the best evaluator depends on the search depth

Any topic that does not fit elsewhere
Post Reply
ddyer
Posts: 28
Joined: Tue Feb 12, 2008 7:35 pm
Location: Los Angeles

Insight: the best evaluator depends on the search depth

Post by ddyer » Tue May 30, 2017 7:56 pm

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.
my game site is http://Boardspace.net

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Insight: the best evaluator depends on the search depth

Post by Rémi Coulom » Wed May 31, 2017 9:47 am

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
Posts: 28
Joined: Tue Feb 12, 2008 7:35 pm
Location: Los Angeles

Re: Insight: the best evaluator depends on the search depth

Post by ddyer » Fri Jun 30, 2017 7:15 pm

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.
my game site is http://Boardspace.net

Post Reply