1

I'm working on creating a simple minimax algorithm for a Tic Tac Toe bot. I've read some of the other answers on here, but I'm still not really sure what I'm doing wrong, I'm pretty new to recursive functions. I think I understand how the algorithm works, but I'm not totally sure.

def minimax(board, player, originalPlayer):
    global ai, human
    if gameOver(board):
        if hasWon(board, originalPlayer):
            return 1, None
        if hasWon(board, opposite(originalPlayer)):
            return -1, None
        if len(getEmptyIndexes(board)) is 0:
            return 0, None

    possibleMoves = getEmptyIndexes(board)
    if player == originalPlayer:
        bestScore = float('-inf')
    else:
        bestScore = float('inf')

    for moveIndex in possibleMoves:
        clone = copy(board)
        clone = makeMove(clone, moveIndex, player)
        score, index = minimax(clone, opposite(player), originalPlayer)

        if player == originalPlayer:
            if score > bestScore:
                bestScore = score
                bestMove = index
        else:
            if score < bestScore:
                bestScore = score
                bestMove = index

    return bestScore, bestMove

My game loop is below, I'm just using it for debugging. The error I've been getting is that the minimax function returns the tuple (0, None) when I'm expecting to have an index of the board where the None is.

ai = 'X'
human = 'O'
board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']

while True:
    print('Board:')
    printBoard(board)
    choice = int(input('Your choice: '))
    board[choice] = human
    print('AI Moves')
    score, index = minimax(board, ai, ai)
    board[index] = ai

Thanks for your help!

Edit: getEmptyIndexes returns the indexes of blank spaces on the board; for example:

getEmptyIndexes([' ', 'X', ' ', 'X', ' ', 'O', ' ', 'O', ' ']) = [0, 2, 4, 6, 8]

Edit 2: I think I actually just fixed it, I was writing "bestMove = index" instead of "bestMove = moveIndex", pretty much I was using the old move index from the older leaf nodes instead of the new one.

Evan Gebo
  • 51
  • 5
  • what is `getEmptyIndexes`? – iamanigeeit Nov 29 '18 at 03:02
  • also, use `len(getEmptyIndexes(board)) == 0` instead of `is`: https://stackoverflow.com/questions/132988/is-there-a-difference-between-and-is-in-python – iamanigeeit Nov 29 '18 at 03:03
  • I think your edit 2 means you have identified the problem. You can answer your own question if you want, but do try to make it something that another user might benefit from (not just a message that you've solved it). – Blckknght Nov 29 '18 at 03:46

0 Answers0