Author: Eelco de Groot
Date: 12:07:22 08/03/99
Go up one level in this thread
On August 03, 1999 at 10:24:34, Robert Hyatt wrote: >On August 03, 1999 at 09:00:31, Eelco de Groot wrote: > >> >>On August 02, 1999 at 20:21:10, Robert Hyatt wrote: >> >>>On August 02, 1999 at 12:39:33, J. Wesley Cleveland wrote: >>> >>>>On August 02, 1999 at 09:19:29, Robert Hyatt wrote: >>>> >>>>>On August 02, 1999 at 06:25:19, José Carlos wrote: >>>>> >>>>>> Maybe discarding "bad enought moves" (considering a fixed minimum difference >>>>>>beteewn first and second move), or the mate-test mentioned could help much in >>>>>>quick games. >>>>>> It could be interesting using such idea in games faster than 5min/game. >>>>>> >>>>>> José C. >>>>> >>>>> >>>>>There are two obvious problems with this: (1) discarding 'really bad' moves >>>>>doesn't help... because most use a time-limit for their search. And discarding >>>>>a few moves at the root doesn't help other than we might barely get one ply >>>>>deeper than normal; (2) Rememeber that in the position I posted, Bxh6 looks >>>>>"really bad" at ply 1, 2, etc.. because Qxb6 wins a piece, Bxh6 loses a piece. >>>>>A difference of 6, roughly... So discarding this move because it looks bad >>>>>would be a big mistake... >>>> >>>>My idea about "forced moves", is to set the search time to 1/3 (more or less) >>>>the normal, window to (very bad, -infinity), search all moves except the forced >>>>one, if any moves returns a score better than "very bad", start over with a >>>>normal search, or else make the forced move without searching it. The idea being >>>>if all other moves lose, make the one that looks good, and if it is bad, you >>>>haven't lost much. >>> >>> >>>This is exactly the sort of approach that killed me in 1981. Because all of >>>the other moves look bad when compared to the 'best' move. Because the best >>>move wins a piece instantly. None of the other moves appear to do so. And >>>they _never_ do so. But if you search this 'best' move long enough you realize >>>it loses, and then the other moves are better... >> >>Hello Mr Hyatt! >> >>Sorry if I am completely missing the point here, Robert? I never tried any >>chess-programming myself, so this is just somewhat of a bystanders view: >> >>In the above approach, don't you spend most of the search on the bad-looking >>moves? Because you make a move *instantly* if the other moves prove bad? Why >>can't you make a case for the opposite view, to spend more time on the promising >>move, "deepening" it, just to check if it is really that good? That principle >>wouldn't suddenly not apply if it is an "easy" move. The sooner you find out the >>earlier you can switch to another move or decide to make the move on the board. >> > >I can only speak for Crafty, but it spends more time on the move it is going >to play than it does on all the other moves combined... > >the crux here is can we play an 'obvious' move quicker than normal. IE if the >target time is 3 minutes, can we play an obvious move after only one minute of >searching. > > > >>I always thought that the main point of doing all the iterations on the >>different plydepths is to (a) try to steer the most promising rootmove to the >>top of the rootmove list and (b) because you can never be sure that the most >>promising move is actually the best move, to order the rest of the rootmoves as >>best as you can so that you know where to look for a new candidate. > > >close to correct. The goal is to search all the moves as deeply as possible >to find the best one. Iterated search helps this by providing better move >ordering... > > > >> >>Because any profit you make with alpha-beta is at the expense of (b) it would >>seem to make some sense to do "less" alpha-beta if you really can't be to sure >>of your principal move. And that is the case in the first iterations so why not >>try to do less alpha-beta cutoffs there somehow. > > ******************************************************************************************* Robert, thank you for your comments. I still don't completely see this part. I mean, yes the same result for (a), but I thought not for (b)? And therefore also not the same result if you compare iterated alpha-beta with iterated minimax where both operate under a timelimit and can't make a full search? That would be my point, if there is one. That move ordering will suffer if you do a lot of alpha-beta cutoffs. ****************************************************************************************** >alpha/beta isn't a problem, ie it provably produces the same result as a pure >minimax search... so that isn't the issue... it is the question of how to >_really_ discover that a move is 'obvious'. and how to do this reliably to >avoid stopping a search just before you get deep enough to see your best move >(that appears to be obvious) really loses.. > > > >> >>The fact that there seems to be an "easy" move just means that there is a >>somewhat higher probability that you can achieve (a). So why not spend some of >>the expected profit of lots of alpha-beta cutoffs at deeper iterations on (b)? >>The search speed goes down enormously but you can afford it at shallow >>plydepths. And at greater plydepths the chances are that there have been some >>changes at the top of the the movelist so that means that there are likely >>better variations available then for the second-best move etc. Because at one >>time they may have been the principal move. And if you spend more time on >>"deepening" the principal move on shallow plydepths by whatever means, more >>quiescense search or whatever, these variations only get better. The move >>ordering gets better this way. >> >>And I don't really see why all this applies only at the root. >>If deeper in the tree you see a promising move you can expect more alpha-beta >>cut offs. So go a little deeper on this promising move and if it holds try to do >>some more move ordering at that branch. Then continue with the standard >>alpha-beta for the second move at that branch. But first you have to check the >>most promising move. >> >>Could you please shoot some holes in this? Thanks! >> >>Eelco. > >Your last idea is 'selective' and there is nothing wrong with it, except that >it definitely introduces an 'error' term into your search. How big depends on >how you define which moves get searched deeper and which don't... > >I don't do that sort of pruning, but nothing says it is bad if done well.
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.