Chess Search Algorithms 1: Minimax Search

Here's a series of little things I wrote around 10 years ago. Maybe it's time to resurrect them. You probably would have guessed that from the Pascal-ish pseudocode anyway.

It's all about basic Chess Search Algorithms - I wrote that mainly because I never felt too comfortable with the way they're coded in text books. Here "ref" before a parameter means that it should be passed by reference making it an out or in-out parameter; everything else is a value parameter.

1. MiniMax

Minimax search embodies two almost identical routines for the maximizing and minimizing player. It's usually less useful than NegaMax search (next issue), since you have two pieces of code to maintain. Watch out, to make sure it works always evaluate from the max player's side - this will change with NegaMax!

bestVal: best value for max/min player
bestMove: best move leading to this value

Maximizing level

procedure maxSearch(ref bestVal,
                   ref bestMove)
if atLeaf then
 // leaf: static evaluation
 // from maxPlayer's side
 bestVal := evalu8(maxPlayer)
else
 // generate successor moves...
 generate(moves,nMoves)
 // ...and preset return value
 bestVal := -infinity

// loop over all moves
for i := 1 to nMoves do
  // execute move and call min player
  makeMove(moves[i])
  minSearch(succVal,reply)
  // take back before continuing
  retractMove(moves[i])

// compare returned value: update value/move
if succVal > bestVal then
  bestVal  := succVal
  bestMove := moves[i]

Minimizing level

procedure minSearch(ref bestVal,
                 ref bestMove)
// really (almost) identical
if atLeaf then
  // always evaluate from maxPlayer's side
  bestVal := evalu8(maxPlayer)
else
  generate(moves,nMoves)
  bestVal := infinity

for i := 1 to nMoves do
  makeMove(moves[i])
  // now call the max player
  maxSearch(succVal,reply)
 retractMove(moves[i])

if succVal <  bestVal then
  bestVal  := succVal
  bestMove := moves[i]