lihongxun945/gobang

What it solves

This project provides a playable Gomoku (Five in a Row) game featuring an AI opponent that runs entirely within the web browser. It serves as both a functional game and a practical implementation of classic game-tree search algorithms for educational and research purposes.

How it works

The AI is built using the Minimax search algorithm with several performance optimizations to make it viable for JavaScript execution in a browser. Key technical implementations include:

• Search Algorithms: Uses Minimax with Alpha-Beta pruning to reduce the number of nodes evaluated.
• Optimization Techniques: Employs iterative deepening, Zobrist hashing (transposition tables), and "killer move" sorting to improve search efficiency.
• Evaluation: Uses a heuristic evaluation function to score board positions based on patterns (e.g., open threes, blocked fours).
• Tactics: Includes a VCT (Victory by Continuous Threat) search to identify forced win sequences.
• Difficulty Levels: Adjusted by changing the search depth; deeper searches result in stronger play but require more computation time.

Who it’s for

• Developers interested in game AI and search algorithms.
• Students learning about Minimax, Alpha-Beta pruning, and heuristic evaluation.
• Casual players who want to play Gomoku against a browser-based AI.

Highlights

• Pure Frontend: The AI runs locally in the browser, meaning no server-side processing is required after the initial page load.
• Comprehensive Testing: Includes a dedicated AI evaluation suite to measure Elo ratings and node throughput against different baselines.
• Tactical Validation: Features a tactical puzzle library with rotation and mirror extensions to diagnose AI blind spots.
• Educational Resources: Accompanied by a series of detailed blog tutorials explaining the design and implementation of the AI.