Author: Bas Hamstra
Date: 14:56:31 08/16/04
Go up one level in this thread
On August 16, 2004 at 15:23:58, Stuart Cracraft wrote: >I completed some testing on two recently added features >that probably will become permanent additions to this >program at all time levels. My conditions for these kinds >of additions are: > > o reduces search tree without damaging test suite results > o average ply doesn't drop drastically, preferably increases somewhat > o plays reasonable chess and can continue to trounce me > >The first feature is SEE and was motivated by readings but mainly >Bob Hyatt's effective, repeated harping. Fortunately I did >not have to write it and it was very kindly donated to the program >which makes it even easier. :-) > >The research explored 3 uses of SEE: > > 1) use SEE to score each capture, as the move is generated, > and then for later sorting, prior to the normal quiescence and > main search uses of the movelist and its scores > > 2) use SEE for delta pruning / futility cutoff with a MARGIN > of 1.5 pawns > > 3) use SEE to Draconianly cutoff any quiescence capture where SEE < 0. > (the so-called "delta prune" or "futility cutoff in quiescence". > >#1 showed its disadvantages quickly. Generating a SEE for every >move instead of or in addition to MVV/LVA was costly. Using #1 >dropped test results negatively. Test results include tree sizes, >average ply, etc. This program does not generate and search individual >moves on the fly and then generate the next move, etc. All captures >or all moves, all at once. In my case it's a break-even. Slows me down in nps but searches equally deep. Maybe you can try this: sort captures SEE-wise in the normal search (doesn't effect speed much, but results in better sorting) and sorting captures MVV/LVA in the qsearch. You should try it. >#2 had a bug initially with MARGIN being set to only 1/5th of a pawn >or just to the maximum positional score of the side on move (usually >less than a quarter of a pawn.) When the MARGIN was upped to 1.5 pawns >the trees were improved and the tree results were better without hurting >test scores much. The model for this version was GNU 5 and I have >not researched the MARGIN value as much as I would like. I would like >to know what people do. How about 1.5x, 2x, 3x the max positional score? >Any other hard or adaptive settings worth exploring? How about depth >or game-phase auto-variants? How about dumping that futility stuff? Just cut away all captures with SEE < 0 that's good enough. If it doesn't solve more tactics, than why use it? If it *really* searched 0.20 ply deeper it oughta solve more tactics... I don't like it and I have never liked it and IMO it doesn't combine well with checks in the qsearch. >#3 Also helped and showed good tree results without horribly affecting >test score. > >So I kept #2 and #3 and discarded #1. Many people have objected but >all I have to say is that Schaeffer is probably right when he writes that >all one needs for move ordering is probably hashing and history heuristic >besides the hash move and pv's first, etc. All I use in addition to those >is MVV/LVA, a centrality table, and a castle bonus to create the score. >Every other attempt to improve here has failed. Well, I got different results, SEE sorting is a win for me, 10-20% or so (in the normal search, that is). >Separately, in reviewing the search engine logs and Heinz's work, I decided to >throw in an adaptive null move, poor man's version. Only for non-quiescence >search nodes with greater than 6 ply left of search and not endgame, >the null move "R" is set to 3, otherwise it is set to 2 by default. This also >didn't affect test score badly although the average ply depth was shortened >by about 0.13 ply. Perhaps I should have another condition where R=1 >besides the 2/3 above. No research yet there. > >The following is a fast 20 minute test that showed an overall 12% reduction for >very short searches. I do these short searches much to some people's objection >not to be antagonistic or political but simply because turnaround is fast >and I play mostly short games with my program (it's basically all I ever >play chess with except some games at Laguna Beach boardwalk once in a >blue moon.) And besides, cpu's are getting faster and it's not that much >longer for the next 5x speedup here in the household over this 1ghz p3 clunker. >So today's 1 second search is tomorrow's 0.2 second search. > >Results: > >No SEE / no Adaptive Null Move >HERALD ga nothing1300.log 1 300 >**** 6.72/27.70 67% 203/300 267.40 60169024 200563/1/225014 0/0/3745419/0/0/0 > >Adaptive null move (poor man's version) >HERALD ga -DNULLMVADAPTIVE adaptive1300.log 1 300 >**** 6.59/27.62 67% 203/300 268.12 60904880 203016/1/227159 0/0/3836922/0/0/0 > >SEE (delta/futility cutoff + search for non-negative quiescence see's only) >HERALD ga -DSEE adaptive1300.log 1 300 >**** 7.21/21.12 67% 202/300 267.61 53040536 176802/1/198204 0/0/1426136/0/0/0 > >HERALD ga -DSEE -DNULLMVADAPTIVE adaptive1300.log 1 300 >**** 6.97/20.91 67% 201/300 266.70 52709080 175697/1/197631 0/0/1471771/0/0/0 > >So the total tree size has gone down about 12% between having no SEE/ANM >and having both SEE/ANM, in this implementation and the average depth reached >increased by about 0.22 ply in these short searches. The null move used >in the ones above that don't have NULLMVADAPTIVE is the verified null >move with R = 3. For NULLMOVEADAPTIVE ones, the R varies as above >and the verified null is kept. > >I need to re-run these 4 tests tonight in my standard 8 hour test >but I am sure the results will be even better. > >(Please don't bother telling me I need to be solving X out of 300 >unless you have additional substantive suggestions. I regard anything >non-constructive as just that. I consider this program as much communal >as personal based on its rapid progress due to people with very >incisive suggestions in the past 2 months since inception including >hard-code fragments and in one case a function. The program will never >be either commercial nor free. It is a toy to soak up free time and >offer a personal game of chess.) Bas.
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.