Have you ever wondered how computers play games? And, surprising thing is they do win with best possible results? You may say yeah that is whole points of computer - to solve problems and do math, but shouldn’t there be some techniques because just having an oven and flour does not bake the bun itself.

Today, I will help you understand one of such game playing algorithm. The algorithm is called minimax algorithm and is mostly used for the games where there are two players and players play turn by turn.

What is the minimax algorithm?

The minimax algorithm is a recursive decision-making algorithm. It is used in two-player turn-based games like chess and tic-tac-toe. Well, it sounds fancy but the core logic is just playing all* possible moves and choosing the best result.

We should think it this way, suppose we have a game without any algorithm or anything, one player plays a move so does the other, this continues, but the twist is one of the player implementing the algorithm (which is obvisously always the computer), plays all possible states separately before playing its turn, checks the best result and then plays the move, this does sounds very simple and lame because it is.

This algorithm, it assumes, it is the only one trying to win the game and the other is trying to not let them win. Suppose two players in a race, one is running to the endline while the other blocking the road rather than running itself. With this assumption, it calculates best possible result and plays that result in its turn. And it does this everytime because as the players play their move the state of the game changes.

Note: all* meaning sometimes it is not all possible moves but best moves up to certain depth.

Implementing only the tic-tac-toe

We will first start by only implementing the core game - a simple CLI program using python, the second best programming language in the world. We assume, x the human player and o is the computer player which will be the maximizing player playing with minimax algorithm as its brain.

board = [" "] * 9


def intro() -> None:
    print("""## TIC-TAC TUTORIAL ##

0 | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8

Enter 'q' to quit.""")


def print_board() -> None:
    print()
    print(f"{board[0]} | {board[1]} | {board[2]}")
    print("--+---+--")
    print(f"{board[3]} | {board[4]} | {board[5]}")
    print("--+---+--")
    print(f"{board[6]} | {board[7]} | {board[8]}")
    print()

The code here is fairly self explaining, just three objects, board array with default 9 space ' ' values for 3 rows which will be filled by x and o, intro function for simple game introduction and print_board for printing current state of the board in console.

def get_winner() -> str | None:
    patterns = [[0, 1, 2], [3, 4, 5], [6, 7, 8],  # rows
                [0, 3, 6], [1, 4, 7], [2, 5, 8],  # cols
                [0, 4, 8], [6, 4, 2],]            # diagonals
    for i, j, k in patterns:
        if board[i] == board[j] == board[k] and board[i] != " ":
            return board[i]
    return None


def check_full() -> bool:
    return " " not in board

We are sure on how the game ends, either one player wins or there will be draw. To check that is to simply check if all values in one of the rows or cols or across two diagonals are same. The above mentioned patterns are the index of the board array satisfying these conditions. For the game to be draw we check if all the above cases fail with board being full.

def available_moves():
    return [i for i in range(len(board)) if board[i] == " "]


def get_user_input() -> int:
    ip = input(f"x {str(available_moves())}: ").strip()
    if ip == "q":
        exit(0)
    if len(ip) != 1:
        raise ValueError()
    x = int(ip)
    if (x >= 0 and x < 9) and board[x] != " ":
        raise ValueError()
    return x


def human_move():
    x = get_user_input()
    board[x] = "x"

Also, these are functions are also fairly simple. available_moves - checks empty spaces in the board, get_user_input - function as name says gets valid input from the user from CLI, human_move - used alongside get_user_input - completing the user side of game playing logic.

import random

def computer_move():
    while True:
        x = random.randint(0, 9)
        if board[x] == " ":
            board[x] = "o"
            break

For the computer player we use random number generator for now.

def check_over() -> bool:
    winner = get_winner()
    if winner == "x":
        print("\n## X WINNER ##")
        return True
    if winner == "o":
        print("\n## O WINNER ##")
        return True
    if check_full():
        print("\n## DRAW :( ##")
        return True
    return False

Also a basic function for better user experience. Combining all the above codes and the main function from below to get basic tic-tac-toe implementation.

Implementing the minimax algorithm

Now the main part. The core minimax implementation for this game is just a simple recursive function. If you are not 100% sure on recursive functions, you might want to clear that confusion first. The important thing here is while the minimax function recursively calls itself, each call is simulating a different player’s move, which is here is checked by is_max flag parameter. This is_max parameter determines which player is moving currently and simulates all possible move taking maximum value if it true and minimum otherwise.

def minimax(board: list[str], is_max: bool) -> int:
    winner = get_winner()
    if winner == "x":
        return -1
    elif winner == "o":
        return 1
    elif check_full():
        return 0

    if is_max:  # AI
        best_score = -100_000_000
        for i in available_moves():
            board[i] = "o"
            score = minimax(board, False)
            board[i] = " "
            best_score = max(score, best_score)
        return best_score
    else:
        best_score = 100_000_000
        for i in available_moves():
            board[i] = "x"
            score = minimax(board, True)
            board[i] = " "
            best_score = min(score, best_score)
        return best_score


def best_move():
    move = None
    best_score = -100_000_000
    am = available_moves()
    for i in am:
        board[i] = "o"
        score = minimax(board, False)
        board[i] = " "
        if score > best_score:
            best_score = score
            move = i
    return move


def computer_move():
    x = best_move()
    board[x] = "o"

Combining Everything

Combining everything we explain in one place:

# tic-tac-toe.py

board = [" "] * 9

def intro():
  print("""## TIC-TAC TUTORIAL ##

0 | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8

Enter 'q' to quit.""")

def print_board():
  print()
  print(f"{board[0]} | {board[1]} | {board[2]}")
  print("--+---+--")
  print(f"{board[3]} | {board[4]} | {board[5]}")
  print("--+---+--")
  print(f"{board[6]} | {board[7]} | {board[8]}")
  print()


def get_winner() -> str | None:
  patterns = [[0, 1, 2], [3, 4, 5], [6, 7, 8],  # rows
              [0, 3, 6], [1, 4, 7], [2, 5, 8],  # cols
              [0, 4, 8], [6, 4, 2],]            # diagonals
  for i, j, k in patterns:
    if board[i] == board[j] == board[k] and board[i] != " ":
      return board[i]
  return None

def check_full() -> bool:
  return " " not in board

def get_user_input() -> int:
  ip = input(f"x {str(available_moves())}: ").strip()
  if ip == "q":
    exit(0)
  if len(ip) != 1:
    raise ValueError()
  x = int(ip)
  if (x >= 0 and x < 9) and board[x] != " ":
    raise ValueError()
  return x

def human_move():
  x = get_user_input()
  board[x] = "x"

def available_moves():
  return [i for i in range(len(board)) if board[i] == " "]

def minimax(board: list[str], is_max: bool) -> int:
  winner = get_winner()
  if winner == "x":
    return -1
  elif winner == "o":
    return 1
  elif check_full():
    return 0

  if is_max: # AI
    best_score = -100_000_000
    for i in available_moves():
      board[i] = "o"
      score = minimax(board, False)
      board[i] = " "
      best_score = max(score, best_score)
    return best_score
  else:
    best_score = 100_000_000
    for i in available_moves():
      board[i] = "x"
      score = minimax(board, True)
      board[i] = " "
      best_score = min(score, best_score)
    return best_score

def best_move() -> int:
  move = -1
  best_score = -100_000_000
  am = available_moves()
  for i in am:
    board[i] = 'o'
    score = minimax(board, False)
    board[i] = " "
    if score > best_score:
      best_score = score
      move = i
  return move

def computer_move():
  x = best_move()
  board[x] = "o"

def check_over() -> bool:
  winner = get_winner()
  if winner == "x":
    print("\n## X WINNER ##")
    return True
  if winner == "o":
    print("\n## O WINNER ##")
    return True
  if check_full():
    print("\n## DRAW :( ##")
    return True
  return False

def main():
  intro()
  while True:
    print_board()
    # Human move
    try:
      human_move()
    except ValueError:
      print("\n** Invalid input **")
      continue
    if check_over():
      break
    # AI move
    computer_move()
    if check_over():
      break

  print_board()


if __name__ == "__main__":
  main()

To run the game:

python3 tic-tac-toe.py