棋牌游戲及事件對策

棋牌游戲與事件對策徐心和鄭新穎東北大學(xué)人工智能與機器人研究所2006年8月5日北京2006中國機器博弈學(xué)術(shù)研討會本文動機我們所從事的機器博弈活動決不僅僅是計算機游戲，它和程序設(shè)計方法學(xué)密不可分，它是人工智能搜索原理的充分體現(xiàn)，這些都是我們研發(fā)的基礎(chǔ)，不能偏離。棋牌游戲顯然屬于博弈論研究的范疇。但是現(xiàn)有的博弈論成果還無法解決棋牌游戲中的基本問題。機器博弈的輝煌成果為棋類博弈論的研究創(chuàng)造了極好的條件。博弈論（對策論）的一個新分支——”事件對策論”應(yīng)該注意探索和創(chuàng)立！東北大學(xué)人工智能與機器人研究所主要內(nèi)容博弈論研究的基本問題用博弈論研究棋牌游戲什么是離散事件動態(tài)系統(tǒng)？棋牌游戲的系統(tǒng)屬性分析事件對策的理論框架事件對策的基本研究路線事件對策論的應(yīng)用前景東北大學(xué)人工智能與機器人研究所1.博弈論研究的基本問題博弈論研究的是人與人之間利益相互制約下的策略選擇的理性行為及相應(yīng)結(jié)局，又稱對策論，游戲論。系統(tǒng)的博弈論研究是從研究國際象棋開始的。馮·諾依曼通過對二人零和一類博弈游戲的分析，提出了極大極小值定理，這是博弈論產(chǎn)生的第一個里程碑。如今，博弈論已經(jīng)廣泛地運用在經(jīng)濟學(xué)、社會學(xué)、心理學(xué)、政治學(xué)等各類社會科學(xué)，并對進化生物學(xué)和計算科學(xué)等自然科學(xué)產(chǎn)生了重要的影響。這里介紹幾個博弈論研究的基本問題和研究方法。東北大學(xué)人工智能與機器人研究所東北大學(xué)人工智能與機器人研究所問題的模型描述與求解-3，-3-9，0-1，-10，-9坦白沉默囚徒2囚徒1坦白沉默可以用雙變量矩陣的形式進行描述囚徒困境博弈暴露了個人理性與團體理性的沖突問題。都沉默更好，但靠不住對于囚徒而言，它的“嚴(yán)格優(yōu)勢策略”——（坦白，坦白）東北大學(xué)人工智能與機器人研究所囚徒困境問題的普遍意義A,B兩個公司以高低兩種價格向市場競相銷售同一種產(chǎn)品高價壟斷肯定獲利頗豐,但是不穩(wěn)定

競爭的結(jié)果則是低價出售，消費者獲利反對壟斷，打擊寡頭經(jīng)濟公共產(chǎn)品的供給出錢、不出錢

最終選擇都不出錢軍備競賽擴軍、裁軍

最終選擇都擴軍由此可見，理論的突破可以解決一系列問題。東北大學(xué)人工智能與機器人研究所東北大學(xué)人工智能與機器人研究所問題的描述、求解與應(yīng)用3.5，1.56，-0.50，00.5，5拱不拱小豬大豬拱不拱可以用雙變量矩陣的形式進行描述博弈論求解的結(jié)果：

“嚴(yán)格優(yōu)勢戰(zhàn)略組合”——（拱，不拱）股份公司的大股東和小股東

股票市場的大戶與小戶東北大學(xué)人工智能與機器人研究所東北大學(xué)人工智能與機器人研究所問題的分析、求解與應(yīng)用兩個冷飲攤販應(yīng)當(dāng)如何合理地安置自己的攤位這是在連續(xù)的變量區(qū)間進行求解問題的嚴(yán)格優(yōu)勢策略組合是（1/2，1/2）甲乙雙方都在海灘中點設(shè)攤相同行業(yè)的多家商店都擠在一起

電子一條街，飲食廣場不同航空公司經(jīng)營的飛往同一目的地的航班，常常出現(xiàn)起飛時間幾乎相同的現(xiàn)象。由此可見博弈論威力巨大的指導(dǎo)意義。東北大學(xué)人工智能與機器人研究所東北大學(xué)人工智能與機器人研究所類似的博弈論基本問題情侶博弈的其他例子銀行擠兌的成因與預(yù)防諾曼底登陸串通作弊和風(fēng)險優(yōu)勢斗雞博弈和航行規(guī)則………博弈論最成功的應(yīng)用是在經(jīng)濟學(xué)領(lǐng)域。沒有任何其它數(shù)學(xué)分支像博弈論這樣為經(jīng)濟學(xué)研究和發(fā)展提供強有力的理論支持，也沒有任何其它學(xué)科門類像經(jīng)濟學(xué)這樣為博弈論的理論發(fā)展提供如此眾多的背景模型。

東北大學(xué)人工智能與機器人研究所博弈論的基本概念參與者 自然人信息戰(zhàn)略 最優(yōu)戰(zhàn)略（最好招數(shù)）收益是所有參與者各選定一個戰(zhàn)略形成的戰(zhàn)略組合的函數(shù)均衡 所有參與者的最優(yōu)戰(zhàn)略的組合每個博弈主體所選戰(zhàn)略一定是針對其它主體所選戰(zhàn)略的最優(yōu)反應(yīng)

——前提條件東北大學(xué)人工智能與機器人研究所博弈問題的分類四種不同類型的博弈：

從簡單到復(fù)雜排列：完全信息靜態(tài)博弈完全信息動態(tài)博弈不完全信息靜態(tài)博弈不完全信息動態(tài)博弈前面所列舉的大量基本問題還都屬于靜態(tài)博弈的范疇。東北大學(xué)人工智能與機器人研究所2.用博弈論研究棋牌游戲從博弈論的角度來講，棋牌類游戲一般可以分為兩大類：一類如象棋、圍棋等游戲具有完全信息的博弈，即在博弈的每一時刻局中人完全知道自己和對手在這一時刻以前所采用的策略，也能確定這一時刻以后對手的可選擇對策有哪些。另一類是如撲克和麻將等具有不完全信息的博弈。前一種博弈的求解(尋找最優(yōu)策略)一般是和概率論無關(guān)的，而后一種博弈的求解是和概率論密切相關(guān)的。需要說明的是，除單人和個別少數(shù)游戲外，其他均為動態(tài)博弈。由二人參與的游戲，都可以看成是二人零和博弈。東北大學(xué)人工智能與機器人研究所博弈論研究棋牌游戲遇到的問題

博弈論基本問題棋牌類游戲策略空間很小,數(shù)以個計很大,數(shù)以十/百計展開層數(shù)很小,數(shù)以個計很大,數(shù)以十/百計狀態(tài)空間十分有限天文數(shù)字傳統(tǒng)方法可解不可解

棋牌類博弈必須尋找新的理論與求解方法

東北大學(xué)人工智能與機器人研究所3.什么是離散事件動態(tài)系統(tǒng)？交通調(diào)度系統(tǒng)（信號燈）東北大學(xué)人工智能與機器人研究所離散事件動態(tài)系統(tǒng)的特點離散事件動態(tài)系統(tǒng)（DEDS

）（DiscreteEventDynamicSystem）DEDS由離散事件驅(qū)動，是本質(zhì)離散的狀態(tài)與事件按照一定的運行規(guī)則相互作用，進而導(dǎo)致系統(tǒng)狀態(tài)不斷演化的一類動態(tài)系統(tǒng)。實際的DEDS大多屬于人造系統(tǒng)的范疇，不管是系統(tǒng)的運行機制還是系統(tǒng)的研究方法，都和CVDS（ContinuousVariableDynamicSystem）有著重要的區(qū)別。

東北大學(xué)人工智能與機器人研究所CVDS與DEDS的主要區(qū)別東北大學(xué)人工智能與機器人研究所離散事件動態(tài)系統(tǒng)的研究方法在DEDS的研究中，常把DEDS的模型和分析方法區(qū)分為三個基本層次，即邏輯層次、代數(shù)層次和統(tǒng)計性能層次。DEDS的邏輯層次著眼于在邏輯時間層面上研究DEDS中時間和狀態(tài)的符號序列關(guān)系；DEDS的代數(shù)層次著眼于在物理時間層次上來研究DEDS的代數(shù)特性和運動過程；DEDS的統(tǒng)計性能層次，著眼于在性能層面上研究隨機情況下DEDS的各種平均性能及其優(yōu)化。盡管這三個層次模型所面對的都是DEDS，但由于研究側(cè)重點和描述手段不同，目前看來還不具備相互取代的前景。

東北大學(xué)人工智能與機器人研究所4.棋牌游戲的系統(tǒng)屬性分析棋牌游戲系統(tǒng)主要由兩部分構(gòu)成，即局面和著法。著法是導(dǎo)致局面狀態(tài)變化和進而引發(fā)新著法產(chǎn)生的唯一因素，是驅(qū)動棋牌游戲系統(tǒng)狀態(tài)演變的基本因素。局面的狀態(tài)都是在離散時間點上發(fā)生躍變，即僅在著法產(chǎn)生的瞬時局面才能發(fā)生躍變，其它時刻則保持不變，并且在狀態(tài)空間中具有一種不連續(xù)的固有屬性。著法的變化域和局面的狀態(tài)空間都具有離散性。基于以上因素，有理由認為棋牌類游戲系統(tǒng)屬于離散事件動態(tài)系統(tǒng)，著法即是觸發(fā)DEDS狀態(tài)變化的事件。東北大學(xué)人工智能與機器人研究所棋牌游戲的系統(tǒng)屬性——

事件對策問題中國象棋棋局演化過程——棋譜(紅方)(黑方)東北大學(xué)人工智能與機器人研究所5.事件對策的理論框架事件對策系統(tǒng)由以下四個要素構(gòu)成：事件對策的參與者集合。事件的變化集，其中1，2，3…F代表了事件發(fā)生的順序，為第一個發(fā)生的事件，為最后發(fā)生的事件。事件對策系統(tǒng)的狀態(tài)空間

，

代表了系統(tǒng)的初始狀態(tài)，

代表了系統(tǒng)的終止?fàn)顟B(tài)。參與者的收益集，其中代表每個參與者的收益，代表在不同事件序列下的不同收益。

東北大學(xué)人工智能與機器人研究所事件對策的理論框架（續(xù)）所有的事件對策系統(tǒng)都可以用來表示。事件對策系統(tǒng)分析的目的在于，如何在“策略相互制約”的局勢中尋找到每個智能主體的最佳策略（事件集），使得在這一系列事件驅(qū)動下，系統(tǒng)達到的狀態(tài)能夠讓每個智能主體都能獲得盡可能大的盈利(或最大地減少損失)。即如何尋找到一個事件變化集，使。東北大學(xué)人工智能與機器人研究所6.事件對策的基本研究路線事件對策問題都屬于動態(tài)博弈，所以博弈論中的動態(tài)博弈求解方法應(yīng)該適用于事件對策系統(tǒng)。逆向遞歸法（Backwardinduction），也稱倒退法(Rollbackmethod)，即從事件對策系統(tǒng)的最后一個決策階段開始分析，確定該階段局中人的策略選擇；然后再確定前一階段局中人的策略選擇，一直推到起始點。這種方法對于策略空間較小，博弈步數(shù)較少的事件對策系統(tǒng)是適用的，但是對于大策略集或是博弈步數(shù)較多的事件對策系統(tǒng)，這種方法很難求出其均衡解。東北大學(xué)人工智能與機器人研究所事件對策的基本研究路線根據(jù)棋牌游戲的特點，特別受到機器博弈的啟發(fā)，提出了事件動態(tài)系統(tǒng)的另一種求解方法——狀態(tài)空間搜索算法。考慮到象棋大師以及游戲高手們可以在巨大的策略空間中選擇合適的著法，一個主要因素就是因為他們在眾多的棋局對弈中形成了一些定式，把大策略空間縮小到一個小的策略空間里，問題自然容易解決了。基本路線：結(jié)合人工智能的先進技術(shù)——搜索技術(shù)，在博弈樹展開的過程中，裁剪掉沒有價值的分支，成功地把大策略集縮減到小策略集，從而實現(xiàn)了求解過程。東北大學(xué)人工智能與機器人研究所象棋博弈樹展開紅方紅方紅方黑方黑方Depth1Depth3Depth4Depth2Depth0東北大學(xué)人工智能與機器人研究所蠻力搜索（Brutesearch）一般采用廣度優(yōu)先搜索一層層展開，一層層搜索，因為“窮盡”而沒有風(fēng)險，不會漏掉展開深度內(nèi)的最優(yōu)解。假設(shè)計算機搜索節(jié)點速率為1M/秒，中國象棋B=45

（分枝因子B=40~50）下表為在不同的給定時間內(nèi)達到的搜索層數(shù)。給定時間1秒1分1小時1天1年10年100年搜索層數(shù)3.634.705.786.628.178.779.36東北大學(xué)人工智能與機器人研究所出路在哪里？由于完整的博弈樹過于龐大，盲目搜索所能達到的層數(shù)十分有限，在象棋博弈中幾乎沒有實用價值。若想在指定時間內(nèi)將搜索深度加以提高，一方面需要改進硬件與優(yōu)化程序代碼，提高單位時間內(nèi)搜索的節(jié)點數(shù)；另一方面就需要像人類棋手一樣有選擇性地進行搜索，即對博弈樹進行必要的裁剪（cut-off/pruning）。

東北大學(xué)人工智能與機器人研究所奠基者——香儂教授香儂(ClaudeShannon)教授早在1950年首先提出了極大-極小算法（MinimaxAlgorithm），從而奠定了計算機博弈的理論基礎(chǔ)。

Shannon,ClaudeE.,Programmingacomputerforplayingchess[J],PhilosophicalMagazine, Vol.41:256-275,1950.東北大學(xué)人工智能與機器人研究所博弈樹特點分析博弈樹不同于一般的搜索樹，它是由對弈雙方共同產(chǎn)生的一種“變性”搜索樹。紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點中找到評估值最大的一個，即實行“Max搜索”。紅方稱為MAX方。而其應(yīng)對方——黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點中要找到評估值最小的一個，即實行“Min搜索”。黑方稱為MIN方。東北大學(xué)人工智能與機器人研究所MAXMAXMIN1298765433213MaxMin搜索（1）由此產(chǎn)生最佳路徑和最佳著法東北大學(xué)人工智能與機器人研究所MAXMAXMIN5298761431244MaxMin搜索（2）由此產(chǎn)生最佳路徑和最佳著法東北大學(xué)人工智能與機器人研究所α-β剪枝搜索一種基于剪枝（

α-βcut-off）的深度優(yōu)先搜索（depth-firstsearch）。將走棋方定為MAX方，因為它選擇著法時總是對其子節(jié)點的評估值取極大值，即選擇對自己最為有利的著法；將應(yīng)對方定為MIN方，因為它走棋時需要對其子節(jié)點的評估值取極小值，即選擇對走棋方最為不利的、最有鉗制作用的著法。東北大學(xué)人工智能與機器人研究所MAXMAXMIN45682434α剪枝（1）由此產(chǎn)生最佳路徑和最佳著法東北大學(xué)人工智能與機器人研究所MAXMAXMIN13682154α剪枝（2）7491224由此產(chǎn)生最佳路徑和最佳著法東北大學(xué)人工智能與機器人研究所剪枝效果差別很大不難發(fā)現(xiàn)，和最佳著法關(guān)系密切什么是最佳著法？怎樣找到最佳著法？（1）（2）東北大學(xué)人工智能與機器人研究所β-剪枝（1）174298MAXMINMIN77由此產(chǎn)生最佳路徑和最佳著法東北大學(xué)人工智能與機器人研究所β-剪枝（2）835791MAXMINMIN8426由此產(chǎn)生最佳路徑和最佳著法448東北大學(xué)人工智能與機器人研究所β剪枝和α剪枝具有同樣規(guī)律剪枝效果與最佳著法的位置密切相關(guān) 與博弈樹展開的順序密切相關(guān)（1）（2）東北大學(xué)人工智能與機器人研究所需要指出的是