Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move_generation + hash

Author: Ricardo Gibert

Date: 13:05:55 05/31/00

Go up one level in this thread


On May 31, 2000 at 15:46:15, blass uri wrote:

>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.
>
>
>If a program rejects Nxb6 or Nc5 because of Ra1+ Re1 Rxe1# it is using less time
>about Nxb6 and Nc5.
>
>If a program is using less time to get to the same depth the order of moves is
>better.
>
>The point is not to search first the best move but to search first the move that
>you need the minimal number of nodes to create a cutoff.
>
>
>
>  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...
>
>If you search first the move that you need less time to get the cutoff then the
>order of moves is better.
>
>
>>
>>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.
>
>No
>You are not searching the minimal tree because after Nxb6 because you search
>more nodes in the line Rxb6 then in the line Ra1+ with the only exception of a
>very shallow search.
>
>Uri

Line A                     Line B
1 Nxb6                     1 Nxb6
2 Rxb6                     2 Ra1+
3 No captures for white    3 Re1
                           4 Rxe1
                           5 No captures for white

Which is shorter Line A or Line B?



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.