An Algorithm Design and Implementation of Connect6

Abstract:

The new Connect6 game was launched and received the widespread attention in recent years. For the problems existing in pattern judgment way and in 6-8 windows in some literatures, the algorithm of Connect6 is studied by considering the attack and defensive characteristics of the Connect6. By the new 6-8 window approach proposed here, the evaluation function which determines the evaluation value is designed and implemented by calculating the changing quantity of the assessed values of the chessboard before and after the falling a stone. Based on this, an optimal Connect6 program is designed and implemented based on the PVS algorithm and the transposition table optimization, history heuristic optimization, null-move pruning optimization as well as iterative deepening optimization. The pruning rate of nodes in game tree comes to more than 98%. The actual playing of the chess indicates that the program has the strong chess strength.

• Periodical: Advanced Materials Research (Volumes 546-547)
• Pages: 1501-1506
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.546-547.1501
• Online since: July 2012
• Authors: Wei Yi Shi, Yun Fu Shen
• Keywords: Connect6, Evaluation Function, Game Algorithm, New 6-8 Window Approach, PVS Algorithm

References

[1] Wu I-Chen, Huang Dei-Yen. A new family of k-in-a-row games [J]. Lecture Notes in Computer Science, 2006, LNCS 4250: 180-194. (Advances in Computer Games - 11th International Conference, ACG 2005)

DOI: 10.1007/11922155_14

[2] http://www.connect6.org/.

[3] Wu I-Chen, Lin Ping-Hung. Relevance-zone-oriented proof search for Connect6 [J]. IEEE Transactions on Computational Intelligence and AI in Games, 2010, Vol.2, No.3: 191-207.

DOI: 10.1109/tciaig.2010.2060262

[4] Wu I-Chen, Chen Chingping, Lin Ping-Hung, et al. A volunteer-computing-based grid environment for connect6 applications [C]. Proceedings - 12th IEEE International Conference on Computational Science and Engineering. 2009: 110-117.

DOI: 10.1109/cse.2009.412

[5] Li Guo. Research and Realization of the Computer game and system of Connect6 [D]. Chongqing: College of Automation, Chongqing University, 2007.

[6] Li Guo. Adjustment and Optimization of the Connect6 Evaluation Function Parameters Based on Genetic Algorithm [J]. Journal of Southwest University, 2007, Vol.29, No.11: 138-142.

[7] Min Wenjie. Research About The Key Technologies of The Connect6 Computer Game [D]. Chongqing: Chongqing Jiaotong University, 2010.

[8] ZHANG Xiao-chuan, CHEN Guang-nian, ZHANG Shi-qiang, et al. Research on Evaluation Functions for Computer Game of Connect6 [J]. Journal of Chongqing University of Technology, 2010, Vol.24, No.2: 64-68.

[9] HAN Feng-qing, LI Cui-zhu, LI Wei. Research on Revaluation of Connect6 Game [J]. Journal of Chongqing Institute of Technology, 2009, Vol.23, No.11: 57-60.

[10] XU Chang-ming, MA Zong-min, XU Xin-he. A New Board Representation Method for K-in-a-row Games with Its Application to Connect6 [J]. Journal of Northeastern University, 2009, Vol.30, No.4: 514-517.

[11] HUANG Ji-ping, MIAO Hua, ZHANG Dong. Optimizing the Evaluation Function Parameters of Connect6 with Genetic Algorithms [J]. Journal of Chongqing Institute of Technology, 2009, Vol.23, No.11: 85-89.

[12] HUANG Ji-Ping, ZHANG Dong, MIAO Hua. The Research and Implementation of Connect6 Intelligent Chess Game System [J]. Computer Knowledge and Technology, 2009, Vol.5, No.25:7198-7200.