(54.81.44.140) 您好!臺灣時間:2017/09/25 01:27          離開系統
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
研究生:施宣丞
研究生(外文):Hsuan-Chen Shih
論文名稱:暗棋程式DarkCraft的設計與實作
論文名稱(外文):The Design and Implementation of Dark Chess Program DarkCraft
指導教授:林順喜
指導教授(外文):Shun-Shii Lin
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文出版年:2011
畢業學年度:100
語文別:中文
論文頁數:55
中文關鍵詞:電腦對局不完全資訊遊戲暗棋位元棋盤
外文關鍵詞:Computer GamesImperfect Information GamesDark ChessBitBoard
相關次數:
  • 被引用被引用:5
  • 點閱點閱:985
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:60
  • 收藏至我的研究室書目清單書目收藏:0
電腦對局在人工智慧領域中佔有很大的份量,它主要分為完全資訊遊戲和不完全資訊遊戲兩大類,完全資訊遊戲是指所有玩家都可以掌握全部資訊的遊戲,例如:圍棋、西洋棋、象棋,不完全資訊則是各方玩家都只能掌握一部分資訊的遊戲,例如:暗棋、麻將、撲克牌遊戲,其中電腦暗棋是近年剛起步,擁有很大發展空間的不完全資訊遊戲。
一個程式的基礎是資料結構,有了好的資料結構才可以讓我們有足夠的基礎去構思出好的演算法,本研究將西洋棋最有效率的資料結構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
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔