C ++ minimax function

Question

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

I found that the entry on wikipedia 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 α 

A few other minimax features that I found with Google are basically the same; I am 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 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 am rather confused by this minimax function. Please at least give me some tips to help me with this.

Thanks!:)

Answer 1

This Wikipedia sample makes NegaMax alpha / beta cropped.

It can help you by getting the name:

• The foundation is MiniMax, a literal implementation will include 2 methods, which in turn (mutually recursive), 1 for each side.

• Lazy programmers turn this into NegaMax, one of the methods with a strategically located operator - .

• Alpha / beta cropping tracks the best moves window (at several depths) to detect dead branches.

Your playerTurn used to determine your move. In NegaMax, you can get this from a depth (iterations) that is odd or even. But it would be easier to use 2 parameters (myColor, otherColor) and switch them at each level.

Answer 2

Your miniMax () function should remember the best move it has found so far. Therefore, 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 the variable "bestMove" and a way to return the best move to the caller found.

Answer 3

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

In addition, opponentSide must be a playerTurn function.

Answer 4

A good place to start your search for the game tree is the wiki chess programming . To your question about this movement: I think that two max functions are most common. The difference between the two maximum functions is that one returns only the score, and the other returns the score and the best move. The recursive call order will look like this:

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

There are some good pseudo-code documents for the Alpha Beta algorithm:

• TA Marsland - Computer Chess and Search
• J Schaeffer - Games for computers (and people) .

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

There is no alpha window bound in the alpha beta algorithm. The alpha value is updated with the new value. Because alpha and beta exchange a recursive call to the negamax function, the alpha variable refers to the beta variable in the next recursive call.

One note for the playerTurn variable: minimal or alpha-beta algorithm does not need this information. Therefore, I would provide information - who is next - to the Board-Structure. The findPossibleMoves and boardEval functions get all the necessary information from Board-Structure.

One note on the recursive interruption condition: if I understand your code correctly, then you will only have iterations == o . I think this means that the algorithm has reached the desired depth. But what if there are no possible steps left before the algorithm reaches this depth. Perhaps you should write the following:

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

Answer 5

In your pseudo-code, the node variable should contain all the information about the current position of the board (or something else). This information will include in whose turn it should move.