Computer Chess Club Archives


Search

Terms

Messages

Subject: An Idiot's Guide to Minimax, Alpha/Beta, etc...

Author: Mike Carter

Date: 17:22:33 02/03/03


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



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