編輯語：
技術解碼欄目：是面向開發者詳細解讀晶片開放社群（OCC）上關于處理器、晶片、基礎軟體平台、內建開發環境及應用開發平台的相關技術，友善開發者學習及快速上手，提升開發效率。
近日，來自複旦大學的王松、陳布同學，基于wujian100 SoC開發了五子棋AI裝置，并通過人機對戰，充分驗證了五子棋AI的智能性。
（五子棋AI裝置人機對戰過程示範）
本周【技術解碼】要為大家介紹的是，王松、陳布同學設計開發五子棋AI裝置的實戰過程。本文将概述該案例的開發過程，講解基于博弈樹的五子棋AI算法原理。有關五子棋AI算法的硬體實作、軟硬體協同仿真等具體的開發内容，将在後續的《揭秘五子棋AI裝置的煉成：wujian100 SoC助力人機對弈（下）》中更新。
作者介紹
王松：複旦大學微電子學院2020級直博生
陳布：複旦大學微電子學院2019級碩士研究所學生
一、前言
wujian100 SoC是平頭哥基于RISC-V架構打造的開源的晶片設計平台，該平台是一款超低功耗的MCU平台，也是一款基于安全可信系統架構與CSI标準軟體接口，支援從硬體到軟體到系統的全棧靈活開發。在此平台基礎上，可以快速地進行IP核拓展并進行系統前端仿真，并對拓展的硬體設計部分進行功能驗證。
二、開發過程概述
① 設計一個實作五子棋AI核心算法的IP核并将其內建到wujian100 SoC上。
② 将整個設計下載下傳到FPGA開發闆後便構成了一個“擅長下五子棋”的智能裝置。
③ 在與FPGA開發闆進行通信的計算機端，利用Python設計五子棋遊戲的控制程式及人機互動界面。同時，再基于Python實作一個五子棋AI的軟體程式，是以可以讓硬體端的五子棋AI和軟體端的五子棋AI進行對弈。
④ 在此基礎上，建構相應腳本讓wujian100平台上的硬體五子棋AI與“QQ遊戲-五子棋”中的廣大線上玩家進行對弈，進而充分驗證五子棋AI的棋藝水準。
三、基于博弈樹的五子棋AI算法簡介
五子棋無禁手的基本遊戲規則是，雙方棋手分别使用黑白兩色的棋子，下在棋盤豎線與橫線的交叉點上，先形成“五子連線”者獲勝。五子棋AI算法的目的就是根據目前的棋局形勢尋找到一個最佳的落子點，使得我方的勝算最大。
為了判斷到底何處落子才是勝算最大，往往需要多往後推算幾步，包括“猜測”對方落子，這種搜尋方式的拓撲圖就是一顆巨大的博弈樹，如下圖所示：
3.1 極大極小值搜尋算法
為了判斷落點是不是最佳的，通常都是采用對落點位置進行打分的方法，因而需要建立一套評分機制：對己方越有利，分值越高；對敵方越有利，分值越低（負分）。
在博弈樹的搜尋過程中
- 将己方走棋的層稱為 MAX 層，為了保證己方的利益最大化，選下一層得分最高的分支；
- 将敵方走棋的層稱為 MIN 層，為了保證敵方的利益最大化，選下一層得分最低的分支。
若目前節點是黑方回合，則下一步尋找對黑方而言的最佳落點，再下一步尋找對白方而言最佳的落點，依次周遊下去，即所謂的極大極小值搜尋算法。
從上圖中來看，每一個節點就是一個棋局。
目前處于0号節點，深度是0，黑方回合。搜尋樹向後推算三步，一共得到8種可能的棋局（7～14号節點），利用估值函數對這8個節點進行估計得分（紅色标注）。
節點3是黑方回合，黑方會選擇對自己最有利的走法，此時黑方會走到節點8，同理，節點4的黑方會走到節點9，節點5的黑方會走到節點11，節點6的黑方會走到節點14。
節點1的白方，會選擇對自己最有利的走法，該走法使得黑方得分最低，是以節點1的白方會走到節點3，同理，節點2的白方會走到節點5。
節點0的黑方會選擇對自己最有利的走法，黑方會走到節點1。是以，處于目前棋局的黑方，會落子形成節點1的棋局，該落子點就是目前的最佳落子點。
3.2 Alpha-Beta 剪枝算法
通常來講，一場對局的步數（對應搜尋樹的深度）很容易達到50步及以上（對應搜尋樹的層數），每一步還都有多種可能的落子位置（對應每一層搜尋樹的節點），如果把每一步都周遊到位，搜尋量将是巨大的，其時間代價将難以承受。為此，通常采用Alpha-Beta剪枝算法來去除一些明顯不适合的節點，以減少運算量。
分别考慮目前節點是 MAX 節點和 MIN 節點的情況，約定函數 f(node) 表示節點 node 的估值得分，有：
- 目前節點是 MAX 節點：目前節點記為 M，節點 M 有一個 MIN 子節點，記為 m1，且 f(m1) = α，則必有 f(M) ≥ α。這是因為節點 M 是 MAX 節點，會選擇所有子節點中估值最大的那個節點，是以 MAX 節點不會選擇估值比 α 還小的子節點，而隻會選擇估值比 α 還大的子節點，是以得到 f(M) ≥ α，該值稱為 “MAX 節點的 α 值”，α 值刻畫了 MAX 節點的下界；
- 目前節點是 MIN 節點：目前節點記為 m，節點 m 有一個 MAX 子節點，記為 M1，且 f(M1) = β,則必有 f(m) ≤ β，這是因為節點 m 是 MIN 節點，會選擇所有子節點中估值最小的那個節點，是以 MIN 節點不會選擇估值比 β 還大的子節點，而隻會選擇估值比 β 還小的子節點，是以得到 f(m) ≤ β，該值稱為 “MIN 節點的 β 值”，β 值刻畫了 MIN 節點的上界。
一般情況的 α-β 剪枝規則（已在上圖中标注）：
- α 剪枝：目前節點是 MAX 節點，其 α 值大于等于其父節點的 β 值，則可以将以目前節點為根節點的子樹剪枝，該剪枝稱為 “α 剪枝”；
- β 剪枝：目前節點是 MIN 節點，其 β 值小于等于其父節點的 α 值，則可以将以目前節點為根節點的子樹剪枝，該剪枝稱為 “β 剪枝”。
有關于極大極小值搜尋算法和Alpha-Beta剪枝算法的詳細内容可以參考以下文章：1) 基于博弈樹的五子棋 AI 算法及其 C++ 實作2) 五子棋AI算法第二篇-極大極小值搜尋算法3) 五子棋AI算法（三）
3.3 估值函數
從上文的叙述中可以看出，估值函數的好壞直接影響了決策樹的搜尋過程和路徑判斷，是以估值函數的定義至關重要。關于五子棋的估值函數，不同學者的定義往往大不相同，這也導緻決策樹的效率和正确率都有較大偏差。
在此，我們參考了以下文章中的估值算法：基于C的α-β剪枝算法實作的AI五子棋遊戲
對于一個二維的棋面，五子棋的勝負隻取決于一條線上的棋子，根據這一特征，考慮将二維的棋面轉換為一維的，按照四個方向來将棋盤轉換為 15 × 6 個長度不超過 15 的一維向量，參考下圖：
評估每個線狀态，将每個線狀态的評分進行彙總，當做棋面評分：
evaluateValue = ∑ evaluateLine(lineState[i])
接下來所要做的就是評價每一條線狀态，根據五子棋的規則，可以很容易窮舉出各種可能出現的基本棋型，首先為這些基本棋型進行識别和評價， 得到如下圖所示的靜态估值表：
并且統計每個線狀态中出現了多少種下面所述的棋型，并據此得出評價值。考慮到一些實際情況，如果搜尋到第四層，總共需要搜尋
224+224 × 223+224 × 223 × 222+224 × 223 × 222 × 221 = 2,461,884,544
個狀态節點。
搜尋如此多的狀态節點的開銷是十分可觀的，是以，提高效率的方式就在于如何減少需要搜尋的狀态節點。
- 利用 α - β 剪枝算法對博弈樹剪枝 ；
- 每次搜尋僅搜尋落子點周圍 3 × 3 格範圍記憶體在棋子的位置，這樣可以避免搜尋一些明顯無用的節點；
- 避免對必勝/負局面搜尋，當搜尋過程中出現了必勝/負局面的時候直接傳回不再搜尋；
- 規劃搜尋順序 ，很多有價值的落子點更靠近棋盤中央，如果從棋盤中央向外搜尋的話，則能夠提高 α - β 剪枝的效率。