暗棋程式DarkCraft的設計與實作

Abstract

電腦對局在人工智慧領域中佔有很大的份量，它主要分為完全資訊遊戲和不完全資訊遊戲兩大類，完全資訊遊戲是指所有玩家都可以掌握全部資訊的遊戲，例如：圍棋、西洋棋、象棋，不完全資訊則是各方玩家都只能掌握一部分資訊的遊戲，例如：暗棋、麻將、撲克牌遊戲，其中電腦暗棋是近年剛起步，擁有很大發展空間的不完全資訊遊戲。 一個程式的基礎是資料結構，有了好的資料結構才可以讓我們有足夠的基礎去構思出好的演算法，本研究將西洋棋最有效率的資料結構BitBoard融合到暗棋裡，讓程式能有很快的執行速度，並改良演算法強化棋力。 本研究已設計並實作了一個暗棋程式DarkCraft，在2011年於荷蘭獲得由國際電腦對局協會(International Computer Games Association)舉辦之電腦奧林匹亞(Computer Olympiad)冠軍。Computer games are one of the most important research areas in artificial intelligence. These games fall into two fundamentally different classes: perfect information games and imperfect information games. In perfect information games such as Go and Chess, the current state of the game is fully accessible to both players. In games such as Dark Chess and Poker, the players have imperfect information: they have only partial knowledge about the current state of the game. Particularly, many Dark Chess programs have just been developed in recent years and they have a lot of room to improve their algorithms and implementations. The data structure is the foundation of programming and algorithm design. A proper data structure can improve code efficiency. In this research, we apply the BitBoard data structure which was commonly used in chess programs to build our Dark Chess program DarkCraft. We also investigate the special characteristics of Dark Chess to fit the requirements of BitBoard and hence reduce the computation time. Furthermore, some techniques are integrated to improve the playing strength. In this study, we have designed and implemented a Dark Chess program DarkCraft which participated in the 16th Computer Olympiad held in Tilburg, the Netherlands in 2011, and won the gold medal in the Dark Chess tournament.