Designing an Intelligent Five-in-a-Row AI: From Heuristics to Continuous Red Four Search

Executive Summary

In the realm of Artificial Intelligence, board games have long served as the ultimate "drosophila" for testing reasoning and decision-making. This paper delves into the design and implementation of a Five-in-a-Row (Gomoku) AI. By refining the classic Alpha-Beta search and introducing a specialized Continuous Red Four (VCF) search, the author has created a system that balances tactical depth with computational efficiency. The project not only tackles algorithmic challenges but also provides a decoupled system architecture for human-machine interaction.

Problem & Motivation: The Limits of Hindsight

Most entry-level Gomoku AIs rely on a "Greedy Algorithm" or shallow minimax search. The core pain point is two-fold:

1. Blind Spots in Evaluation: If a program only looks at one line at a time, it fails to see the "X" marks the spot—the intersections where two "threes" create a "Three-Three" win.
2. The Horizon Effect: Standard search algorithms are depth-limited. In Gomoku, a winning sequence of forced moves (Continuous Fours) might be 10-15 steps long, far beyond the 4-6 ply depth a standard PC can search in real-time.

Methodology - The Core Algorithms

1. Hybrid Evaluation Function

The author moves beyond simple linear scoring. For every position $(x,y)$, the score is calculated by summing the values of all 5-tuple sets it belongs to across four directions. The innovation lies in the Combo Addition:

$s(x,y)=\sum (w)+\sum (combo)$

By assigning massive bonuses to intersecting patterns (e.g., Two 'Rule 4' occurrences), the AI becomes "aware" of strategic traps like double-fours or four-three combinations.

2. Game-Tree Search with Alpha-Beta Pruning

The system utilizes the Minimax principle, where the PC (Max) seeks to maximize the score and the opponent (Min) seeks to minimize it. Alpha-Beta pruning is applied to skip branches that are guaranteed to be worse than previously explored paths.

Figure 1: The Alpha-Beta pruning process significantly reduces the number of nodes visited (from 34 down to 21 in this example).

3. Continuous Red Four (VCF) Search

This is the "special weapon" of the paper. Since a "Red Four" (an open four or a blocked four) forces a specific response from the opponent, the search space for these moves collapses. The author implements a dedicated VCF module that searches these forced sequences to much greater depths than the main game tree.

Figure 2: A complex winning sequence achieved through continuous forced moves, detectable only by specialized deep-searching VCF.

System Architecture: Decoupling for Scalability

The author emphasizes a software engineering approach by dividing the system into four independent modules:

• Game: Logical flow and rule enforcement.
• GameBoard: Data storage and move history.
• Player: Abstract interface for Humans or External AI "brains."
• Displayer: Java-based GUI.

This decoupling allows the AI (written as a separate executable) to communicate via a custom protocol (START, PUT, REGRET) through standard I/O, making it easy to swap AI engines or host AI-vs-AI battles.

Experiments & Results

The AI was tested in the Peking University AI Lab Gomoku Tournament (72 participants).

• Performance: Rank 23/72.
• First-move Advantage: The AI was significantly stronger when playing Black (First-move), winning 63% of games compared to 46% when playing White.
• Efficiency: The VCF search effectively found winning paths in 9-ply sequences that standard search missed.

(Note: The AI showed a strong mid-to-high tier performance but struggled against top-tier bots that utilize advanced techniques like Transposition Tables.)

Critical Analysis & Conclusion

Takeaway

The paper successfully demonstrates that expert knowledge (specific Gomoku patterns) and specialized search heuristics (VCF) are more critical than raw hardware power for this specific game.

Limitations

1. Static Ordering: While the AI uses a basic sorting for moves, it lacks "History Heuristics" which would improve pruning efficiency by remembering "killer moves."
2. Fixed Evaluation: The scoring is hand-tuned. Modern approaches would use Neural Networks or Genetic Algorithms to optimize these weights automatically.

Future Work

The author suggests integrating Opening Books and Self-Learning databases to prevent the AI from falling for the same trap twice and to enhance performance in the early game.