Want pseudo code of chess programming algorithm
Chavalit Likitvivatanavong
I'm doing my own chess program and didn't understand much about
Singular Extension,although I've read some of its papers.So,if you have
the pseudocode or some explanation please tell me at
u352...@columbia.chula.edu.Thank you in advance.
Chavalit Likitvivatanavong.
P.S I'm also wonder about exact definition of 'quiescence'.Have any comment?
Keywords:
Robert Hyatt
Simple explanation:
there are two parts to singular extensions you have to handle.
1. When searching a move along the PV, after searching the first move, you
lower "beta" by some significant amount and search the remainder of the moves
at that position with this new alpha/beta window. If none of the moves fails
high, you know that they are all worse than the first move by the "significant
amount" you reduced beta by. This is the easy part. However, if one fails high
it does not mean this is not a singular extension position, it just means that
you have two possible best moves, and one of them might be better than the other
by this margin. If you re-search this move with the original beta, and it
doesn't fail high, this is *not* a singular position, because there are two moves
that are fairly close to each other. Give up at this position on the singular
extension. If you get all the way through the rest of the moves (after the first
one) with no fail highs, then the first (PV) move is "singular." You then
increase depth by 1, and re-search it. This new value becomes the *real* value
replacing the value obtained from the first (shallower) search.
2. The second part is more difficult, and (potentially) will add a lot of extra
nodes to your search tree. When searching a non-PV node, you search the first
move with alpha,beta, and you hope if fails high so you are "done." However, if
you want the full benefit of singular extensions, you "aren't". :) You now
have to search the remainder of the moves at this ply, where you wouldn't in a
normal search. To control the cost, you search the remainder of these moves
with a reduced depth D, which is (typically) set to depth-2 to avoid this
search turning into something close to a pure minimax tree in size. Again, you
now search the rest of the moves with (alpha-M, beta-M) and if they all fail
low, you re-search this move to depth+1. If any move fails high, still more
testing is needed. What you strive to prove, at any node in the tree, is that
if there is only one move that is significantly better than the other moves by
some "margin" then such a move should be searched deeper.
Before you write all of this, however, a word of caution. I used the PV-
singular extension on a version of "blitz". Just before the Washington (1978)
ACM event I was experimenting and found that this often costs a ply, which
reduced our depth from 5 to 4 back then. That was too much cost for too little
gain, and I removed it. I didn't discover this idea, however, someone suggested
it to me (might have been Richard Greenblatt but I don't remember) as something
that would improve the accuracy of the PV. It was pretty useful for horizon
effect type positions because it had the effect of extending the pv and if the
score dropped, later another move would try to replace it. however, the singular
extension would then kick in, and show that this was actually worse when searched
to the deeper depth.
The ICCA journal paper that explained this a few years back concluded that it
does not provide significant improvement, and, in particular, on machines that
don't have a lot of horsepower, it might even hurt due to the cost of doing these
re-searches.
Hope that helps... the second part is necessarily short and complicated, because
it's complex. There are many "tricks" here using the trans/ref table to remember
when a position was singular so you can avoid the singular test next time the same
position occurs, or vice-versa.
Bob
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Marcel van Kervinck
: P.S I'm also wonder about exact definition of 'quiescence'.Have any comment?
My definition:
If a position is quiet then the static evaluation is a reasonable substitute
for a search.
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| bue...@urc.tue.nl