張小川，候鑫磊，涂飛

(重慶理工大學(xué)a.計(jì)算機(jī)科學(xué)與工程學(xué)院;b.人工智能系統(tǒng)研究所，重慶 400054)

博弈機(jī)器人的行為規(guī)劃

張小川a，b，候鑫磊a，b，涂飛a

(重慶理工大學(xué)a.計(jì)算機(jī)科學(xué)與工程學(xué)院;b.人工智能系統(tǒng)研究所，重慶 400054)

博弈行為是博弈機(jī)器人智能的外在表現(xiàn)，行為選擇是提高機(jī)器人智能的重要手段之一，而博弈行為體系是行為選擇的重要基礎(chǔ)。通過模擬人類下棋過程，提出了博弈機(jī)器人的行為過程結(jié)構(gòu)，依據(jù)系統(tǒng)分類思想，構(gòu)建了博弈機(jī)器人的博弈行為體系，提出了博弈行為規(guī)劃方法，借助六子棋博弈平臺(tái)，驗(yàn)證了研究成果的有效性。

機(jī)器博弈;博弈機(jī)器人;行為規(guī)劃;六子棋

智能是生命體最精彩的功能。人類從未停止過對(duì)自身及其他自然生命體的思考:智能的本質(zhì)是什么?長期以來，這是困擾人類的重要科學(xué)問題。國內(nèi)學(xué)者鐘義信［1］認(rèn)為:關(guān)于智能的本質(zhì)，可從“信息－知識(shí)－策略－行為”的轉(zhuǎn)換過程獲得初步的認(rèn)識(shí);行為是生命體外在的表現(xiàn)形式，是生命體內(nèi)在智能的外部表象。Tyrell認(rèn)為［2］:“行為選擇就是從一組可能的候選集中選擇最適合的行為。”因此，行為選擇是生命體智能的高級(jí)形式，對(duì)行為選擇的研究將有助于揭示智能過程和智能的本質(zhì)，具有重要的科學(xué)意義，而行為本身的研究又是行為選擇研究的重要基礎(chǔ)。

本文以機(jī)器博弈為研究原型，以博弈機(jī)器人的競(jìng)爭性行為作為研究對(duì)象，首先建立了博弈機(jī)器人的行為過程結(jié)構(gòu)，提出了機(jī)器博弈的行為體系，為研究機(jī)器博弈中的聯(lián)想推理行為奠定基礎(chǔ)。

1 博弈機(jī)器人的行為過程結(jié)構(gòu)

在雙方完備信息博弈活動(dòng)中，雙方都需要考慮對(duì)手各種可能的方案、著法，并試圖發(fā)現(xiàn)、選擇對(duì)己方有利或合理的方案、著法。這個(gè)過程的外在表現(xiàn)就是一個(gè)博弈行為序列，其實(shí)質(zhì)是博弈行為選擇問題。因此，雙方完備信息博弈問題具有3個(gè)特點(diǎn)，即雙方對(duì)弈，嚴(yán)格控時(shí)，共同產(chǎn)生了博弈行為時(shí)間序列。比如象棋的甲1步→乙1步→甲1步→乙1步……單步博弈行為序列，或如六子棋的甲1步→乙2步→甲2步→乙2步……多步博弈行為序列。信息完備是指博弈各方能獲得相同的博弈信息。零和博弈即不存在博弈各方均得利或無利的博弈行為，博弈結(jié)果只能是某一方勝、另一方負(fù)或和局的狀況，且必須是其一狀況。據(jù)此特點(diǎn)，可以進(jìn)一步提煉如下博弈規(guī)則:

①雙方輪流完成博弈行為;

②博弈過程有時(shí)間限制;

③博弈過程是尋找對(duì)己方有利的博弈行為的時(shí)間序列過程;

④各方不能干預(yù)對(duì)方選擇;

⑤比賽結(jié)果是贏、輸、平局之一，且只能是之一。

假設(shè)我方為W、對(duì)方為E并為先手。從上面的分析可知:如果是六子棋博弈的多步博弈行為序列，那么經(jīng)過n步對(duì)弈后，就形成如下博弈行為時(shí)間序列S:

在式(1)中，W和E之間任何一輪次切換都為雙方留下發(fā)現(xiàn)、規(guī)劃自認(rèn)為有利或合理著法的時(shí)空。此處著法可以是單步，也可以是多步所構(gòu)成的博弈行為序列。因此，通過模仿人類博弈過程，本文構(gòu)建了如圖1所示的博弈機(jī)器人行為過程結(jié)構(gòu)。

圖1 博弈機(jī)器人的行為過程結(jié)構(gòu)

在圖1中，利用數(shù)據(jù)庫作為機(jī)器人的知識(shí)源。采用分層遞階的模塊化控制思想，將機(jī)器人博弈過程分解為相對(duì)獨(dú)立的、耦合度比較低的工作模塊，從而形成了機(jī)器人的博弈行為過程。其中:模塊a完成博弈初始化狀態(tài);模塊b完成博弈棋盤、博弈現(xiàn)場(chǎng)情況(如是人－機(jī)博弈，還需采集人的情感信息等)的規(guī)范化處理工作;模塊c完成感知模塊b的數(shù)字化圖像處理、分析和判讀，形成可支持判斷棋盤狀態(tài)的數(shù)據(jù)，并借助知識(shí)庫形成初步的策略，比如攻、防，或吃、兌、棄、馬后炮、雙迫著、單迫著等比較高層的謀劃;模塊e針對(duì)模塊d的策略，借助行為庫，規(guī)劃、選擇具體的實(shí)施行為，如“馬后炮”、“三.三”等定式，規(guī)劃具體行為或行為序列;模塊f完成前述模塊的具體動(dòng)作，是具體的執(zhí)行機(jī)構(gòu);模塊g主要完成博弈過程的結(jié)束掃尾工作，比如保存棋譜、執(zhí)行機(jī)構(gòu)歸位等。

2 博弈行為體系

智能是感知、理解、判斷、推理、規(guī)劃和學(xué)習(xí)的一種能力，其中策略、規(guī)劃的制定與行為選擇過程密切相關(guān)。通常將行為選擇分為競(jìng)爭型和合作型2種類型，前者是以最大行為驅(qū)動(dòng)力大于一定閾值為目標(biāo)的行為選擇;后者是以合作行為驅(qū)動(dòng)力強(qiáng)度趨大為原則的行為選擇［3］。競(jìng)爭性的博弈行為還具有比較明顯的特征，如目的性強(qiáng)、時(shí)效性突出、對(duì)抗激烈。博弈各方必須在有限時(shí)間內(nèi)選擇、產(chǎn)生合適的博弈著法，為己方博弈進(jìn)程貢獻(xiàn)最大利益值。該利益值通常由相應(yīng)的評(píng)估函數(shù)估算［4］。因此，著法產(chǎn)生就是博弈過程的核心步驟。而任何著法的產(chǎn)生都源于對(duì)當(dāng)前局勢(shì)的判斷、評(píng)估，理論上可以建立一棵完全博弈樹，對(duì)該博弈樹進(jìn)行完全搜索，即可產(chǎn)生最佳的博弈著法。但現(xiàn)實(shí)是目前運(yùn)算速度最快的計(jì)算機(jī)都無法滿足博弈規(guī)則對(duì)時(shí)間嚴(yán)格限制的需要，這樣人們就嘗試?yán)猛评砑夹g(shù)，化繁為簡，構(gòu)建機(jī)器人的推理能力。

通過分析發(fā)現(xiàn):在博弈機(jī)器人的棋類博弈活動(dòng)中，推理過程大多數(shù)采用定式型聯(lián)想式推理方法，也有少部分采用規(guī)則型搜索式推理方法。但這些推理方式都需要比較完備的、形式化的行為體系來支撐，這就是本文構(gòu)建博弈行為庫，研究博弈行為規(guī)劃的重要原因。

從仿人、仿生角度出發(fā)，本文采用系統(tǒng)科學(xué)的分層分類方法分析和模仿人類的博弈行為，對(duì)機(jī)器人博弈行為進(jìn)行表1所示的分層，即將機(jī)器人的博弈行為劃分為優(yōu)先順序從低到高的4個(gè)層次:基本行為、技術(shù)行為、戰(zhàn)術(shù)行為和戰(zhàn)略行為。

表1 博弈機(jī)器人的博弈行為分層體系列表

1)基本行為:指博弈機(jī)器人的基本動(dòng)作，基本行為依據(jù)不同的棋類博弈規(guī)則會(huì)有所不同。如吃子、落子、移動(dòng)等。

2)技術(shù)行為:指博弈機(jī)器人在基本行為基礎(chǔ)之上所形成的有一定技術(shù)含量的技巧性進(jìn)攻、防守性行動(dòng)。如象棋中的將、吃、兌等，圍棋中的打、提、征、枷、扳、(找)眼位、(計(jì)算)氣，六子棋的連、擋、斷等。

3)戰(zhàn)術(shù)行為:指具有一定知識(shí)含量、可復(fù)用的一些組合動(dòng)作，是一種行動(dòng)。此外，失敗行為也以案例形式歸入本類，以避免歷史性悲劇的再次發(fā)生。如象棋的馬后炮、雙將，圍棋中的劫、大飛、雙燈，六子棋的連五、連四、連三等。

4)戰(zhàn)略行為:為實(shí)現(xiàn)某個(gè)特定戰(zhàn)略意圖，由2個(gè)或2個(gè)以上技術(shù)行為、戰(zhàn)術(shù)行為組成的動(dòng)作序列是一種行動(dòng)方案。如象棋的仙人指路、各殘局定式，圍棋的點(diǎn)三.三、大場(chǎng)、終局定式，六子棋的雙迫著、單迫著等。

技術(shù)行為是以基本行為為基礎(chǔ)，戰(zhàn)術(shù)行為又是以技術(shù)行為為基礎(chǔ)，戰(zhàn)略行為則是建立在技術(shù)行為和戰(zhàn)術(shù)行為基礎(chǔ)之上的。因此，4類行為的層次就如堆積臺(tái)階一樣，逐層向上堆積，低層行為是上層行為實(shí)現(xiàn)的保障，最終組成博弈行為體系。

3 博弈行為規(guī)劃

博弈行為是博弈機(jī)器人智能的外在表現(xiàn)，博弈行為選擇是博弈機(jī)器人內(nèi)在智能的表現(xiàn)形式之一。實(shí)際上，人類的高級(jí)博弈策略，如“以退為進(jìn)”、“得寸進(jìn)尺”、“欲擒故縱”、“圍魏救趙”等，都是在經(jīng)驗(yàn)、先驗(yàn)知識(shí)基礎(chǔ)上進(jìn)行規(guī)劃、布局的產(chǎn)物。

在文獻(xiàn)［3］中，筆者所在團(tuán)隊(duì)建立了人工生命體行為選擇模型。該模型是一個(gè)基于優(yōu)先度的行為選擇分級(jí)模型。它能較好地體現(xiàn)動(dòng)物在特別饑餓時(shí)，冒著被捕獵的危險(xiǎn)實(shí)施“順手牽羊”的進(jìn)食行為，體現(xiàn)出動(dòng)物的高級(jí)智能。這個(gè)模型利用優(yōu)先度方法，從另外角度提出了一種可行的行為選擇機(jī)制。因此，應(yīng)用優(yōu)先度思想，對(duì)表1的行為進(jìn)行規(guī)劃，就能減少搜索的盲目性，提高博弈行為搜索的準(zhǔn)確性和搜索效率。這樣，獲取優(yōu)先度數(shù)值就成為首要問題。

實(shí)際上，要獲取表1中各具體行為的優(yōu)先度值，通?？梢圆捎?種方法:一是利用人類博弈的先驗(yàn)知識(shí)，在此基礎(chǔ)上，利用各類算法進(jìn)行優(yōu)選、調(diào)整，這也是機(jī)器博弈領(lǐng)域的主要方法。如1997年IBM“更深的藍(lán)”打敗世界國際象棋大師卡斯帕羅夫，就得到了1名國際特級(jí)大師、4名電腦專家的先驗(yàn)知識(shí)支持;二是利用機(jī)器學(xué)習(xí)技術(shù)，讓機(jī)器人在不斷的博弈實(shí)戰(zhàn)中積累博弈經(jīng)驗(yàn)，逐漸形成自己的博弈先驗(yàn)知識(shí)及其優(yōu)先度值，這種方法也是不少學(xué)者常選的方法，但其不確定性因素太多，目前表現(xiàn)的效果較差。另外，不少學(xué)者融合應(yīng)用2種方法，取長補(bǔ)短，也取得了實(shí)戰(zhàn)效果。

3.1 博弈行為的形式化

由于目前計(jì)算機(jī)結(jié)構(gòu)基本上還是二進(jìn)制的馮·諾依曼體系，因此，無論采用什么方法獲取行為優(yōu)先度，都必須對(duì)式(1)所代表的博弈問題進(jìn)行形式化、數(shù)字化。通過分析，可以將其描述為如下形式:

定義1基于四元函數(shù)的博弈過程

其中:ΩG={c}表示博弈空間，即棋局或博弈狀態(tài)空間，是一個(gè)二維狀態(tài)空間;ΩO={o}表示算子空間，即操作或規(guī)則的集合，是圖1知識(shí)庫的主體內(nèi)容;c(o)∈ΩG表示當(dāng)前博弈狀態(tài);式(1)中開始時(shí)的博弈初始狀態(tài)，也稱開局狀態(tài);c(g)∈ΩG表示博弈目標(biāo)、結(jié)果，Σc(g)是所追求博弈目標(biāo)的集合。

定義2博弈行為集合A。假設(shè)A為博弈機(jī)器人所有可能行為所構(gòu)成的集合，其取值包含基本行為Ab、技術(shù)行為At、戰(zhàn)術(shù)行為Aw和戰(zhàn)略行為As共4個(gè)子集，如Ab={Fc－落子，Ec－吃子，Mc－移動(dòng)}，則A取值為

在實(shí)施中，進(jìn)一步細(xì)分上述行為，如基本行為子集Ab中的Mc包含圖2中8個(gè)方位的移動(dòng)動(dòng)作，即從左到右、從前到后構(gòu)成為{LF，F(xiàn)，RF，L、R、LB、B、RB}。

圖2 棋盤上節(jié)點(diǎn)周圍的8個(gè)方位圖

由于受具體行棋規(guī)則所限，8個(gè)方位并不是各類博弈都擁有的行為。為便于使用，在實(shí)施中，進(jìn)一步按表2進(jìn)行8位編碼。

表2 博弈行為編碼列表

在編碼規(guī)則表2中，第1位表示行為類型、第2～6位表示行為、第7位表示棋種類、第8位為標(biāo)示位。

需要注意的是，對(duì)于不同棋類，集合A的取值范圍大不相同，算子空間ΩO的運(yùn)算規(guī)則也是極不相同。比如，在象棋中，有吃子著法，棋盤上的棋子隨棋局發(fā)展會(huì)越來越少，而諸如五子棋、六子棋的K－子棋就沒有吃子著法，隨著棋局推進(jìn)和不斷落子，棋盤上的棋子數(shù)目會(huì)越來越多。這些具體差異需要通過算子、編碼予以規(guī)范，通過第7，8位編碼的不同值來體現(xiàn)不同棋類及其運(yùn)算規(guī)則。

3.2 博弈行為規(guī)劃示例

下面以六子棋“迫著”算法為例，說明博弈行為的規(guī)劃過程?！捌戎本褪羌追叫枰聇顆子來避免乙方連k，則稱該乙方有“迫著”。當(dāng)t=2，k= 6時(shí)，就是“雙迫著”，即甲方要下2顆子才能避免乙方連六的“迫著”。當(dāng)t=1，k=6時(shí)，就是“單迫著”，即甲方需要下1顆子才能避免乙方連六的“迫著”。通過“迫著”，強(qiáng)迫對(duì)方只能在指定點(diǎn)下棋，否則將輸棋，這極大地限制了對(duì)方，并牽著對(duì)方走棋，從而使對(duì)方處于被動(dòng)挨打的地步。

為實(shí)施戰(zhàn)略性行為，進(jìn)行行為規(guī)劃如下:

①搜索六子棋博弈空間，發(fā)現(xiàn)W，E雙方的連四、連五技術(shù)行為(棋形)。

在六子棋中，表1戰(zhàn)術(shù)行為中，理論上連四行為有32種，連五行為有8種。搜索棋盤狀態(tài)空間可能存在的上述戰(zhàn)術(shù)行為，并標(biāo)記和單獨(dú)存儲(chǔ)。

②計(jì)算E方“必堵點(diǎn)”PlugChessN［5－6］

必堵點(diǎn)數(shù)PlugChessN就是需要立即堵住對(duì)方特殊棋形否則我方必輸所需的棋子數(shù);type表示戰(zhàn)術(shù)行為的子類，此處為某方棋子連續(xù)成形的棋形，如連五、連四等，此處取值為4或 5;TypeN表示對(duì)應(yīng)type數(shù)的棋形數(shù)目;typeReTimes表示對(duì)應(yīng)type數(shù)棋形交叉點(diǎn)的重復(fù)數(shù)量。

③依據(jù)PlugChessN，執(zhí)行相應(yīng)行為。

If PlugChessN=0 then plan－behavior－1

plan－behavior－1:執(zhí)行己方最大優(yōu)先度值的指定行為

If PlugChessN=1 then plan－behavior－2

plan－behavior－2:在必堵點(diǎn)落1子再執(zhí)行己方最大優(yōu)先度值的指定行為

If PlugChessNum=2 then plan－behavior－3

plan－behavior－3:在必堵點(diǎn)落2子

If PlugChessNum＞2 then failure(認(rèn)輸)

注:六子棋博弈基本規(guī)則是在19×19圍棋棋盤上，雙方交替落子，先手方第1手只能下1顆棋子，此后各方交替每次落子2顆，當(dāng)某方率先連六成功時(shí)為勝，如果棋盤下滿無勝負(fù)即為和。

上述研究成果已應(yīng)用于重理工騎士隊(duì)的六子棋博弈項(xiàng)目，并參加全國大學(xué)生錦標(biāo)賽，獲得了亞軍的優(yōu)異成績。這從一個(gè)側(cè)面證明了本文研究思想、成果的有效性。

4 結(jié)束語

本文以博弈機(jī)器人的完備信息博弈行為作為研究對(duì)象，為機(jī)器人利用聯(lián)想推理技術(shù)，實(shí)現(xiàn)博弈樹的剪枝奠定基礎(chǔ)。本文的研究對(duì)其他機(jī)器人行為的研究具有直接的借鑒意義。

［1］鐘義信.人工生命由分立走向和諧［M］.北京:科學(xué)出版社，2006.

［2］Tyrrell T.Computational mechanisms for action selection［D］.Edinburgh:University of Edinburgh，1993.

［3］李祖樞，謝汝林，張小川.人工生命體行為選擇及其進(jìn)化研究［J］.模式識(shí)別與人工智能，2005，18(3):49－55.

［4］呂艷輝，宮瑞敏.計(jì)算機(jī)博弈中估值算法與博弈訓(xùn)練的研究［J］.計(jì)算機(jī)工程，2012，38(11):163－166.

［5］張世強(qiáng).基于六子棋機(jī)器博弈平臺(tái)的智能決策系統(tǒng)的研究與設(shè)計(jì)［D］，重慶:重慶理工大學(xué)，2009.

［6］陳東立，姚杰，史艷維.基于純策略的區(qū)間數(shù)矩陣博弈模型的研究［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2012，26(2):107－111.

(責(zé)任編輯 劉舸)

Behavior Planning for the Game Robot

ZHANG Xiao－chuana，b，HOU Xin－leia，b，TU Feia
(a.School of Computer Science and Engineering;b.Institute of Artificial Intelligent，Chongqing University of Technology，Chongqing 400054，China)

The game behavior is an outward manifestation of the game robot’s intelligence，and the behavior selection is one of the important methods to improve robot intelligence.And the game behavior system is also an important research foundation of behavior selection.This article simulated the process of human game playing，and put forward the behavior process structure for the computer game robot.According to the system classification thought，the article built the robot’s computer game behavior system，put forward the behavior planning method，and verified the effectiveness of the research result with the Connect6 game platform.

computer game;game robot;behavior planning;Connect6

TP18

A

1674－8425(2014)04－0099－05

10.3969/j.issn.1674－8425(z).2014.04.021

2014－01－16

國家自然科學(xué)基金資助項(xiàng)目(60443004);重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ120824)

張小川(1965—)，男，四川鄰水人，碩士，教授，主要從事人工生命、計(jì)算機(jī)軟件方面的研究。

張小川，候鑫磊，涂飛.博弈機(jī)器人的行為規(guī)劃［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2014(4):99－103.

format:ZHANG Xiao－chuan，HOU Xin－lei，TU Fei.Behavior Planning for the Game Robot［J］.Journal of Chongqing University of Technology:Natural Science，2014(4):99－103.