Author: Robert Hyatt
Date: 10:16:02 03/11/03
Go up one level in this thread
On March 10, 2003 at 10:18:27, Peter Fendrich wrote: >On March 04, 2003 at 11:04:00, Robert Hyatt wrote: > >>On March 04, 2003 at 05:04:55, Sune Fischer wrote: >> >>>>Note that I don't know of anyone extending when there is only one legal move. >>>>The >>>>original algorithm was "one legal reply to check" which means you are in check >>>>_and_ >>>>you have only one way out. >>> >>>Well _I_ want to extend in this case :) >>>Anyway, I don't think "original algorithm" necessarily means "optimal algorithm" >>>;) >>> >>>I think it is related to the re-capture and singular extensions, only problem is >>>how to actually "remember" the only move, on my movelist moves are deleted after >>>being searched... grrr what a drag. >> >>I'll bet that if you extend only on one legal move and not in check, it will >>only fire a >>dozen times during an entire game. One legal move is _very_ rare if you aren't >>in check. >>One "logical" move is a different matter. We played with an option "one sane >>reply" which >>is more general. Peter Gilgasch proposed it to me and I tried it in Cray Blitz. >> The idea is >>that often you have 2-3 ways out of check, but all but one lead to your getting >>mated. So you >>extend the one that doesn't get you mated so that you can see deeper to possibly >>see a mate >>there as well... >> >>It is pretty expensive to do this, however, and I didn't keep it very long >>because I was >>beginning to work on the singular extension code and it is a super-set of this >>kind of >>"one-sane-reply" extension. >> >>> >>>While on the subject, how does one detect singular moves? >> >>Singular as in deep blue? >> >>For a move on the PV, search the first move with the normal window a,b. Search >>the >>remaining moves with the window a-s, b-s where s is the "singular margin, I >>think I >>used 3/4 pawn or something similar as they did in DB. If all moves fail low, >>except >>for the first one obviously, then the first move is significantly better than >>the rest. But >>if one fails high, you have to test _it_ for singularity by seeing if it is "s" >>better than the >>original best move. >> >>For fail-high nodes the same idea but it is expensive. You fail high on move X. >> Normally >>you would exit _right now_ returning beta, but you first test all the other >>moves with the >>offset (downward) alpha/beta window, but you search to reduced depth to control >>the >>cost. If the rest of the moves fail low, the fail-high move is singular. >>Re-search it with a >>deeper search. >> >>There is another way to do "pseudo-singular" I can describe if you want... > >Yes, Please! >/Peter When you enter Search(), you first call a procedure Singular(). What this procedure does is to search the move list, but using an alpha/beta window that is offset downward by a SINGULAR_MARGIN. IE smove = Search(alpha-MARGIN, beta-MARGIN, etc) This is used to detect that _one_ move fails high only. If more than one fails high, then we give up. If none fail high, we don't have a singular move (you might not want to test all of them as it is expensive, but if something doesn't fail high pretty early, it is pretty safe to give up and say "no singular move here." What you hope to end up with is a single move that failed high on the offset window while all others fail low. If this happens, pass this move back to search and search everything as you normally would, except when you encounter this specific move, extend the depth by whatever value you want. There are additional ideas you can do, such as Deep Blue's "sticky transposition table" so that once you find a move is singular in a given position, you extend it the next time without having to do the singular test above. One thing I mentioned is that the singular test above is very expensive. To control this cost, it is done with a "reduced depth". Say depth-3 rather than the normal depth-1, to limit the computational cost. That's a basic explanation. I can give you more if you want. I've played with _both_ types of SE (Hsu's approach and the "cheapo" approach given above.) In Cray Blitz, Hsu's approach seemed to work well. In Crafty, it did not. The above approach seemed good in places, but bad in other places and I have never released a version with this code as I never thought it was better than non-SE crafty. But I will go back and play with it from time to time, when I have time.
This page took 0.01 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.