基于matlab的巴什博弈的算法實現

[摘 要] 從博弈論的發展歷史出發，介紹了博弈論的發展歷程。對博弈論中的巴什（bashgame）博弈進行了重點介紹，利用matlab軟件進行了巴什博弈的算法實現。

[關 鍵 詞] 巴什博弈算法；博弈論；決策

[中圖分類號] G718.5 [文獻標志碼] A [文章編號] 2096-0603（2016）15-0053-01

博弈論又稱對策論，是使用嚴謹的數學模型研究現實世界中沖突對抗條件下最優決策問題的理論。作為一門正式學科，博弈論是在20世紀40年代形成并發展起來的。1944年美國數學家馮·諾依曼和美國經濟學家摩根斯坦合著的《博弈論與經濟行為》一書中描述了經濟主體的行為特征，提出了單人博弈、雙人博弈和多人博弈等基本模型，包含了豐富的策略思維和博弈的解概念，構建了一個完備的用數學和邏輯學描述經濟科學的理論體系及方法論基礎。

所謂巴什博弈，是ACM題中最簡單的組合游戲，大致上是這樣的：只有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取1個，最多取m個，最后取光者得勝。巴什博弈屬于完全信息博弈，雙方都享有完整的信息，參與人的信息是公開且對稱的，或者說參與人之間不存在不對稱信息，博弈雙方都是理性人。在巴什博弈中，博弈雙方的當事人地位是不同的，它反映的是一種參與人地位不對等的博弈結構，這種不對等可以是參與人所采取的策略和行動，在信息公開且對稱的博弈中，先手一方往往具有較大優勢，而在巴什博弈中這種優勢是絕對的，是一種很特殊并且基礎的博弈形式，可以在此基礎上建立其他的博弈形式。為了模擬bashgame的具體情況，編寫了bashgame的matlab算法類，來具體模擬對方先走的情況下，每一步的方案。在本例中，規定每次取出的石子數目是可以為0的，程序控制在1000次之內，每次取出的石子數目不得超過預先規定的最大值。算法如下：

classdefBashGame

properties

m；n；

personInput；compute；

person；

end

methods

function

obj=BashGame（）

disp（’最多只能取1000次’）；

obj.compute=zeros（1000，1）；

obj.person=zeros（1000，1）；

end

functioncalbashgame（obj）

obj.n=input（輸入1000以內的整數’）；

obj.m=input（’輸入每次取走的石子最大值＼n’）；

i=1；

while（obj.n>0）

obj.compute（i）=mod（obj.n，obj.m+1）；

fprintf（’第%.0g次電腦拿出石子%.0g個＼n’，i，obj.compute（i））；

obj.n=obj.n-obj.compute（i）；

obj.personInput=input（’取得石子數為’）；

while（obj.personInput>obj.m）

fprintf（’輸入小于%.0g的數字＼n’，obj.m）；

obj.personInput=input（’取石子數為’）；

end

while（obj.personInput<=obj.m）

obj.person（i）=obj.personInput；

fprintf（’第%.0d次取石子%.0d＼n’，i，obj.person（i））；

obj.n=obj.n-obj.person（i）；

i=i+1；

break；

end

ifobj.n<=obj.m

fprintf（’電腦最后拿出的石子數目為%.0g＼n’，obj.n）；

obj.compute（i）=obj.n；

fprintf（’電腦每次拿出石子的數目為’）；

obj.compute（1：i）

fprintf（’人每次拿出石子的數目為’）；

obj.person（1：i-1）

break

end

end

end

end

end

假定石子總數目為32個，每次最大取出數目為8個，機器先進行取子，人取石子數隨機，程序運行如下：

obj=BashGame（）

obj.calbashgame

電腦每次拿出石子的數目為：

第一次取出石子數目為：5；第二次取出石子數目為：4；

第三次取出石子數目為：5；第四次取出石子數目為：3。

人每次拿出石子的數目為：

第一次取出石子數目為：5；第二次取出石子數目為：4；

第三次取出石子數目為：6。

綜上所述，所編寫的bashgame類實現了預定的目標，雖然比較簡單，但是奠定了bashgame的基礎性工作，為后續的研究打下的基礎。

參考文獻：

[1]梁旭，黃明.現代智能優化混合算法及其應用[M].北京：電子工業出版社，2011：32.

[2]楊梅，劉堅.一種基于博弈論的混合優化算法[J].計算機應用研究，2015（33）.