Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Measure of moveorder quality

Author: Robert Hyatt

Date: 06:41:03 09/05/99

Go up one level in this thread


On September 05, 1999 at 08:55:34, Pauli Misikangas wrote:

>On September 05, 1999 at 04:09:58, Pauli Misikangas wrote:
>
>>On September 04, 1999 at 22:15:16, Robert Hyatt wrote:
>>
>>>The measurement I do inside crafty is to count the number of positions where I
>>>get a fail-high, and then count the number of positions where I get a fail high
>>>on the _first_ move I search.  I am generally seeing this average about 94%,
>>>which means 94% of the times when I fail high, I fail high on the first move,
>>>which is pretty good.
>>
>>Have you tested what this "first-fails-high" percentage is when searching to
>>different depths? In other words, instead of using only one counter for
>>fail-highs, use one for each depth. So, if you get a fail-high in a node that
>>was searched to depth d, increase counter fail_high_counter[d] and if the move
>>was the first one, increase also first_failed_high[d]. What kind of
>>first-fails-high percentages (100*first_failed_high[d]/fail_high_counter[d]) do
>>you get for each d?
>>
>>In my understanding, finding a fail-high move quickly is much more important in
>>nodes near the root than in leaf nodes. If you don't count fail-highs separately
>>for each depth, fail highs in leaf nodes will dominate and hide possible
>>weaknesses in move ordering near the root. Do you agree?
>>
>>If 94% first-fails-high percentage is "pretty good" for a chess program, what
>>would you expect the percentage to be for a shogi program that has a good move
>>ordering? In shogi, you have average 80 possible moves per turn while in chess
>>you have "only" 35.
>
>You can find some fail-high statistics of my shogi program ("Shocky") from my
>web page http://www.cs.helsinki.fi/Pauli.Misikangas/shocky/failhigh.txt
>
>Statistics are from a game in which Shocky played against Shotest 3 (3rd best
>shogi program in the world), and won. :-)
>
>Here is a sample of the statistics. For example, the table below shows that I
>got 235037 fail-highs on the first move when searching to depth 2 and that it
>was 86.5% of the total fail-highs at that depth. The percentages are
>accumulative, e.g. in 96% of the fail-highs at depth 1, the fail-high move was
>within first 6 moves.
>
>Move  Quiescense            Depth 1            Depth 2
>----|---------------------|------------------|------------------| ...
>  1 :    6507600    93.8%    608743    82.3%    235037    86.5%
>  2 :     287578    97.9%     63112    90.8%     16116    92.5%
>  3 :      77930    99.1%     18759    93.3%      5134    94.4%
>  4 :      28986    99.5%      8833    94.5%      2514    95.3%
>  5 :      13510    99.7%      6148    95.4%      1910      96%
>  6 :       8062    99.8%      4812      96%      1562    96.6%
>  7 :       4496    99.9%      4066    96.6%      1339    97.1%
>  8 :       2628    99.9%      3429      97%      1125    97.5%
>  9 :       2447    99.9%      3055    97.4%       924    97.8%
> 10 :       1544     100%      2650    97.8%       784    98.1%
>...
>
>Interestingly, the first-fails-high percentages seem to bet better when the
>depth increases. Is this normal?
>
>Best,
>
>Pauli Misikangas


I would think so...  ie the deeper you go, the better the hashing works, and
that gives good move ordering for positions with hash hits.  Also other ordering
algorithms (history, killers, etc) seem to work better with deeper searches,
because, in the case of history moves, this lets shallow moves affect the
ordering of moves deeper in the tree...



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.