Optimized VCST Algorithm for Connect6

Since the concept of Connect6 was first introduced by Professor Wu at National Chiao Tung University in Taiwan, there has been massive progress in the study of Connect6. Recently VCF(victory by continuous four) algorithm has become a well-known game search method for Connect6. This method performs well in attacking the opponent and finding offensive ways to win. Based on the VCF method of Gomoku, this paper proposes an algorithm called VCST (victory by continuous single-threat-or-more moves) for Connect6. For any feasible solution searched out, the solution is a winning strategy, and there is no need to continue traversing the tree. This method uses the AND/OR tree strategy to improve the search efficiency of the algorithm, and a parallel implementation method is designed for this strategy to speed up The running speed of the algorithm. The experimental result shows that our improved VCST algorithm improves the program robustness and leads to an increment of winning chance. Our gaming program won second place in the 14th National Undergraduate Computer Game Competition.