Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move_generation + hash

Author: Ricardo Gibert

Date: 12:32:31 05/31/00

Go up one level in this thread


On May 31, 2000 at 15:23:28, Robert Hyatt wrote:

>On May 31, 2000 at 13:22:34, blass uri wrote:
>
>>On May 30, 2000 at 18:11:51, Robert Hyatt wrote:
>>
>>>On May 30, 2000 at 15:24:36, Ed Schröder wrote:
>>>
>>>>On May 30, 2000 at 00:28:47, Robert Hyatt wrote:
>>>>
>>>>>On May 28, 2000 at 16:37:32, Gian-Carlo Pascutto wrote:
>>>>>
>>>>>>On May 28, 2000 at 10:02:05, Georg v. Zimmermann wrote:
>>>>>>
>>>>>>>From my tests it shows that it sticks with the hash-move about 50% of the time.
>>>>>>>Should this number be higher ?
>>>>>>
>>>>>>Hmm...if this number is also effectively your 'move ordering percentage',
>>>>>>which I assume it is, it is quite low. I'd expect it to be at least about 75%.
>>>>>>
>>>>>>>
>>>>>
>>>>>
>>>>>
>>>>>The classic definition of a "strongly-ordered tree" is this:  If, for every
>>>>>node where you fail high, you fail high on the first move at least 90% of the
>>>>>time, then your move ordering is good."  If you are much below 90% and already
>>>>>have a serious problem that is not hard to fix.  The traditional ordering ideas
>>>>>holds Crafty at 92% and better for most of the game.
>>>>
>>>>I can't understand the 92%. A perfect mini-max search requires many many
>>>>nodes an alpha-beta cutoff will not work and you are forced to search all
>>>>the nodes of the ply in question. And this number is certainly much higher
>>>>than 8%.
>>>
>>>You have to re-read the definition again, _very carefully_ to avoid the semantic
>>>trap you just fell into.
>>>
>>>For every position where you fail high, if you fail high on the first move you
>>>try, you increment a counter "right++".  You always increment a counter "fh++".
>>>When you finish the search,  you compute percent=right/fh.  That number needs to
>>>be over 90% to consider your tree strongly ordered.  Notice that this 92% number
>>>(in crafty) simply says this:
>>>
>>>    "if we look at _all_ the positions in the tree where the search fails high,
>>>     then 92% of those fail highs happen on the first move searched in that
>>>     position, which is known as 'optimal move ordering'.
>>
>>
>>I do not agree that failing high on the first move is optimal move ordering.
>>
>>Here is an example:
>
>That particular idea isn't open to debate.  Alpha/beta is all about minimizing
>the number of nodes searched.  It is easy to prove mathematically that if I
>get the best move first every time, and you don't, I am going to search fewer
>total nodes than you are to get the exact same score.
>
>
>
>
>
>>
>>[D]8/6k1/rp3ppp/8/N7/8/4RPPP/6K1 w - - 0 1
>>
>>My understanding of optimal move ordering is that after the moves Nxb6 or Nc5
>>the first move to search will be Ra1+(at least in cases that you are going to
>>search more than few plies after these moves because Ra1+ Re1 Rxe1# is the
>>faster way to prove that Nxb6 or Nc5 is wrong)
>>
>>If you start with taking the knight than your first move may fail high but you
>>waste more time to prove that Nxb6 or Nc5 are wrong.
>>
>>Uri
>
>
>No...   that is the wrong way to think about alpha/beta.  In any given position,
>the 'best' move is the one which produces the best score _in that position_.  It
>doesn't matter a dime what has happened in similar positions, or at shallower
>search depths.  Ie it doesn't matter if a move looks "best" to a human, in the
>context of alpha/beta, or anything else.  It is all about the move that produces
>a move that causes a cutoff.  It is _not_ necessary that alpha search the "best"
>move first, ever.  It is only necessary that alpha/beta searches a move good
>enough to cause a cutoff...
>
>My original statement is still on target:  If, at every move where you get a
>cutoff, you get it on the _first_ move, you are searching the "minimal tree"
>which is the goal of alpha/beta.

Oops! I duplicated! Oh well.



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.