C++ minimax function

I have searched Google and Stackoverflow for this question, but I still don't understand how a minimax function works.

I found the wikipedia entry has a pseudocode version of the function:

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

Several other minimax functions I found with Google are basically开发者_开发问答 the same thing; I'm trying to implement this in C++, and this is what I have come up with so far:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

As you can see, I'm pretty confused about this minimax function. Please at the very least give me some hints to help me with this.

Thanks! :)

That sample from Wikipedia is doing NegaMax with Alpha/Beta pruning.

You may be helped by getting the naming straight:

• The basis is MiniMax, a literal implementation would involve 2 methods that take turns (mutually recursive), 1 for each side.

• Lazy programmers turn this into NegaMax, one method with a strategically placed - operator.

• Alpha/Beta pruning is keeping track of a Window of best moves (over multiple depths) to detect dead branches.

Your playerTurn is used to determine whose turn it is . In NegaMax you can derive this from the depth (iterations) being odd or even. But it would be easier to use 2 parameters (myColor, otherColor) and switch them at each level.

Your miniMax() function should remember the best move it found so far. So instead of this code:

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

You should do something like this:

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

Of course, you need a variable "bestMove" and a way to return the best move found to the caller.

Add the playerTurn variable as an argument to miniMax, and call miniMax which the current player's move initially and recursively.

Also, opponentSide needs to be a function of playerTurn.

A good place to start with game tree searching is the chess programming wiki. For your question about the move: I think it is most common to have two max-functions. The difference between the two max functions is that one returns only the score and the other returns the score and the best move. A recursive call order would be like following:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

There are some good papers with pseudocode for the Alpha Beta algorithm:

• TA Marsland - Computer Chess and Search
• J Schaeffer - The games Computers (and People) Play

To your question in the comment: and math.max(alpha,score) or math.min(alpha,score) Is alpha a boolean there?!

No alpha is a window bound in a alpha beta algorithm. The alpha value gets updated with a new value. Because alpha and beta are swapped with the recursive call of the negamax-Function the alpha variable refers to the beta variable in the next recursive call.

One note to the playerTurn variable: The minimax or alpha-beta algorithm doesn't need this information. So i would give the information -- who's next --, into the Board-Structure. The functions findPossibleMoves and boardEval get all information they need from the Board-Structure.

One note to the recursive break condition: If i understand your code right, then you only have the one with iterations == o. I think this means the algorithm has reached the desired depth. But what if there are no possible moves left befor the algorithm reaches this depth. Maybe you should write following:

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

In your pseudocode, the node variable has to contain all the information about the current board position (or whatever). This information would include whose turn it is to move.