暗棋程式DarkCraft的設計與實作

The Design and Implementation of Dark Chess Program DarkCraft

施宣丞(Hsuan-Chen Shih)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2012年)

摘要

電腦對局在人工智慧領域中佔有很大的份量，它主要分為完全資訊遊戲和不完全資訊遊戲兩大類，完全資訊遊戲是指所有玩家都可以掌握全部資訊的遊戲，例如：圍棋、西洋棋、象棋，不完全資訊則是各方玩家都只能掌握一部分資訊的遊戲，例如：暗棋、麻將、撲克牌遊戲，其中電腦暗棋是近年剛起步，擁有很大發展空間的不完全資訊遊戲。
一個程式的基礎是資料結構，有了好的資料結構才可以讓我們有足夠的基礎去構思出好的演算法，本研究將西洋棋最有效率的資料結構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.

並列關鍵字

Computer Games ； Imperfect Information Games ； Dark Chess ； BitBoard

參考文獻

[1]謝曜安，電腦暗棋之設計及實作，國立台灣師範大學資工所碩士論文，2008。

[3]謝政孝，暗棋中棋種間食物鏈關係之探討與實作，國立臺灣師範大學資工所碩士論文，2010。

[4]勞永祥，電腦暗棋之人工智慧改良，國立臺灣師範大學資工所碩士論文，2011。

[2]賴學誠，電腦暗棋程式與經驗法則之配合與實作，國立東華大學資工所碩士論文，2008。

[5] WIKI Chess Programming網站