Artificial Intelligence: 3. Minimax on tic-tac-toe

Code: GitHub

Minimax

Minimax is an algorithm which can never lose. Basically what happens here is that it increases its chances of winning and minimises the opponent’s chances of winning.

Max → Min

Min → Max

Max will call min and min will call max recursively. This basically forms a game tree where we have the whole game tree from that particular point.

We award +1 for a win and -1 for a lose and 0 for a draw, and these values will be carried up along the tree.

Basic Steps

- If it is a leaf, return the awarded value (checking the game state)

- At each state check if the game is won by someone, and if done, return the award appropriately

Algorithm:

minimax(board, isMaximising):
if GameIsDone:
if X WON:
return 1
else:
return -1

if BoardIsFull:
return 0

if isMaximising:
return max(value, minimax(board, False)

else:
return min(value, minimax(board, True)

In Max:

Value = Max(value, Min())

In Min:

Value = Min(value, Max())

There might be many +1’s up there in the start of the tree, all might not lead to winning but the least it does is a draw. There is no possibility of losing using this minimax.

Basically we have developed an impossible tic-tac-toe game, in which the user can never win.

I just want to quote geeksforgeeks here: if both the players are playing optimally, then it always ends in a draw.

Minimax using Alpha-Beta Pruning:

This is the same as the minimax algorithm, but in this we have additional values called alpha and beta which will denote the maximum value and minimum value at that particular node respectively.

These values are passes along the tree, both up and down.

Using these values, we will decide if further evaluation is useful in that particular direction.

Algorithm:

minimax(board, isMaximising, alpha, beta):
     if GameIsDone:
        if X WON:
            return 1
        else:
            return -1
if BoardIsFull:
        return 0
if isMaximising:
        best = max(value, minimax(board, False, alpha, beta)
        
        if alpha < best:
            alpha = best
        if beta <= alpha:
            break
        return best
else:
        best = min(value, minimax(board, True, alpha, beta)
        if beta > best:
            beta = best
        if beta <= alpha:
            break
        return best

Additional Pruning:

In Max:

Update value if the return value is greater

Update alpha if the return value is greater

In Min:

Update beta if the return value is smaller

Prune (cut-off) if beta <= alpha

Minimax and Minimax with alpha-beta pruning give the same output, even though the evaluated nodes are very less when pruning technique is used.

Important Observation: both minimax and minimax with alpha-beta pruning take steps in a direction that leads to winning, but both of those will not take an action that is best logical at that point. E.g., if there is a move that can lead to winning in that stage, it is not assured that it will take that move.

Proof:

Now, if we analyse the mentioned game played, User starts first chooses the location (0, 0), and then the algorithm chose (2, 2) followed by (0, 2) move of the user. At this stage, the algorithm can win the game directly at this stage itself by placing the X at (2, 1), but instead, it kept at (1, 2). Obviously this depends on implementation, but then too, these kind of cases are inevitable.

But do not fret, the algorithm never fails, even though it didn’t choose a smart move at that stage, whatever move it choose will definitely lead to its win.

Assumptions:

- Location should be entered as x,y combination