人工智能之計(jì)算機(jī)博弈相關(guān)研究報(bào)告

1、人工智能導(dǎo)論課 程 項(xiàng) 目 報(bào) 告 人工智能之計(jì)算機(jī)博弈相關(guān)研究報(bào)告項(xiàng)目名稱 _ _曹航學(xué)生姓名_2013141463108學(xué)生學(xué)號_311091020課 程 號_阮樹驊任課教師_學(xué)生成績_軟件工程9軟件學(xué)院_院（部）_專業(yè)_班20151210_年 _月 _日9人工智能之計(jì)算機(jī)博弈相關(guān)研究報(bào)告 曹航 2013141463108 caohang 摘要：計(jì)算機(jī)博弈（也稱機(jī)器博弈），是一個挑戰(zhàn)無窮、生機(jī)勃勃的研究領(lǐng)域，是人工智能領(lǐng)域的重要研究方向，是機(jī)器智能、兵棋推演、智能決策系統(tǒng)等人工智能領(lǐng)域的重要科研基礎(chǔ)。機(jī)器博弈被認(rèn)為是人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一。國際象棋的計(jì)算機(jī)博弈已經(jīng)有了很長的歷

2、史，并且經(jīng)歷了一場波瀾壯闊的“搏殺”，“深藍(lán)”計(jì)算機(jī)的勝利也給人類留下了難以忘懷的記憶。中國象棋計(jì)算機(jī)博弈的難度絕不亞于國際象棋，不僅涉足學(xué)者太少，而且參考資料不多。在國際象棋成熟技術(shù)的基礎(chǔ)上，結(jié)合在中國象棋機(jī)器博弈方面的多年實(shí)踐，總結(jié)出一套過程建模、狀態(tài)表示、著法生成、棋局評估、博弈樹搜索、開局庫與殘局庫開發(fā)、系統(tǒng)測試與參數(shù)優(yōu)化等核心技術(shù)要點(diǎn),最后提出了當(dāng)前研究的熱點(diǎn)與方向。關(guān)鍵詞：極大極小樹、人工智能、計(jì)算機(jī)博弈1.計(jì)算機(jī)博弈-人工智能的經(jīng)典領(lǐng)域1.1發(fā)展歷史計(jì)算機(jī)博弈，歷來是人工智能的一個重要的研究領(lǐng)域，早期人工智能的研究實(shí)踐，正是從計(jì)算機(jī)下棋開始。因?yàn)槿祟愰_發(fā)下棋軟件，目的是讓計(jì)算機(jī)模

3、仿人腦進(jìn)行思維，如果能夠掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心，那些能夠存在與下棋活動中的重大原則，或許就存在于其它人格需要人類智能的活動中。所以說，下棋軟件某種意義上可以代表人工智能的發(fā)展程度從上世紀(jì)六十年代的”跳棋機(jī)”到1997年的深藍(lán)”,計(jì)算機(jī)下棋程序在人機(jī)博弈中取得了一個又一個勝利，但是這些程序雖然屬于人工智能范疇，實(shí)際上它們并沒有多少”智”的成分，主要部分都是在可行范圍內(nèi)搜索。各種研究也大都是怎樣使搜索更快更有效。它們?nèi)狈Α敝恰钡某煞值母驹?，是我們自己并不清楚人類是以怎樣的形式思考的。比如你寫一個名字問一位教師，這人是不是他班上的學(xué)生。教師馬上可以回答是或不是。如果你問計(jì)

4、算機(jī)，計(jì)算機(jī)搜索很快，全走一邊幾乎可以瞬間完成。但我們知道教師是不可能在短時間內(nèi)把我們所有學(xué)生的名單過一遍的。類似的，我們看到一個人的照片，馬上就知道我們以前見沒見過這個人，我們不可能在短時間內(nèi)把我們以前見過的人都檢查一遍，那么我們是怎樣得出結(jié)論的呢？現(xiàn)在我們對此還不是完全清楚 黃葦：計(jì)算機(jī)博弈與人工智能，教科指導(dǎo)2010（27）。1.2對于人類思維的挑戰(zhàn) 常見機(jī)器博弈系統(tǒng)的構(gòu)成計(jì)算機(jī)博弈是要讓計(jì)算機(jī)和人類一樣能在對抗中做出決策，其典型表現(xiàn)讓計(jì)算機(jī)下棋，下國際象棋，下中國象棋，等等各種棋。現(xiàn)在還有的科學(xué)家研究讓計(jì)算機(jī)打牌，打撲克牌，打麻將等。讓計(jì)算機(jī)能像人一樣，能夠思維、判斷和推理，能夠作出理

5、性的決策。下棋過程是建立各種形式的數(shù)學(xué)模型，它屬于博弈論的范疇，這是對于人類思維的挑戰(zhàn)。下棋時候棋盤上可走的地方很多，但下棋的人并不是每種走法都去考慮。那么哪些為止不需要考慮，這就是”模式識別”問題。人腦有”模式識別”功能，可以很快得出一個大致的結(jié)論，計(jì)算機(jī)沒有這種功能，只好所有的位置都考慮。在人機(jī)博弈中，計(jì)算機(jī)人工智能基本的思考方式是窮舉法，即通過對所有可能的招法的演化結(jié)果進(jìn)行比較，最后選擇一個最好的招法。但是，國際象棋的變化總數(shù)達(dá)到10的123次方，而中國象棋的變化數(shù)量比這還要多得多，可達(dá)10的144次方以上，圍棋的變化就更多達(dá)10的172次方以上，計(jì)算機(jī)不可能算出棋盤上的所有變化。因此，

6、所謂的”利用窮舉法選擇最好的走法”，指的是棋局的局部，并且是在有限的步驟里，而不是通盤窮舉，它更沒辦法對整盤棋的形勢做正確判斷。目前，在三大棋類項(xiàng)目中，國際象棋和中國象棋兩項(xiàng)，計(jì)算機(jī)的水平都已經(jīng)可以和最頂級的職業(yè)選手抗衡了，但在圍棋項(xiàng)目中計(jì)算機(jī)的水平始終上不去，目前圍棋計(jì)算機(jī)大賽獲得冠軍的軟件也只勉強(qiáng)達(dá)到業(yè)余初段水平，和頂級職業(yè)棋手相比，大概要被讓七子。1.3人工智能的經(jīng)典領(lǐng)域機(jī)器博弈是既簡單方便、經(jīng)濟(jì)實(shí)用，又豐富內(nèi)涵、變化無窮的思維邏輯的研究載體。人機(jī)對弈的程序，至少應(yīng)該具備以下部分：1.某種在機(jī)器中表示棋局的方法，能夠讓程序知道博弈的狀態(tài)，產(chǎn)生合法走法的規(guī)則并能夠評估局面優(yōu)劣； 2.通過某

7、個大師的大量棋譜，自動歸納這位大師的下棋風(fēng)格與特點(diǎn)，長項(xiàng)與弱項(xiàng)。這是知識挖掘的典型課題； 3.剖析一盤棋的勝敗過程與原因，進(jìn)而自動修改博弈程序，這是機(jī)器學(xué)習(xí)的典型例題； 4.將圍棋的各種定式進(jìn)行表示和分辨，這是模式識別的典型問題； 1.4未來趨勢應(yīng)用前景分析機(jī)器博弈最直接的應(yīng)用之一，便是在作戰(zhàn)模擬領(lǐng)域?？梢栽趦绍妼竞妥鲬?zhàn)形式上找到相互對應(yīng)的模式與范例。如兵種的設(shè)計(jì)與配合、消滅有生力量、圍而攻之奪取地盤等。部隊(duì)的指揮機(jī)關(guān)在謀劃一場戰(zhàn)役（斗）之前總是要詳細(xì)分析雙方的兵力部署、戰(zhàn)場的自然環(huán)境、對方的可能調(diào)動、以及大量難以預(yù)見的事件、戰(zhàn)斗與結(jié)果。早期的戰(zhàn)事謀劃是在物理模型上進(jìn)行的，稱之為沙盤推演。近

8、代的戰(zhàn)事謀劃，包括日軍襲擊珍珠港，聯(lián)合國軍諾曼底登陸，美軍的海灣戰(zhàn)爭等都是事先進(jìn)行過周密的“兵棋推演（” War gaming, War simulation），以便做到“不打無準(zhǔn)備之仗”。二戰(zhàn)退役的老兵還專門開發(fā)了一種游戲，稱之為“兵棋” 楊南征：虛擬演兵兵棋、作戰(zhàn)模擬與仿真M. 北京：解放軍出版社， Nanzheng Yang: Wargame, War Game, SimulationM. Liberation Army Press, Beijing 。 在兵棋推演數(shù)字化的情況下，兵棋推演的智能化便是必然的發(fā)展趨勢。如何實(shí)現(xiàn)兵棋推演的智能化？如何研制無人作戰(zhàn)飛機(jī)的聯(lián)合作戰(zhàn)策略？如何在未來

9、的無人作戰(zhàn)部隊(duì)中實(shí)現(xiàn)自動指揮與配合？機(jī)器博弈的成果必然能夠成為諸多關(guān)鍵技術(shù)的核心，因?yàn)樗侨斯ぶ悄艿母呒夡w現(xiàn) 徐心和，鄧志立：基于機(jī)器博弈的作戰(zhàn)模擬系統(tǒng)探討C. 中國系統(tǒng)建模與仿真技術(shù)高層論壇論文集，北京, 113-117 Xinhe Xu, Zhili Deng：Study on war simulation system based on computer gamesC. Proceedings on High-level Workshop of Chinese System Modeling and Simulation Technology, Beijing. 113-117。聯(lián)合博弈

10、的多Agent學(xué)習(xí)：在研究Q-Learning算法的基礎(chǔ)上,將博弈論中的團(tuán)隊(duì)協(xié)作理論引入到強(qiáng)化學(xué)習(xí)中,提出了一種基于聯(lián)合博弈的多Agent學(xué)習(xí)算法。該算法通過建立多個階段博弈,根據(jù)回報(bào)矩陣對階段博弈的結(jié)果進(jìn)行評估,為其提供一種有效的A-gent行為決策策略,使每個Agent通過最優(yōu)均衡解或觀察協(xié)作Agent的歷史動作和自身當(dāng)前情況來預(yù)測其所要執(zhí)行的動作。對任務(wù)調(diào)度問題進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證了該算法的收斂性 黃付亮 ，張榮國， 陳大川 ，劉焜：基于聯(lián)合博弈的多Agent學(xué)J，計(jì)算機(jī)與數(shù)字工程 2011年06期 。另一個重要的應(yīng)用方面就是在游戲人工智能設(shè)計(jì)中，因?yàn)橛螒蛑薪^大多數(shù)人工智能的使用目的就是與

11、玩家博弈，無論是棋牌類游戲，街機(jī)格斗類，動作類，還是回合制RPG游戲，處處都充斥了與玩家一較高下的博弈元素。而且由于游戲中游戲機(jī)制都是設(shè)計(jì)好了的，游戲內(nèi)博弈需要的決策，常常都有規(guī)律可循，博弈所需要考慮的參數(shù)也往往是確定并且易得的，因此，在游戲中，博弈的程序相對于許多復(fù)雜的現(xiàn)實(shí)問題更好設(shè)計(jì)以及實(shí)現(xiàn)。下面會講到游戲中雙人博弈最經(jīng)典的極大極小算法。2.計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析-極大極小搜索算法2.1關(guān)于極大極小搜索極大極小搜索策略一般都是使用在一些雙人博弈類的游戲之中：這樣策略本質(zhì)上使用的是深度搜索策略，所以一般可以使用遞歸的方法來實(shí)現(xiàn)。在搜索過程中，對一方有利的搜索點(diǎn)上應(yīng)該取極大值，而對另一方有利的

12、搜索點(diǎn)上應(yīng)該取極小值。極小值和極大值都是相對而言的。實(shí)際上極大或極小都只是一種區(qū)分的標(biāo)記方式而已，無論先手后手都可以用極大或者極小表示。另外極大極小搜索是用于尋找必勝法的。因此，算法的大致思想是先把每一步所導(dǎo)致的局面情況用一個數(shù)據(jù)結(jié)構(gòu)記錄下來。并且將該局面的各種下一步所產(chǎn)生后代局面作為其子節(jié)點(diǎn)。于是該游戲所有可能產(chǎn)生的局面便可記錄在這一棵樹中。2.2算法示例以及問題描述：游戲大航海時代中出現(xiàn)過的拿硬幣小游戲：拿硬幣游戲規(guī)則：一共有n枚，兩個人輪流拿金幣，一次可以拿1到3枚金幣，拿到最后一枚金幣的人輸。2.3算法原理：先為游戲產(chǎn)生所有可能的局面的游戲樹。第一位玩家為Max,選取最佳步驟進(jìn)攻;第二

13、位玩家為Min進(jìn)行防守，兩位玩家每次都盡力尋找必勝法。對于游戲中任意一次局面如果該局面中下一步由Max玩家采取措施且此時局面中存在Max玩家必勝法則將該局面標(biāo)記為1，如果下一步由Min玩家采取措施且此時局面中存在Min玩家必勝法則將該局面標(biāo)記0。先給游戲的結(jié)束狀態(tài)如下賦值：Max贏得游戲的狀態(tài)節(jié)點(diǎn)標(biāo)記為1。Min贏得游戲的狀態(tài)節(jié)點(diǎn)標(biāo)記為0。然后不斷從葉節(jié)點(diǎn)向上逐層回溯，對于回溯中遇到的每一個節(jié)點(diǎn)，如果他處于Max玩家行動產(chǎn)生下一局面的情況，則該層稱為Max層，當(dāng)子局面中含有被標(biāo)記為1(即Max玩家可以必勝)時，該層節(jié)點(diǎn)也可被標(biāo)記為1，即Max層（所有深度為偶數(shù)的層，樹的深度從0開始）的節(jié)點(diǎn)其值

14、取子節(jié)點(diǎn)中最大值，相反可知Min層（所有深度為奇數(shù)的層）的節(jié)點(diǎn)其值取子節(jié)點(diǎn)中最小值。2.4算法步驟：（1）遍歷至每一個葉子節(jié)點(diǎn)，并分析游戲在該節(jié)點(diǎn)的狀態(tài)，可以將先手贏標(biāo)記為1，后手贏標(biāo)記為0。然后使用一啟發(fā)式算法為該節(jié)點(diǎn)產(chǎn)生一個值，值越高對Max越有利。相反，值越低對Min越有利。（2）進(jìn)行樹的回溯。若父節(jié)點(diǎn)為Min，則該父節(jié)點(diǎn)值為所有子節(jié)點(diǎn)中的最小值（AI選擇時，選擇最小的子節(jié)點(diǎn)的操作進(jìn)行執(zhí)行）；若父節(jié)點(diǎn)為Max,則父節(jié)點(diǎn)的值為所有子節(jié)點(diǎn)的最大值（AI選擇時，選擇最大的子節(jié)點(diǎn)的操作進(jìn)行執(zhí)行）；如果多個最?。ù螅┲档淖庸?jié)點(diǎn)，則隨機(jī)選一個（更lifelike）或選第一個(其他方法也可以)。 2.

15、5流程圖：2.6實(shí)現(xiàn)結(jié)果評價：運(yùn)行截圖：成功生成了某一金幣下所有游戲的結(jié)果的最大最小樹，遺憾的是未能以圖形化打印樹，而是使用了前序遍歷輸出最大最小樹。能夠正確判斷誰能夠在某一情況下必勝。由于不存在勝負(fù)不可定局（即任何情況下先手或者后手都能夠必勝），所以估價函數(shù)f（p）的取值只有0及1兩個值附錄A：程序主要源代碼及實(shí)驗(yàn)說明使用說明：開發(fā)環(huán)境：windows 7 ultimate x64, visual studio 2013使用環(huán)境：WINDOWS x64/x86操作方法：編譯生成程序后運(yùn)行，輸入一個整數(shù)（起始金幣數(shù)量，建議不要過大，內(nèi)存空間會不足，建議在25以下）。按Enter，即可看到前序遍

16、歷輸出的最大最小樹，以及誰能必勝。最大最小樹以前序遍歷輸出，每個節(jié)點(diǎn)用 (剩余金幣數(shù)量,f(p) 格式輸出，子樹會在節(jié)點(diǎn)后的 “”內(nèi)輸出實(shí)現(xiàn)代碼：main.cpp#include <iostream>#include "Tree.h"using namespace std;int GOLD_COIN=3;/*!curNum 該回合后剩下的金幣數(shù)量minMaxVal 最大最小值,1表示先手贏，0表示后手贏*/class treeNodepublic:int curNum;int minMaxVal;bool isChildrenAllEqual(Tree<t

17、reeNode>* tree,int equalVal)if (tree =NULL)return false;DListIterator<Tree<treeNode>:Node *> it = tree->m_children.GetIterator();while(it.m_node!=tree->m_children.m_tail)if (it.Item()->m_data.minMaxVal != equalVal)return false;it.Forth();if (it.Item()->m_data.minMaxVal !=

18、equalVal)return false;return true;/*!GOLD_COIN 剩下金幣的數(shù)量depth 樹的深度，從0開始算*/Tree<treeNode>* initMinMaxTree(int GOLD_COIN,int depth)if (GOLD_COIN<0 |depth<0 )return NULL;Tree<treeNode>* tn = new Tree<treeNode>tn->m_data.curNum=GOLD_COIN;if (GOLD_COIN = 0)tn->m_data.minMaxVal

19、 = depth%2?0:1;elseTree<treeNode>* temp = initMinMaxTree(GOLD_COIN-1,depth+1);tn->m_children.Append(temp);temp = initMinMaxTree(GOLD_COIN-2,depth+1);if(temp!=NULL)tn->m_children.Append(temp);temp = initMinMaxTree(GOLD_COIN-3,depth+1);if(temp!=NULL)tn->m_children.Append(temp);if (depth

20、%2=0)/max層if (isChildrenAllEqual(tn,0)tn->m_data.minMaxVal = 0;elsetn->m_data.minMaxVal = 1;else/min層if (isChildrenAllEqual(tn,1)tn->m_data.minMaxVal = 1;elsetn->m_data.minMaxVal = 0;return tn;void printTree(Tree<treeNode>* tree)cout << "(" << tree->m_data.

21、curNum << "," << tree->m_data.minMaxVal << ")"if (tree->m_children.m_count = 0)return;DListIterator<Tree<treeNode>:Node *> it = tree->m_children.GetIterator();cout << ""while (it.Valid()printTree(it.Item();it.Forth();cout << ""int main()cout <<"問題描述：總共有N個金幣。兩個人輪流拿，每次拿的數(shù)目不超過3個，判斷是先手還是后手有必勝的可能性" << endl;while (1)/初始化GOLD_COIN值cout << "請輸入起始金幣總數(shù)量" << endl;cin >> GOLD_COIN;Tree<tree