Can You Create a Strategic Connect 4 AI Opponent?

Abstract

When you play Connect 4, what strategies do you use to increase your chances of winning? In this project, you will explore how artificial intelligence can make decisions in two-player games such as Connect 4. This project requires little to no coding skill. Instead, you will need patience and an open mind. Why not give it a try yourself?

Summary

Areas of Science

Artificial Intelligence

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.

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

Objective

Examine how changing the values in the evaluation function affects the performance of an AI player using the Minimax algorithm with alpha-beta pruning in a game of Connect 4.

Introduction

Imagine playing Connect 4 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 Connect 4 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 Connect 4. 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 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. When you play Connect 4, for example, you might be red, and your friend might be yellow. Your goal is to get four red pieces in a row, and your friend's goal is to get four yellow pieces in a row. Since you have different competing goals, you are playing an adversarial game.

The term "Minimax" reflects the algorithm's approach of mini mizing 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 Connect 4 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 using a simpler game (tic-tac-toe):

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 Connect 4, 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.

For a simple game like tic-tac-toe, it is easy to explore to the bottom of the game tree, even from the beginning, since there is a maximum of only nine possible moves in a single game. For a game like Connect 4, where there are more possible combinations, it becomes necessary to either reduce the depth that the algorithm explores or make the algorithm more efficient.

One strategy that has proven powerful in allowing the Minimax algorithm to search deeper down the game tree is called alpha-beta pruning. Alpha-beta pruning functions as a heuristic search algorithm—a problem-solving approach that uses shortcuts or rules of thumb to find solutions more efficiently. Alpha-beta pruning works by strategically reducing the number of nodes it evaluates in the game tree. It ignores branches that are unlikely to influence the final decision . This is particularly helpful when fully exploring every option would take too long. Watch this video for a simple explanation of Minimax with Alpha-Beta Pruning on our Connect 4 example:

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

Even with alpha-beta pruning, it might take too long for the algorithm to explore every possible path at the bottom of the game tree—especially in the early stages of the game. But what if we did not have to exhaustively explore the bottom of the tree for every move?

Image Credit: Science Buddies

At the top is one game grid with open circles representing empty places on the board. One piece has been played: a red circle in the middle of the bottom row. From this grid there are 7 arrows down to the next level, which represents the second play of the game. At the end of each arrow is another grid, this time adding a yellow game piece to the existing red one. The 7 grids at this level represent each possible move for the second (yellow) player. The middle grid on the second row has 7 arrows down to the third row, each ending in a new grid showing possible placements for the third (red) turn. The other grids on the second row each have 7 small arrows down from them, but due to space limitations there is no further representation of those branches. The fourth row represents the possible yellow turns resulting from one of the red positions in the third row. (The other third row branches are again omitted due to space restrictions).

Figure 1. A portion of the game tree starting from a particular state in a Connect 4 game. The Minimax algorithm will search up to a depth (number of turns) specified by the user or until it reaches a terminal state. Note: This illustration does not show every possible outcome from this game state. Additional branches of the game tree are represented by the small arrows.

You might have noticed that certain positions on the board are more desirable than others. For instance, positions in the center offer the player more possible winning combinations than positions on the edges. We can use this information to make our algorithm more efficient.

Image Credit: Science Buddies

Left: A yellow piece in the bottom left corner. Potential 4-piece sequences that include this position are circled: a vertical line up from the bottom left corner, a horizontal line to the right from the bottom left corner, and a diagonal line to the upper right from the bottom left corner. Right: A yellow piece in the middle position. Some of the potential 4-piece sequences that include this position are circled. The possibilities include 3 different vertical sequences, 4 different horizontal sequences, and 6 different diagonal sequences.

Figure 2. Each corner position can only contribute to three winning combinations (left). The center position can contribute to 13 different winning combinations (right). Note: Not all combinations are shown.

To speed up decision-making, we can enhance our algorithm by incorporating an evaluation function. The function we will use assigns a numerical value to each board position based on its desirability. By assessing the strategic advantage or disadvantage associated with a particular position, the algorithm can prioritize exploring paths that lead to more promising game states. This not only reduces the computational burden of exploring every possible move but also empowers the algorithm to make quicker and more informed decisions. Essentially, the evaluation function acts as a heuristic, steering the algorithm toward positions with higher apparent value.

In this Connect 4 challenge, we will provide you with the basic code to create an AI player that makes decisions using the powerful Minimax algorithm with alpha-beta pruning. Your task is to assign every position on the game board a numerical value that reflects its desirability. This step refines the evaluation function and contributes to the creation of a hard-to-beat AI.

Terms and Concepts

• Artificial intelligence
• Algorithm
• Minimax
• Adversarial game
• Recursive
• Game tree
• Game state
• Depth of exploration
• Terminal state
• Alpha-beta pruning
• Heuristic search algorithm
• Evaluation function

Questions

• In adversarial games like Connect 4, what does the Minimax algorithm aim to achieve?
• Explain why the term "Minimax" is used to describe the algorithm's approach.
• What is a game tree? How does it represent the possible outcomes of a game like Connect 4?
• Explain the trade-off involved in choosing the right depth for exploration in the context of Connect 4.
• How does alpha-beta pruning work? What advantage does it provide in the context of game tree exploration?
• Why might the algorithm face challenges in exploring the bottom of the tree, especially in the early stages of the game?
• How does incorporating an evaluation function enhance the algorithm's decision-making process?

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 connect4.ipynb file from Science Buddies.
3. Upload the file to Google Colaboratory. (You will need to sign in to 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.
5. Run the code block under Importing Libraries to bring in all the functions.

Coding Tip:

Occasionally your Runtime may get disconnected, causing your local variables to be lost. If you find yourself getting NameError messages, such as "name 'variable' is not defined," then you have two options:

• Run all of the cells by selecting Runtime > Run all at the top of the notebook.
• Select the cell you are currently working on, then select Runtime > Run before.

Preparing the Game Environment

Next, we will set up the constants and functions required for our game. All the necessary functions have been prepared, so your task is to run the code provided 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 first cell block is where we have defined our constants. Run the code in this cell.
   1. Note: The reason we have defined each of the constants this way is to avoid the use of "magic numbers"—numeric constants used in the code without explanation or clear context. Using magic numbers in code can make it difficult for others (or even the original coder) to understand the significance of these values. It can lead to confusion, maintenance issues, and errors, especially when changes are later made to the code by someone who does not understand what the numbers mean.
   2. To make your code easier to read and maintain, it is a good idea to replace magic numbers with named constants or variables with descriptive names. This makes the code self-explanatory, reducing the chances of introducing errors and making it easier for others to understand the logic.
2. The second cell block contains all helper functions necessary for gameplay.
   1. The create_board function creates an empty game board. The size of the board is determined by the constants ROW_COUNT and COLUMN_COUNT.
   2. The drop_piece function is used to drop a game piece into a specified position on the board.
   3. The is_valid_location function checks whether a given column is a valid location for placing a piece in the game.
   4. The get_next_open_row function finds the next available (empty) row in a given column of the game board.
   5. The print_board function prints the game board for better readability.
   6. The winning_move function checks whether a player with a given game piece has a winning move on the board.
   7. The get_valid_locations function returns a list of valid locations (columns) where a piece can be placed on the current game board.

Creating Our Alpha-Beta Connect 4 Player

Now it is time to develop the evaluation function, a crucial component that will empower our alpha-beta AI player to make informed decisions.

1. The score_position function evaluates the given game board's position for a specific player.

   Navigate to the #TODO comment, below which you will find a 6x7 array. This array is initialized with all zeros, and each element corresponds to a position on the Connect 4 board. Your task is to replace the values in the array with values of your choice, based on your assessment of each position's desirability.

   Assign higher values to positions that you believe are more strategically advantageous. For example, you might prioritize central positions over edge positions, as they offer increased potential for forming winning combinations.

   Strategically assigning values to different board positions this way will influence the AI's decision-making process during gameplay. Take the opportunity to fine-tune the evaluation function, which will enhance the overall performance of our alpha-beta AI.

   Tips:
   • Begin with a reasonable order of magnitude for values. It is often practical to start with values in the range of single or double digits.
   • Focus on the relative ratios between values rather than absolute magnitudes. This means that if one position is assigned a value of 20 and another position is assigned a value of 10, it is the ratio (2:1) that matters more than the difference between the values (10).
   • Negative values are discouraged for this game. As gameplay continues, certain moves may be unavoidable and therefore not necessarily a bad choice.
2. The remaining functions in this code block contribute to the implementation of the Minimax algorithm, enhanced with alpha-beta pruning.
   1. The is_terminal_node function checks whether the current state of the game board represents a terminal node, indicating the end of the game.
   2. The minimax function implements the Minimax algorithm with alpha-beta pruning for finding the best move on the board.
3. To integrate these functionalities into our AI player, run this code block.

Playing the Game Against Our AI Player

We are ready to play against our AI player! Run the code block in this section to start the game. You can run it again to play the game multiple times—no need to rerun every cell each time you play.

1. Challenge yourself to win against the AI player.
   1. As a control test, set all positions in the evaluation function to zero. Play some games against the AI and record your results.
   2. Set the evaluation function to your chosen values and record them in your lab notebook. Play 10 games against the AI player and record how many times you won, lost, and ended the game in a draw.
   3. Make changes to your evaluation function. Play 10 more games against the AI player and record the results.
      Note: If your AI is making moves that are undesirable to you (for example, making moves at the edges instead of the center), give more weight to the positions you want your AI to choose and less weight to the positions you do not want your AI to choose.
   4. Continue to make changes and record your results until you are satisfied that your AI player is performing well.
2. Look at your data and compare how well the AI performed with different values for the evaluation function. Do you notice a significant difference?

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

Can you solve this air pressure puzzle? | STEM Activity

Candy Core Samples | STEM Activity

How to Calibrate the Sound Sensor in Phyphox