Author: Stuart Cracraft
Date: 12:23:58 08/16/04
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?
#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.
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.