TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Vincent Diepeveen

Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands

Post subject: Re: The evaluation value and value returned by minimax searc    Posted: Sun Mar 11, 2012 5:09 am

 nkg114mc wrote: Hi, all. These days I was thinking about using reinforcement learning to train my evaluation function. I came up with a question about how to understand the relationship between evaluation and the search. Let us go back to the original definition of evaluation and minimax search. We know that for each position, the evaluation gives us an estimation of the current position. If this estimation is exactly enough (which means this evaluation is *perfect*), the engine should be strong even only search for just 1 depth to pick a best move whose leading position has the maximum evaluation. Unfortunately, it is impossible to make such a 100% exact estimation. However, a minimax search with depth D can make the evaluation more exactly. It is intuitive to believe that the value of a minimax search with depth D (D > 1) should be more accurate than calling the evaluation function directly. Now the question is coming: if we have an evaluation function Eval() which is not accurate enough (for example, an evaluation that only make the summation of all material values in that position), firstly we use this evaluation function to evaluate a position, suppose the value return by Eval(pos) is H. Then we run a minimax search of depth D with the same evaluation function (which is called when the search reach the leaf nodes) and the position above is the root position. The search use qsearch and check extension to avoid horizon effect. The search will also return a value for this position, say V. My question is: “Can we say that V is more accurate than H respectively?”

It doesn't matter whether we speak about go or chess, in all cases statistically D > 1 will statistically return a much better score.

A statistical better score doesn't mean it's true for all positions.

 Quote: Notice that the evaluation function itself is not accurate at all. So the search result may also not be accurate. Another more interesting topic is about the delta between V and H. Suppose Delta = |V – H|, what conclusion can we get from this Delta? Can we say that Delta reflect the degree of accuracy of an evaluation function?

That would be a heuristic with a weak positive relationship.
A stronger assumption would be that the position isn't quiet.

 Quote: Or it is just a essential condition for an accurate evaluation function, but not sufficient (we can say “an accurate evaluation => a small Delta”, but can not say “a small Delta => an accurate evaluation”)? Or neither?

In classic game tree search the assumption is that we strive for returning an evaluation of this position removing possible tactics that are there, so returning a quiet evaluation.

Now that said, i must note that the years 70/80 razoring technique is again very fashionable, which contradicts the above statement.

 Quote: Dose the evaluation of Stockfish or Crafty has such a property of “small Delta”?

I didn't checkout the latest crafty, as for Stockfish it's razoring last plies bigtime.

 Quote: Have someone made such a test? (The comparison may need some normalization to the percentage pawn score scale)

You don't need to test it - the relationship is there, just it's a weak positive relationship, so filtering out tactics has an overwhelming bigger impact on the score difference the first few plies, than the above heuristical relationship, yet it is there.

So if you'd compare a search depth of say n with n+i , with n rather big and n+i immense bigger, the initial weak positive relationship gets a lot stronger.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Ma Chao Fri Mar 09, 2012 11:51 am
Joona Kiiski Fri Mar 09, 2012 12:06 pm
Pio Korinth Fri Mar 09, 2012 9:51 pm
Vincent Diepeveen Sun Mar 11, 2012 5:34 am
Vincent Diepeveen Sun Mar 11, 2012 5:58 am
Joona Kiiski Sun Mar 11, 2012 12:20 pm
Vincent Diepeveen Sun Mar 11, 2012 2:41 pm
Joona Kiiski Sun Mar 11, 2012 3:44 pm
Vincent Diepeveen Sun Mar 11, 2012 3:47 pm
Joona Kiiski Sun Mar 11, 2012 3:51 pm
Vincent Diepeveen Sun Mar 11, 2012 3:55 pm
Marco Costalba Sun Mar 11, 2012 4:04 pm
Vincent Diepeveen Sun Mar 11, 2012 4:10 pm
Joona Kiiski Sun Mar 11, 2012 5:03 pm
Vincent Diepeveen Sun Mar 11, 2012 2:43 pm
Uri Blass Sun Mar 11, 2012 3:07 pm
Vincent Diepeveen Sun Mar 11, 2012 3:23 pm
Joona Kiiski Sun Mar 11, 2012 3:47 pm
Vincent Diepeveen Sun Mar 11, 2012 3:50 pm
Joona Kiiski Sun Mar 11, 2012 3:52 pm
Joona Kiiski Sun Mar 11, 2012 3:42 pm
Han Chengye Sat Mar 10, 2012 2:22 am
Marco Costalba Sat Mar 10, 2012 12:48 pm
Ralph Stoesser Sat Mar 10, 2012 11:12 pm
Vincent Diepeveen Sun Mar 11, 2012 6:27 am
Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:09 am
Vincent Diepeveen Sun Mar 11, 2012 5:27 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum