Author: Robert Hyatt
Date: 05:09:53 01/22/98
Go up one level in this thread
On January 22, 1998 at 01:17:32, James Long wrote: >On January 22, 1998 at 00:10:41, Andrew Walker wrote: > >>On January 21, 1998 at 23:54:49, James Long wrote: >> >>>On January 21, 1998 at 22:27:42, Andrew Walker wrote: >>> >>>> Here's an idea I came up with recently, it may be old news >>>>but I've never heard of it being used so here goes: >>>> >>>> One thing I've noticed with chess programs (mainly at a fixed time per >>>>move) is that often the search will stop when they have spent ages >>>>considering the main move, or when several replys to a none best >>>>move have been examined and it looks like it may become the new best >>>>move. Generally the best thing that can happen in a search is when a new >>>>move becomes the main move and with a reasonably higher evaluation. >>>>So we would like this to happen sooner if at all possible. >>>> The way searches normally work is that when the depth is increased, the >>>>best move will be searched first. My idea is to search >>>>all of the other moves first. >>> >>>When searching, it is important that the correct move be very close >>>to the top of the list. This way, all other moves will be cut off >>>with minimal work. If you searched in the opposite direction, you >>>would get absolutely no benefit from a/b cutoffs. >>> >> Did you read the next paragraph of my post? As I have said, the >>alternate moves may be all cut off! >> >>>> Lets say a depth 6 search has been done for white and the best move is >>>>e2-e4 with a score of +0.1. What we could do is start the depth 7 search >>>>looking at all moves except e2-e4, and make them try to beat a score of >>>>0.1+c, where c is a small positive constant such as 0.2. >> > >Yes I did, but it doesn't make sense. The first move you search in >any branch of the tree will be searched exhaustively. Hopefully that >one was correct, because if another move comes along that is better >it too will be searched exhaustively. > >You stated before that the best thing that could happen in a search >is for a new move to become the best move. That's not true. The >best thing that could happen is for the first move to remain the >best move. > >Instead of arguing over this, let's see some data. I'd be >interested to see what happens. > >-- >James I interpreted this a bit different: the reason for doing a depth N+1 search is to discover that your depth N move is not best and there is something better to play. Intuitively obvious when you think about it, otherwise there's no point in doing the n+1 search. Of course, for efficiency we hope it doesn't change as that produces a much smaller tree, faster, but if it *never* changed its mind, we'd be doing searches for nothing... So in this case, the N+1 search is a sort of validation of the N ply search... But I don't want to change my mind because it is very expensive to do so, in terms of total nodes searched. To see this, watch how long the first move at a new depth takes to search and then how fast all the other ones are dismissed. Except when the first gets replaced by one of the later moves on occasion. Then that non-first move takes just as long (or longer) to search as the original best move.
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.