劉 成，李 飛，孫玉霞，尹 航，邱虹坤，王亞杰

（沈陽航空航天大學(xué) 工程訓(xùn)練中心，遼寧 沈陽 110136）

0 引 言

AlphaGo戰(zhàn)勝李世石之后，機器博弈技術(shù)實現(xiàn)飛速發(fā)展，人工智能再次成為業(yè)界熱點，成為時代標(biāo)簽[1]。在新形勢下，國務(wù)院在2017年7月制定了《新一代人工智能發(fā)展規(guī)劃》，提出高校應(yīng)該“拓寬人工智能專業(yè)教育內(nèi)容，形成人工智能+X復(fù)合專業(yè)培養(yǎng)新模式”，鼓勵以“寓教于樂”的形式普及與推廣人工智能[2]；教育部在2018年4月印發(fā)了《高等學(xué)校人工智能創(chuàng)新行動計劃》的通知，要求高校落實新一代人工智能發(fā)展規(guī)劃，“進一步提升高校人工智能領(lǐng)域科技創(chuàng)新、人才培養(yǎng)和服務(wù)國家需求的能力”[3]。

機器博弈是人工智能研究的理想載體，是人工智能學(xué)科的“果蠅”[4]。在高校開設(shè)關(guān)于機器博弈的基礎(chǔ)課程，是培養(yǎng)大學(xué)生人工智能科學(xué)素養(yǎng)、提高大學(xué)生大數(shù)據(jù)專業(yè)技能的重要途徑，符合我國《新一代人工智能發(fā)展規(guī)劃》的戰(zhàn)略要求。因此，在高校的本科教學(xué)中開設(shè)有關(guān)機器博弈的課程意義重大，無論是課程內(nèi)容的設(shè)計，還是教學(xué)方法的選取，都值得廣泛深入的探討。

1 計算機博弈基礎(chǔ)課程簡介

計算機博弈基礎(chǔ)課程是沈陽航空航天大學(xué)于2015年開設(shè)的校級選修課，其目的是為了拓寬學(xué)生視野、激發(fā)學(xué)生創(chuàng)新潛能、夯實學(xué)生參與機器博弈等課外科技活動的技術(shù)儲備。該課程面向全校各專業(yè)各年級的學(xué)生，總學(xué)時為16，其中理論學(xué)時為10，上機實驗學(xué)時為6。

在授課時發(fā)現(xiàn)，選課的學(xué)生絕大多數(shù)是理工科的低年級學(xué)生，其中大一學(xué)生的人數(shù)比例有時高達85%。較多的零基礎(chǔ)學(xué)生以及較短的學(xué)時，給授課工作帶來一定的難度。如果通過提高選課條件的方式來限制選課學(xué)生的數(shù)量，則學(xué)生的受益面變窄，對機器博弈課外活動感興趣的學(xué)生不能及時得到技術(shù)支持，背離了課程的目標(biāo)?？梢姡捎脗鹘y(tǒng)的授課方式很難解決實際的教學(xué)條件和教學(xué)目標(biāo)之間的矛盾。

貫穿式案例教學(xué)法的核心思想就是選取最具代表性和完整性的教學(xué)案例，用以貫穿整個教學(xué)過程的一種教學(xué)方法，是案例教學(xué)法[5-6]的一個變種。貫穿式案例教學(xué)法具有知識點銜接性強、理論聯(lián)系實際和任務(wù)驅(qū)動等特征，被一些學(xué)者應(yīng)用到教學(xué)中[7-8]。在計算機博弈基礎(chǔ)課程中，作者選取“井字棋博弈程序”作為教學(xué)案例貫穿整個教學(xué)過程。

2 井字棋簡介

井字棋（英文名稱Tic-Tac-Toe）是與五子棋游戲規(guī)則類似的一種棋類游戲，棋盤是3×3的格子；在行棋過程中，首先形成“連三”的一方獲勝。如圖1所示，圖1中黑方獲勝?？梢姡制逡部梢苑Q為“三子棋”。源于人們對五子棋的認(rèn)知，棋盤很小且規(guī)則簡單的井字棋會給學(xué)生一種熟悉而親近的感覺，能激發(fā)學(xué)生的熱情和好奇心，也能樹立學(xué)生深入學(xué)習(xí)的自信心，為教學(xué)活動創(chuàng)造了良好的開端?！芭＝瞧濉笔橇硗庖环N規(guī)則簡單的中國民間游戲[9]，有不少學(xué)者使用牛角棋作為博弈程序的學(xué)術(shù)研究載體[10-11]。

井字棋和牛角棋都屬于規(guī)則簡單的游戲，一些學(xué)者選擇后者作為學(xué)術(shù)研究載體可能有其獨特的考量，不過從教學(xué)的角度看，選取井字棋作為教學(xué)素材更有優(yōu)勢。井字棋的棋盤相對更顯規(guī)則，用于繪制界面的程序開發(fā)工作量較小，而且井字棋的棋盤較小，為概念的圖形化表示提供了更加便利的條件，這些是筆者選擇井字棋而不是牛角棋作為教學(xué)案例的一個重要原因。

事實上，井字棋與五子棋、六子棋等棋類游戲一樣，都屬于連珠棋（英文名叫k-in-a-row），文獻[12]對連珠棋進行了統(tǒng)一的描述和游戲公平性的證明?？梢姡@些棋種存在很大的共性，井字棋博弈程序在多個方面（如程序的框架、界面的繪制、搜索算法等）可以為其他規(guī)則更復(fù)雜的連珠棋種所借用。這樣，學(xué)生可以根據(jù)個人的興趣能夠較容易地擴展到其他棋種，教師的教學(xué)投入則容易體現(xiàn)事半功倍的效果，較好地符合了“從個別到一般，再到個別”的認(rèn)知規(guī)律，這是筆者選擇井字棋作為貫穿式教學(xué)案例的主要原因。

3 井字棋案例的實施

圖1 井字棋的例子：機器執(zhí)黑勝

井字棋案例是基于VC++6.0和MFC開發(fā)的完整源程序，其可執(zhí)行程序的運行界面如圖1所示。案例的實施過程是整個教學(xué)過程的主線，將授課內(nèi)容分層次、分模塊地和源程序?qū)?yīng)起來，學(xué)生隨時可以看到理論和概念在源程序中的具體實現(xiàn)。授課內(nèi)容主要劃分為以下6個模塊。

3.1 VC++面向?qū)ο蟮闹饕卣骱喗?/h3>

介紹類的封裝和繼承特性以及基于事件驅(qū)動的程序設(shè)計理念在VC++6.0中實現(xiàn)，教學(xué)目的是填補學(xué)生“面向?qū)ο蟪绦蛟O(shè)計”有關(guān)概念的空白。

案例中定義CGame類，用以封裝著法搜索模塊的數(shù)據(jù)和函數(shù)。在數(shù)據(jù)方面，CGame類定義常量、棋盤等；在函數(shù)方面，定義局面評估函數(shù)、展開博弈樹的遞歸函數(shù)等。

CGame類定義的主體內(nèi)容如下：

通過對比分析，引導(dǎo)學(xué)生能夠理解CGame類在應(yīng)用程序中的作用和地位以及與應(yīng)用程序向?qū)傻钠渌鸐FC類之間的關(guān)系；要求學(xué)生掌握添加事件處理（信息響應(yīng)）函數(shù)OnLButtonDown的方法。

3.2 井字棋源程序的框架分析

框架分析能夠使學(xué)生從宏觀上把握博弈程序的邏輯，防止陷入局部的不易理解的細(xì)節(jié)，影響學(xué)生的興趣和信心。

框架分析以“事件驅(qū)動”為主線，沿著從“人方點擊鼠標(biāo)左鍵落下棋子”到“機器給出著法更新棋盤”這個線路，理順關(guān)鍵函數(shù)之間的調(diào)用關(guān)系。

表1列出了案例中關(guān)鍵函數(shù)的名稱、功能和來源，這些函數(shù)構(gòu)造了博弈程序的框架。

在表1中，前4個函數(shù)按照順序構(gòu)成了主調(diào)和被調(diào)關(guān)系，即OnLButtonDown→GetBestPoi nt→MinSearch ? MaxSearch。其中的MinSearch和MaxSearch是核心函數(shù)，因為這兩個函數(shù)是博弈樹的主要構(gòu)造者（參見3.4），采用“?”符號表示二者特殊的互相調(diào)用的關(guān)系，即遞歸調(diào)用關(guān)系。

在關(guān)鍵函數(shù)之間的調(diào)用關(guān)系理順之后，教師重點講解OnLButtonDown函數(shù)和OnDraw函數(shù)，因為前者處理了輸入問題，后者處理了輸出問題，都直觀地對應(yīng)于用戶的界面操作，易于理解。

表1 案例中程序框架的關(guān)鍵函數(shù)

3.3 局面的評估

局面的評估，就是站在機方的角度，依據(jù)計分標(biāo)準(zhǔn)對雙方盤面分別進行量化的評價，由GameState成員函數(shù)完成。原則上，局面的評估要以線型的評估為基礎(chǔ)，即只有確定了線型估值，才能夠進行局面估值[13]。為了簡化局面估值，突出教學(xué)重點，案例直接依據(jù)局面的特性進行局面估值。局面特性共有4個方面（7種取值）：①如果當(dāng)前局面存在連三，則給出勝負(fù)的判定，此時局面的估值為極值±100；當(dāng)機方擁有連三時為+100，當(dāng)人方擁有連三時為-100；②當(dāng)不存在上述的情況時，如果當(dāng)前局面某方擁有2個連二，則局面的估值為±50；③在不存在上述的情況時，如果棋盤存在空位（可以落子的地方），則局面的估值為±1；④如果棋盤不存在可以落子的空位，則局面的估值為0。

由于局面估值的取值范圍也是博弈樹結(jié)點的取值范圍，所以，博弈樹結(jié)點的取值v也是此7種值之一，即v∈{±100，±50，±1，0}。

3.4 博弈樹的展開

博弈樹是依據(jù)極大極小值算法展開的。這部分內(nèi)容是課程的核心內(nèi)容，但比較抽象，因此在授課方法和內(nèi)容設(shè)計都遵循變抽象為形象、變復(fù)雜為簡單的原則。按照這樣的原則，對搜索算法的講解進行了兩方面的設(shè)計。

（1）將構(gòu)造博弈樹的遞歸函數(shù)由1個“負(fù)極大值”函數(shù)分解為2個函數(shù)，MaxSearch和MinSearch。雖然采用負(fù)極大值算法具有源碼簡潔等優(yōu)點，但學(xué)生很難理解；將該函數(shù)分解為2個函數(shù)，極大值和極小值的求解步驟更加明顯；在對博弈樹進行剪枝操作時，對剪枝的具體實現(xiàn)以及剪枝的效果也易于觀察和理解（剪枝的實現(xiàn)參見3.5的內(nèi)容）。事實上，對“負(fù)極大值”函數(shù)的拆分，并不影響程序的執(zhí)行效率[14]。

（2）博弈樹結(jié)點的圖像化表示。在繪制極大極小值算法的博弈樹結(jié)點時，大多數(shù)的參考資料采用數(shù)值的形式來表示博弈樹結(jié)點，學(xué)生很難將這樣的一個數(shù)值和一個實際局面對應(yīng)起來，為理解該算法的原理增加了難度，但以圖像作為結(jié)點來描繪博弈樹，則形象很多。圖3用圖像表示博弈樹的例子，展示在當(dāng)前局面下，機器如何依據(jù)極大極小值算法從ABC三種著法中判斷出最佳著法。在圖2中，每個圖像代表博弈樹的一個結(jié)點，也代表一個局面。有向線段表示結(jié)點的父子關(guān)系（即主調(diào)函數(shù)和被調(diào)函數(shù)的關(guān)系）；圖像下面是局面的名稱和局面估值；除了根結(jié)點之外，局面的名稱以英文字母（D～P）命名，這樣的字母順序表達了博弈樹結(jié)點動態(tài)構(gòu)造和釋放的順序，也表達了算法深度優(yōu)先的特征。

圖2 基于極大極小值的博弈樹示意圖

在案例中，形如圖2的博弈樹的最大深度不會超過8，原因是當(dāng)機方執(zhí)黑先行時，第1手棋不必搜索，直接在棋盤中央落子即可；在第3手時，最多需要在7個空位中搜索，即最大深度為7；當(dāng)人方執(zhí)黑先行時，機方的第1手棋最多需要在8個空位中搜索，即最大深度為8。

3.5 博弈樹的剪枝

剪枝，就是將最佳著法保留在博弈樹中的前提下，忽略掉沒有意義的博弈樹結(jié)點，縮小博弈樹的規(guī)模，以提高程序執(zhí)行效率的搜索算法。應(yīng)用于極大極小值的剪枝算法被稱為Alpha-Beta剪枝。

圖2共有4層結(jié)點，即第1、2、3、4層，父結(jié)點從子結(jié)點中獲取值的大小遵循如下的規(guī)則：當(dāng)父結(jié)點為奇數(shù)層時，應(yīng)獲取所有子結(jié)點中的極大值（即局部最大值）；當(dāng)父結(jié)點為偶數(shù)層時，應(yīng)獲取所有子結(jié)點中的極小值（即局部最小值）。

根據(jù)上述規(guī)則，圖2中的F和G兩個結(jié)點是應(yīng)該被剪掉的：D處于偶數(shù)層，應(yīng)該獲取E和F中的最小值；在D的所有子結(jié)點中，E是首先被構(gòu)造和求解的；由于E的值為-100（即負(fù)無窮大），為全局最小值，則F的值不可能小于E的值，所以，F(xiàn)這個結(jié)點就沒有構(gòu)造的必要；不構(gòu)造F，結(jié)點G就不存在了。

圖2表達的剪枝效率較低，實際授課時可以挑選像圖3那樣剪枝效率較高的局面展示給學(xué)生。圖3的A圖表示，當(dāng)把程序設(shè)置為“人方先手”且“不實施剪枝操作”時，機方搜索了一棵具有18 512個結(jié)點的博弈樹，最終選取棋盤中心點作為最佳著法；圖3的B圖表示，當(dāng)把程序設(shè)置為“人方先手”且“實施剪枝操作”時，機方搜索了一棵只有5 457個結(jié)點的博弈樹，仍然選取棋盤中心點作為最佳著法。對比圖3（A）和圖4（B）圖可見，實施Alpha-Beta剪枝后，博弈樹的結(jié)點數(shù)量大約減少了2/3。

圖3 是否實施Alpha-Beta剪枝的效果對比

另外，Alpha-Beta算法的剪枝效率與結(jié)點的排列順序有關(guān)。例如，對于圖3中的E和F兩個結(jié)點，如果F先于E構(gòu)造，則F和G兩個結(jié)點不會被剪掉，剪枝效率變低。這樣的問題可以引導(dǎo)學(xué)生加以關(guān)注和討論。

3.6 案例的擴展

案例的擴展，就是在井字棋框架的基礎(chǔ)之上，增加其他新技術(shù)實現(xiàn)新功能，目的是讓學(xué)生不要把視野僅僅局限到案例源程序上，而是從具有一定高度的視角看待案例，理解案例潛在的可擴展性。由于擴展的內(nèi)容有較多選擇，所以應(yīng)根據(jù)課時的長度做適當(dāng)選擇。例如，可以介紹哈希散列表技術(shù)，用以實現(xiàn)對局面的比較以及已知棋譜的使用；可以介紹挑戰(zhàn)性更強的六子棋的行棋規(guī)則以及六子棋中常用的局面評估方法；可以修改GetBestPoint函數(shù)，用蒙特卡洛算法取代極大極小值算法來進行著法的評價，等。

3.7 教學(xué)實踐效果

從學(xué)生評價以及完成的作業(yè)（包括當(dāng)堂作業(yè)和大作業(yè)）質(zhì)量看，教學(xué)效果良好。選修該課程的一部分學(xué)生參加了機器博弈校級比賽并取得了良好的成績。表2為近3年校內(nèi)機器博弈比賽獲獎并且選修了該課程的學(xué)生人數(shù)統(tǒng)計。

表2 選修計算機博弈基礎(chǔ)的部分學(xué)生在校賽中獲獎人數(shù)統(tǒng)計

4 結(jié) 語

沈陽航空航天大學(xué)從2011年開始，以機器博弈為基點，以課程改革為手段，在培養(yǎng)大學(xué)生人工智能素養(yǎng)方面做了一些實際工作并取得了一定的成績[15]，為新工科的建設(shè)提供了支撐，其中開設(shè)的計算機博弈基礎(chǔ)課程是教學(xué)改革的一個重要方面。筆者在最近幾次的計算機博弈基礎(chǔ)課程的授課中，選擇井字棋博弈程序作為貫穿式教學(xué)案例，收到了較好的教學(xué)效果，為學(xué)生參加機器博弈類課外科技活動提供了一定的技術(shù)支持。