國立臺灣師範大學博碩士論文全文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	施宣丞 Hsuan-Chen Shih
論文名稱：	暗棋程式DarkCraft的設計與實作 The Design and Implementation of Dark Chess Program DarkCraft
指導教授：	林順喜 Lin, Shun-Shii
學位類別：	碩士 Master
系所名稱：	資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2012
畢業學年度：	100
語文別：	中文
論文頁數：	55
中文關鍵詞：	電腦對局、不完全資訊遊戲、暗棋、位元棋盤
英文關鍵詞：	Computer Games, Imperfect Information Games, Dark Chess, BitBoard
論文種類：	學術論文
相關次數：	點閱：163 下載：48
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

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

摘要    i
ABSTRACT    ii
致謝    ii
目錄    iv
表目錄    vi
圖目錄    vii
第一章 緒論    1
第一節    暗棋的規則    1
第二節    論文概要    2
第三節    相關論文及程式介紹    3
第四節    近年Computer Olympiad比賽紀錄    4
第二章 資料結構相關研究    5
第一節    西洋棋BitBoard表示法    5
第二節    西洋棋BitBoard產生小兵走步    8
第三節    西洋棋BitBoard產生國王走步    10
第四節    西洋棋BitBoard產生騎士走步    11
第三章 搜尋演算法相關研究    12
第一節    Game Tree    12
第二節    Min-Max Search    13
第三節    Nega-Max Search    16
第四節    Alpha-Beta Pruning    17
第四章 暗棋與BitBoard資料結構    19
第一節    簡介    19
第二節    暗棋BitBoard資料結構表示法    20
第三節    BitBoard兵種表示法    21
第四節    BitBoard行與列的遮罩    23
第五節    遮罩用法    25
第六節    BitBoard產生一般兵種走步    26
第七節    BitBoard產生炮之吃子步    29
第五章 BitBoard與棋盤編號之間的轉換    34
第六章 BitBoard效能測試    35
第七章 新的暗棋演算法策略    37
第一節    翻子策略    37
第二節    向上傳遞更新法    42
第三節    同分步處理    43
第四節    單向搜尋    45
第五節    寧靜搜尋    46
第八章 結論與未來方向    47
第一節    結論    47
第二節    未來方向    49
第九章 附錄    50
第十章 參考文獻    55

                                

[1]謝曜安，電腦暗棋之設計及實作，國立台灣師範大學資工所碩士論文，2008。
[2]賴學誠，電腦暗棋程式與經驗法則之配合與實作，國立東華大學資工所碩士論文，2008。
[3]謝政孝，暗棋中棋種間食物鏈關係之探討與實作，國立臺灣師範大學資工所碩士論文，2010。
[4]勞永祥，電腦暗棋之人工智慧改良，國立臺灣師範大學資工所碩士論文，2011。
[5] WIKI Chess Programming網站
http://chessprogramming.wikispaces.com/
[6]Game Tree by Yosen Lin
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
[7]維基百科
http://zh.wikipedia.org/