Author: Robert Hyatt
Date: 07:03:27 01/19/98
Go up one level in this thread
On January 19, 1998 at 07:10:46, Bernhard Bauer wrote: >Hallo, > >I want to add some numbers to the hash table discussion. >This applies only? to Crafty. >Since the Fine position No 70 heavily depends on a hash table, >I use this well known posuition. The hash table sice varies >from the min of 64 kb up to 24 Mb. > >Crafty v14.4 >White(1): egtb 0 >White(1): time cpu >White(1): sd 31 >search depth set to 31. >White(1): hashp 640k >pawn hash table memory = 640K bytes. > > +---+---+---+---+---+---+---+---+ > 8 | | | | | | | | | > +---+---+---+---+---+---+---+---+ > 7 | *K| | | | | | | | > +---+---+---+---+---+---+---+---+ > 6 | | | | *P| | | | | > +---+---+---+---+---+---+---+---+ > 5 | *P| | | P | | *P| | | > +---+---+---+---+---+---+---+---+ > 4 | P | | | P | | P | | | > +---+---+---+---+---+---+---+---+ > 3 | | | | | | | | | > +---+---+---+---+---+---+---+---+ > 2 | | | | | | | | | > +---+---+---+---+---+---+---+---+ > 1 | K | | | | | | | | > +---+---+---+---+---+---+---+---+ > a b c d e f g h >White(1): setboard 8/k7/3p/p2P1p/P2P1P///K w > >White(1): d >White(1): d > > hash depth time score trans/ref pawn used w used b nps > 64k 31-> 34.82 2.85 79% 99% 98% b96% 109889 > 96k 31-> 23.34 3.04 53% 99% 99% b98% 125695 > 192k 31-> 25.12 3.04 66% 99% 99% b98% 122916 > 384k 31-> 17.73 3.02 74% 99% 99% b98% 126340 > 768k 31-> 9.85 3.25 90% 99% 99% b98% 125667 > 1.5M 31-> 6.50 3.25 121% 99% 79% b92% 126525 > 3M 31-> 3.17 3.25 136% 99% 27% b37% 123640 > 6M 31-> 34.66 2.85 79% 99% 98% b96% 110491 > 12M 31-> 34.25 2.85 82% 99% 88% b83% 109862 > 24M 31-> 36.02 2.85 84% 99% 68% b62% 110227 > > >As we might espect, the solution time decreases as the hash table size >increases. However, after reaching a min of 3.2 sec the solution time >jumps up by a factor of 10! >So it looks like there is an optimal hash size, at least for Crafty >and this problem. The solution move Kb1! is found on ply 19 for a >hash table size of 3M. For a hash table size of 24M Crafty needs 26 >plies. > >My be there is something unclear for Crafty? >Are there similar results available for other programs? > >Kind Regards >Bernhard the reason for this is the following: this position takes 26 plies of search to solve. Here's how you solve it quicker (crafty's 19 plies, for example): you first search decent moves at every ply for white, but poor moves at every ply for black. By the time you reach depth 19 or so, you reach positions where white can force a win. Lets call these positions Pi. For any position in Pi, we can (at depth=19) force a win. The only problem with the Pi positions is that they were reached by poor play by black, but after reaching them, it doesn't matter whether black plays perfectly or horribly, we can prove we can win. Now we search good moves by white and black, but notice at depth=19 that no matter what black does, we can force positions in Pi. We can't search the Pi deep enough to see that they are won for white, but we can look them up in the hash table and discover that they are still won. The idea then, is that we first find positions (reached by weak moves) where we can force the win no matter what the opponent does, then we use these positions to prove other positions where black has played better are still winnable. But notice that this is based on bad move ordering, so that we first must search the weak black moves before we search the good black moves, so our hash table will hold that Pi set of positions. If move ordering is better, this may well not happen at all, since we know that the solution is 26 plies deep based on best play by both sides. As you change the hash table size, you change the move ordering significantly since the hash table is a prime source of move ordering info. If it is too small, the Pi entries go lost before they are used. If it is too large, move ordering is improved so that few Pi positions are found. It has to be "just right" for optimal search results. In short, it is a matter of luck. If Crafty knew anything about coordinate squares, it would not solve this until depth=26, because the best black moves would always be tried first...
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.