趙才榮，傅佳悅，衛(wèi)志華，丁志軍，苗奪謙

(同濟大學電子與信息工程學院計算機科學與技術系，上海 201804)

0 引 言

隨著計算機科學領域的發(fā)展，人工智能成為了迅速發(fā)展的最新興的科學與工程領域之一。2016年3月15日，Google旗下Deep Mind團隊開發(fā)出的圍棋程序AlphaGo[1]以4∶1擊敗了韓國頂尖棋手李世乭，這一事件拉開了人工智能熱潮的序幕[2]。次年5月，同樣由英國的Deep Mind團隊開發(fā)的升級版人工智能圍棋程序AlphaGo Master[3]擊敗了當時的人類頂尖棋手柯潔，從此人工智能在棋類領域顯露出了無與倫比的威力。這種包含計算機程序的博弈稱為計算機博弈，也可稱為機器博弈。在博弈中，計算機程序能夠像人一樣進行判斷和推理，以此做出理性的決策。

棋類游戲是計算機博弈的一個標準性問題，人們對棋類人工智能博弈原理與決策機理的研究，可應用于其他諸多領域中，例如軍事演練中的最佳作戰(zhàn)策略、形式化數(shù)學證明問題、物流問題等。棋類對弈過程中展現(xiàn)出來的邏輯思維、形象思維和靈感思維完美地覆蓋了計算思維能力涉及的各個方面[4]。學生通過對棋類計算機博弈的學習和研究，可以提高計算機程序設計能力、動手實踐能力，同時可以提高計算思維能力和自主創(chuàng)新能力。

為促進學生對人工智能博弈算法的學習、實現(xiàn)棋類博弈程序間的對弈，設計一個通過統(tǒng)一的交互協(xié)議進行通訊的棋類博弈平臺是有必要的。在該平臺上，博弈程序間可以通過比賽的形式比較程序的優(yōu)劣。

為此，很多文獻探討了棋類人工智能博弈平臺的設計。文獻[5]設計并實現(xiàn)了五子棋機器博弈教學實驗平臺，支持學生將獨立開發(fā)的算法策略載入平臺，實現(xiàn)在線博弈與交流；文獻[6]設計開發(fā)了一種能夠與人進行五子棋實時對弈的程序，但主要集中在博弈程序的設計，且不支持博弈程序間的對弈。文獻[7-8]實現(xiàn)了網頁圍棋游戲的開發(fā)，但不支持博弈程序間的對弈，且界面不夠美觀；象棋巫師網站[9]提供了支持象棋博弈程序對弈的軟件，但其通信協(xié)議較為復雜，加大了學生設計博弈程序的實踐難度；孔德帥等人[10]實現(xiàn)了一種基于機器視覺的中國象棋人機博弈系統(tǒng)設計，主要通過攝像頭采集棋盤圖像，調用系統(tǒng)內置博弈算法計算走法，再采用機械臂實現(xiàn)棋子移動。

可以看到，現(xiàn)有博弈平臺一般只針對某種特定的棋類，例如五子棋或圍棋，且基本上不具備博弈程序間對弈的功能。主要原因在于這些平臺沒有提供確定的通信協(xié)議以及博弈程序對戰(zhàn)入口，因此博弈程序設計者無法成功地將人工智能博弈程序接入平臺中。

針對上述工作的問題和不足，本文提出并設計了一種新的教學輔助平臺：面向棋類博弈智能體設計的教學輔助平臺。該平臺可以支持多種棋類智能體的博弈，達到教學輔助作用，便于學生自主、創(chuàng)新學習，提高教學效率。本文的主要工作包括：

1)規(guī)定了不同棋類的通信協(xié)議，遵循簡單性、開放性和可擴展性原則。能夠有效輔助學生實現(xiàn)博弈程序與平臺的交互。

2)設計實現(xiàn)了棋類博弈平臺，該平臺可以支持五子棋、中國象棋、國際象棋、圍棋這4類棋的人人對弈、博弈程序間對弈以及人與博弈程序間的博弈。

1 博弈智能體的設計

本研究的目的是輔助人工智能博弈類算法的學習，即促進學生自主、創(chuàng)新地開發(fā)棋類博弈程序。棋類博弈程序的設計和開發(fā)旨在讓學生將所學人工智能理論知識應用于實踐中，以提高解決實際問題的能力。為保證學生所編程序能夠在本教學輔助平臺上成功運行，并進行博弈比賽，需要統(tǒng)一規(guī)定明確的引擎(即博弈程序)與平臺通信協(xié)議。確定引擎通信協(xié)議后，引擎和平臺之間的交互即可通過標準的指令和反饋進行。下文給出中國象棋的引擎協(xié)議。其他棋類的協(xié)議也可在本平臺中查閱。

1.1 通信協(xié)議制定

為了降低學生處理博弈程序交互的難度，更多地關注于博弈算法本身和相關人工智能算法的優(yōu)化改進，本平臺的中國象棋引擎協(xié)議是基于中國象棋通用引擎協(xié)議[11]的簡化版本。采用FEN格式串來表示象棋局面的記錄規(guī)范。

引擎和界面通信的指令和反饋如下：

(1)ucci。

引導狀態(tài)的指令。引擎啟動后，平臺給引擎發(fā)送的第一條指令，通知引擎現(xiàn)在使用的協(xié)議是UCCI。

(2)ucciok。

引導狀態(tài)的反饋，此后引擎進入空閑狀態(tài)。

(3)isready。

空閑狀態(tài)和思考狀態(tài)的指令。檢測引擎是否處于就緒狀態(tài)，其反饋總是readyok，該指令僅僅用來檢測引擎是否能夠正常接收指令。

(4)readyok。

空閑狀態(tài)和思考狀態(tài)的反饋。表明引擎處于就緒狀態(tài)(可正常接收指令)。

(5)position {fen | startpos} [moves<后續(xù)著法列表>]。

空閑狀態(tài)的指令。設置“內置棋盤”的局面，用fen來指定FEN格式串，moves后面跟的是隨后走過的著法，例如：“position fen rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR r--01 moves h2e2 h9g7 startpos”表示開始局面，它等價于“fen rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/ 1C5C1/9/RNBAKABNR r--01”。

(6)go time。

空閑狀態(tài)的指令，此后引擎進入思考狀態(tài)。讓引擎根據(jù)position指令設定的棋盤來思考，milliseconds為限定時間。若超出限定時間，引擎未給出反饋，則判定失敗。

(7)bestmove<最佳著法>。

思考狀態(tài)的反饋，此后引擎返回空閑狀態(tài)。顯示思考結果，即引擎認為在當前局面下的最佳著法。

(8)nobestmove。

思考狀態(tài)的反饋，引擎主動認輸。

(9)quit。

空閑狀態(tài)的指令。讓引擎退出運轉。

(10)bye。

接收到quit指令后的反饋。引擎完成了退出運轉前的準備工作，通知界面，引擎將在瞬間正常退出運轉。界面收到該指令后，即可關閉輸入輸出通道。

1.2 博弈算法

計算機博弈包括博弈過程建模、搜索算法、棋局評估等過程[12]。在實踐過程中，博弈程序從平臺處獲取當前局面的狀態(tài)(例如FEN格式串)，隨后博弈程序啟動搜索算法，并給出其認定的最優(yōu)走子方案返回給平臺，平臺根據(jù)走子方案實現(xiàn)前端棋子的移動。在設計博弈程序時，搜索算法作為關鍵技術，直接決定了程序的性能。

常用的博弈算法是極小極大搜索算法。對弈雙方都非常理智，但所要達到的目的相反，所以在考慮著法的時候都盡量想讓棋局朝著自己的方面轉化。在同一棵博弈樹的不同的層面上就要有不同的選擇標準，即一方總是希望下一步是兒子節(jié)點中取值最大者，而另一方恰恰相反，希望在下一步是兒子節(jié)點中取值最小者。Alpha-Beta剪枝算法用于裁剪博弈樹中對搜索結果不影響的樹枝，以提高運算速度。

此外，在設計博弈程序時，可以針對不同的棋類特性對基礎算法進行改進優(yōu)化。文獻[13]針對五子棋模型提出了一系列的改進著棋方法，即利用局部搜索、多線程技術、淺層最優(yōu)算法優(yōu)化剪枝算法等。文獻[14]通過知識庫的構建和專家開局走法的引入有效解決了中國象棋重復局面導致的時間、硬件資源浪費的問題。文獻[15]在傳統(tǒng)Alpha-Beta剪枝的基礎上，通過引入迭代深化和歷史表等輔助剪枝手段，有效減少了搜索節(jié)點數(shù)目，提高了剪枝效率。文獻[16]對圍棋博弈進行深入研究，提出了結合深度學習與蒙特卡洛樹搜索算法的快速走子網絡。文獻[17]結合時間差分算法和反向傳播神經網絡，設計了一種局面估值算法，可以實現(xiàn)估值函數(shù)參數(shù)的自動調整，提升程序的博弈水平。

本平臺支持用戶上傳智能體程序與平臺內置棋類智能體程序對弈。在此，介紹本平臺中中國象棋內置智能體程序采用的相關博弈算法。首先是開局庫[18]的設置，由于開局局面落子情況較為簡單，單純的搜索效果不如利用人類一直以來的下棋經驗所總結出的好。核心搜索算法為基于Alpha-Beta剪枝的極小極大搜索算法[19]，為了產生更多的Alpha-Beta截斷，采用多種啟發(fā)搜索算法[20-22]優(yōu)化走法搜索順序，包含置換表啟發(fā)、靜態(tài)評估啟發(fā)、殺手啟發(fā)、歷史表啟發(fā)。在對吃子著法進行排序時，根據(jù)MVV/LVA的原則進行：優(yōu)先搜索“最有價值的受害者和最沒價值的攻擊者”。在搜索博弈樹的過程中，由于對戰(zhàn)時間的不確定性，程序采用迭代加深搜索算法。算法中采用了置換表技術[23]，其原理是采用哈希表將已搜索的節(jié)點的局面特征、估值和其他相關信息記錄下來，如果待搜索的節(jié)點的局面特征在哈希表中已經有記錄，在滿足相關條件時，就可以直接利用置換表中的結果。

棋類博弈程序的設計和開發(fā)可以結合人工智能多方面的知識，內容豐富，變化無窮。學生在程序設計過程中不僅可以提高編程能力、實踐能力，還能有豐富的空間自主探索，提高科研創(chuàng)新能力。

2 博弈平臺的設計

本平臺提供了對多種棋類(五子棋、國際象棋、圍棋、中國象棋)進行對弈的支持，用戶注冊后可使用該平臺實現(xiàn)不同棋類的人人對弈、人機對弈和機機對弈。平臺的總體架構如圖1所示，包含3個主要模塊：主頁模塊、用戶模塊、博弈模塊。

圖1 平臺總體架構

2.1 主頁模塊

主頁模塊分為：首頁、聯(lián)系、通信協(xié)議。通信協(xié)議中包含4類棋采用的具體通信方式，以輔助用戶順利實現(xiàn)博弈程序與平臺的交互。主頁提供了各個棋類比賽的入口，用戶可進一步創(chuàng)建對局并設置對局參數(shù)，例如棋手可設置為計算機棋手、人類棋手或系統(tǒng)預置AI(計算機棋手為博弈智能體，需用戶自行上傳)。在主頁中也可進入用戶模塊進行相關操作。

2.2 用戶模塊

用戶模塊包含的功能：用戶注冊、用戶登錄、密碼修改、個人信息修改以及歷史對局查看。在用戶注冊與登錄過程中，加入了用戶名和密碼的表單驗證，使得注冊用戶僅能擁有合法用戶名，用戶郵箱必須惟一。用戶登錄后，平臺可以記錄其用戶行為，包括勝負記錄、積分詳情、對局信息，在個人信息中可以一一查看。通過設置用戶身份來管理用戶，如普通用戶和管理員用戶，管理員能夠加入任意棋局，實時查看比賽進程。

2.3 博弈模塊

作為本平臺的重點，博弈模塊包含3個部分：查看對局、創(chuàng)建對局和積分排名。

1)查看對局。

針對每種棋類，查看對局頁面將從數(shù)據(jù)庫的數(shù)據(jù)表中，根據(jù)對應棋種的標志號，讀取棋局的比賽記錄，加載于網頁表單之中。用戶可瀏覽所有的對局房間，對于未開始棋局，可加入房間參與對局。

2)創(chuàng)建對局。

創(chuàng)建對局前，用戶可以設置棋局采用的引擎協(xié)議、棋手模式、比賽步時、比賽局時。進入棋局對弈界面后，通過記錄用戶發(fā)送的請求號，系統(tǒng)將同一對弈棋局中的用戶捆綁在同一個房間內(包括被設置為實時觀戰(zhàn)的管理員用戶)，后端應用引擎通信協(xié)議，對接用戶與博弈智能體的著子操作，前后端通過SocketIO服務，在同一個房間內，進行異步數(shù)據(jù)通信，并在頁面端應用JS作出動畫響應。

在進行棋局對弈時，系統(tǒng)根據(jù)有無棋類博弈智能體程序的參與，選擇不同的運作方式，對弈流程如圖2所示。

圖2 棋局對弈流程圖

若無博弈智能體程序參與對弈，即無需處理上傳文件有效性的驗證，也無需啟動后臺線程。系統(tǒng)僅需要利用SocketIO異步通信機制，根據(jù)引擎通信協(xié)議，同步用戶雙方的棋盤著子進程。有棋類博弈智能體程序參與的情況下，需要啟動博弈智能體程序作為后臺線程，當輪到博弈智能體程序著子的時候，需要將一方的棋盤狀態(tài)以引擎通信協(xié)議規(guī)定的格式，標準輸入輸出到博弈智能體程序中，待其運行搜索算法，在有限時間內做出決策，并以規(guī)定格式返回決策結果，系統(tǒng)再將結果廣播給同一棋局中的所有用戶，并在前端界面利用JS棋盤腳本予以呈現(xiàn)。

3)積分排名。

積分排名頁面直接從數(shù)據(jù)庫的用戶表中讀取用戶的積分信息，對其進行排名并加載。在每次對局結束后，平臺根據(jù)棋局種類、勝負情況，計算用戶積分變化并更新數(shù)據(jù)庫中積分值。

3 博弈平臺實現(xiàn)

3.1 數(shù)據(jù)庫的設計與實現(xiàn)

在平臺的實現(xiàn)中，數(shù)據(jù)庫是支撐平臺運作的關鍵。由于平臺支持用戶注冊、用戶比賽數(shù)據(jù)記錄、用戶比賽數(shù)據(jù)查閱等功能，所以需要為此設計不同的數(shù)據(jù)庫表，并降低數(shù)據(jù)之間的冗余，具體的數(shù)據(jù)庫表結構如圖3所示。

圖3 數(shù)據(jù)庫類圖

Chess類為平臺所支持的棋的種類；Game類是每個棋局所具有的屬性；Role類是用戶所在的類別，管理著其所擁有的權限；User類是每個用戶所具有的屬性。在平臺不斷改進完善中，根據(jù)具體需求，可以更新數(shù)據(jù)庫類結構，添加新的屬性。

數(shù)據(jù)庫軟件選用SQLite，系統(tǒng)與數(shù)據(jù)庫軟件的交互主要依賴于Python平臺下的ORM框架SQLAlchemy，即能夠以Python語言面向對象的編程方式，等價執(zhí)行SQL語句對數(shù)據(jù)庫的操作。

3.2 平臺實現(xiàn)

本平臺采用客戶服務器結構，服務器端基于Python語言Flask框架、SQLite數(shù)據(jù)庫進行開發(fā)，客戶端采用基于Html、CSS、JavaScript的Bootstrap框架。表1給出了平臺開發(fā)過程中所依賴的Python庫及其相關功能。

表1 Python后端依賴

棋類博弈程序間的自動對弈是本平臺的核心內容之一。根據(jù)通信協(xié)議，棋類博弈程序采用標準的輸入輸出流，因此系統(tǒng)采用Python標準庫中subprocess模塊實現(xiàn)與子程序之間進行交互的功能。

4 平臺使用評估

4.1 平臺展示

本系統(tǒng)運行環(huán)境為Apache服務器。瀏覽器訪問平臺網址，首先進入的是平臺主頁。主頁上擺放著通往各個頁面的鏈接，通過點擊導航欄右上角進行用戶登錄或注冊，已登錄用戶可以查看到4大棋種創(chuàng)建對局的按鈕。首頁的整體布局如圖4所示。

點擊任意棋類創(chuàng)建對局，進入設置對局參數(shù)的中間頁面，用戶設置好引擎協(xié)議、棋手模式、單方步時、局時等參數(shù)以后，進入棋局頁面，處于待準備狀態(tài)。

圖5為用戶上傳棋類程序參與對局的操作步驟。首先從主頁開始創(chuàng)建對局，然后設置棋局為計算機棋手對決人類棋手，進入等待頁面。被設定為計算機棋手的一方，需要點擊“點擊上傳文件”按鈕，進行智能體程序路徑的查找并確認，確認以后點擊“上傳”按鈕，棋類程序會自動在系統(tǒng)后臺加載完成。

圖4 平臺首頁

圖5 用戶上傳棋類程序

圖6為智能體雙方準備就緒以后，輪流著子的過程。與此同時，管理員用戶也可以加入二人對局觀戰(zhàn)。

圖6 智能體間對局

4.2 教學使用情況

本棋類博弈教學輔助平臺已于2018年起應用于本科課程《人工智能原理與應用》的實踐教學中。

在算法學習過程中，學生可自主登錄平臺，上傳編寫好的智能體程序，并與其他用戶進行對弈，促進對博弈算法的理解改進。實踐環(huán)節(jié)成績評定采用瑞士制分組對抗，由云蛇比賽編排軟件給出對局名單以及先后手，學生根據(jù)初始編排結果進入平臺創(chuàng)建對局，上傳智能體程序實現(xiàn)對弈。平臺具有積分計算功能，每局比賽獲勝方可獲得2個積分，平局雙方獲得1個積分，敗北隊伍獲得0個積分。首輪比賽結束后，將積分結果輸入編排軟件中，得到下一輪對局名單，重復操作直至完成預定輪數(shù)。圖7給出了中國象棋用戶積分排名情況，用戶積分記錄中包含得分棋局編號，總積分為用戶所有棋局得分之和。通過比賽最終積分值，可獲取實踐智能體程序得分。

圖7 棋類積分排名

最終實踐成績由實驗報告和智能體程序得分組成，分別占40%和60%。實踐成績占課程總成績的比例為40%。實踐內容的安排，旨在讓學生能夠靈活掌握并運用博弈算法，棋類博弈教學輔助平臺能夠有效促進該過程的實施。

4.3 實踐效果

以往學生在博弈算法相關實驗中，能夠掌握基礎的極小極大搜索算法、Alpha-Beta剪枝算法。對于復雜場景下的博弈算法設計，例如不完美的實時決策，僅限于理解，未實際動手實踐。

在本博弈平臺開發(fā)前，人工智能專業(yè)課程博弈算法實驗一般基于井字棋或五子棋設計博弈智能體。智能體與人對弈進行測試，或是在離線軟件上與智能體對弈測試。學生無法隨時開展線上對局博弈。由于井字棋、五子棋的博弈樹復雜度不是非常高，影響學生對博弈算法的深入探索及自主創(chuàng)新。

開發(fā)本棋類博弈輔助平臺后，人工智能課程博弈算法實驗可設計五子棋、中國象棋、國際象棋以及圍棋的智能體程序，內容豐富有趣。針對更復雜的博弈場景和博弈樹，研究不限于極小極大搜索算法和Alpha-Beta剪枝，需要對博弈算法進行優(yōu)化改進。例如，針對中國象棋等更復雜的走子情況和更大規(guī)模的博弈樹，程序如何優(yōu)化著法順序、提高剪枝效率；針對平臺給定任意行棋步時，程序如何判斷搜索深度、設計評估函數(shù)。更復雜的博弈場景給予學生更多的空間探索新的博弈算法并優(yōu)化改進。棋類博弈輔助平臺的設計，允許學生在線上開展對局，通過競爭的方式提高學生學習的主動性，鼓勵學生在競爭中不斷創(chuàng)新以提高智能體程序的性能。因此，棋類博弈輔助平臺的開發(fā)具有實用創(chuàng)新性。

本文以2019學年《人工智能原理與應用》課程的一個教學班為例介紹具體的實踐教學成果。班級共有85名學生，分為21組(小組成員為4人)，以小組為單位開展智能體程序的設計。不同小組所設計的智能體性能有區(qū)別的原因主要在于所設計的博弈算法不同，程序應對不同局面的落子反饋不同。

通過2個學期的改革方案實施嘗試，選修了本門課程的本科生基本都具備了問題抽象化、解決實際問題的能力，95%以上的學生表示對課堂教授的博弈算法有了更深刻的理解和更熟練的運用，80%以上的學生表示通過實驗過程掌握了許多新知識，例如開局庫和殘局庫的使用、評估函數(shù)的設計、置換表技術等。

5 結束語

本文滿足面向人工智能博弈領域算法輔助教學的需求，在定義了嚴格的通信協(xié)議的基礎上，設計并實現(xiàn)了教學輔助平臺，該平臺能夠支持五子棋、中國象棋、國際象棋和圍棋的3種博弈模式：人人對弈、人與博弈智能體對弈、以及博弈智能體之間的對弈。目前，該平臺已經用于同濟大學課程教學中，平臺的設計有效增加了學生的學習興趣，提升了課程的教學效果，起到了很好的教學輔助作用，更有利地促進了對學生自主創(chuàng)新能力的培養(yǎng)，提升了理論與實踐結合的動手能力。