How does minimax work?

Question

Here's the case. I'm trying to make a Chess engine. Not that I believe that I can make anything better than what's already out there, but I want to see how it works. I've made some of the important parts, such as board representation and the evaluation function. The evaluation function seems to produce decent results, so now I need to implement the search (minimax?) function. I won't be doing any kind of transposition tables, book openings etc. yet, but I want to do a full-width search for a reasonable depth (say 4 plies). How do I do that?

The important functions and types that are available to you, my dear Stack Overflow-helper, are:

type
  TMoves = record
    Move : integer; //Bit-encoded,6 LSB=To,6 next=From,3 next=Promote to 
    Score : integer;
  end;

  TMoveList = class
    //Regular list with an iterator - for TMove in TMovelist do ... etc
  end;

  TChessBoard = record
    <snip>
    procedure SetInitialPosition;
    procedure GenerateLegalMoves(aList : TMoveList); 
    procedure DoMove(aMove : TChessMove); //Doesn't use the score-part, obviously
    property Turn : TChessColor; //ccWhite or ccBlack
    function WhiteInCheck : boolean;
    function BlackInCheck : boolean;
  end;

  //Evaluate Returns >0 for white advantage, <0 for black advantage
  function Evaluate(aBoard : TChessBoard) : integer; 

Now I want to implement this function

function BestMove(aBoard : TChessBoard; aMaxDepth : integer) : TMove;

and probably a helper-function or two (preferably just one)

I've read about minimax on Wikipedia, but I just don't understand it. It's not that it's recursive, I get that, but there's something mystical going on that I don't get. And since I don't understand it, I turn to Stack Overflow :-) Could someone please explain this function for me? I want it to be very simple, and no "smarty stuff". No optimizations, transposition tables, pruning etc, just a function to evaluate every possible move up to given depth (and, yes, I know there will be many nodes for depths above about 4 plies)

Thanks in advance. Whoever helps me will receive a fair share of the sales of the finished game. We're potentially talking billions of dollars here ;-)

Answer 1

It looks like you've already got everything you need, except a function to determine whether you're at a terminal node, which in chess is checkmate. Trying to adapt the idea from the pseudocode in Wikipedia here:

function minimax(node: TChessBoard; depth: integer): integer;
var
  moveList: TMoveList;
  child: TChessBoard;
begin
  if (node.CheckmateExists) or (depth = 0) then
    result := Evaluate(node)
  else
  begin
    result := low(integer);
    moveList := TMoveList.Create;
    try
      node.GenerateLegalMoves(moveList);
      for child in moveList do
        result = max(result, -minimax(child, depth-1));
    finally
      moveList.Free;
    end;
  end;
end;

Also, your TChessBoard should probably be an object, not a record, or this is going to be very slow because you'll be copying a lot of memory around.

This is actually pretty straightforward if you can wrap your head around the recursion involved. Does seeing it in a familiar language make the concept any clearer for you?

Answer 2

What you are trying to do is a great exercise and you'll have fun with it.

The concept of minimax is simple. In a two player game, player 1 is trying to maximize his score and player 2 is trying to minimize.

At the bottom of the Wikipedia article you found is the "See Also" section, containing:

• Alpha-beta pruning
• Claude Elwood Shannon
• Computer chess
• Expectiminimax
• Horizon effect
• Maximin
• Minimax
• Condorcet
• Minimax
• regret
• Transposition table

Follow up all of these, but the most important of them is Alpha-beta pruning. It is the algorithm that will mathematically reduce the magnitude of the brute force search to a square root of itself.

As far as code goes, of course it depends on your language. But the best description and pseudo code of minimax and alpha-beta can be found at this McGill University Computer Science page: http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/ Their listed code is fairly simple:

    evalutemin(u,  B) //u is a min node 
    {
                    Alpha=+infinity; 
                    if u =leaf return the score;   
                    else  
                             for all children v of u
                             {  
                                    Val = evalutemax(v,  B); 
                                    alpha= Min{alpha, Val}; 
                                    if  Alpha<=beta  then exit loop; 
                              }                                  
                    Return alpha; 
}

    evalutemax(u,B)   // u is a Max node 
    { 
                            alpha=-infinity; 
                             if u=leaf return the score; 
                             else 
                                    for all children v of u
                                    { 
                                        Val = evalutemin(v, B); 
                                        Alpha = Max{Alpha, Val}; 
                                        if Alpha >= Beta then exit loop; 
                                    }
                             Return Alpha; 
      } 

But you will reach your limit, and you won't beat the best programs available with your own brute force algorithm. They've been at it for decades and use all the tricks in the book. The undisputed current computer chess champion Rybka is now much better than the world's best human player with (as I write it) an ELO rating of 3570. Compare that to the top rated humans who go up to the 2800's.

So what to do about your magic "BestMove" routine?

I suggest you try something that will give you hope. I have some unfinished work and challenges to chess programmers that I'd love to see someone attempt. The first section on "The Search Algorithm" will be of interest to you. But it is specifically the last section: "The Evaluation Routine" that I think you should look at. I believe it might give you a chance. You will need to incorporate or modify a version of the B* search algorithm developed by Hans Berliner that he had used in his program HiTech, and add my ideas of maximizing ties and minimizing opponent's mobility. There is very little available today about that algorithm. You'll have to do some research.

Finally, as a Delphi programmer, you'll want to check out the free Chessboard Component available at: http://www.resplendence.com/chessbrd

It is freeware with source written for Delphi 2 - 7. It includes Tom's Simple Chess Program which was translated into Pascal and added to the compenent. I haven't looked at that myself, but I'm sure it will give you a few tips and most likely already has the alpha-beta algorithm (and maybe a few other speedups) programmed into it as well.

Finally I recommend my Chess and Computer Chess Links for more good references.

I hope this helps.

Have fun and good luck!