How to make minimax optimal?
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.