Mastermind game implemented in Java with an AI solver based on graph traversal, greedy heuristics, dynamic programming, and backtracking optimizations, inspired by ideas from Simon Tatham.
This project is an advanced Java-based implementation of the Mastermind game featuring an intelligent AI solver.
The solver combines multiple algorithmic paradigms:
- Graph-based Breadth First Search (BFS) for state traversal
- Greedy Minimax strategy for selecting optimal guesses
- Dynamic Programming (Tabulation) for fast feedback lookup
- Backtracking (DFS) for constraint-based candidate generation
- Divide & Conquer (Merge Sort) for ordering candidate states
The game includes a fully interactive Java Swing GUI allowing both human and AI turns.
- Graph Modeling of Game States
- Breadth First Search (BFS)
- Greedy Algorithms (Minimax Strategy)
- Dynamic Programming (Tabulation)
- Backtracking with Constraint Pruning
- Divide & Conquer (Merge Sort)
- Object-Oriented Programming (OOP)
- Java
- Java Swing (GUI)
- Graph Traversal Algorithms
- Greedy Heuristics
- Dynamic Programming
- Backtracking Search
- Event Handling
- Interactive drag-and-drop color selection
- Graph-based BFS solver for game state management
- Improved greedy move selection minimizing worst-case search space
- Dynamic Programming feedback table for constant-time lookup
- Backtracking candidate generation with constraint pruning
- Merge Sort ordering of remaining possibilities
- Visual feedback using black and white pegs
- Human vs AI cooperative gameplay
- Restartable game session
Handles core game logic:
- Secret code generation
- Guess evaluation (black & white peg feedback)
- Generation of all possible code vertices
- Dynamic Programming feedback table
Responsible for AI solving logic:
- BFS-based game state traversal
- Constraint pruning of candidate codes
- Backtracking-based candidate generation
- Greedy minimax move selection
- Merge Sort ordering of candidate states
Implements recursive DFS-based candidate generation:
- Builds possible codes slot-by-slot
- Applies feedback constraints from previous guesses
- Prunes invalid branches early
Java Swing graphical interface:
- Drag-and-drop color input
- Displays guess history and feedback pegs
- Manages human and AI turns
- Integrates solver with the game board
Human Guess
↓
Engine Feedback Evaluation
↓
Backtracking Candidate Generation (DFS)
↓
Merge Sort Ordering (Divide & Conquer)
↓
Greedy Minimax Move Selection
↓
BFS State Update
git clone https://github.com/yourusername/Mastermindjavac *.javajava MastermindBoardGUI