跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/20 06:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張懷文
論文名稱:5五將棋程式Wonders的設計與實作
論文名稱(外文):Design and Implementation of Computer Minishogi “Wonders”
指導教授:林順喜林順喜引用關係
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:63
中文關鍵詞:5五將棋人工智慧TAAIICGATCGA
外文關鍵詞:AImini-shogiTAAIICGATCGA
相關次數:
  • 被引用被引用:1
  • 點閱點閱:544
  • 評分評分:
  • 下載下載:30
  • 收藏至我的研究室書目清單書目收藏:0
利用人工智慧與人對弈的這個概念,可以追溯自1769年。但直到了1950年,人工智慧這個領域出現了一位Shannon教授致力於如何發展能夠與人對弈的西洋棋程式,這領域的研究才逐漸有穩定發展的方向。許多後來從事電腦對局領域的相關研究人員,也都跟隨Shannon教授的觀念發展而來。直至現今,無論是西方的跳棋、西洋棋、五子棋、撲克牌,抑或是東方的象棋、暗棋、孔明棋、將棋等等,許多的對弈遊戲皆成為電腦對局領域裡面研究的項目。
其中日本的mini-shogi(5五將棋),為日本將棋於1970年左右發展的其一分支。並於2007年開始,發展國際電腦對局的相關賽事。由日本的電氣通信大學所舉辦的UEC Cup到ICGA的Computer Olympiad,5五將棋已經成為在國際賽事中被熱烈參與的項目之一。在台灣近幾年也被TCGA(Taiwan Computer Games Association)和TAAI(Technologies and Applications of Artificial Intelligence)列為固定的競賽項目之一了。
本研究論文中實作之程式Wonders,利用alpha-beta搜尋來幫助我們找到最佳走步。並且利用嶄新的審局函數快速的減少搜尋分支,以減少執行時間。另外我們也使用暫存表以及Zobrist hashing 和 bitboard的技術來提升程式的計算效能。從2011年研發至今,Wonders於2013年的TAAI 電腦對局競賽當中獲得5五將棋的金牌,期望在未來能夠有更穩定且具有突破性的研究發展。

Since 1769, people already started the research about artificial intelligence ( AI ) . Until 1950, Professor Shannon devoted in developing the program, which can play Chess against human. This field became more stable with his research. Till now, many games such as Chess, Checkers, Connect Five, Pokers etc. have already been included in computer games research.
Among these games, mini-shogi came from a branch of shogi around 1970. The competition of computer mini-shogi had become one of the international events since 2007. From the UEC Cup in Japan to the Computer Olympiad from ICGA (International Computer Games Association), mini-shogi has become one of the important game items. In Taiwan, there are more and more competitions, for example, TCGA (Taiwan Computer Games Association) and TAAI (Technologies and Applications of Artificial Intelligence), that also included mini-shogi.
In this paper, the author implemented the mini-shogi engine which is called “Wonders” with alpha-beta search algorithm for AI to search the best move. Cut-off and a novel evaluation function were applied to reduce the execution time. The transposition table, Zobrist hashing and bitboard techniques were used in the program.
From 2011 till now, “Wonders” has already attended a lot of events. This program also won the champion of TAAI 2013 computer game tournament of mini-shogi. Hope we can have more stable and more promotions in this research in the future.

目錄
摘要 2
Abstract 3
致謝 4
目錄 5
圖目錄 7
表目錄 8
第一章 緒論 9
1.1 研究背景 9
1.2 研究目的 11
1.3 研究意義 13
1.4 論文架構介紹 14
第二章 5五將棋介紹 15
2.1 5五將棋簡介 15
 2.1.1 5五將棋歷史 15
 2.1.2 5五將棋走步 17
 2.1.3 5五將棋規則 20
2.2 5五將棋目前研發狀況 23
 2.2.1 台灣 25
 2.2.2 國際研發狀況 27
第三章 演算法及資料結構文獻探討及研究 29
3.1 遊戲樹(Game Tree Search)相關介紹 29
 3.1.1 Game Tree 29
 3.1.2 Min-Max Search 30
 3.1.3 Alpha-Beta Search 32
 3.1.4 Nega-Max Search 34
3.2 Bitboard 35
 3.2.1 Bitboard 在各棋類的應用 35
 3.2.2 Bitboard 在各棋類的走步生成 38
第四章 資料結構實作 39
4.1 5五將棋棋盤表示法 39
4.2 王將、金將、銀將、步兵走步生成 41
4.3 飛車、角行、龍王、龍馬走步生成 43
4.4 Bitboard與棋盤之間的轉換 45
第五章 系統實作與改良 46
5.1 針對「打入」的搜尋複雜度控制 46
5.2 子力分設計 48
5.3 向上傳遞更新法 51
5.4 千日手與特殊開局庫 52
5.5 Transposition Table 54
第六章 相關效能測試 56
第七章 結論與未來方向 58
第八章 附錄 59
8.1 比賽紀錄 59
8.2 參考文獻 63

[1]Levitt, G. M. (2000). The Turk, chess automaton.McFarland & Co Inc Pub.
[2] Shannon, C. E. (1950). XXII. Programming a computer for playing chess.Philosophical magazine, 41(314), 256-275.
[3] Van den Herik, H. J., Uiterwijk, J. W., & Van Rijswijck, J. (2002). Games solved: Now and in the future. Artificial Intelligence, 134(1), 277-311.
[4]ICGA網站。2013-02-28 取自http://icga.uvt.nl/
[5]5五將棋歷史。2013-02-26取自http://zh.wikipedia.org/wiki/5%E4%BA%94%E5%B0%87%E6%A3%8B
[6]UEC Cup官方網站。2013-02-26取自http://minerva.cs.uec.ac.jp/~uec55/index.php?option=com_content&view=article&id=12&Itemid=21
[7]Thomas, L. C., Games, Theory and Applications,Mineola N.Y.: Dover Publications.(2003) pp. 19. ISBN 0-486-43237-8.
[8]吳光彧(2013)。5五將棋知識庫系統實作(碩士)。長榮大學資訊管理研究所學位論文,臺南縣。
[9]Wu, K. Y., Chen Jr, C., Yen, S. J., & Hsu, S. C. (2012, November).Design of Knowledge-Based Opening Database for MiniShogi. In Technologies and Applications of Artificial Intelligence (TAAI), 2012 Conference on (pp. 290-293). IEEE.
[10]Knuth, D.E., Moore, R.W.: An Analysis of Alpha-Beta Pruning. Artificial Inteligence 6,
293–326 (1975)
[11]Soeda, Shunsuke, Tomoyuki Kaneko, and Tetsuro Tanaka."Dual lambda search and shogi endgames." Advances in Computer Games (2006): 126-139.
[12]Takizawa, Takenobu, and ReijerGrimbergen. "Review: Computer shogi through 2000." Computers and Games (2001): 433-442.
[13]WinBoard mini-Shogi package。 2014-01-12取自 http://hgm.nubati.net/miniShogi.html
[14]HendrixMathematics & Computer Science。2014-01-12取自http://ozark.hendrix.edu/
[15]GAMELab - 國立東華大學。2014-01-12取自http://www.game.csie.ndhu.edu.tw/
[16]Brudno, A. L. (1963).Bounds and valuations for abridging the search of estimates. Problems of Cybernetics, 10, 225-241.
[17]Bitboard Board-Definition。2014-01-12取自http://chessprogramming.wikispaces.com/Bitboard+Board-Definition
[18]Bitboards。2014-01-12取自http://redalt.com/working-in-reversi-part-3
[19]詹凱翔(2013)。電腦暗棋程式Darkness的設計與實作(碩士)。國立臺灣師範大學資訊工程研究所碩士論文,臺北市。
[20]施宣丞(2012)。電腦暗棋程式DarkCraft的設計與實作(碩士)。國立臺灣師範大學資訊工程研究所碩士論文,臺北市。

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 林振源。〈閩南客家地區的道教儀式:三朝醮個案〉《民俗曲藝》(十二月號,1
2. 林振源。〈閩南客家地區的道教儀式:三朝醮個案〉《民俗曲藝》(十二月號,1
3. 李豐楙。〈臺灣中部紅頭司與客屬聚落的教儀行事〉《臺灣文獻》(卷四十九,第
4. 李豐楙。〈臺灣中部紅頭司與客屬聚落的教儀行事〉《臺灣文獻》(卷四十九,第
5. 呂錘寬。〈臺灣道教儀式與音樂的資料〉。(臺北:《藝術學》,1993)。
6. 呂錘寬。〈臺灣道教儀式與音樂的資料〉。(臺北:《藝術學》,1993)。
7. 呂錘寬。〈臺灣道教音樂源流略稿〉。(臺北:藝術學,1989)。
8. 呂錘寬。〈臺灣道教音樂源流略稿〉。(臺北:藝術學,1989)。
9. 呂錘寬。〈臺灣的道教醮祭儀式與科儀〉。(臺北:藝術評論,1989)。
10. 呂錘寬。〈臺灣的道教醮祭儀式與科儀〉。(臺北:藝術評論,1989)。
11. 呂錘寬。〈臺灣天師派道教儀式音樂的功能〉《藝術學》(第6期,1991),159-176。
12. 呂錘寬。〈臺灣天師派道教儀式音樂的功能〉《藝術學》(第6期,1991),159-176。
13. 勞格文著、許麗玲譯。〈臺灣北部正一派道士譜系〉《民俗曲藝》(九月號,103
14. 勞格文著、許麗玲譯。〈臺灣北部正一派道士譜系〉《民俗曲藝》(九月號,103
15. 勞格文著、許麗玲譯。〈臺灣北部正一派道士譜系(續篇)〉《民俗曲藝》(七月號,