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]

Abstract data types

Interesting topic - I used to follow the definition not unlike given here:
Abstract data type - Wikipedia, the free encyclopedia

But somehow I'm not so sure anymore. The reason is that the separation of interface and implementation - which is a very good idea, don't get me wrong! - makes it difficult to do a thorough complexity analysis of an algorithm that uses this particular ADT.

This cannot be done correctly, unless the operations of the ADT can be analyzed in terms of their intrinsic complexity, at least aymptotically.

Obviously, this depends on the well-hidden implementation of the ADT. E. g. a "Priority Queue" can be implemented in a way that insertion and removal have a complexity of O(log n) or in a way that one of them is O(n) and the other is O(1).

This also raises the question of how to perform an average-case analysis of the surrounding algorithm - would you need to specify the average complexity of the ADT operations as well (e. g. as amortized costs).

Let me see what's around on the subject - there's a 1980 paper by Ehrig and Mahr. Just need to get a hold of it.

Until then