Proposal : Gomoku AI with Adjustable Difficulty & Algorithm Comparison

[kimpro82]

1. Overview

The goal of this project is to develop a Gomoku (Five-in-a-Row) game that serves as a sandbox for testing and comparing various CPU decision-making algorithms. Instead of a single static AI, the system will allow users to toggle between different logic sets (Heuristics, Minimax, MCTS) and adjust parameters like search depth and simulation counts to observe how they affect difficulty and gameplay balance.

2. Technology Stack Options (Under Evaluation)

The project will be implemented using one of the following:

• Python: Ideal for rapid prototyping of complex algorithms (MCTS, Alpha-Beta).
• Web (Vanilla TypeScript): Best for accessibility and visual interaction without installation.
• Excel VBA: A unique challenge leveraging grid-based UI, though potentially limited in heavy recursion performance.

3. Core Features

• Interactive Game Board: A standard 15x15 Gomoku grid with stone placement and win-condition detection.
• Algorithm Toggle Menu: A real-time UI component to switch the CPU's logic during or before a match.
• Visualized Debugging (Optional): Highlighting the board positions the AI is currently evaluating or scoring.

4. Implementation Scopes (Difficulty Control)

The AI difficulty will be categorized and adjustable via the following methods:

A. Rule-Based / Heuristic Engine (Level 1-2)

• Priority 1: Immediate win (Connect 5).
• Priority 2: Immediate block (Stop opponent's 4).
• Priority 3: Pattern Matching (Score Open 3s, Broken 4s).
• Control: Adjusting weight tables for different patterns.

B. Search-Based Engine (Level 3-4)

• Minimax with Alpha-Beta Pruning: Simulating $N$ moves ahead.
• Control:
  • Depth (d): Limit the number of turns the AI "looks into the future."
  • Move Candidate Limit: Restrict search to stones within $k$ distance of existing pieces to optimize performance.

C. Simulation-Based Engine (Level 5+)

• Monte Carlo Tree Search (MCTS): Using random playouts to determine the win probability of a branch.
• Control:
  • Iterations (n): Restrict the number of simulations per move to simulate "thought time" or "processing power."

5. Comparative Analysis Tooling

• Step-by-Step Execution: A mode to see the "Score" the AI assigns to each coordinate.
• Performance Metrics: Display time taken per move (ms) and nodes visited.
• AI vs. AI Mode: Ability to watch two different algorithms (e.g., Minimax Depth 3 vs. MCTS n=1000) play against each other to evaluate balance.

6. Success Metrics

• CPU should not miss an obvious "Open 4" on Medium difficulty.
• AI vs. AI matches should demonstrate a clear hierarchy in win rates as search depth or iterations increase.
• The UI must remain responsive during CPU calculation (especially for Web/Python versions).