tic tac toe python minimax alpha beta

[deanhystad]

I played some games and the code appears to work just fine. One thing you might want to consider is returning a higher score for wins that occur in fewer moves. Your minimax code scores every win as 1 regardless of how many moves it takes to win. While I was playing the minmax algorithm occasionally passed on moves that would win immediately, picking other moves that were still guaranteed wins, but for the next move.

Below is a minimax algorithm that gives higher scores for wins that occur sooner. In addition to giving more weight to moves that win faster, I changed the board from a 2D list to a flat list. Just because a tic-tac-toe board has rows and columns is no reason why the software has to save the board in a 2D container. Iterating and indexing are easier with a flat list. Making a new board is easier with a flat list. Checking for wins is even easier with a flat list. The only time the software has to know about rows and columns is when it draws X's and O's on the board, and when the user clicks on the board to place their mark. In both cases additional transformations are required to get to/from turtle coordinates.

import turtle
import random

wins = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6))
board = [''] * 9
ROBOT = 'X'
HUMAN = 'O'
DRAW = 2


def line(start, end):
    """Draw a line from start to end."""
    turtle.up()
    turtle.goto(*start)
    turtle.down()
    turtle.goto(*end)


def draw_marker(square, marker):
    """Draw an x or o."""
    x = square % 3 + 0.5
    y = square // 3 + 0.5
    if marker == ROBOT:
        turtle.color('blue')
        line((x-0.4, y-0.4), (x+0.4, y+0.4))
        line((x-0.4, y+0.4), (x+0.4, y-0.4))
    elif marker == HUMAN:
        turtle.color('red')
        turtle.up()
        turtle.goto(x, y-0.4)
        turtle.seth(0)
        turtle.down()
        turtle.circle(0.4, steps=100)


def draw():
    """Draw the board."""
    turtle.pencolor('green')
    turtle.pensize(10)
    line((0, 1), (3, 1))
    line((0, 2), (3, 2))
    line((1, 0), (1, 3))
    line((2, 0), (2, 3))
    for square, marker in enumerate(board):
        draw_marker(square, marker)
    screen.update()


def game_over():
    """Return marker if marker won, 2 if draw, else 0."""
    for win in wins:
        a, b, c = [board[square] for square in win]
        if a and a == b == c:
            return a
    if '' not in board:
        return DRAW
    return 0


def open_squares():
    """Return list of squares that are open."""
    squares = [index for index, player in enumerate(board) if not player]
    random.shuffle(squares)  # Shuffle to make robot player less predictable.
    return squares


def minmax(marker=ROBOT, alpha=-11, beta=11, weight=10):
    """Use min-max algorithm to pick best move for robot player."""
    if (winner := game_over()) == ROBOT:
        return weight, None
    elif winner == HUMAN:
        return -weight, None
    elif winner == DRAW:
        return 0, None
    
    if marker == ROBOT:
        best = -weight, None
        other = HUMAN
    else:
        best = weight, None
        other = ROBOT

    for square in open_squares():
        board[square] = marker
        score, _ = minmax(other, alpha, beta, weight-1)
        board[square] = ""

        if score > best[0] and marker == ROBOT:
            best = score, square
            alpha = max(alpha, score)
        elif score < best[0] and marker == HUMAN:
            best = score, square
            beta = min(beta, score)
        if alpha >= beta:
                break
    return best


def play(square, marker):
    """Place marker in square.  Return game_over status."""
    board[square] = marker
    draw()
    return game_over()


def click(x, y):
    """Respond to mouse click.

    If player clicked on open square, place o marker and have robot play x.
    Display message if game over.
    """
    square = None
    if 0 <= x < 3 and 0 <= y < 3:
        square = int(x) + int(y) * 3
    if square is None or board[square]:
        return

    winner = play(square, HUMAN)
    if not winner:
        winner = play(minmax()[1], ROBOT)

    if winner:
        """Display results if game over."""
        if winner == DRAW:
            screen.textinput("Game over!", "Tie!")
        else:
            screen.textinput("Game over!", f"{winner} won!")
        turtle.bye()


screen = turtle.Screen()
screen.title("Tic Tac Toe ")
screen.setup(800, 800)
screen.setworldcoordinates(-0.2, 3.2, 3.2, -0.2)
screen.tracer(0, 0)
turtle.hideturtle()
screen.onclick(click)

# Robot makes first move.
play(minmax()[1], ROBOT)
screen.mainloop()