Connect 4 with Minimax & Alpha-Beta Pruning

Overview

This project is a two-player Connect 4 game implementation featuring an AI opponent powered by the Minimax algorithm with Alpha-Beta pruning. The AI simulates optimal play by evaluating future game states and selecting the best possible move while limiting search complexity through depth constraints.

This project demonstrates fundamental concepts in game theory, adversarial search, and artificial intelligence.

---

Problem Description

Players:

• Two players take turns dropping discs into the board
• One player uses red (MAX) discs
• The other uses blue (MIN) discs

Objective:
Be the first player to connect four discs in a row.

Board:

• 7 columns × 6 rows vertical grid

Gameplay Rules:

• Players alternate turns
• A disc is dropped into a chosen column
• The disc falls to the lowest available position in that column

Winning Conditions:

• Four connected discs horizontally
• Four connected discs vertically
• Four connected discs diagonally

Draw Condition:

• If the board fills completely with no winner, the game ends in a draw

---

AI Approach: Minimax Algorithm

Minimax Overview

The Minimax algorithm is used for:

• Two-player
• Turn-based
• Deterministic games

Key Concepts:

• One player acts as the Maximizer
• The opponent acts as the Minimizer
• Both players are assumed to play optimally
• The algorithm simulates all possible future moves
• The best move is selected based on maximizing or minimizing the evaluation score

---

Alpha-Beta Pruning

To improve performance, Alpha-Beta pruning is used to:

• Eliminate branches of the game tree that cannot influence the final decision
• Reduce the number of states evaluated
• Allow deeper searches within reasonable execution time

---

Implementation Details

Depth Limiting

• A maxDepth parameter limits how deep the Minimax search goes
• Necessary due to the large size of the Connect 4 game tree
• Depth is passed recursively through Minimax calls
• Once maxDepth is reached, the board state is evaluated heuristically

---

Core Methods

getAllRemainingMoves()

• Returns all valid columns where a disc can be dropped
• Checks only the top cell of each column to determine availability

execute(Square move, boolean isMax)

• Simulates placing a disc in the selected column
• Drops the disc into the lowest available row
• Uses:
  • X for MAX player
  • O for MIN player

utility()

Evaluates the board state:

• 1 → MAX player wins
• -1 → MIN player wins
• 0 → No winner yet

A return value of 0 signals that the game should continue searching deeper until a terminal state or depth limit is reached.

---

Technologies Used

• Java
• Minimax Algorithm
• Alpha-Beta Pruning
• Game Tree Search
• Artificial Intelligence

---

Key Concepts Demonstrated

• Adversarial search
• Decision-making under optimal play assumptions
• Recursive algorithms
• Game state evaluation
• Performance optimization through pruning