Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Search algorithms in chess programs

Author: Christophe Theron

Date: 09:35:35 12/13/01

Go up one level in this thread


On December 13, 2001 at 10:13:32, Uri Blass wrote:

>On December 13, 2001 at 09:17:23, Josť Carlos wrote:
>
>>On December 13, 2001 at 03:47:39, Uri Blass wrote:
>>
>>>On December 13, 2001 at 03:33:07, Wylie Garvin wrote:
>>>
>>>>On December 12, 2001 at 23:27:58, Russell Reagan wrote:
>>>>
>>>>>Depth-first search is usually what is used in chess programs (at least all that
>>>>>I have seen source for). What are the drawbacks of other search algorithms such
>>>>>as breadth-first and best-first that prevent them from being more widely used in
>>>>>chess programs?
>>>>
>>>>speed and space requirements.  Keep in mind that since nearly all chess programs
>>>>use iterative deepening on their depth first searches
>>>
>>>Nearly all?
>>>I doubt it.
>>>There are a lot of weak chess programs that do not use this technique.
>>>
>>>One of them (TSCP) even could win a tournament of weak programs that Dan Corbit
>>>made.
>>
>>  TSCP _does_ iterative deepening. Iterative deepening means: first search with
>>depth = 1, then search with depth = 2, ... and so on.
>>  I don't know of any program that do fixed ply search with no iterative
>>deepeing. Sure there must be some, but not that I know of.
>>
>>  Josť C.
>
>Yes
>You are right
>I looked at bruce web site of Gerbil and find the same definition.
>
>I thought that it means something else about order of moves when in order to
>decide which move to try next you do a search to reduced depth.



You were close. What you describe above is called "Internal iterative
deepening". That's a reduced search you do at a node when you have no idea of
what the best move can be at this node. In this case it is better to do a short
search in order to "sniff" the best move. It improves your move ordering at that
node and is supposed to save time, even with the extra work needed by the short
search.



    Christophe




>What is defined as iterative deepening is exactly what is defined intuitively by
>me as depth first.
>
>First depth 1,second depth 2...
>
>I see that I probably understand nothing from what was explained and I also do
>not understand what is the meaning of depth first.
>
>I also did not understand much from the reply to my post when I asked about the
>other techniques.
>
>I will be happy to see chess trees that demonstrate the techniques that were
>discribed in the first post instead of definitions that part of them are also
>based on things that I do not understand.
>
>Uri



This page took 0.02 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.