[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-gnubg] [Fwd: gnubg search function]

From: Thomas Hauk
Subject: Re: [Bug-gnubg] [Fwd: gnubg search function]
Date: Thu, 27 Mar 2003 12:22:53 -0700 (MST)

On Fri, 28 Mar 2003, Joseph Heled wrote:
> Would you care to enlighten us a little more, say by explaining how it 
> would speed up a 1ply search? Just a rough idea would do.

The algorithm wouldn't speed up a 1-ply search; at 1-ply, all children of 
the root node are guaranteed to be expanded (because it is a max node). 
The benefits of search algorithms like alphabeta and *-minimax is they 
reduce the complexity of deep searches.

Alphabeta uses upper and lower bounds on what can be acheived to create 
cutoffs. For example, if you are searching in a part of the tree where 
you have a move that guarantees you a score of at most 10, but you 
already know of a move that will guarantee you a score of 12, then you can 
cut off search there because there's no sense looking around for a move 
worse than you already have.

*-minimax works on the same principle, but uses a weighted sum of the 
moves beneath a chance node to determine upper and lower bounds.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]