Author: Stuart Cracraft
Date: 07:05:26 08/17/04
Go up one level in this thread
On August 16, 2004 at 17:56:31, Bas Hamstra wrote: >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. > I agree. But your program sounds more impressive when you can list all those neat features. :-) Just kidding but it's not far from the truth. I hear about XYZ program with every whiz-bang feature and I really start to wonder about the methodology used to verify each one! My qsearch does extend (back to the main search) if there is a check so there may be a problem. I think what I'll need to do to get additional insight is go beyond the Win at Chess suite and expand to a larger suite before I do anything drastic. >>#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). I did SEE sort and verified the losing captures were further down the move list. But the searches didn't improve. More testing is needed here but I didn't see it. > >>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.