貫穿式案例教學法在機器博弈課程中的實踐

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

（沈陽航空航天大學 工程訓練中心，遼寧 沈陽 110136）

0 引 言

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

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

1 計算機博弈基礎課程簡介

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

在授課時發現，選課的學生絕大多數是理工科的低年級學生，其中大一學生的人數比例有時高達85%。較多的零基礎學生以及較短的學時，給授課工作帶來一定的難度。如果通過提高選課條件的方式來限制選課學生的數量，則學生的受益面變窄，對機器博弈課外活動感興趣的學生不能及時得到技術支持，背離了課程的目標。可見，采用傳統的授課方式很難解決實際的教學條件和教學目標之間的矛盾。

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

2 井字棋簡介

井字棋（英文名稱Tic-Tac-Toe）是與五子棋游戲規則類似的一種棋類游戲，棋盤是3×3的格子；在行棋過程中，首先形成“連三”的一方獲勝。如圖1所示，圖1中黑方獲勝。可見，井字棋也可以稱為“三子棋”。源于人們對五子棋的認知，棋盤很小且規則簡單的井字棋會給學生一種熟悉而親近的感覺，能激發學生的熱情和好奇心，也能樹立學生深入學習的自信心，為教學活動創造了良好的開端。“牛角棋”是另外一種規則簡單的中國民間游戲[9]，有不少學者使用牛角棋作為博弈程序的學術研究載體[10-11]。

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

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

3 井字棋案例的實施

圖1 井字棋的例子：機器執黑勝

井字棋案例是基于VC++6.0和MFC開發的完整源程序，其可執行程序的運行界面如圖1所示。案例的實施過程是整個教學過程的主線，將授課內容分層次、分模塊地和源程序對應起來，學生隨時可以看到理論和概念在源程序中的具體實現。授課內容主要劃分為以下6個模塊。

3.1 VC++面向對象的主要特征簡介

介紹類的封裝和繼承特性以及基于事件驅動的程序設計理念在VC++6.0中實現，教學目的是填補學生“面向對象程序設計”有關概念的空白。

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

CGame類定義的主體內容如下：

通過對比分析，引導學生能夠理解CGame類在應用程序中的作用和地位以及與應用程序向導所生成的其他MFC類之間的關系；要求學生掌握添加事件處理（信息響應）函數OnLButtonDown的方法。

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

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

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

表1列出了案例中關鍵函數的名稱、功能和來源，這些函數構造了博弈程序的框架。

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

在關鍵函數之間的調用關系理順之后，教師重點講解OnLButtonDown函數和OnDraw函數，因為前者處理了輸入問題，后者處理了輸出問題，都直觀地對應于用戶的界面操作，易于理解。

表1 案例中程序框架的關鍵函數

3.3 局面的評估

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

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

3.4 博弈樹的展開

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

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

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

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

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

3.5 博弈樹的剪枝

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

圖2共有4層結點，即第1、2、3、4層，父結點從子結點中獲取值的大小遵循如下的規則：當父結點為奇數層時，應獲取所有子結點中的極大值（即局部最大值）；當父結點為偶數層時，應獲取所有子結點中的極小值（即局部最小值）。

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

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

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

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

3.6 案例的擴展

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

3.7 教學實踐效果

從學生評價以及完成的作業（包括當堂作業和大作業）質量看，教學效果良好。選修該課程的一部分學生參加了機器博弈校級比賽并取得了良好的成績。表2為近3年校內機器博弈比賽獲獎并且選修了該課程的學生人數統計。

表2 選修計算機博弈基礎的部分學生在校賽中獲獎人數統計

4 結 語

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