臺灣博碩士論文加值系統

　　吹牛骰子主要分為individual hand（多人共用一副骰子）與common hand（玩家各自擁有一副骰子）兩種。其中individual hand類型在過去已有些許研究成果，例如使用近似模擬法、經驗法則、對手行為模擬與動態規劃等。而common hand類型於2009年由國立台灣師範大學黃信翰研究生發表吹牛骰子之人工智慧論文中首度呈現研究結果。其捨棄傳統常用的賽局樹搜尋與亂數模擬法等耗用大量計算資源的方法，利用賽局理論，以一種簡單明快的作法來達到此遊戲的最佳（或較佳）玩法，並採用貝氏信賴網路，在連續對局中對網路進行訓練，達成對手行為模擬的效果，藉此發掘對手的弱點來提高勝率。此為common hand類型的吹牛骰子之創新與突破的研究，對於其他與各種啟發式規則所實作之程式均有六至七成的勝率，並且與具有一定水準的人類玩家對戰，也有與之抗衡的能力。
　　本論文主要針對黃信翰研究生的吹牛骰子之人工智慧程式加以改良，並提出更佳的電腦決策流程，以期提高與其他電腦程式和人類玩家對戰的能力。
　　實驗結果顯示，與黃信翰研究生的吹牛骰子之人工智慧程式對局，勝率約為56%；與目前網路上吹牛骰子程式對局，勝率可達八成以上。

Liar dice evolved two different versions, one is individual hand and the other is common hand. In “individual hand”, there is only a set of dice which is passed from player to player. In “common hand”, each player has his own set of dice. There are some researches in individual hand version in the past, and the algorithms they used were simulation approximate method, empirical rule, opponent modeling and dynamic programming, etc. There is no research on common hand version until 2009, when H. H. Huang studied this game by applying game theory and using Bayesian belief network to train it by successively playing to build a model of an opponent. The model can help us to find the weakness of the opponent and win more games. This was an innovative approach and achieved about 60 to 70 percent of winning rate against other heuristic-based test programs. And it is competitive when playing with human players.

This thesis focuses on improving Huang’s liar dice program, brings up a better strategy, and expects to win more games against other computer programs and human players.

The experiment results show that we can achieve 56% win rate against Huang's liar dice program, and achieve more than 80% percent win rate against other liar dice programs on the Internet.

摘要 i
ABSTRACT ii
誌謝 iii
第一章 緒論 1
　第一節 研究背景與動機 1
　第二節 研究方向與目的 6
　第三節 論文架構 6
第二章 吹牛骰子 8
　第一節 簡介 8
　第二節 遊戲進行方式 9
　第三節 相關研究探討 13
第三章 進一步改良吹牛骰子程式 32
　第一節 程式流程與架構 32
　第二節 喊牌策略之改進 38
　第三節 抓牌策略之改進 42
第四章 實驗與結果 44
　第一節 系統研發 44
　第二節 測試結果 51
第五章 結論與未來發展 54
附錄A　指定點數提供機率推導與計算過程 56
附錄B　詳細測試結果 59
參考文獻 77

[1] A. M. Brandenburger, B. J. Nalebuff, “The Right Game: Use Game Theory to Shape Strategy,” Journal of Harvard Business Review, Vol.73, No.4, pp.57-71, 1995.
[2] G. H. Freeman, “The Tactics of Liar Dice,” Applied Statistics, Vol.38, No.3, pp.507-516,1989.
[3] T. Johnson, “An evaluation of how Dynamic Programming and Game Theory are applied to Liar’s Dice”, Rhodes University, 2007.
[4] D. Koller, A. Pfeffer, “Representations and Solutions for Game-theoretic Problems,” Artificial Intelligence, Vol.94, No.1, pp.167-215, 1997.
[5] K. B. Korb, A. E. Nicholson, N. Jitnah, “Bayesian Poker,” in Proceedings of 15th Conference on Uncertainty in Artificial Intelligence, pp.343-350, 1999.
[6] O. Morgenstern, J. V. Neumann, “Theory of Games and Economic Behavior,” Princeton University Press, 1944.
[7] J. F. Nash, Jr., “The Bargaining Problem,” Econometrica, Vol.18, No.2, pp.155–162, 1950.
[8] J. F. Nash, Jr., “Equilibrium Points in N-person Games,” Proceedings of the National Academy of Sciences of the United States of America, Vol.36, No.1, pp48-49, 1950.
[9] J. F. Nash, Jr., “Non-cooperative Games,” Annals of Mathematics, Vol.54, No. 2, pp.286–295, 1951.
[10] J. V. Neumann, “Zur Theorie der Gesellschaftsspiele,” Mathematische Annalen, Vol.100, pp.295-320, 1928.
[11] S. J. Russell, P. Norvig, “Artificial Intelligence: A Modern Approach,” Prentice Hall, 2002.
[12] D. Snidal, “Game Theory of International Politics,” in Kenneth Oye, eds. Cooperation under Anarchy, pp.25-57, 1986.
[13] F. Southey, M. Bowling, B. Larson, C. Piccione, Neil Burch, Darse Billings, Chris Rayner, “Bayes’ Bluff: Opponent Modelling in Poker,” in 21st Conference on Uncertainty in Artificial Intelligence (UAI-2005), pp.550-558, 2005.
[14] J. Sum, J. Chan, “On a Liar Dice Game - Bluff,” in International Conference on Machine Learning and Cybernetics, Vol.4, pp.2179-2184, 2003.
[15] “Bayes' Theorem”, http://plato.stanford.edu/entries/bayes-theorem/.
[16] “Game theory: Types of games”, http://en.wikipedia.org/wiki/Game_theory.
[17] “Prisoner's dilemma”, http://en.wikipedia.org/wiki/Prisoner's_dilemma.
[18] “Von Neumann's Minimax Theorem”, http://library.thinkquest.org/26408/math/minimax.shtml.
[19] 巫和懋、夏珍，賽局高手－全方位策略與應用，台北：時報出版，2002。
[20] 張振華，人生無處不賽局，台北：書泉出版，2007。
[21] 黃信翰，“吹牛骰子之人工智慧研究”，國立臺灣師範大學資訊工程研究所碩士論文，2009。
[22] “古惑大話骰”，http://www.teddyboy.com.hk/gamezone/dicegame/main.php.
[23] “資料探勘(Data Mining)的介紹”，http://www.uniminer.com/center01.htm.
[24] “資料探勘(Data Mining)”，http://sunrise.hk.edu.tw/~msung/Ecommerce/Data_Mining/DM_Index.htm.
[25] “骰子”，http://baike.baidu.com/view/28173.htm#1.
[26] “賽局理論”，http://www.managertoday.com.tw/?p=588.
[27] “賽局理論與經營策略”，http://web.thu.edu.tw/et/www/GT01.pdf.