Author: Dave Gomboc
Date: 08:26:43 08/21/00
Go up one level in this thread
On August 21, 2000 at 04:10:01, José Carlos wrote: >On August 20, 2000 at 20:12:02, Uri Blass wrote: > >>On August 20, 2000 at 18:44:04, Georg v. Zimmermann wrote: >> >>>On August 20, 2000 at 18:29:06, José Carlos wrote: >>> >>>>On August 20, 2000 at 18:15:48, Robert Hyatt wrote: >>>> >>>>>On August 20, 2000 at 16:13:22, Frank Phillips wrote: >>>>> >>>>>>Can anyone sketch out the singular extension algorithm. I found some general >>>>>>information on the net, but nothing that helps me understand how to implement it >>>>>>in a PVS alpha/beta search. Descriptions tended to mention only that it is >>>>>>invoked when there are only a few good moves in a variation. Since alpha/beta >>>>>>does not yield the value of moves other than the principal variation, I am not >>>>>>sure what this means in practice. >>>>>> >>>>>>Frank >>>>> >>>>> >>>>>The simple case is on the PV search. When you search the first (and >>>>>hopefully best) move at each ply, you search the remainder of the moves >>>>>with alpha-w, beta-w, where w is some window offset (say 1/2 pawn). If >>>>>all the other moves still fail low, then the 'best' move is better than >>>>>the remaining moves by at least 1/2 ply. You re-search the 'best' move >>>>>one ply deeper. >>>>> >>>>>Ie some programs search deeper if there is only one legal way out of check. >>>>>Suppose there are three legal ways out, but two of them drop all kinds of >>>>>material. There is only one "reasonable" move and singular extension will >>>>>follow it more deeply than the other two 'silly' moves... >>>> >>>> This suggests me an idea, I don't know if it has been tried: >>>> >>>> Suppose you've searched all moves at depth d. Then, at depth d+1, the PV move >>>>has a bigger value then at d. In that case, you could simply go to d+2 without >>>>looking at the rest of the moves. >>>> Only when the PV value drops down at any depth, search the rest of the moves. >>>> >>>> Just a thought... >>>> >>>> José C. >>> >>>This seems flawed to me >>> >>>1.) Lets say at ply7 you think position is equal at ply8 the first move searched >>>turns out to win the queen, but the second would mate ? Why skip it ? >> >>If both moves win then it is not important. >>The important case is when you have not a win with move A and have a win with >>move B. >> >>I do not say that the idea is practically good but I understand the reason for >>the idea. >> >>If the pv has a bigger value the chances to find a better move are smaller so >>instead of wasting time in searching the rest of the moves it may be better to >>save time by not searching them. >> >>The problem with the idea is that it is also correct that when the pv has bigger >>value you search less time the rest of the moves so the gain is also smaller >>from not searching the rest of the moves and not only the loss(in cases that >>another move is better. > > Yes, exactly. But what I was thinking about is that, if the PV value increases >(assuming you have a 'good enough position'), the rest of the moves are not >likely to give a big improvement, but if one of them is, say 0.03 better, then >you fail high and have to research with a wider window, just to find you have a >very small improvement. > Probably this idea only makes sense in won positions, or positions with a >clear advantage, where you want to make sure the move you are gonna play doesn't >have a hidden trick. Then, you go much deeper with that move than with the >others. If nothing strange happens, you can play it and you know you're gonna >win. > There can be a better move, of course, but you'll win anyway. > > José C. > >PS.: I'll try it in Averno when I have some free time :) > >>>2.) If I go to d+2 with move1 immediately the other moves will not get better >>>sorted. >>> >>>3.) The first move takes longer to search than the others anyway. >> >>It is not always the case but usually it is the case when the pv gets a bigger >>value and it is the problem with the idea. >> >>There are some cases when programs search the first move for a short time and >>waste almost all the time in other moves(mainly when there is a transition to a >>simple endgame) and I think that in this case it may be a good idea to search >>the first move to a bigger depth than the other moves. >> >>Uri If you're worried about wasting time searching a move that might only be very slightly better, then use an artificially-high lower bound for your window. Dave
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.