Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New(?) search idea.

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.09 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.