簡易檢索 / 詳目顯示

研究生: 楊承恩
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 1.1 研究背景 1 1.2 研究目的 2 第二章 文獻探討 3 2.1 蜜月橋牌介紹 3 2.2 Monte Carlo Method 5 2.3 Minimax Algorithm 6 2.4 Alpha-Beta Pruning 7 2.5 Hash table 9 2.6 Bijective Function 10 2.7 相關程式介紹 12 第三章 方法與步驟 13 3.1 蜜月橋牌打牌階段 13 3.1.1 資料結構 13 3.1.2 蜜月橋牌的Minimax Algorithm 16 3.1.3 蜜月橋牌的Alpha-Beta Pruning優化 19 3.1.4 相鄰裁剪與有限的展開 21 3.1.5 無王的打牌策略 24 3.2 蜜月橋牌叫牌階段 25 3.2.1 利用Monte Carlo Method評估牌力 25 3.2.2 對手牌力分析 26 3.2.3 無王叫牌策略 28 3.3 蜜月橋牌換牌階段 29 3.3.1 換牌階段牌局狀態記錄 29 3.3.2 換牌策略與審局函數 31 3.3.3 無王換牌策略與審局函數 38 3.4 蜜月橋牌對戰平台 40 3.4.1 平台規範 42 3.4.2 平台指令及流程 44 第四章 殘局庫 50 4.1 有王殘局庫 50 4.1.1 建殘局庫的方法構想 50 4.1.2 重複牌型與不可能組合刪減 53 4.1.3 加速與資料壓縮 56 4.2 無王殘局庫 60 第五章 實驗與結果 62 5.1 打牌階段驗證 62 5.2 叫牌模擬次數比較 64 5.3 對戰測試 65 5.3.1 叫牌階段對戰測試 65 5.3.2 換牌階段對戰測試 67 5.3.3 無王規則對戰測試 70 5.3.4 人機對戰測試 72 5.3.5 TCGA 2020比賽成績 73 5.4 殘局庫 74 5.4.1 殘局庫檔案大小比較 74 5.4.2 載入及模擬速度 76 第六章 結論及未來方向 78 參考文獻 79

    [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.

    下載圖示
    QR CODE