研究生: |
楊承恩 Yang, Chang-En |
---|---|
論文名稱: |
蜜月橋牌程式開發及殘局庫的建立 The Development of Honeymoon Bridge Program and Endgame Database |
指導教授: | 林順喜 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2020 |
畢業學年度: | 108 |
語文別: | 中文 |
論文頁數: | 80 |
中文關鍵詞: | 電腦對局 、蜜月橋牌 、殘局庫 |
英文關鍵詞: | Honeymoon bridge, Computer games, Endgame database |
DOI URL: | http://doi.org/10.6345/NTNU202001544 |
論文種類: | 學術論文 |
相關次數: | 點閱:181 下載:12 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
蜜月橋牌為兩人對戰的橋牌遊戲,遊戲有三個階段,分別為叫牌、換牌、打牌,規則與合約橋牌大致相同。只是多了換牌階段,增加了更多變化性,在叫牌階段屬於不完全資訊賽局,換牌階段會從不完全資訊賽局慢慢變成完全資訊賽局,在最後的打牌階段則是完全資訊賽局,是非常有挑戰性的遊戲。
在本論文中針對此三個遊戲階段設計了不同的演算法及策略,改良並整合了前人的策略,將無王及有王的規則結合在一起。並構思一套嶄新的做法,建立了殘局庫,將雙方13張手牌所有可能的組合,包含先後手及不同王牌花色的賽局結果紀錄起來,已成功破解蜜月橋牌的打牌階段,使得打牌階段不再需要花大量時間搜索。針對殘局庫的資料也進行了壓縮,完整的有王殘局庫Trump_D_level1~13大小共佔4.59GB,無王殘局庫NoTrump_D_level1~13大小共佔1.34GB,目前程式牌力有很不錯的水平,已與蜜月橋牌高手相當了。
最後開發了簡易蜜月橋牌對局平台,方便後人研究蜜月橋牌時使用,也有助於推廣此項遊戲。
Honeymoon Bridge is a two-player bridge game. There are three stages in the game, bidding, changing, and playing. The rules are roughly the same as contract bridge except that there is an extra changing stage, which adds more variability. In the bidding stage, it is an imperfect information game. During the changing stage, it will gradually change from an imperfect information game to a perfect information game. In the playing stage, it is a perfect information game.
In this thesis, different algorithms and strategies are designed for these three stages. We improve and integrate previous researchers' methods, and deal with both the trump and no trump contracts. We investigate a novel idea to establish an endgame database for the playing stage that can store in advance the gaming results of all possible combinations of two players' cards as well as the trump and no trump contracts. Hence, the third stage of honeymoon bridge has been successfully solved so that it is unnecessary to spend a lot of time to search the game tree in the playing stage. The data in the endgame database has also been further compressed. The complete trump and no trump endgame databases named Trump_D_level1~13 and NoTrump_D_level1~13 only have a size of 4.59GB and 1.34GB, respectively. The current program's strength is very good, and it is comparable to the honeymoon bridge master.
Finally, we develop a simple honeymoon bridge gaming platform that is convenient for people to use when studying honeymoon bridge and also helps to promote the game.
[1]葉俊廷,不完全資訊賽局蜜月橋牌之研究,2009,國立臺灣師範大學資工所碩士論文。
[2]林澤沅,蜜月橋牌考慮無王並改良各階段演算法之研究與實作,2014,國立臺灣師範大學資工所碩士論文。
[3]陳彥吉,蒙地卡羅樹搜索法的必贏策略以及快速Nonogram解題程式的實作,2019,國立臺灣師範大學資工所碩士論文。
[4]吳天宇,基於AlphaZero General Framework實現Breakthrough遊戲,2019,國立臺灣師範大學資工所碩士論文。
[5]DarkChess電腦暗棋對戰平台。
https://web.ntpu.edu.tw/~jcchen/clients/ver5/Readme.pdf
[6]蒙地卡羅方法,維基百科。
https://zh.wikipedia.org/wiki/%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%96%B9%E6%B3%95
[7]徐讚昇、許舜欽、陳志昌、蔣益庭、陳柏年、劉雲青、張紘睿、蔡數真、林庭羽、范綱宇,電腦對局導論,2017,國立臺灣大學出版中心。
[8]張瓈文,「德州撲克」 不完全資訊賽局之研究,2005,國立臺灣師範大學資工所碩士論文。
[9]徐大開,電腦暗棋程式Observer的設計與實作,2014,國立臺灣師範大學資工所碩士論文。
[10]Yen-Chi Chen, Jia-Fong Yeh and Shun-Shii Lin, “Design and Implementation Aspects of a Surakarta Program,” ICGA Journal, vol.40, no.4, pp.438-449, March 25, 2019.
[11]Douglas Rebstock, “Improving AI in Skat through Human Imitation and Policy Based Inference”, Department of Computing Science University of Alberta , 2019.
[12]D. E. Knuth and R. W. Moore, “An analysis of alpha-beta pruning. ” Artificial Intelligence, vol. 6, no. 4, pp. 293-326, 1975.
[13]J. C. Chen, T. Y. Lin, B. N. Chen, and T. S. Hsu, “Equivalence Classes in Chinese Dark Chess Endgames. ” IEEE Transactions on Computational Intelligence and AI in Games (T-CIAIG), vol. 7, no. 2, pp. 109–122, 2015.
[14]Jr-Chang Chen, Gang-Yu Fan, Hung-Jui Chang, Tsan-sheng Hsu. “Compressing Chinese Dark Chess Endgame Databases by Deep Learning. ” IEEE Transactions on Games 10(4), 413–422, 2018.
[15]Jiang Rong, Tao Qin, and Bo An, “Competitive bridge bidding with deep neural networks.” in Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 16–24. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
[16]Johan W¨astlund, “Two-person symmetric whist”, The electronic journal of combinatorics, 12(1), 44, 2005.
[17]Jonathan Rubin, and Ian Watson , “Computer Poker: A Review”, Artificial Intelligence, 175 (5–6): 958–987, 2011.
[18]Chih-Kuan Yeh and Hsuan-Tien Lin, “Automatic Bridge Bidding Using Deep Reinforcement Learning. ” In Proceedings of the 22nd European Conference on Artificial Intelligence. 1362–1369, 2016.