How to fix my minimax algorithm for tic tac toe game

Question

For a school project I have been trying to make an unbeatable tic tac toe game. To do this I have attempted to implement a minimax algorithm, and it is giving unexpected outputs, and I have not been able to figure out why, ot fix anything.

I have tried printing out variables to see when things go wrong, but for anything more complex than the most simple cases (which it works in) it outputs way too much stuff for any human to sift through, and when I do work through it, keeping track of the function calling itself, and how many times it calls itself is difficult. I Have tried changing strict inequalities to non strict ones. I have tried rewriting the whole thing a few times to see if I just had a typo. I have stepped through the logic and have been able to find nothing.

Here is my algorithm

def minimax(newboard, player, huplayer, aiplayer):
    move=-1
    empty=emptyindices(newboard)
    if winning(newboard, huplayer):
        score=-1
    elif winning(newboard, aiplayer):
        score = 1
    elif empty==[]:
        score=0
    else:
        if player == aiplayer:
            score=0
            for i in empty:
                newboard[i]=player
                output=minimax(newboard, huplayer, huplayer, aiplayer)
                tempscore=output[1]
                if tempscore > score:
                    score=tempscore
                    move = i
                    newboard[i]=""
                newboard[i]=""
        if player == huplayer:
            score=0
            for i in empty:
                newboard[i]=player
                output=minimax(newboard, aiplayer, huplayer, aiplayer)
                tempscore=output[1]
                if tempscore < score:
                    score=tempscore
                    move = i
                    newboard[i]=""
                newboard[i]=""
    return [move,score]

I have indexed the board from 0 to 8 like

0 | 1 | 2

3 | 4 | 5

6 | 7 | 8

I don't think the other functions used have errors in them, but I will include them here anyway, just in case they are actually the problem.

def winning(board,player):
    if (board[0]==player and board[1]==player and board[2]==player) or (board[3]==player and board[4]==player and board[5]==player) or(board[6]==player and board[7]==player and board[8]==player) or(board[0]==player and board[3]==player and board[6]==player) or (board[1]==player and board[4]==player and board[7]==player) or(board[2]==player and board[5]==player and board[8]==player) or (board[0]==player and board[4]==player and board[8]==player) or (board[2]==player and board[4]==player and board[6]==player):
        win=True
    else:
        win=False
    return win

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

For simple situations where the computer can make a move to win right away it does it. however for something like

print(minimax(['X', '', '', 'O', '', 'X', 'X', 'O', 'O'],"X","O","X"))

the output is

[-1, 0]

even though the computer could guarantee a win by making the move 2, meaning that for some reason the move is not changing from the default value

Answer 1

I think that should work (I just tested what I proposed in the comment). The poor loosing player was too paralized to take a move recognizing it's inevitable fate :-)

def minimax(newboard, player, huplayer, aiplayer):
    move=-1
    empty=emptyindices(newboard)
    if winning(newboard, huplayer):
        score=-1
    elif winning(newboard, aiplayer):
        score = 1
    elif empty==[]:
        score=0
    else:
        if player == aiplayer:
            score=-2
            for i in empty:
                newboard[i]=player
                output=minimax(newboard, huplayer, huplayer, aiplayer)
                tempscore=output[1]
                if tempscore > score:
                    score=tempscore
                    move = i
                    newboard[i]=""
                newboard[i]=""
        if player == huplayer:
            score=2
            for i in empty:
                newboard[i]=player
                output=minimax(newboard, aiplayer, huplayer, aiplayer)
                tempscore=output[1]
                if tempscore < score:
                    score=tempscore
                    move = i
                    newboard[i]=""
                newboard[i]=""
    return [move,score]

Nice function!

Btw. you could make the code even a bit shorter by using a factor for the score. So for the minimizing player you set the factor to -1 for the maximizing to 1. This way you could reuse the loops over the empty fields and the body of the loop for both players without implementing them twice by just changeing your condition to something like:

if tempscore*factor > score: