Opening Moves: Origins of Computer Chess
2.0 Opening Moves
2.1 Early Theorists
2.2 First Tests
2.3 Minimax and Alpha-Beta Pruning
2.4 Getting Going
2.5 Chess Software Basics

Advanced Search



The Minimax Algorithm and Alpha-Beta Pruning

Allen Newell and Herbert Simon at Carnegie Mellon University and Cliff Shaw at the Rand Corporation developed some of the fundamental programming ideas behind all computer chess programs.

The team studied computer chess as part of its larger research interest in Artificial Intelligence, and in 1958 developed the NSS chess program. This program combined “algorithms” (step by step procedures) that searched for good moves, with “heuristics” (rules of thumb) that captured well-known chess strategies to reduce the number of possible moves to explore.

The best chess programming approach combined the “minimax” algorithm with the “alpha-beta pruning” technique. Using minimax, the computer searched a game tree of possible moves and counter-moves, evaluating the best move on its turn and the worst move on its opponent’s turn. Adding the “alpha-beta pruning” technique allowed the computer to ignore or “prune” branches of the search tree that would yield less favorable results, thus saving time. Most two-person game-playing programs use the minimax algorithm with the alpha-beta pruning technique.


Share your thoughts on computer chess in the Forum
Related Collection Materials
forum
resources
feedback
tell a friend
Documents
Computer Science as Empirical Inquiry: Symbols and Search Computer Science as Empirical Inqui...

pdf
 
Images
Aritificial Intelligence pioneers Allen Newell (right) and Herbert Simon Aritificial Intelligence pioneers A...

Herbert Simon Herbert Simon

Artifacts
No Items Found
Oral Histories
No Items Found
Moving Images
No Items Found
Software
No Items Found