Author: Bruce Moreland
Date: 10:19:48 02/04/03
Go up one level in this thread
On February 03, 2003 at 20:22:33, Mike Carter wrote:
>I am writing a chess engine in QuickBasic - I have an ancient DOS(!) compiler -
>and have a question re: the subject line. I've seen some pretty comprehensive
>discussions/papers on the above topics (usually in pseudo-C) but I still don't
>fully understand the concepts (be patient, my degree is in statistics and not
>computer science) and I am looking for a *very* basic description of the general
>chess program algorithm.
>
>For example: first you generate moves, then sort them... I'm fine up to here.
>When I try to evaluate, my crude attempts to prune the tree fall way short of
>other methods and I'm left with hundreds of thousands of nodes for 3 to 5 ply.
>My gut feeling is, with alpha-beta, I might have 20K nodes to examine at that
>ply.
>
>The main question: in simple terms, how do I use alpha/beta?? How often do I
>evaluate? Do I take each root move, generate moves to a certain ply (say 5),
>then evaluate? Even if this gives me a score that ultimately is the PV, don't I
>still have to at least check one node at ply 5 for all the other branches
>(assuming an average of approx. 35 legal moves, that's still 35^4... 1.5
>million nodes!). I *know* I'm missing some fundamental aspect of a/b... if
>someone could provide a clear, very high-level description it would be greatly
>appreciated! Thanks!
>
>Mike
http://www.brucemo.com/compchess/programming/index.htm
This is basic min-max. It has been set up so that it thinks that each side is
the maximizing player, in order to make it more compact. This just generates
moves and recurses on each one, until it runs out of depth, at which point it
calls an eval function and returns.
int NegaMax(int depth)
{
int best = -INFINITY;
if (depth <= 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -NegaMax(depth - 1); // Note the minus sign here.
UnmakeMove();
if (val > best)
best = val;
}
return best;
}
This is alpha-beta. Note that there is very little difference. All it is doing
is stopping early if it has proven that the node it is processing will not be in
the principle variation (the expected "best" line) when the search completes.
With poor move ordering, branching factor is still 35. With perfect move
ordering, branching factor is approximately 6. This means that you search twice
as deep in the same time.
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}
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.