Can You Create an Unbeatable Tic-Tac-Toe AI Player?

Abstract

Do you think you can win tic-tac-toe against an AI player? In this project, you will explore how the Minimax algorithm makes decisions in two-player games such as tic-tac-toe. This project requires little to no coding skill; instead, you will need an open mind and curiosity. Why not give it a try yourself?

Summary

Areas of Science

Artificial Intelligence
Video & Computer Games

Difficulty

Method

Engineering Design Process

Time Required

Short (2-5 days)

Prerequisites

None

Material Availability

Readily available

Cost

Very Low (under $20)

Safety

No issues

Credits

Tracey Ngo, Science Buddies

Science Buddies is committed to creating content authored by scientists and educators. Learn more about our process and how we use AI.

Objective

Examine how changing the "exploration depth" changes the difficulty of playing tic-tac-toe against an AI that is using the Minimax algorithm.

Introduction

Imagine playing tic-tac-toe with a friend. Both you and your friend are trying your best to win. For your strategy, you think about what moves your friend might make after each of yours. You try to predict outcomes for each board position to maximize your chances of winning. However, especially in the early game, it's hard to think about all possible moves at once.

Have you ever played tic-tac-toe against a computer opponent instead of a human? How do you think the computer made its decisions?

Artificial intelligence (AI) is a branch of computer science focused on the creation of tools that can solve problems and analyze information. Within AI, various algorithms are used to enhance decision-making processes. One notable algorithm is Minimax, which is often used in two-player games like tic-tac-toe. In such games, Minimax helps the computer assess potential moves, anticipate the opponent's responses, and strategically choose the best course of action to maximize its chances of winning or minimize its risk of losing.

The core objective of the Minimax algorithm is to determine the optimal (best) move for a player in an adversarial game. An adversarial game is one in which two or more players with opposing objectives compete against each other. When you play tic-tac-toe, for example, you might be "X" and your friend might be "O." Your goal is to get three X's in a row, and your friend's goal is to get three O's in a row. Since you have different competing goals, you are playing an adversarial game.

The term "Minimax" reflects the algorithm's approach of minimizing potential loss while simultaneously maximizing potential gain. It does this through a recursive exploration of the game tree. A game tree is a representation of all the possible ways a game could go. Each node on the tree represents a particular game state—in this case, a particular arrangement on the tic-tac-toe board. From each node, it branches off to represent each of the possible next moves and the resulting game states. The algorithm's process is called "recursive" because it loops repeatedly through the game tree, evaluating all potential outcomes for each move. You can think about it like exploring all the different paths in a maze to find the best way through. Watch this video for a simple and clear introduction to the Minimax algorithm:

https://www.youtube.com/watch?v=5y2a0Zhgq0U

The depth of exploration in a game tree refers to how many moves ahead the algorithm looks while considering possible future game states. In the context of tic-tac-toe, the game tree represents all possible sequences of moves that can be made by both players until the game reaches a terminal state, meaning the game ends in a win for either player or in a draw (tie). Choosing the right depth is a trade-off between computational resources and decision quality. Deeper exploration provides a more strategic understanding of the game, but it requires more processing time.

Image Credit: Science Buddies

This game tree starts at one game state on level 0. (Top row: O, O, X; Middle row: blank, X, blank; Bottom row: O, blank, X). It branches down to Level 1 to show the board after each possible next move. In this case, the X player can choose the left middle, the right middle, or the bottom middle. The right middle option is circled to represent a terminal state: three X's in a row in the right column. From each of the other two game states, it branches down to two more possible game states at level 2. One of those is a terminal state (three O's in a row). The other three continue down to level three, where each one is in a terminal state: a draw, three in a row for X, and a draw, respectively.

Figure 1. A game tree starting from a particular game state in a tic-tac-toe game. The Minimax algorithm will search up to a depth specified by the user or until it reaches a terminal state (circled in green). The depth is labeled on the left. In this game tree, the maximum depth is three since there are only three moves left to be made.

Although the Minimax algorithm is effective in strategic decision-making, it has some drawbacks. It needs a lot of computational power and memory, especially when games grow more complex. Also, it assumes that each player knows everything about the game and will play perfectly. In other words, it assumes that each player will consider all possible outcomes and then make the optimal move every time. In reality, human players do not play perfectly, so actual games deviate from the algorithm's ideal scenario. As a result, the Minimax algorithm may face challenges when it is applied to games that involve messiness or randomness. Games characterized by unpredictable events or random factors such as chance cards or dice rolls, may confound the algorithm's attempts to predict outcomes accurately.

In this tic-tac-toe challenge, we will provide you with the basic code to create an AI player that uses the powerful Minimax algorithm for decision-making. Your task is to experiment with changing the depth of exploration—the number of steps ahead the algorithm looks—to observe how that influences the decisions made by the AI player. Make sure to document your observations, noting any changes in the AI player's behavior and the impact on overall game performance. Happy coding and experimenting!

Terms and Concepts

• Artificial intelligence
• Algorithm
• Minimax
• Adversarial game
• Recursive
• Game tree
• Game state
• Depth of exploration
• Terminal state

Questions

• What is the core objective of the Minimax algorithm, and why is it particularly useful in two-player games like tic-tac-toe?
• Can you explain the concept of minimizing potential loss and maximizing potential gain?
• What does the term "depth of exploration" mean in the context of the Minimax algorithm?
• What are some drawbacks of the Minimax algorithm?

Materials and Equipment

• Computer with Internet access

This project follows the Engineering Design Process. Confirm with your teacher if this is acceptable for your project, and review the steps before you begin.

Setting up the Google Colab Environment

1. You will need a Google account. If you do not have one, make one when prompted.
2. Download the tic-tac-toe.ipynb file from Science Buddies.
3. Upload the file to Google Colaboratory. (You will need to sign into your Google account at this point or make an account.)
4. Read the Troubleshooting Tips and How to Use This Notebook sections. Follow the instructions you find there.

Setting Up the Tic-Tac-Toe Board

1. To start the tic-tac-toe game, we need to create the game board. We have prepared a function called display_board that will visually represent the current state of the board as we make moves. Begin by executing the code containing the display_board function to make it accessible.
   1. The tic-tac-toe board is a 3x3 grid of rows and columns. The numbering for the rows and columns starts at 0.
   Image Credit: Science Buddies

   The 3-by-3 grid has rows 0 (top), 1, and 2 and columns 0 (left), 1, and 2. Each space is labeled with its coordinates: for example, the top left space is labeled 0-comma-0 in parentheses and the top right space is labeled 0-comma-2 in parentheses.

   
   Figure 2. Coordinates are used to specify the location of the moves. The coordinates are based on rows and columns starting at (0,0).
2. The tic-tac-toe board will be represented as a 2D list with dimensions 3x3. Execute the provided code to see what the initial empty board looks like. This empty board will serve as the canvas for our game.

Preparing the Game Environment

Next, we will set up the functions required for our game. All the necessary functions have been prepared, so your task is to run the provided code to make these functions accessible. This step ensures that the essential game functions are ready for use as we progress in the game.

1. The check_win function checks whether the specified player has won the game. This function checks for a win in three directions: rows, columns, and diagonals. If a winning combination is found, the function returns True; otherwise, it returns False.
2. The is_draw function checks whether the Tic-Tac-Toe game ends in a draw. If there are no more empty spaces (' ') on the board, indicating a draw, it returns True.
3. The player_move function gets the player's move (row and column) from the user input. This function uses a "while loop" to repeatedly prompt the player for input until a valid move is entered. It ensures that the input consists of valid integers within the range 0–2 and that the chosen cell on the board is empty. If the input is invalid, an appropriate error message is displayed.

Building the Minimax AI Player

1. The minimax_with_eval function implements the Minimax algorithm with our evaluation function. This function is similar to Minimax but includes a simple evaluation function to assign scores to the board. Run the code in this cell.
2. The ai_move function determines the best move for the AI ("O") by using the Minimax algorithm with our simple evaluation function. This function iterates through each empty cell on the board, calculates the score for each potential move using the Minimax algorithm with our simple evaluation function, and selects the move with the highest score. The chosen move represents the optimal move for the AI to make. Run the code in this cell.

Playing the Game Against Our AI Player

We are ready to play against our AI Player! Run the main function to start the game. You can run this code block again to play the game multiple times; no need to rerun every cell each time you play.

1. In the code, there is a comment that indicates where you can change the depth explored. Experiment with changing this value between 0 and 9. (Nine is the maximum since there are nine moves total that can be made).
   1. Challenge yourself to win against the AI player. First, set the depth explored to 0. Play 10 games against the AI player and record how many times you won, lost, and ended the game in a draw.
   2. Then, increase the depth explored by one and repeat this process.
   3. Compare how well the AI performs as the depth explored increases. Have you noticed a significant difference?

https://www.youtube.com/watch?v=JWRxdoPrk7M

Ask an Expert

Do you have specific questions about your science project? Our team of volunteer scientists can help. Our Experts won't do the work for you, but they will make suggestions, offer guidance, and help you troubleshoot.

Post a Question

Variations

Careers

If you like this project, you might enjoy exploring these related careers:

Computer Programmer

Log in to add favorite More Menu

• Read More

Career Profile

Computers are essential tools in the modern world, handling everything from traffic control, car welding, movie animation, shipping, aircraft design, and social networking to book publishing, business management, music mixing, health care, agriculture, and online shopping. Computer programmers are the people who write the instructions that tell computers what to do. Read more

Computer Software Engineer

Log in to add favorite More Menu

• Read More

Career Profile

Are you interested in developing cool video game software for computers? Would you like to learn how to make software run faster and more reliably on different kinds of computers and operating systems? Do you like to apply your computer science skills to solve problems? If so, then you might be interested in the career of a computer software engineer. Read more

News Feed on This Topic

 

, ,

Explore Our Science Videos

Motor Imagery Visualization's Impact on Fine Motor Skills for Space Flight | Science Project

Build a Bird Feeder to Study Birds – STEM activity

Leaf Chromatography: Explore the Colors of Fall | Science Project