Author: José Carlos
Date: 09:04:10 08/21/00
Go up one level in this thread
On August 21, 2000 at 11:26:43, Dave Gomboc wrote: >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 Mmmm, sounds interesting for positions with clear advantage/disadvantage, where what you want to discover are big changes in the eval. José C.
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.