AI MinMax Model Report

Overview

To develop this model, we employed various algorithms, heuristics, and optimization strategies. The key components of our approach include:

• MinMax algorithm
• Alpha-Beta pruning
• Our heuristic, based on a scoring system
• Using Transposition Table to enhance performance
• Strictly deciding the next move if it's 100% winning or losing in the current position

---

MinMax Algorithm

We needed a model that was deterministic, static, and discrete; therefore, we used the MinMax algorithm.

The MinMax algorithm is a pivotal tool in game theory, especially effective in zero-sum games like Connect 4, where each player’s gain or loss is exactly balanced by the losses or gains of the other player.

---

Optimization: Pruning Based on Win/Loss

We attempted to optimize our algorithm using Alpha-Beta pruning.

Problem:

• We can’t always find a winning or losing position in our depth search.

Solution: Using Heuristics

• We enhanced our optimization method by using a heuristic function and a scoring system to assign points to each move.
• We implemented a better version of Alpha-Beta pruning, which later enhanced our performance.

---

Heuristic Function

Our scoring system is based on:

• 4 pieces together (highest score)
• 3 pieces together
• 2 pieces together
• 3 pieces of the opponent together (dangerous positions)

We prioritize:

• Following variations that create 4 of our pieces together.
• Avoiding variations where the opponent has 3 pieces together.
• Stopping the opponent from winning should score higher than forming 2-3 pieces together but lower than making a winning move.
• Assigning more points for pieces in the center column of the board.

---

Enhancing Implementation

To speed up the implementation of our MinMax algorithm and minimize runtime delay, we used a Transposition Table.

Transposition Table:

A cache of previously seen positions and associated evaluations in a game tree generated by a computer game-playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position. Similar to how Dynamic Programming works.

---

Bug Fixes

Issue:

• When both the robot and the opponent were one move away from winning, the robot would sometimes block the opponent instead of making the winning move itself.

Solution:

• We implemented a check to determine if the robot can win in one move using our evaluation function, ensuring that it prioritizes a winning move over blocking.

---

Performance

This model is highly effective!

• We tested it against multiple human players at different skill levels.
• It successfully defeated the AI opponents at “too easy,” “easy,” “medium,” and “hard” difficulty levels on the Mathsisfun website.
• Even though Connect 4 is a solved game (where the first player always wins with optimal moves), our robot managed to win multiple times as the second player!

---

Future Optimizations

To further enhance performance, we plan to:

• Use Bitboards:

  • Store board positions using two bitboards per player, allowing faster access and easier computations.

• Implement Iterative Deepening:

  • Explore the search tree at shallow depths first, then iteratively deeper.
  • Helps find shallow winning paths early and improves transposition table efficiency for better pruning.

• Reimplement in C or C++:

  • Using higher depths in search algorithms to improve decision-making speed and accuracy.

---

Conclusion

Our MinMax-based AI model demonstrates strong performance in Connect 4 by integrating heuristics, Alpha-Beta pruning, and transposition tables. Future improvements will focus on speed and efficiency, making the model even stronger against advanced opponents.