(54.224.247.42) 您好!臺灣時間:2018/10/19 06:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:黃信翰
論文名稱:吹牛骰子之人工智慧研究
論文名稱(外文):On the Study of Artificial Intelligence in Liar Dice
指導教授:林順喜林順喜引用關係
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:69
中文關鍵詞:骰子賽局理論貝氏網路
外文關鍵詞:DiceGame TheoryBayesian Network
相關次數:
  • 被引用被引用:4
  • 點閱點閱:1021
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:164
  • 收藏至我的研究室書目清單書目收藏:2
吹牛骰子是一種較為特殊的骰子遊戲,屬於不完全資訊賽局的一種。在此遊戲中,骰子扮演著類似撲克牌的角色,玩家必須根據手中的骰子牌型採取喊牌方式,直到有一方決定要做勝負的判定。吹牛骰子最初起源於南美,經過長時間的演化,發展出多人共用一副骰子的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.
第一章 簡介 1
第一節 研究背景與動機 1
第二節 問題敘述 3
第三節 研究方向及目的 4
第四節 論文架構 5
第二章 吹牛骰子 6
第一節 吹牛骰子簡介 6
第二節 遊戲進行方式 7
第三節 複雜度分析 12
第三章 相關研究探討 14
第一節 經驗法則 14
第二節 對手行為模型 16
第三節 動態規劃 19
第四章 雙人吹牛骰子探討 22
第一節 特性分析 22
第二節 隨機玩法 27
第三節 貝氏信賴網路 34
第五章 實驗及結果 47
第一節 系統研發 47
第二節 測試結果 51
第六章 結論與未來發展 55
附錄 詳細測試結果 58
參考文獻 68
[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.
[3] T. Johnson, “An evaluation of how Dynamic Programming and Game Theory are applied to Liar’s Dice,” Rhodes University, 2007.
[4] D. Egnor, “ Iocaine powder,” International Computer Games Association Journal, 23 (1), pp. 33–35, 2000.
[5] K. B. Korb, A. E. Nicholson, N. Jitnah, “Bayesian Poker,” Uncertainty in Artificial Intelligence, 1999.
[6] P. Woodward, “Yahtzee: The solution,” Chance, 16(1), pp. 10–22, 2003.
[7] T. W. Neller, I. Russell, Z. Markov, “Solving the Dice Game Pig: an introduction to dynamic programming and value iteration,” 2005.
[8] T. Hicks-Wright, E. Schkufza, “A Machine Learning Approach to Opponent Modeling in General Game Playing,” 2006.
[9] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, 1990.
[10] M. Negnevitsky, Artificial Intelligence: A Guide to Intelligent Systems, Pearson, 2002.
[11] PN. Tan, M. Steinbach, V. Kumar, Introduction to Data Mining, Addison-Wesley, 2005.
[12] W. Poundstone, The Prisoner's Dilemma, Doubleday, New York, 1992.
[13] D.M. Bourg, G. Seemann, AI for Game Developers, Cambridge, O’Reilly Media, Inc., 2004.
[14] 巫和懋、夏珍,賽局高手-全方位策略與應用,台北:時報出版,2002。
[15] 張振華,人生無處不賽局,台北:書泉出版,2007。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔