Recursive Minimax Function returns None instead of optimal score

Question

I'm simply working on a Minimax algorithm that can play TicTacToe, For some reason the max_value and min_value functions occasionally return None.

def player(board):
    if Terminal(board) != False:
        return None
    else:
        if turn(board) == "X":
            value,move = max_value(board)
            return move
        else:
            value,move = min_value(board)
            return move
        
def max_value(board):
    if Terminal(board) != False:
        return Utility(board),None
    else:
        v = -1000
        move = None
        for action in Actions(board):
            aux,act = min_value(Result(board,action))
            print(aux)
            if aux > v:
                v = aux
                move = action
                if v == 1:
                    return v,move
        return v,move

def min_value(board):
    if Terminal(board) != False:
        return Utility(board),None
    else:
        v = 1000
        move = None
        for action in Actions(board):
            aux,act = max_value(Result(board,action))
            print(aux)
            if aux < v:
                v = aux
                move = action
                if v == -1:
                    return v,move
        return v,move

Terminal returns state of the game,Action returns possible moves and result creates a board given an action.

The error I get is '>' not supported between instances of 'NoneType' and 'int' pops up for if aux < v: and if aux > v: When I print aux, it occasionally appears as None. Thanks.

Answer 1

The code you have shared is fine.

The error message indicates that Utility returns None when you call it. This should not happen. Utility should always return an integer when the game is over, and looking at your code it should return -1, 0 or 1.

There is also the possibility that Utility returns None when the game is not over, but that Terminal has a bug such that it returns something else than False even when the game is not over.

Here is an implementation of the functions Terminal and Utility that do not produce the error you got, but make it work as expected.

In fact, I added all missing functions based on a board representation that is a string of 9 characters, and a game loop so you can play against the minimax algorithm:

import re

def Utility(board):
    m = re.findall(r"([XO])(?:\1\1(?:...)*$|..\1..\1|...\1...\1|.\1.\1..$)", board)
    return -1 if "O" in m else len(m)
    
def Terminal(board):
    return "O X"[Utility(board)+1].strip() or not board.count(".") and "draw"

def turn(board):
    return "OX"[board.count(".") % 2]

def Actions(board):
    return (i for i in range(9) if board[i] == ".")

def Result(board, action):
    return board[:action] + turn(board) + board[action+1:]

board = "." * 9
while True:  # Interactive game between human and minimax
    print(f"{board[:3]}\n{board[3:6]}\n{board[6:]}")
    winner = Terminal(board)
    if winner:
        print(f"Winner: {winner}")
        break
    if turn(board) == "X":
        action = int(input("Your move (0..8)? "))
        if board[action] != ".":
            print("Invalid move. Try again.")
            continue
    else:
        action = player(board)
        print("minimax chooses", action)
    board = Result(board, action)