pseudcode for minmax algorithm

Question

I want to get the pseudocode for minmax algorithm. I have to make 2 functions, def maxAgent(gameState, depth) and minAgent. Is there any body who has the right and easy pseudocode for it.

Answer 1

The minmax algorithm tries to maximize the score for player A and minimize the score for player B. Given a node, you can find the final outcome from optimal play by taking the max (for A) or min (for B) of the score for successor nodes.

Assuming that the leaf nodes have an assigned winner (1 for A, -1 for B) while all other nodes have a score of 0. You can then compute the final winning outcome for A with something like

  getMaxScore(node) {
    score = node.score;
    for each child node 
       score = max(score, getMaxScore(node))  
    next

    return score;
  }

This is the basic algorithm. You can short-circuit the evaluation as soon as the score becomes 1 then you have a known win for A.

The algorithm is the same for B, getMinScore, only you use the min function, and if short-circuiting, look for -1.

Answer 2

Two players, A and B, take turns to play.

We are given a scoring function f that evaluates a given board position, P. Larger values of f(P) are better for A and worse for B (i.e., f(P) is an estimate of how "good" P is for A without doing any further lookahead).

Consider a board position P.

If P is a leaf node (i.e., P is a winning position or we have looked as far ahead as we want to) then we return f(P) as the score for this node.

Otherwise P is not a leaf node and has children C1, ..., Cn. We recursively compute the scores for the children, giving S1, ..., Sn.

If A plays at P then the score for P is max{S1, ..., Sn} since A will always play to maximise his advantage.

If B plays at P then the score for P is min{S1, ..., Sn} since B will always play to minimise A's advantage.

That should be enough to turn into code.

Once you've done that, have a look at alpha-beta pruning, which should (drastically) reduce the amount of search you need to do. Alpha-beta pruning is based on the idea that if A deduces that B can play to force A's maximum advantage to be M, then there is no point in considering any subtree whose score is greater than M since B will never allow A that option!