吹牛骰子之人工智慧研究

On the Study of Artificial Intelligence in Liar Dice

黃信翰

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2009年)

摘要

吹牛骰子是一種較為特殊的骰子遊戲，屬於不完全資訊賽局的一種。在此遊戲中，骰子扮演著類似撲克牌的角色，玩家必須根據手中的骰子牌型採取喊牌方式，直到有一方決定要做勝負的判定。吹牛骰子最初起源於南美，經過長時間的演化，發展出多人共用一副骰子的individual hand類型與玩家各自使用一副骰子的common hand兩大類型。
本研究以common hand類型為主，因為骰子數變多，且遊戲中僅能獲得少量不可靠的資訊，要找出好的玩法策略顯得更加困難。我們希望能捨棄傳統上常用的賽局樹搜尋與亂數模擬法等耗用大量計算資源的方法，利用賽局理論，以一種簡單明快的作法來達到此遊戲的最佳(或較佳)玩法。並採用貝氏信賴網路，在連續的對局中對網路進行訓練，達成對手行為模擬的效果，藉由發掘對手的弱點來提高勝率。
實驗結果顯示，我們所找到的以隨機猜測為基礎的演算法，對於其他以各種啟發式規則所實作的32種測試程式，都有約6~7成的勝率，並且與具有一定水準的人類玩家對戰，也有與之抗衡的能力。在加入貝氏網路的學習之後，戰績也有明顯的提升。在不完全資訊遊戲的分析上，先以隨機玩法使自己不易吃虧，再搭配上對手行為模型的輔助，的確為一種可行的作法。

關鍵字

骰子 ； 賽局理論 ； 貝氏網路

並列摘要

Liar dice is a special dice game. It’s a kind of imperfect information game. In this game, the dice play the roles like the cards in a poker game. Players have to make their calls according to the type of the dice they own until one of them decides to do the judgment. Liar dice was originated from South America and has been evolving for a long time. Eventually, this game evolved two different versions. 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.
This thesis focuses on the study of the common hand liar dice. Because of the increasing number of dice, we receive too little reliable information when we play. This makes the common hand version much more difficult than the individual hand version. We hope that we can abandon the traditional algorithms such as game tree search and random simulation, which will consume lots of time and space. By applying game theory, we find a simple, fast way to compute the optimal (or suboptimal) solution. Furthermore, we use a Bayesian belief network, and train it by successive playing to build a model of an opponent. The model can help us to find the weakness of the opponent and to win more games.
The experiment results show that the proposed scheme based on random guessing, can achieve about 60 to 70 percent of winning rate against all 32 heuristic- based test programs we designed. And it is competitive when playing with a human player. After we add the Bayesian belief network, the performance of our program also has significant improvement. This shows that when we want to solve an imperfect information game, trying to explore the advantages of random guessing and use an opponent modeling technique is indeed a considerable approach.

並列關鍵字

Dice ； Game Theory ； Bayesian Network

參考文獻

[1] G. H. Freeman, “The Tactics of Liar Dice,” Applied Statistics, Vol. 38, No. 3, pp. 507-516, 1989.

[2] J. Sum, J. Chan, “On a liar dice game - bluff,” International Conference on Machine Learning and Cybernetics Vol. 4, pp. 2179 - 2184, 2003.

[6] P. Woodward, “Yahtzee: The solution,” Chance, 16(1), pp. 10–22, 2003.

[8] T. Hicks-Wright, E. Schkufza, “A Machine Learning Approach to Opponent Modeling in General Game Playing,” 2006.

[11] PN. Tan, M. Steinbach, V. Kumar, Introduction to Data Mining, Addison-Wesley, 2005.