So my code run, but only the first move, after that I keep getting "Invalid move" message (which was declared by myself) in my result function. I'm not sure what's wrong with my result function, or I wonder the bug is in my minimax fuction.

import math
import copy
from random import randint

X = "X"
O = "O"
EMPTY = None

def initial_state():
    Returns starting state of the board.
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]

def player(board):
    Returns player who has the next turn on a board.
    # start counting the number of X and O
    number_of_X = 0
    number_of_O = 0

    for row in board:
        for cell in row:
            if cell == X:
                number_of_O += 1
            elif cell == O:
                number_of_X += 1

    # if X goes first, number of X > number of O, then it's O's turn
    # if then O goes after, number of O == number of X and if not terminal state,
    # then it's X's turn

    if number_of_X > number_of_O:
        return O
    elif number_of_O == number_of_X and not terminal(board):
        return X
        return None 

def actions(board):
    Returns set of all possible actions (i, j) available on the board.
    # create a set of all possible moves
    possible_moves = set()

    # all the possible move in 3x3 board
    for i in range(3):
        for j in range(3):
            # if cell empty, then can make a move at that cell
            if board[i][j] == EMPTY:
                possible_moves.add((i, j))
    # else, return actions
    return possible_moves

def result(board, action):
    Returns the board that results from making move (i, j) on the board.

    if action in actions(board):
        (i, j) = action
        result_board = copy.deepcopy(board)    
        result_board[i][j] = player(board)
        return result_board

        raise Exception("Invalid")

def winner(board):
    Returns the winner of the game, if there is one.
    # if 3 cells in a row horizontally, vertically or diagonally and not None -> win
    # else, tie -> return None

def terminal(board):
    Returns True if game is over, False otherwise.

def utility(board):
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.

def minimax(board):
    Returns the optimal action for the current player on the board.
    # output: action (i, j)
    # track each move
    player_name = player(board)

    if terminal(board):
        return None

    if board == initial_state():
        i, j = randint(0, 2), randint(0, 2)
        return (i, j)
    # X should be trying to maximize the utility
    # which means O should be trying to minimize the utility
    # X should choose the move that maximize the utility of optional moves of O
    if player_name == X:
        value = -math.inf
        move = (-1, -1)
        for action in actions(board):
            minv = MIN_VALUE(result(board, action))
            if minv > value:
                value = minv
                move = action
        return move

    if player_name == O:
        value = math.inf
        move = (-1, -1)
        for action in actions(board):
            maxv = MAX_VALUE(result(board, action))
            if maxv < value:
                v = maxv
                move = action
        return move

def MAX_VALUE(board):
    if terminal(board):
        return utility(board)
    v = -math.inf
    for action in actions(board):
        v = max(v, MIN_VALUE(result(board, action)))
    return v

def MIN_VALUE(board):
    if terminal(board):
        return utility(board)
    v = math.inf
    for action in actions(board):
        v = min(v, MAX_VALUE(result(board, action)))
    return v
  • Did you find any solution? I'm having the same problem
    – Belen
    Commented Apr 21, 2020 at 5:51
  • Yes, silly me I made a typo at the first function when I count the number of X and O. Maybe you should check for that too. A small typo can ruin everything.
    – earlpanda
    Commented Apr 22, 2020 at 14:14

1 Answer 1


For the result function, you don't need to iterate through all the actions available for the given board.

Instead you just need to return newboard which will result it the action parameter given in the result function is executed to the given board (given in parameter of the result function).

So here are few things you need to do:

  1. check if the action ((i,j) cell) in the given board is "EMPTY"
  2. if not raise exception
  3. else: get the player whose turn is current turn and replace "EMPTY" with the player in the action cell.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .