Tic-Tac-Toe Computer Wins

Tic-Tac-Toe Python AI (3)

Today is the magic day when our Tic-Tac-Toe AI will finally become perfect and unbeatable!

Minimax Algorithm

Tic-Tac-Toe is a game of perfect information like Go and Chess meaning that when making a decision you have access to all the information about the game including where the opponent can play, where the opponent has played, where you can play…

The minimax algorithm is an algorithm which enumerates all possible moves in a game until it reaches an end state such as a win, a loss or a tie (of course, in a game like chess where there are over 101000000 possible boards the algorithm will stop at a certain depth). In this algorithm, the computer must assume that the human player will try to minimise the game score and the computer will maximise the game score. We can visualise this as such: Tic-Tac-Toe Game Tree

There is one big problem with this algorithm: the game tree will grow exponentially which means that even in a small game like Tic-Tac-Toe, running the minimax algorithm is rather slow. This is why we will “prune” the tree to not calculate the “useless moves”. For a more in-depth explanation of the minimax algorithm read this article.

Alpha-Beta Pruning

Alpha-Beta pruning consists in not calculating a certain move if we already have a move which is better than it. This makes the gameplay considerably faster and actually better as it means that the computer will prefer to win in two goes than in three or four. For a more in-depth explanation of alpha-beta pruning read this article.

Time to code!

Minimax algorithm with alpha-beta pruning

Here is the function that we will use to calculate the score of a certain board:

def minimax(node, player, alpha, beta):
    if node.leaf():
        if node.X_won():
            return -1
        elif node.tied():
            return 0
        elif node.O_won():
            return 1

    for move in node.legal_moves():
        node.move(move, player)
        score = minimax(node, get_opponent(player), alpha, beta)
        node.move(move, ' ')
        if player == 'O':
            if score > alpha:
                alpha = score
            if alpha >= beta:
                return beta
        else:
            if score < beta:
                beta = score
            if beta <= alpha:
                return alpha
    if player == 'O':
        return alpha
    else:
        return beta

Wrapper function

The minimax function returns a score but we don’t want a score: we want a move. Let’s create a function that uses the minimax function to calculate the score of every move and returns the best move:

import random
def computer_move2(board, player):
    best = -2
    choices = []
    
    if len(board.legal_moves()) == 9:
        return random.choice([0,2,6,8])
    for move in board.legal_moves():
        board.move(move, player)
        score = minimax(board, get_opponent(player), -2, 2)
        board.move(move, ' ')
        print("Move: ",move+1," has a score of: ",score)
        if score > best:
            best = score
            choices = [move]
        elif score == best:
            choices.append(move)
    choice = random.choice(choices)
    print("[+] Selected move: ",choice+1)
    return choice

Now, all we have to do is update the computer_play function to use the player_move2 function instead of player_move:

 

def computer_play():
    """ Play Tic-Tac-Toe against a (perfect) computer"""
    board = Board()
    board.output()
    player1 = input("What are you called? ")
    player2 = "Computer"
    print('{} is X and {} is O'.format(player1,player2))
    player = None
    while player not in ['X','O']:
         player = input('Who goes first?(X or O) ').capitalize()

    while not board.leaf():
        if player == 'X':
            move = player_move(board, '{}\'s turn'.format(player1))
            board.move(move, player)
        else:
            move = computer_move2(board, player)
            print("Computer will play at square: {}".format(move))
            board.move(move, player)
        board.output()
        player = get_opponent(player)

    if board.X_won():
        print("{} won!".format(player1))
    elif board.O_won():
        print("{} won!".format(player2))
    else:
        print("It's a tie!")

Our computer is at last completely unbeatable! All the code used in this project can be found here.

If you would like me to create a connect4 AI please leave a comment saying so! Don’t forget to subscribe to our email list if you want to hear more from us!

[sp-form formid=377]

 

Part 1

Part 2

2 Comments

Leave a Reply