Author: Robert Hyatt
Date: 07:44:52 01/20/98
Go up one level in this thread
On January 20, 1998 at 10:03:54, Bernhard Bauer wrote: >Up to 3MB everything looks ok, but then we have a jump. Hope you can >resolve >the problem, because it may be everywhere, but not as visible as here. > >Kind regards >Bernhard First, here are my results, 24K thru 96M bytes of hash: hash time (30) t/d (kb1) t/d (>+2) nodes hash usage 24K 9.45s .37s/19 .60s/21 621K 93% 48K 8.14s .23s/19 .56s/21 621K 93% 96K 15.60s .42s/19 .96s/23 1118K 99% 192K 27.89s .37s/19 .37s/19 2347K 99% 384K 12.34s .42s/19 .62s/21 1029K 99% 768K 8.04s .45s/19 .61s/21 621K 93% 1.5M 8.10s .37s/19 .50s/21 621K 93% 3M 4.82s .36s/19 1.18s/23 294K 20% 6M 17.16s 3.11s/25 3.95s/26 1059K 55% 12M 15.63s 2.26s/25 3.55s/26 1112K 36% 24M 13.64s 2.51s/25 3.12s/26 960K 15% 48M 13.48s 2.35s/25 2.94s/26 971K 8% 96M 14.11s 2.46s/25 3.86s/26 956K 4% hash is the size of the hash table in bytes, not entries time (30) is the time taken to reach depth=30, which is where I stopped all runs. t/d (kb1) is the time and depth where Crafty decided Kb1 was the best move. t/d (>+2) is the time and depth where Crafty found that Kb1 led to a score > +2 pawns for white. This is often a ply or two deeper as Kb1 can fail high but not get resolved to a real score due to the way the hash table generally stores way more bounds than good scores. nodes is total nodes searched to reach depth=30 hash usage is the percentage of the hash entries stored into during the search. I averaged black/white here. First, why does it take deeper depths to solve as the hash gets larger? As I mentioned earlier this is a 26 ply position at least, meaning that with best play by both sides it takes at least 26 plies and it might be deeper (IE it might take a non-hash program 28 plies to solve, I'm not sure.) The only way to solve this in less than N where N is >= 26 plies is to have poor move ordering in the search so that we first search a branch where the opponent plays poorly and we reach a position where even if the opponent plays perfectly we discover we can force a win. Then we search branches where the opponent plays perfectly, and reach these "winnable" positions much deeper into the search, but use the information from the earlier searches to resolve them as "won". If we *always* search best moves first, this won't happen. As the hash gets bigger, the liklihood of finding "hash moves" goes up, meaning that move ordering gets better, and eventually, it pushes the "winnable positions" away so that it takes the full 26 plies to find the right answer. In these cases, and a few other anomolies, the tree size explodes and the total nodes searches gets larger. 192K is a good case in point where the tree size quadruples for no good reason other than move ordering is changing from bad to good and luck affects the size of the tree. This has always been a favorite of mine, because it is *so* sensitive to hash size. Notice that with big hash tables it takes 6-7 more plies to find the right answer, although the time is not very significant for any of the searches. I've never let this run for a long time to see how deep it can go.. but the search will definitely blow up somewhere beyond 30 because once it can force a queen, that's it. Right now all the lines that lead to queening can be pruned. But not once a queen can be forced. It will likely search at that depth for a year before getting anything back. :)
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.