Author: Robert Hyatt
Date: 21:01:24 08/24/02
Go up one level in this thread
On August 24, 2002 at 20:38:05, scott farrell wrote: >Guys, > >Chompster is still going slow, but let's see if we can make it search >smarter. > >I have the basics if SE going. > >If any of these, I do a serach extension >single legal move, >null move returns -INFINITY, >isCheck, >recapture > >The search extension is just doing search(-beta,-alpha,depth) instead >of search(-beta,-alpha,depth-1) > >It seems to work OK. It solved one of my hard test positions in one ply >less, but in about the same time, as it used many more nodes. > >My questions: >- I cant work out the impact on the hash tables. For example, if when >eventually return to the root of the tree, after a few SEs, and we store >the value in the hashtable, what depth should we put on it? If we are >searching all moves to 3 plies, and do 2 SE's during a particular branch >search, should I not store it in the HT as depth=5 (and how do I work >out depth=5?) Think about it for a minute. When you do a hash _probe_ in the exact same position, how will you see if the depth is good enough to use in this position? You will compare it to the current depth value, at the instant you do the probe. Therefore you _must_ store the same depth value at the instant you complete the ply, storing the depth that was passed _in_ to this recursive Search() call... >- should there be a limit on how SE's you do. I know crafty does "no >more than one ply of extensions are allowed at any one level in the >tree". But it depends how how you look at "any one level in the tree", >given SEs play around with the tree, as what this really means. >- I found I just burned more nodes, and time, and generally about 5% >worse on WAC for 1 and 2 seconds/position >- I run all the calcs to determine if to do a SE (see above) before I >iterate the moves and doMove (other than recapture which doesnt make >sense without a move). I am unsure as to test things like isCheck before >or after doMove. The obvious rule has to be that you can not possibly do one ply of extensions for every ply you search. Otherwise you get a non-terminating search to nearly infinite depth. (nearly infinite is say 30-40 plies in todays hardware). However, there are things you can work with. For example, in Crafty, when I check the opponent, I extend when I do the check. Then, at the next ply, if he has one legal move, I extend there as well, which means that I sort of extend twice, but my one-legal-reply extension is 3/4 ply, so in 2 plies, I can extend no more than 1.75 plies for that case... The new version (19.0) is doing it differently, but until I decide that it is working as well or better, there is not much point in saying more as it may well not pan out to be worthwhile... > >Scott >sfarrell@icconsulting.com.au >sfarrellc(ICC)
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.