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

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!