ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The evaluation value and value returned by minimax search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Vincent Diepeveen



Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
PostPost subject: Re: The evaluation value and value returned by minimax searc    Posted: Sun Mar 11, 2012 5:09 am Reply to topic Reply with quote
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.

There is no question about this.

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.
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN Messenger
Display posts from previous:   
Subject Author Date/Time
The evaluation value and value returned by minimax search Ma Chao Fri Mar 09, 2012 11:51 am
      Re: The evaluation value and value returned by minimax searc Joona Kiiski Fri Mar 09, 2012 12:06 pm
            Re: The evaluation value and value returned by minimax searc Pio Korinth Fri Mar 09, 2012 9:51 pm
            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:34 am
            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:58 am
                  Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 12:20 pm
                        Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 2:41 pm
                              Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:44 pm
                                    Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:47 pm
                                          Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:51 pm
                                                Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:55 pm
                                                      Re: The evaluation value and value returned by minimax searc Marco Costalba Sun Mar 11, 2012 4:04 pm
                                                            Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 4:10 pm
                                                                  Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 5:03 pm
                        Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 2:43 pm
                        Re: The evaluation value and value returned by minimax searc Uri Blass Sun Mar 11, 2012 3:07 pm
                              Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:23 pm
                                    Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:47 pm
                                          Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 3:50 pm
                                                Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:52 pm
                              Re: The evaluation value and value returned by minimax searc Joona Kiiski Sun Mar 11, 2012 3:42 pm
      Re: The evaluation value and value returned by minimax searc Han Chengye Sat Mar 10, 2012 2:22 am
            Re: The evaluation value and value returned by minimax searc Marco Costalba Sat Mar 10, 2012 12:48 pm
      Re: The evaluation value and value returned by minimax searc Ralph Stoesser Sat Mar 10, 2012 11:12 pm
            Re: The evaluation value and value returned by minimax searc 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
      Re: The evaluation value and value returned by minimax searc Vincent Diepeveen Sun Mar 11, 2012 5:27 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads