Author: Ian Osgood
Date: 14:35:27 07/30/99
Go up one level in this thread
On July 29, 1999 at 20:54:08, Bruce Moreland wrote: > >On July 29, 1999 at 18:58:12, Ian Osgood wrote: > >>Do other program authors curtail the search when there is a forced move at the >>root? >> >>How do you detect that a root move may be forced? >> >>Could you compare the values of the best and second-best root moves after a >>search iteration to detect a forced root move? (Granted, the second-best score >>won't be accurate due to alpha-beta, but I figure that if the difference was >>greater than a queen's value, you could still conclude that the best move was >>forced.) > >The only sure way to do this is if there is only one legal move. So this would be considered root processing? Or is this detected at each iteration as you detect longer mate lines for alternative moves? I'm a bit unclear about the alpha-beta return value: if your search of a non-PV root move to depth N leads to mate in M<=N or cutoff in all branches searched, will a near-mate score be returned, or will a near-alpha score be returned? Would other types of searches return a near-mate score in this case? >Any other technique is going to leave you open to cases where you can make >mistakes, and I'm sure there are cases where you'll miss a win or make a losing >move, and you won't do this if you'll think longer. > >If you decide that you can live with walking into losses and missing wins, the >first question is why did you decide that you can live with this. > >One reason is to impress the humans, or avoid having them call you stupid. This >is a valid reason, in my opinion. Very perceptive! I am concerned in this case with consumer-level play rather than championship-level play. I think that many humans are annoyed when a computer doesn't make an "obvious" forced move quickly. In fact, an occasional blunder because of a quick recapture may be judged as human-like play! (One could allow such behaviour to be disabled for a championship style of play.) >Another reason is that you save time on the clock this way, and in a computer vs >computer game with both sides thinking on the opponent's time, you could >initiate a sequence of instant moves this way, rather than walk into a situation >where your opponent has a sequence of instance moves. I don't know if the >strength gain is higher from catching mistakes, or having extra time or going >for an instant-move sequence, but I'll bet on the latter. Which was latter? This brings up another thorny issue: good humans have an intuitive grasp of the difficulty of a position, choosing to spend less time on easy situations and more time on difficult or critical ones. Has anyone come up with a model for this which a computer could understand as an aid to time allocation? Or do you think this is a false distinction? >Now the question is deciding what is forced. An obvious clue is that the search >sticks with one move more or less forever. Another clue might be that all of >the other moves can be refuted in a small amount of time, but I haven't >experimented with this. And if you need to restrict this because you are doing >forced moves that aren't really forced, you can restrict it so that you only do >this if the program wants to make a recapturing move. > >bruce I remember a discussion of search tree branch size as a move-ordering heuristic. I wouldn't think it would be useful, because you might not get to the bad result in a refuted branch until late in the search of that branch. I would think that recapturing is too narrow a measure. Wouldn't any unique move which prevents a large score drop be considered forced? This might include protective moves, capture avoidance, zwischenzug checks, etc. I also realize that you have to define "forced" in the context of a particular search depth. (Thanks for all the responses! This is an interesting discussion.) Ian
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.