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

人工智能之計(jì)算機(jī)博弈相關(guān)爭(zhēng)論報(bào)告摘要：計(jì)算機(jī)博弈〔也稱機(jī)器博弈〕，是一個(gè)挑戰(zhàn)無(wú)窮、生氣勃勃的爭(zhēng)論領(lǐng)域，是人工智能領(lǐng)域的重要爭(zhēng)論方向，是機(jī)器智能、兵棋推演、智能決策系統(tǒng)等人工智能領(lǐng)域的重要科研根底。機(jī)器博弈被認(rèn)為是人工智能領(lǐng)域最具挑戰(zhàn)性的爭(zhēng)論方向之一。國(guó)際象棋的計(jì)算機(jī)博弈已經(jīng)有了很長(zhǎng)的歷史，并且經(jīng)受了一場(chǎng)波瀾壯闊的“搏殺”，“深藍(lán)”計(jì)算機(jī)的成功也給人類留下了難以遺忘的記憶。中國(guó)象棋計(jì)算機(jī)博弈的難度絕不亞于國(guó)際象棋，不僅涉足學(xué)者太少，而且參考資料不多。在國(guó)際象棋成熟技術(shù)的根底上，結(jié)合在中國(guó)象棋機(jī)器博弈方面的多年實(shí)踐，總結(jié)出一套過(guò)程建模、狀態(tài)表示、著法生成、棋局評(píng)估、博弈樹搜尋、開局庫(kù)與殘局庫(kù)開發(fā)、系統(tǒng)測(cè)試與參數(shù)優(yōu)化等核心技術(shù)要點(diǎn),最終提出了當(dāng)前爭(zhēng)論的熱點(diǎn)與方向。關(guān)鍵詞：極大微小樹、人工智能、計(jì)算機(jī)博弈計(jì)算機(jī)博弈--人工智能的經(jīng)典領(lǐng)域進(jìn)展歷史智能的活動(dòng)中。所以說(shuō)，下棋軟件某種意義上可以代表人工智能的進(jìn)展程度從上世紀(jì)六十年月的”跳棋機(jī)”1997年的’’深藍(lán)”,計(jì)算機(jī)下棋程序在人機(jī)博弈中取得了一個(gè)又一個(gè)成功，但是這些程序雖然屬于人工智能范疇，實(shí)際上它們并沒(méi)有多少”智”的成分，主要局部都是在可行范圍內(nèi)搜尋。各種爭(zhēng)論也大都是怎樣使搜尋更快更有效。它們?nèi)狈Α敝恰钡某煞值母揪売桑俏覀冏约翰⒉磺宄祟愂且栽鯓拥男问剿伎嫉?。比方你寫一個(gè)名字問(wèn)一位教師，這人是不是他班上的學(xué)生。教師馬上可以答復(fù)是或不是。假設(shè)你問(wèn)計(jì)算機(jī)，計(jì)算機(jī)搜尋很快，全走一邊幾乎可以瞬間完成。但我們知道教師是不行能在短時(shí)間內(nèi)把我們?nèi)繉W(xué)生的名單過(guò)一遍的。類似的，我們看到一個(gè)人的照片，馬上就知道我們以前見沒(méi)見過(guò)這個(gè)人，我們不行能在短時(shí)間內(nèi)把我們以前見過(guò)的人都檢查一遍，那么我們是怎樣得出結(jié)論的呢？現(xiàn)在我們對(duì)此還不是完全清楚[]i對(duì)于人類思維的挑戰(zhàn)1常見機(jī)器博弈系統(tǒng)的構(gòu)成博弈論的范疇，這是對(duì)于人類思維的挑戰(zhàn)?？赡艿恼蟹ǖ难莼Y(jié)果進(jìn)展比較，最終選擇一個(gè)最好的招法。但是，國(guó)際象棋的變化總數(shù)到達(dá)10的123次方，而中國(guó)象棋的變化數(shù)量比1014410172以上，計(jì)算機(jī)不行能算出棋盤上的全部變化。因此，所謂的”利用窮舉法選擇它更沒(méi)方法對(duì)整盤棋的形勢(shì)做正確推斷。目前，在三大棋類工程中，國(guó)際象棋和中國(guó)象棋兩項(xiàng)，計(jì)算機(jī)的水平都已目前圍棋計(jì)算機(jī)大賽獲得冠軍的軟件也只牽強(qiáng)到達(dá)業(yè)余初段水平，和頂級(jí)職業(yè)棋手相比，或許要被讓七子。人工智能的經(jīng)典領(lǐng)域爭(zhēng)論載體。人機(jī)對(duì)弈的程序，至少應(yīng)當(dāng)具備以下局部：走法的規(guī)章并能夠評(píng)估局面優(yōu)劣；與弱項(xiàng)。這是學(xué)問(wèn)挖掘的典型課題；的典型例題；將圍棋的各種定式進(jìn)展表示和區(qū)分，這是模式識(shí)別的典型問(wèn)題；將來(lái)趨勢(shì)—應(yīng)用前景分析圍而攻之奪取地盤等。部隊(duì)的指揮機(jī)關(guān)在謀劃一場(chǎng)戰(zhàn)役〔斗〕之前總是要具體分析雙方的兵力部署、戰(zhàn)場(chǎng)的自然環(huán)境、對(duì)方的可能調(diào)動(dòng)、以及大量難以預(yù)見的大事、戰(zhàn)斗與結(jié)果。早期的戰(zhàn)事謀劃是在物理模型上進(jìn)展的，稱之為沙盤推演。近代的戰(zhàn)事謀劃，包括日軍攻擊珍寶港，聯(lián)合國(guó)軍諾曼底登陸，美軍的海灣戰(zhàn)斗等都是事先進(jìn)展過(guò)周密的“兵棋推演〔”Wargaming,Warsimulation〕，以便做到“不打無(wú)預(yù)備之仗”。二戰(zhàn)退役的老兵還特地開發(fā)了一種玩耍，稱之為“兵棋”[]ii。關(guān)鍵技術(shù)的核心，由于它是人工智能的高級(jí)表達(dá)[]iii。AgentQ-LearningAgentA-gentAgentAgent的歷史動(dòng)作和自身當(dāng)前狀況來(lái)推想其所要執(zhí)行的動(dòng)作。對(duì)任務(wù)調(diào)度問(wèn)題進(jìn)展仿真試驗(yàn),驗(yàn)證了該算法的收斂性[]iv。另一個(gè)重要的應(yīng)用方面就是在玩耍人工智能設(shè)計(jì)中，由于玩耍中絕大多數(shù)人工智能的使用目的就是與玩家博弈，無(wú)論是棋牌類玩耍，街機(jī)搏斗類，動(dòng)作RPG于玩耍中玩耍機(jī)制都是設(shè)計(jì)好了的，玩耍內(nèi)博弈需要的決策，常常都有規(guī)律可循，博弈所需要考慮的參數(shù)也往往是確定并且易得的，因此，在玩耍中，博弈的程序相對(duì)于很多簡(jiǎn)潔的現(xiàn)實(shí)問(wèn)題更好設(shè)計(jì)以及實(shí)現(xiàn)。下面會(huì)講到玩耍中雙人博弈最經(jīng)典的極大微小算法。計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析--極大微小搜尋算法關(guān)于極大微小搜尋取微小值。微小值和極大值都是相對(duì)而言的。用極大或者微小表示。另外極大微小搜尋是用于查找必勝法的。全部可能產(chǎn)生的局面便可記錄在這一棵樹中。2.2問(wèn)題描述：拿硬幣玩耍規(guī)章：13幣的人輸。算法原理：先為玩耍產(chǎn)生全部可能的局面的玩耍樹。第一位玩家為Max,選取最正確步驟進(jìn)攻;其次位玩家為Min進(jìn)展防守，兩位玩家每次都盡力查找必勝法。對(duì)于玩耍中任意一次局面假設(shè)該局面中下一步由Max玩家實(shí)行措施且此時(shí)局面中存在Max玩家必勝法則將該局面標(biāo)記為1，假設(shè)下一步MinMin0。先給玩耍的完畢狀態(tài)如下賦值：然后不斷從葉節(jié)點(diǎn)向上逐層回溯，對(duì)于回溯中遇到的每一個(gè)節(jié)點(diǎn)，假設(shè)他處于Max玩家行動(dòng)產(chǎn)生下一局面的狀況，則該層稱為Max層，當(dāng)子局面中含有被標(biāo)1，Max〔全部深度為偶數(shù)的層，樹的深度從0開頭〕的節(jié)點(diǎn)其值取子節(jié)點(diǎn)中最大值，相反可知Min〔全部深度為奇數(shù)的層〕的節(jié)點(diǎn)其值取子節(jié)點(diǎn)中最小值。算法步驟：遍歷至每一個(gè)葉子節(jié)點(diǎn)，并分析玩耍在該節(jié)點(diǎn)的狀態(tài)，可以將先手贏標(biāo)記0。然后使用一啟發(fā)式算法為該節(jié)點(diǎn)產(chǎn)生一個(gè)值，值越高對(duì)MaxMin進(jìn)展樹的回溯。假設(shè)父節(jié)點(diǎn)為Min，則該父節(jié)點(diǎn)值為全部子節(jié)點(diǎn)中的最小值選擇時(shí)，選擇最小的子節(jié)點(diǎn)的操作進(jìn)展執(zhí)行〕；假設(shè)父節(jié)點(diǎn)為Max,則父節(jié)點(diǎn)的值為全部子節(jié)點(diǎn)的最大值〔AI選擇時(shí)，選擇最大的子節(jié)點(diǎn)的操作進(jìn)展執(zhí)行〕；假設(shè)多個(gè)最小〔大〕值的子節(jié)點(diǎn)，則隨機(jī)選一個(gè)〔更 lifelike〕或選第一個(gè)(其他方法也可以)。流程圖：運(yùn)行截圖：實(shí)現(xiàn)結(jié)果評(píng)價(jià)：運(yùn)行截圖：成功生成了某一金幣下全部玩耍的結(jié)果的最大最小樹，圓滿的是未能以圖形化打印樹，而是使用了前序遍歷輸出最大最小樹。能夠正確推斷誰(shuí)能夠在某一狀況下必勝。由于不存在勝敗不行定局〔即任何狀況下先手或者后手都能夠必勝〕，f〔p〕01兩個(gè)值附錄A：程序主要源代碼及試驗(yàn)說(shuō)明使用說(shuō)明：開發(fā)環(huán)境：windows7ultimatex64visualstudio2023使用環(huán)境：WINDOWSx64/x86操作方法：編譯生成程序后運(yùn)行，輸入一個(gè)整數(shù)〔起始金幣數(shù)量，建議不要過(guò)大，內(nèi)存空間會(huì)缺乏，建議在25以下〕。按Enter，即可看到前序遍歷輸出的最大最小樹，以及誰(shuí)能必勝。最大最小樹以前序遍歷輸出，每個(gè)節(jié)點(diǎn)用(剩余金幣數(shù)量,f(p))格式輸出，子樹會(huì)在節(jié)點(diǎn)后的輸出實(shí)現(xiàn)代碼：main.cpp#include<iostream>#include#include“Tree.h“usingnamespacestd;intGOLD_COIN=3;/*!/*!\curNum該回合后剩下的金幣數(shù)量\minMaxVal\minMaxVal最大最小值,10*/classtreeNode{classtreeNode{public:intcurNum;intintminMaxVal;};boolboolisChildrenAllEqual(Tree<treeNode>*tree,intequalVal){if(tree==NULL){returnfalse;returnfalse;}DListIterator<Tree<treeNode>::Node*>it=tree->m_children.GetIterator;whilewhile(it.m_node!=tree->m_children.m_tail){if(it.Item->m_data.minMaxVal!=equalVal){returnfalsereturnfalse;}it.Forth;}}if(it.Item->m_data.minMaxVal!=equalVal){returnfalsereturnfalse;} returntruereturntrue;}/*!/*!\GOLD_COIN剩下金幣的數(shù)量\depth\depth0*/Tree<treeNode>*initMinMaxTree(intGOLD_COIN,intdepth){ifif(GOLD_COIN<0||depth<0){returnNULL;}}if(GOLD_COIN==0){Tree<treeNode>*tn=newTree<treeNodeif(GOLD_COIN==0){tn->m_data.minMaxVal=depth%2?0:1;}}else{Tree<Tree<treeNode>*temp=initMinMaxTree(GOLD_COIN-1,depth+1);tn->m_children.Append(temp);temptemp=initMinMaxTree(GOLD_COIN-2,depth+1);if(temp!=NULL)tn->m_children.Append(temp);temptn->m_children.Append(temp);temp=initMinMaxTree(GOLD_COIN-3,depth+1);if(temp!=NULL)tn->m_children.Append(temp);tn->m_children.Append(temp);if(depth%2==0){//maxifif(isChildrenAllEqual(tn,0)){tn->m_data.minMaxVal=0;}elseelsetn->m_data.minMaxVal=1;}}else{//minifif(isChildrenAllEqual(tn,1)){tn->m_data.minMaxVal=1;}elseelse{tn->m_data.minMaxVal=0;}}}}}returnreturntn;}voidprintTree(Tree<treeNode>*tree){cout<<“(“<<tree->m_data.curNum<<“,“<<tree->m_data.minMaxVal<<“)“;ifif(tree->m_children.m_count==0)return;DListIteratorDListIterator<Tree<treeNode>::Node*>it=tree->m_children.GetIterator;cout<<“{“;whilewhile(it.Valid){printTree(it.Item);it.Forth;it.Forth;}coutcout<<“}“;}intintmain{cout<<N3還是后手有必勝的可能性“<<endl;while(1){////GOLD_COINcout<<“請(qǐng)輸入起始金幣總數(shù)量“<<endl;cin>>GOLD_COIN;TreeTree<treeNode>*tn=initMinMaxTree(GOLD_COIN,0);cout<<“最大最小樹初始化完成“<<endl;coutcout<<“前序遍歷輸出最大最小樹\nf(p)值])“<<endl;printTree(tn);coutcout<<endl;if(tn->m_data.minMaxVal==1){coutcout<<“先手能夠必勝“<<endl;if(!isChildrenAllEqual(tn,1)){cout<<“假設(shè)第一次先手取走“cout<<“假設(shè)第一次先手取走“;DListIterator<Tree<treeNode>::Node*>it=tn->m_children.GetIterator;while(it.Valid){if(it.Item->m_data.minMaxVal==0)cout<<(GOLD_COIN-it.Item->m_data.curNum)<<“、“;it.Forth;it.Forth;}coutcout<<“\b<<endl;}}else}else{cout<<“后手能夠必勝“<<endl;}}deletetn;tntn=NULL;}return0;}4.參考文獻(xiàn)：[i]黃葦：計(jì)算機(jī)博弈與人工智能，《教科指導(dǎo)》2023〔27〕[ii]楊南征：虛擬演兵——兵棋、作戰(zhàn)模擬與仿真[M].NanzhengYang:Wargame,WarGame,Simulation[M].LiberationArmyPress,Beijing[iii]徐心和，鄧志立：基于機(jī)器博弈的作戰(zhàn)模擬系統(tǒng)探討[C]