Minmax tic-tac-toe algorithm that never loses

Question

I'm trying to build a min-max algorithm for a Tic-Tac-Toe that never lose...

I try to build it from reading few sources:

1. http://neverstopbuilding.com/minimax
2. http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/ (I built something very similar to this one).

Here is the code: class tree:

def find_best_move(self,board,depth,myTurn,sign):
    """

    :param board:
    :return:
    """
    if (board.empty==[]): return None

    best_move=-(2**(board.s**2))
    m=board.empty[0]
    for move in board.empty:
        b=copy.deepcopy(board)
        b.ins(move,sign)
        if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
            return move
        curr_move=self.minimax(b,depth,myTurn,sign)
        if (curr_move > best_move):
            best_move = curr_move
            m=move
        print(curr_move,best_move,m)

    return m #This should be the right move to do....


# *****************************************************************************************************#

def minimax(self,board,depth,myTurn,sign):
    """

    :param depth:
    :param myTurn:
    :return:
    """
    #print(depth,end='\n')
    if (self.is_win(board,sign)):
        #print("I win!")
        return (board.s**2+1) - depth
    elif (self.is_win(board,xo.opp_sign(sign))):
        #print("You win!")
        return -(board.s**2+1) + depth
    elif (board.is_full()):
        return 0

    if (myTurn):
        bestVal=-(2**700)
        for move in board.empty: #empty - the empty squares at the board 
            b = copy.deepcopy(board)
            b.ins(move, sign)
            value=self.minimax(b,depth+1,not myTurn, xo.opp_sign(sign))
            #xo.opp_sign(sign) - if function for the opposite sign: x=>o and o=>x
            bestVal = max([bestVal,value])
        return bestVal

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, xo.opp_sign(sign))
            value = self.minimax(b, depth + 1, not myTurn, xo.opp_sign(sign))
            #print("opp val: ",value)
            bestVal = min([bestVal, value])
        return bestVal


# *****************************************************************************************************#
def is_win(self,board, sign):
    """
    The function gets a board and a sign.
    :param board: The board.
    :param sign: The sign (There are only two options: x/o).
    :return: True if sign "wins" the board, i.e. some row or col or diag are all with then sing. Else return False.
    """

    temp=board.s
    wins = []  # The options to win at the game.
    for i in range(1, temp + 1):
        wins.append(board.get_col(i))
        wins.append(board.get_row(i))
    wins.append(board.get_diag1())
    wins.append(board.get_diag2())

    for i in wins:
        if (self.is_same(i, sign)):
            return True
    return False



# *****************************************************************************************************#
def is_same(self, l, sign):
    """
    The function get a list l and returns if ALL the list have the same sign.
    :param l: The list.
    :param sign: The sign.
    :return: True or false
    """

    for i in l:
        if (i != sign):
            return False
    return True

If something is wrong at my code please tell me!

But, I always can beat this - I just need to make a "fork"
.e.g.: (I'm x, the algorithm is o)

xx-   
xo-   
-o- 

And I win...
There is algorithm for making a tree that can block forks?

Answer 1

You have three errors.

1. In your minimax method the sign is swapped one time too many

You swap the sign in the else block -- for the case where myTurn is False -- but you shouldn't. You already swap the sign with each recursive call. Because of this bug, you always puts the same sign on the board during your minimax search, never the opposite one. Obviously you therefore miss all the threats of the opponent.

So change:

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, error xo.opp_sign(sign)) # <-- bug

to:

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, sign) # <-- corrected 

2. In find_best_move you should swap the move as you call minimax

And a similar bug occurs in find_best_move. As you go through each move, you must swap the sign when calling minimax in the new board, otherwise you let the same player play twice.

So change this:

    for move in board.empty:
        b=copy.deepcopy(board)
        b.ins(move,sign)
        if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
            return move
        curr_move=self.minimax(b,depth,myTurn,sign) # <-- bug

to:

    for move in board.empty:
        b=copy.deepcopy(board)
        b.ins(move,sign)
        if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
            return move
        curr_move=self.minimax(b,depth,not myTurn,xo.opp_sign(sign)) # <-- corrected

Note that the second condition should not be necessary: if you are the one who just moved, it is not logical that the other should come in a winning position.

3. In minimax you don't consider the value of myTurn when there is win

Although you consider the value of myTurn to determine whether to minimise or maximise, you don't perform this operation when checking for a win.

You currently have this:

if (self.is_win(board,sign)):
    #print("I win!")
    return (board.s**2+1) - depth
elif (self.is_win(board,xo.opp_sign(sign))):
    #print("You win!")
    return -(board.s**2+1) + depth
elif (board.is_full()):
    return 0

First of all, the first if condition should not be true ever, because the most recent move was for the opposite sign, so that could never lead to a win for sign.

But to the issue: the second if does not look to myTurn to determine whether the return value should be negative or positive. It should do so to be consistent. So change the above code to this:

if self.is_win(board,xo.opp_sign(sign)):
    if myTurn: 
        return -(board.s**2+1) + depth
    else:
        return (board.s**2+1) - depth
elif board.is_full():
    return 0

How to call find_best_move

Finally, the above works if you always call find_best_move with the myTurn argument as True, because find_best_move maximises the result as can be seen from if (curr_move > best_move). So, to avoid that you call it with False, you would better remove this argument and pass False to minimax. So:

def find_best_move(self,board,depth,sign): # <-- myTurn removed as argument
    # ... etc ...

        curr_move=self.minimax(b,depth,False,xo.opp_sign(sign)) # pass False

This way, the argument myTurn indicates whether the turn is to the same player as the player for which find_best_move was called.

Working Solution

With minimal code added to make it work (Board and XO classes added), the program can be seen to run on repl.it.

Note that this algorithm is not optimal. It is just brute force. You could look into storing results of previously evaluated positions, doing alpha-beta pruning, etc...