Author: Don Dailey
Date: 10:33:42 01/22/98
Go up one level in this thread
Hi Andrew, The only reason the first move takes longest to search is because it is carrying all of the burden. You can shift the responsibility to other moves but you cannot get something for nothing. At some point you will have to come back and resolve the first move or ignore it in which case you are prunning the tree. (this is not something for nothing.) If you are a gambler then you can get something for nothing on individual attempts but not in the long run. Your idea is likely to occasionally pay off (in individual searches) but not in the long haul. If you are content to get a best move only without a correct score then you can get some minor speedups but there is probably no point to searching non-best moves first to accomplish this. Even in this case you are not getting "something for nothing", you are accepting the tradeoff of not knowing the correct score which you may very well be willing to do. It's refreshing to see people thinking about algorithms. I will be interested in hearing more ideas from you. By the way, I use an algorithm called mtd(f) and there is no concept of a "window" in the search itself (just the search driver.) All searches return quickly and are guaranteed to fail! In some sense the same moves get searched over and over on the same iteration although the hash table tends to avoid most of this work (except when it is needed to prove a point.) The search driver is tricky piece of code and the obvious approach is quite bad (don't use a binary search mtd probe strategy!) The thing I hate about mtd is the data returned is so different from a conventional program. You cannot get a nice list of moves showing progress and the pv appears many times (usually modified) each time. Even though I have good root move ordering I stopped thinking about it with mtd(f). Your ideas almost sounded foreign to me because of this! Massaging my root move list would clearly be a problem for efficiency. MTD is so good I cannot imagine using anything else though. I am getting over 15% speedup over my very best implementation of pvs search (margin on first move, zero width on siblings with research on fail hi's) I prefer PVS's behavior but cannot ignore the extra performance of MTD(f). The (f) refers to the type of driver used. I don't strictly use the 'f' driver because I found some enhancements of my own but it's basically mtd(f) - Don P.S. Keep posting. 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
This page took 0.12 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.