Author: Stuart Cracraft
Date: 07:16:09 08/17/04
Go up one level in this thread
On August 16, 2004 at 15:31:42, Robert Hyatt 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. >> >>#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? > >Why more than 1.0? What possible error can 1.0 introduce since you can't >produce a positional score larger than that, and since the material value is >static, making it larger makes no sense... No reason other than I noticed a lot more cutoffs with higher MARGIN My maximum positional is about 1/3 to 1/2 a millipawn... > > >> >>#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. > >Schaeffer really didn't say exactly that. Getting good captures first is >_critical_ to tree size, because captures more often refute moves than any other >single kind of move... I experimented with SEE. Putting SEE into all move ordering (move generator for captures only in quiescence) and move generator for all moves in main search. This slowed down performance and impacted solution rates. I verified that the see<0 captures were getting scores that drove them down (much) further on the list. I suppose they should not be the very last moves searched but with negative see() scores there's not a lot of choice for me. So perhaps that is the reason. They should be lower but not all the way at the bottom. > > >> >>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.) >> >>Greetings, >> >>Stuart
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.