Connect Four AI

Project Overview

This project implements a Connect Four AI using the negamax algorithm (a variant of minimax) with alpha-beta pruning and a transposition table. The AI is capable of playing Connect Four at a high level by efficiently evaluating game states and choosing optimal moves.

Technical Implementation

1. Negamax Algorithm: Uses a variant of the minimax algorithm for game tree search
2. Alpha-Beta Pruning: Optimizes the search by eliminating branches that don't need to be evaluated
3. Transposition Table: Stores previously evaluated game states to avoid redundant calculations
4. Heuristic Function: Evaluates non-terminal game states based on board position

Key Features

• Generates all possible outcomes for each new game state (to a certain depth)
• Evaluates the value of each outcome based on a heuristic function and win conditions
• Uses alpha-beta pruning to optimize the search process
• Implements the negamax algorithm to choose the best move

Improvements

Additional enhancements were made based on Jonathan Schaeffe's paper "The History Heuristic and Alpha-Beta Search Enhancements in Practice".

Future Work

• Implement machine learning techniques to improve the heuristic function
• Develop a graphical user interface for human vs. AI play
• Optimize for multi-threaded execution to increase search depth