2022人工智能機(jī)器博弈白皮書(shū)

第1章引 第2章機(jī)器博弈的發(fā)展?fàn)? 第3章博弈的復(fù)雜 概 第4章機(jī)器博弈的典型技 概 窮盡搜 裁剪搜 啟發(fā)式算 迭代深 并行計(jì) 遺傳算 神經(jīng)網(wǎng) 機(jī)器學(xué) 第5章機(jī)器博弈的平臺(tái)技 第6章完備信息機(jī)器博弈的專(zhuān)項(xiàng)技 概 概 概 概 第7章非完備信息機(jī)器博弈的專(zhuān)項(xiàng)技 概 概 概 第8章機(jī)器博弈的國(guó)內(nèi)外賽 第9章結(jié)束 1ComputerGames定義為讓計(jì)算機(jī)能夠像人一樣開(kāi)來(lái)，ComputerGames中文名字便稱(chēng)之為機(jī)器博弈，或者計(jì)算機(jī)博1997年IBM深藍(lán)戰(zhàn)勝世界棋王在中國(guó)大陸計(jì)算機(jī)博弈還只是極個(gè)別人的個(gè)人行為。當(dāng)谷歌的AlphaGoAlphaGo的升級(jí)版Master橫掃了包括中國(guó)在內(nèi)的60位世界頂尖高手，中國(guó)人才認(rèn)識(shí)到機(jī)器博弈太始研究AlphaGo的技術(shù)和能力，這也把計(jì)算機(jī)博弈推向了新的高度。先行者中山大學(xué)化學(xué)系教授陳志行（1931—2008）。陳老先生1991全國(guó)錦標(biāo)賽時(shí)，興奮不已，抱病參加了在重慶理工大學(xué)舉行的IBM1997年以戰(zhàn)勝卡斯帕羅夫的輝煌速。2005年，中國(guó)人工智能學(xué)會(huì)成立了機(jī)器博弈專(zhuān)業(yè)委員會(huì)，一批ICGA2006、2007年國(guó)際棋類(lèi)奧林匹克大賽中國(guó)象棋冠軍。而且，2006年首屆中期的熱潮，但卻推動(dòng)了全國(guó)錦標(biāo)賽每年一屆的舉行。而且，在2011影圍棋、軍棋等，還有考慮隨機(jī)因素的愛(ài)恩斯坦棋。自2013年起，的研究更加全面和深入。特別值得提及的在，2015年得到國(guó)家體育總局棋牌運(yùn)動(dòng)管理中心支持，將該項(xiàng)比賽納入2015年第三屆全國(guó)智2人數(shù)是實(shí)際參與這項(xiàng)科技活動(dòng)人數(shù)的1/5，那么，實(shí)際參加計(jì)算機(jī)博包括不完備信息的牌類(lèi)游戲搜索算法，當(dāng)然還包括目前最先進(jìn)的AlphaGo的深度學(xué)習(xí)算法、最新的橋牌和德州撲克博弈算法等。機(jī)器博弈的產(chǎn)業(yè)化前景也是很可觀的。AlphaGo的成功，標(biāo)志著2被稱(chēng)作計(jì)算機(jī)之父的馮．諾依曼（JohnvonNeumann）通過(guò)對(duì)兩人零本原理。在馮·諾依曼和摩根斯特恩合著的《博弈論和經(jīng)濟(jì)行為》麥卡錫（JohnMcCarthy）以及馮?諾依曼等人都曾經(jīng)涉足計(jì)算機(jī)博弈19501953年，阿蘭?圖靈設(shè)計(jì)了一個(gè)能夠下國(guó)際象棋的紙上程序，并經(jīng)過(guò)IBMIBM704，成為了第一臺(tái)與人類(lèi)進(jìn)行國(guó)際象家卻對(duì)此歡欣鼓舞。1959年，人工智能的創(chuàng)始人之一塞繆（A．L1962年該程序擊敗了美國(guó)的一個(gè)州冠軍，這是計(jì)算機(jī)博弈歷程中一際象棋計(jì)算機(jī)程序；1988-1989年間，IBM“深思”分別與丹麥特級(jí)大師拉爾森、世界棋王卡斯帕羅夫進(jìn)行了“人機(jī)大戰(zhàn)”。cauo的MMN吸引了前世界棋王卡爾波夫和世界優(yōu)秀女棋手小波爾分別前來(lái)與之（90和93年（96年（1997年）與卡斯帕羅夫的兩場(chǎng)比賽，引起全球媒體的關(guān)注。在隨類(lèi)頂級(jí)高手，計(jì)算機(jī)博弈水平迅速上升。特別是，2016-2017年，AlphaGo完備信息機(jī)器博弈領(lǐng)域的人工智能劃時(shí)代Libratus4名人類(lèi)頂尖德州撲克選手之間進(jìn)行了“人機(jī)大與真人對(duì)打的撲克大賽——“‘冷撲大師’（Libratus撲克機(jī)器人）2006年的人機(jī)大戰(zhàn)中，展現(xiàn)了具有挑戰(zhàn)國(guó)內(nèi)中國(guó)象棋頂4名。這項(xiàng)活動(dòng)最重要的事件是由東北大學(xué)徐心和教授發(fā)起成立的中2006年起每年一屆的12屆。沈陽(yáng)航空航天大學(xué)王亞杰教授在國(guó)內(nèi)大力推廣計(jì)算機(jī)博弈Lab（Fine201721屆世界計(jì)算機(jī)橋牌錦標(biāo)賽中獲得亞軍。DeepMindDemisHassabis曾言：“游戲是測(cè)試人工學(xué)者們?cè)谟?jì)算機(jī)博弈搜索與評(píng)估方面進(jìn)行了大量深入探索和實(shí)質(zhì)性索、Alpha-Beta剪枝、并行搜索算法等[3-7]。06oferyinn發(fā)（epBeiefetors,BN）可使[8]（epeari）習(xí)[0,]等技術(shù)的突破性進(jìn)展，成功解決了機(jī)器博弈中抽象認(rèn)知的難GoogleAlphaGo，作為完備信息博弈代2-1AlphaGo（Policy（Value AlphaGo算法組AlphaGo分為落子棋感和勝負(fù)棋感，AlphaGo3000萬(wàn)的經(jīng)典棋局進(jìn)行和勝負(fù)棋感不斷展開(kāi)搜索樹(shù)[12AlphaGo的成功充分驗(yàn)證了深度學(xué)習(xí)與計(jì)算機(jī)博弈技術(shù)結(jié)合的實(shí)用性。Google公司宣布將其弈系統(tǒng)Libratus為代表，被學(xué)者們總結(jié)為主要包括三個(gè)關(guān)鍵模塊：賽前納什均衡近似（Nashequilibriumapproximationbefore個(gè)模型的幫助下，Libratus自己學(xué)會(huì)了德州撲克，而且比以前速度更殘局解算（Endgamesolving）Libratus最重要的部分，因?yàn)橐痪值聯(lián)渲恍枰獛讉€(gè)回合，耗費(fèi)時(shí)間短。因此Libratus的開(kāi)高手會(huì)尋找Libratus的漏洞，并展開(kāi)有針對(duì)性的攻擊。這個(gè)模塊的作[21]AlphaGoLibratusAI的成功，引發(fā)了國(guó)內(nèi)外學(xué)者AI。左右，主要驅(qū)動(dòng)力在手機(jī)游戲。2015年移動(dòng)游戲收入占移動(dòng)應(yīng)用市2020746相對(duì)于國(guó)外，我國(guó)游戲產(chǎn)業(yè)發(fā)展較快，2014年中國(guó)游戲的營(yíng)業(yè)99個(gè)體育項(xiàng)目外，還將電33-1給出了求解博弈問(wèn)狀態(tài)復(fù)雜度策略策略策略采取任何方法，都可求解。策略采用蠻力搜索，可以求解。博弈樹(shù)復(fù)雜度文獻(xiàn)[37]討論了博弈問(wèn)題的狀態(tài)復(fù)雜度及其博弈樹(shù)復(fù)雜度對(duì)尋3-1西洋跳棋國(guó)際象棋（Chinese日本將棋圍棋文獻(xiàn)[37]tic-tac-toe（三子連珠棋）為例，估算了此博弈問(wèn)5478；9，第i（1i≤9）9-i（即博弈樹(shù)復(fù)雜度）9！。果問(wèn)題被證明是難解的（比如NP-complete、PSPACE-complete及8×8的西洋跳棋（Checkers）2007年得到了理論解[39]，證明比賽雙方各有4個(gè)棋子；每個(gè)棋子都相當(dāng)于國(guó)際象棋中的皇當(dāng)輪到一方走棋時(shí)，此方只能而且必須移動(dòng)4個(gè)棋子中的一4個(gè)棋子均不能再移3-2410010為1041。821223-3棋盤(pán)上總共有36個(gè)交叉點(diǎn)，每個(gè)交叉點(diǎn)有三個(gè)可能的狀態(tài)（即以對(duì)數(shù)值（10為底）的形式表示，則大小約為17.2，這些局面中存在一些非法的局面，比如：根據(jù)規(guī)則，棋盤(pán)上最多只能出現(xiàn)24個(gè)棋24個(gè)。因此，可以換一種角度來(lái)估算，根據(jù)蘇拉卡爾塔的規(guī)則，初36個(gè)棋子、35個(gè)棋子、...、25為底）16.9。己3-4棋盤(pán)與棋子（3-5所示3-5VCF（VictoryofContinuousFours）迫著算法（與五子棋類(lèi)似的搜索算法）VCF361個(gè)點(diǎn)可下，第二步有C2（出現(xiàn)同色六子連珠的局面數(shù)為生同色六子連珠的局面，即棋盤(pán)上可能出現(xiàn)的連六總數(shù)為Count(6)。C2Countpoints6361

nCountpoints(n)=

棋盤(pán)和棋子（3-6所示6×636個(gè)點(diǎn)，而沒(méi)有任60個(gè)3-6tic-tac-toe類(lèi)似。根據(jù)點(diǎn)格6×6終將完成所有鄰近兩點(diǎn)的連線（60個(gè)），60一步走棋；接下來(lái)，另一走棋方能夠在剩下的59個(gè)連線中，選擇一6010為底的形式1082，這是一個(gè)天荒地老的巨型數(shù)值，即使當(dāng)今最先進(jìn)的（15秒/步內(nèi)完成。國(guó)際象棋[42]和西洋跳棋[47]被證明屬于EXPTIME-completeEXPTIME-completeG3游戲[48G3游戲可多項(xiàng)式時(shí)間內(nèi)歸約到被廣義化的國(guó)EXPTIME-complete問(wèn)題[42]），五子棋[50]、六子棋[51]、奧賽羅棋[52]被證明屬于PSPACE-complete用到了廣義地理學(xué)游戲（GeneralizedGeographyGame[53]）；亞馬遜公式博弈（FormulaGame[53]）。n×n類(lèi)似圍棋的棋盤(pán)，的k子連珠，則該方獲勝，如廣為流行的四子棋（Connect-Four）、函數(shù)Connect(m,n,k,p,q)[51]mnk表示走棋規(guī)則中獲勝的條件，即形成同色連珠所包含的棋子數(shù)。p指第一手落幾個(gè)棋子，q規(guī)定第一手之后走棋方每輪落子的數(shù)量。要根據(jù)PSPACE-complete的定義[52]PSPACE的問(wèn)題都?xì)w約到該判定問(wèn)題PSPACE-completePSPACEPSPACE-completePSPACE-complete的一般選PSPACE-complete定義的第二個(gè)條件，需要找到一個(gè)PSPACE-complete的判定問(wèn)題；4中，找到了一個(gè)解決方法（即必勝策略）說(shuō)明步驟2中所選擇的判定問(wèn)題可歸約到該博弈問(wèn)題。即滿(mǎn)足了51，可知該博弈問(wèn)題滿(mǎn)足定義的兩個(gè)條條件，因此根據(jù)相關(guān)定義可知該博弈問(wèn)題的計(jì)算復(fù)雜性屬于在文獻(xiàn)[51]n×n（3-其中包括：1個(gè)仿真區(qū)域、1個(gè)獲勝區(qū)域、p-1個(gè)輔助區(qū)域。其中仿真p-1個(gè)棋子，直到仿真區(qū)域已滿(mǎn)，這樣該1，對(duì)方而說(shuō)明其他的屬于PSPACEPSPACE-complete定義的第二個(gè)條件，得證。3-74GPU并行計(jì)算技術(shù)的廣泛應(yīng)用，使得深度學(xué)習(xí)變Alpha-Beta剪枝搜索[56]和以此為基礎(chǔ)改進(jìn)與增強(qiáng)的（Aspirationsearch）[57]（Memory-enhancedTestDriverwithfandn）[58]等。在具體應(yīng)用Alpha-Beta剪枝Alpha-Beta枝算法的基礎(chǔ)。目前，多數(shù)博弈程序都采用負(fù)極大值形式的渴望搜索MTD(f)Alpha-Beta搜索，縮小上界和下界，并移動(dòng)初始值使其接近最優(yōu)著法。MTD(f)算法簡(jiǎn)單高效，在國(guó)際象棋、國(guó)際跳棋等博弈程序里，MTD(f)算法平均表現(xiàn)平均搜索效率高于MTD(f)搜索[61]。通常，裁剪算法需要與置換表技HashZobristHash技術(shù)來(lái)實(shí)現(xiàn)。Alpha-Beta歷史啟發(fā)（HistoryAlpha-Beta搜索對(duì)節(jié)點(diǎn)排列順序敏感的特點(diǎn)殺手啟發(fā)（KillerAlpha-Beta可以進(jìn)行較深層次的搜索。Alpha-Beta剪枝經(jīng)過(guò)一系列技術(shù)如置換PB*[70]算法。蒙特卡洛樹(shù)搜索（MCTS，MonteCarloTreeSearch）[71-戰(zhàn)的經(jīng)典游戲。近年來(lái)，MCTS在類(lèi)似計(jì)算機(jī)圍棋等完備信息博弈、理論上，MCTS可以被用在以{狀態(tài)，行動(dòng)}定義并用模擬預(yù)測(cè)輸出結(jié)基本的MCTS算法根據(jù)模擬的輸出結(jié)果，按照節(jié)點(diǎn)構(gòu)造博弈樹(shù)，其過(guò)程如圖4-1所示，包括路徑選擇（Selection）博弈程序，例如，AlphaGoMCTS算法進(jìn)行搜索[10]多次重復(fù)4-1MCTSUCT搜索算法UCT算法，即上限置信區(qū)間算法（UCBforTree），是一種基于MCTS發(fā)展的博弈樹(shù)搜索算法，該算法通過(guò)擴(kuò)展UCB（UpperConfidenceBound）MCTSUCB方法相對(duì)于傳統(tǒng)的搜索算法，UCT時(shí)間可控，具有更好的魯棒性，出時(shí)間和空間方面的優(yōu)勢(shì)。目前，UCT在搜索規(guī)模較大的完備信息大部分采用了UCT搜索算法。并行計(jì)算主要有兩種體系，單機(jī)體系SMP（Symmetric近年來(lái)，網(wǎng)絡(luò)并行計(jì)算及多CPU、多核技術(shù)的研究日趨成熟，SMP方式的多線人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworkANN），簡(jiǎn)稱(chēng)為人工神經(jīng)網(wǎng)絡(luò)研究以多倫多大學(xué)的GeoffreyHinton[8,9,96-101]為代（Feedforwardneuralnetworks，F(xiàn)ForFFNN）、徑向神經(jīng)網(wǎng)絡(luò)（Radialbasisfunction，RBF）、霍普菲爾網(wǎng)DBN）、卷積神經(jīng)網(wǎng)絡(luò)（Convolutionalneuralnetworks，CNN）、深層玻爾茲曼機(jī)（DeepBoltzmannMachine，DBM）、堆疊自動(dòng)編碼器機(jī)器學(xué)習(xí)（MachineLearning）的根本任務(wù)是數(shù)據(jù)的智能分析與Learning博弈環(huán)境學(xué)習(xí)器4-2GPUQ-LearningDeepQ-Network[111]技術(shù)的博AlphaGo[10,11]則可以戰(zhàn)勝人類(lèi)頂級(jí)高5致比賽中具有一定的潛在危險(xiǎn)。模塊級(jí)博弈平臺(tái)尚處于探索研究階可以進(jìn)一步避免非法操作或?qū)崿F(xiàn)針對(duì)某一特殊博弈項(xiàng)目情景進(jìn)行專(zhuān)項(xiàng)測(cè)評(píng)[1]。以通過(guò)TCPUDP2012年最早被指定為全國(guó)哈爾濱理工大學(xué)二打一（斗地主）2014年被指2015年全國(guó)智力運(yùn)動(dòng)會(huì)AI陪人競(jìng)賽的模式開(kāi)拓并驗(yàn)證了機(jī)器博弈的173萬(wàn)人在線競(jìng)技，是6專(zhuān)項(xiàng)技2005年提出了六子棋[46,119]kconnect(n=15,k=5,p=1,q=1)Renju[120]Go-Moku[121]19952001年被connect(n=19,k=6,p=2,q=1)。二人的、完備信息的、非合作的博弈問(wèn)題。設(shè)博弈雙方分別為side16-1所示。 m1 m3 mm7side2side16-1六子棋有如下顯著特點(diǎn)：1)平均分枝因子大。普通的博弈樹(shù)搜索的深度太淺，在一定程度上抑制了搜索的作用。2)開(kāi)局、中局、殘局的策略差異不顯著。3)一次走兩顆子的規(guī)則，導(dǎo)致六子棋的狀了“棋盤(pán)三進(jìn)制線二進(jìn)制模式點(diǎn)”的分層表示方法，實(shí)現(xiàn)了領(lǐng)181716151413121110 181716151413121110 6-21,048,512[14]1515種類(lèi)型：勝、必勝、活五、死五、活四、眠四、死四、活6-3所示。6-1為六子棋知識(shí)庫(kù)中全部二進(jìn)制模式的類(lèi)型、數(shù)目、比例的15%。同樣類(lèi)型的棋形，其(a)勝(b)必勝(c)活 (e)活四(f)眠(g)死四(h)活三(i)活 (j)眠二(k)活 6-36-1connect(19,62,1)UCT策略之外，k子棋研究者在文獻(xiàn)[121]提出了兩種有效的搜索方法：證據(jù)計(jì)數(shù)搜索RenjuGo-muku的主要技術(shù)。PNS度給出關(guān)于贏/不贏這類(lèi)二元問(wèn)題的肯定或否定的解答。TSS是一種也更為復(fù)雜。采用TSS搜索策略已成為所有六子棋程序的必備選項(xiàng)AlphaGOTSS有助于構(gòu)建大規(guī)模有監(jiān)督的訓(xùn)練集。第三，六子棋基礎(chǔ)知識(shí)庫(kù)較學(xué)習(xí)等為代表的新技術(shù)突破，構(gòu)建水平更高的六子棋程序越來(lái)越容Allis對(duì)10360）。由于其極大極小樹(shù)的分支因子過(guò)大，Alpha-BetaGNUGO9*957級(jí)水平。06年被S.llyCT算法[2]C[1]919還遠(yuǎn)遠(yuǎn)無(wú)法與人類(lèi)棋手抗衡[2]。此后的十年中，圍棋的研究基本限于CT[81]，直至.Sler學(xué)習(xí)[1]。該方法對(duì)專(zhuān)家棋譜進(jìn)行監(jiān)督學(xué)習(xí)和自博弈強(qiáng)化學(xué)習(xí)，使用CPPUpao于6年擊敗了韓國(guó)九段棋手李世石；其升級(jí)版本Mate17年6017hao的新0UCT2006年，Kocsis和SzepesvariUCT[125]算法，UCT的全名為UCBforTree。UCB(UpperConfidenceBound)[126]Geni

公式（1）UCB的計(jì)算公式，其中Genii臺(tái)機(jī)器新的收Xii臺(tái)機(jī)器目前為止的平均收益，Tii臺(tái)機(jī)器玩過(guò)的次數(shù)，N表示全部機(jī)器玩過(guò)的次數(shù)。UCT其實(shí)就是把UCB的公式勝負(fù)結(jié)果將更新樹(shù)中所有節(jié)點(diǎn)的收益值。UCT算法不斷展開(kāi)博弈樹(shù)UCT算法的最終選擇。UCT算法是將蒙特卡洛方法和UCB的思想結(jié)合到樹(shù)搜索的算法重復(fù)N重復(fù)N6-4簡(jiǎn)而言之，UCT搜索過(guò)程使用UCB作為博弈樹(shù)展開(kāi)的依據(jù)，利樹(shù)，作為節(jié)點(diǎn)的收益，即公式（1）X。UCT發(fā)展的過(guò)程中，文獻(xiàn)[131]RAVE增強(qiáng)算法，文獻(xiàn)UCT并行化[134,135]4*4Pattern庫(kù)提高模[136]UCT搜索中加入了使用深度學(xué)習(xí)結(jié)合強(qiáng)化學(xué)習(xí)方法創(chuàng)建CPU集群和GPU集群進(jìn)行計(jì)深度學(xué)習(xí)與UCTAlphaGo中，利用深度學(xué)習(xí)的方法訓(xùn)練了兩個(gè)網(wǎng)絡(luò)，即Policy6-5AlphaGoUCB（公則用于蒙特卡洛模擬過(guò)程（rolloutsimulation），而且并Atari、Extension、Capture這些明顯的走子）。葉子節(jié)點(diǎn)進(jìn)行蒙特卡UCT也是類(lèi)似的。DeepMind發(fā)表在Nature的論文[10]19*19ExtendedDataTable24。也就是說(shuō)，按照不同角度衡量每個(gè)點(diǎn)周?chē)那闆r，一起做編碼。在近期東北大學(xué)所做實(shí)驗(yàn)中，采用22位19*1922位數(shù)。當(dāng)然，編碼過(guò)程也要時(shí)游戲。點(diǎn)格棋已經(jīng)被納入國(guó)際計(jì)算機(jī)奧林匹克大賽多年，2010年正點(diǎn)格棋雖然規(guī)則簡(jiǎn)單，但是其狀態(tài)空間巨大，BarkerKorf使Alpha-Beta4×5棋盤(pán)尺寸的點(diǎn)格棋問(wèn)題，并得出結(jié)論，這一尺寸下，棋局一定可以以平局結(jié)束[138]6×6棋盤(pán)規(guī)格。棋盤(pán)表示是博弈的基礎(chǔ)，好的棋盤(pán)表示可以獲得更高的執(zhí)行效hsh6×6當(dāng)且僅當(dāng)|i-k|+|j-l|=1時(shí)叫做鄰近的。鄰近的兩點(diǎn)連成一條邊，每個(gè)格6-6所示的等效變換。原棋盤(pán)中的豎邊對(duì)應(yīng)于變換后的橫232H,V表示，0表示該邊未被刪去，1表示該邊已經(jīng)刪去。此外，可以通過(guò)(H,V,S0,S1)S16-6AI程序使用的是靜態(tài)估值，即按照已知的策略和文獻(xiàn)[142]ANN(ArtificialNeuralNetwork)進(jìn)行題，具有很好的通用性和可控性。在DeepMind團(tuán)隊(duì)將卷積神經(jīng)網(wǎng)絡(luò)CNN（ConvolutionalNeuralNetwork）技術(shù)引入計(jì)算機(jī)博弈[10]之后，UCTANN文獻(xiàn)[142]UCTANN相結(jié)合的方式。ANN具有近似估ANN用在對(duì)葉子節(jié)點(diǎn)的評(píng)估上，可以不必將ANN是近似估計(jì)，錯(cuò)誤不可避免，這就需要通過(guò)大量UCTANN的結(jié)合使CNNAlpha-BetaAlpha-Beta完全搜索可以提供最精確的游戲局面在非完全的Alpha-Beta面評(píng)估函數(shù)，開(kāi)發(fā)難度高，時(shí)間開(kāi)銷(xiāo)大。一個(gè)經(jīng)過(guò)充分訓(xùn)練的CNNCNN的評(píng)估精度尚Alpha-BetaCNN與其他算法集經(jīng)網(wǎng)絡(luò)的置信回合區(qū)間中時(shí)，卷積神經(jīng)網(wǎng)絡(luò)模型將直接充當(dāng)Alpha-Beta網(wǎng)絡(luò)的MCTSCNN也可以與MCTS搜索使用監(jiān)督學(xué)習(xí)方法離線訓(xùn)練得到的人工神經(jīng)網(wǎng)絡(luò)模型作為點(diǎn)格棋局CT數(shù)學(xué)家IngoAlth?fer2004年發(fā)明的棋盤(pán)游戲。愛(ài)恩斯坦棋是比較5*5的方格棋盤(pán)[1,146,147]，方格是棋子的移6-7(b)所示。 圖6-7棋子開(kāi)局與布局2。 6-86-8(a)21或者56-8(b)53。5*5示[146]ID6-9所示。ID=20num（num166個(gè)棋子）表示紅方棋子，ID=10+num表示藍(lán)方，ID=0

23 14

06-9在傳統(tǒng)的MAXMIN層之間加入CHANCE骰子隨機(jī)事件發(fā)生的預(yù)期期望值。在傳統(tǒng)的極大極小樹(shù)中，MAX層MIN層交替出現(xiàn)直至達(dá)到固定搜索深度，MAXMIN層分別取6-10攻防兼?zhèn)涞钠谕阉魉惴?AnOffensiveandDefensiveExpectMinimaxAlgorithm，ODEMA)[152]考慮愛(ài)恩斯坦棋規(guī)則的特殊性，結(jié)MAXMINDICE3個(gè)方面的估值來(lái)全在攻防兼?zhèn)涞钠谕阉魉惴ㄖ休斎肽M棋子的相關(guān)屬性包括棋1所示，其中M=06-11中，ODEMA所構(gòu)造的博弈樹(shù)并不是一顆標(biāo)準(zhǔn)的完全MAXMIN層的 ODEMA示意7專(zhuān)項(xiàng)技P難問(wèn)題[5].16×07,此，德州撲克也是人工智能領(lǐng)域非常具有挑戰(zhàn)性和代表性的博弈課-17-12008PolarisBorisIolis[154]提出了一種適用于撲克牌問(wèn)題的選擇策略，該策略以決Heinrich[155]Kuhnpoker的近似納什均衡策略；2011年，文獻(xiàn)[156]中首次應(yīng)用了模式匹配算法研究德州撲克游戲。2015年，現(xiàn)實(shí)悔恨值最小化（Counterfactualregretminimization,CFR）算州撲克的DeepStack算法研究[157]，DeepStack是首個(gè)打敗職業(yè)撲克玩CFR2007Zinkevich和Johanson提出了基CFR算法[158]。CFRCounterfactualRegretMinimization，其中，RegretMinimization即為悔恨值最小化。T

max(ui(i,i)ui())

t算方法如公式（2）。其中，tit輪游戲中所使用的策零和游戲中，如果雙方玩家的平均悔恨值均小于，則可以看作達(dá)到了一個(gè)2均衡。CFR算法與普通悔恨值最小化算法的不同之處在于其將平均悔T(I,a)1 t(I

t

,I)

t,I

t

ui

I

ui對(duì)于信息集I中的每一個(gè)

ai的反現(xiàn)實(shí)悔恨值如公式（3）i外其他玩家依據(jù)策略7-2CFR算法的迭代求 CFR算法迭代過(guò)CFR算法及其變形廣泛應(yīng)用于撲克游戲中近似納什均2015BowlingBurchJohansonCFRCFR+的新算法[159]，CFR算法截取博弈過(guò)程的一部CFR+算法對(duì)整棵博弈樹(shù)迭代，且規(guī)定悔恨值必須為DeepStackDeepStack2017年由CFR+算法的研究團(tuán)隊(duì)提出的又一DeepStack算法由三個(gè)部分組成：針對(duì)當(dāng)前公共狀態(tài)的本地策略全連接隱含層，每層500個(gè)節(jié)點(diǎn)。訓(xùn)練樣本分別為1,000,000 7-3（a）中，在每一個(gè)公共狀態(tài)中，DeepStack使用有限深度10步以?xún)?nèi)完全可以應(yīng)付一些極端情況。A棋子初始可能性向量是(0.06,0.06,(0.06,0.06,0.08,0.08,0,0,0,0,0,0,0)1計(jì)算得到(0.17,0.17,0.22,0.22,0.22,0,0,0,0,0,0,0)BB棋子可能性向量也是(0.06,0.06,0.08,0.08,0.08,0.08,0.12,0.12,0.12,0.12,0.08,0)A棋子勝過(guò)營(yíng)長(zhǎng)，那么B棋子大于營(yíng)長(zhǎng)的可能性就應(yīng)25×127-4 營(yíng) 炸0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.02,0.02,0.03,0.03,0.03,0.03,0.05,0.05,0.05,0.17,0.04,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.02,0.02,0.03,0.03,0.03,0.03,0.05,0.05,0.05,0.17,0.04,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.03,0.03,0.06,0.06,0.06,0.06,0.09,0.09,0.09,0.33,0.08,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.09,0.09,0.09,0.09,0.14,0.14,0.14,0.00,0.13,0.05,0.05,0.11,0.11,0.11,0.11,0.16,0.16,0.16,0.00,0.00,0.05,0.05,0.11,0.11,0.11,0.11,0.16,0.16,0.16,0.00,0.00,0.05,0.05,0.11,0.11,0.11,0.11,0.16,0.16,0.16,0.00,0.00,0.05,0.05,0.11,0.11,0.11,0.11,0.16,0.16,0.16,0.00,0.00,0.05,0.05,0.11,0.11,0.11,0.11,0.16,0.16,0.16,0.00,0.00, A11。每個(gè)NP-hard問(wèn)題[165]，直接使用精確推理方法效[6][4,6]該算法精髓是計(jì)算局部消息傳遞，從而可以計(jì)算結(jié)點(diǎn)的邊緣概率分AI，才能UCT算法是通過(guò)對(duì)多種狀態(tài)空間（即多個(gè)可能的完UCT算法7-5中分別顯示了叫牌過(guò)程和首攻后的打牌狀態(tài)。 ≈108，每手牌的出牌可能性約為1021，因此打牌階段最復(fù)雜的情況1029。13239≈1021造一個(gè)快速雙明手求解器》就提出了。結(jié)合橋牌專(zhuān)家技術(shù)，利用有算法優(yōu)化的改進(jìn)論文發(fā)表，提升了算法的運(yùn)行效率[168,169]。圖7-6 局面下叫牌和出牌回報(bào)的數(shù)學(xué)期望。AI可以結(jié)合數(shù)學(xué)期望和必要的 AI戰(zhàn)勝人類(lèi)必須突破的關(guān)鍵點(diǎn)。目前常見(jiàn)的做法是基礎(chǔ)的框架采用專(zhuān)家編寫(xiě)叫牌博弈樹(shù)，AI查AI具備甚至超過(guò)人類(lèi)牌AI的思維向人類(lèi)一樣細(xì)膩、嚴(yán)瑾，并具備人類(lèi)牌81958年，名為“思考”的IBM704200198775245019896200021993年，“深思”二代擊敗了丹麥國(guó)家隊(duì)，在與前女子世界19962241997年，“更深的藍(lán)”開(kāi)發(fā)出了更加高級(jí)的“大腦”，4名國(guó)際大師參與IBM3.52.5擊敗了卡斯帕羅夫，卡斯帕羅夫要求2001年，一家德國(guó)公司開(kāi)發(fā)的國(guó)際象棋軟件“更弗里茨”200210600442003123320046月，國(guó)際象棋特級(jí)大師諸宸首度代表中國(guó)棋手參0：2敗下陣來(lái)。20055.50.520061124“UEC2007年始于日本，每年邀AI齊聚東京比賽，促進(jìn)相關(guān)學(xué)術(shù)及科技的交流。日本DeepZenGo、法國(guó)的“瘋石”（CrazyStone）、美國(guó)Facebook公UEC杯折桂獲獎(jiǎng)。2017310UEC杯計(jì)算機(jī)圍棋大賽在東京落幕，今30AlphaGoAILab（騰訊人工智能實(shí)驗(yàn)室）研發(fā)的圍棋人工智能程序“絕藝”（FineArt）首次UEC杯冠軍，2017DeepZenGo”201511月，美林谷杯首屆世界計(jì)算機(jī)圍棋錦