How to make minimax optimal? By optimal I mean that:


If max has a winning strategy then minimax will return the strategy for max with the fewest number of moves to win.
If min has a winning strategy then minimax will return the strategy for max with the most number of moves to lose.
If neither has a winning strategy then minimax will return the strategy for max with the most number of moves to draw.


The idea is that you want to win in the fewest number of moves possible but if you can't win then you want to drag out the game for as long as possible so that the opponent has more chances of making mistakes.

So, how do you make minimax return the best strategy for max?
Minimax deals with two kinds of values:


Estimated values determined by a heuristic function.
Actual values determined by a terminal state.


Commonly, we use the following denotational semantics for values:


A range of values centered around 0 denote estimated values (e.g. -999 to 999).
A value less than the smallest heuristic value denotes a loss for max (e.g. -1000).
A value more than the biggest heuristic value denotes a win for max (e.g. 1000).
The value 0 denotes either an estimated draw or an actual draw.


The advantage of this denotational semantics is that comparing values is the same as comparing numbers (i.e. you don't need a special comparison function). We can extend this denotational semantics to incorporate optimality of winning and losing as follows:


A range of values centered around 0 denote estimated values (e.g. -999 to 999).
A range of values less than the smallest heuristic value denote loss (e.g. -2000 to -1000).
A range of values more than the biggest heuristic value denote win (e.g. 1000 to 2000).
The value 0 denotes either an estimated draw or an actual draw.
A loss in n moves is denoted as -(m - n) where m is a sufficiently large number (e.g. 2000).
A win in n moves is denoted as (m - n) where m is a sufficiently large number (e.g. 2000).


Using this denotational semantics for values requires only a small change to the minimax algorithm:



function minimax(node, depth, max)
    if max
        return negamax(node, depth, 1)
    else
        return -negamax(node, depth, -1)

function negamax(node, depth, color)
    if terminal(node)
        return -2000

    if depth = 0
        return color * heuristic(node)

    value = -2000

    foreach child of node
        v = -negamax(child, depth - 1, -color)

        if v &gt; 1000
            v -= 1

        if v &gt; value
            value = v

    return value


Incorporating optimality for draws is a lot more difficult.