實踐 | 手把手教你開發三子棋AI

ApacheCN 優質AI博文推薦專案正式啟動

優質AI博文推薦

每日從從所有投稿博文中精選兩篇，在ApacheCN全公眾平臺推送。

投稿須知

接受

個人學習博文，論文解讀，打比賽心

得等AI相關文章投稿。

投稿時請新建Issues，按以下格式進行填寫：

博文地址：是否為個人原創：

投稿推薦語：

原作者資訊（選填）：作者暱稱，原始釋出平臺，聯絡方式

投稿地址：

https：//github。com/apachecn/awesome-AI-blog-post

本期給大家帶來由

Jeff-Tian

（jeff。tian@outlook。com）

小哥哥帶來的

《手把手教你開發三子棋AI》

試玩三子棋地址：

https：//tictactoe。js。org

一、摘要：

二、三子棋

三、遊戲介面編寫

四、人工智慧

五、機器學習

1

、定義

2

、設計

2.1

、選擇訓練經驗

2.2

、選擇目標函式

2.3

、選擇目標函式的表示

2.4

、選擇函式逼近演算法

六、應用程式架構

1

．域名：tictactoe.js.org

2.

系統型別：純靜態網站

2.1 ReactJs

2.2 Ant Design

3.

原始碼

3.1

目標函式的表示

3.2

檢查棋盤的邊

3.3

函式逼近演算法

4. CI/CD

：

七、評估以及後續工作：

簡化

複雜化

趣味性

八、參考文獻：

一、摘要：

2016

年 3 月，AlphaGo【1】擊敗世界圍棋冠軍李世石，使得人工智慧引起人們的廣泛討論。如今，人工智慧創業潮不斷湧現，這個話題不僅活躍於科技教育界，甚至進入了街頭巷尾，成為了人們的日常談資。

各種人工智慧框架的出現，也大大降低了人工智慧程式設計的門檻。比如 tensorflow 不僅開源，還提供了一個線上訓練人工神經網路的介面：https：//playground。tensorflow。org【2、3】。這使得開發人員可以利用各種強大的工具，給自己的應用賦能，讓傳統的應用程式變得“聰明”。

透過使用這些工具，開發人員不需要理解人工智慧的根本原理，知其然而不知其所以然。即如果需要從 0 開始，編寫具有智慧特性的程式，往往不知道如何下手。原因是這些框架本身是為了解決實際的應用問題而產生，並不是用來學習人工智慧的知識和思想的。

所以本文嘗試透過一個實際的例子（

https：//tictactoe。js。org/

），展示人工智慧程式開發的一般步驟。出於演示目的，本文選擇了三子棋（tic-tac-toe）這個最簡單的棋類遊戲來舉例。簡化，也是學習根本原理的通用方法，透過簡化的問題和模型排除不必要的干擾，讓人看清原理。在掌握了原理之後，即可推而廣之，解決更復雜的問題。

本文展示的一般步驟，不僅可以應用於棋類遊戲開發，而且是所有人工智慧程式開發的一般步驟。當然，複雜的程式步驟會更繁雜，但仍然會以本文列出的一般步驟為主幹。

二、三子棋

三子棋，起源於古希臘【4】，也稱為井字棋，或者圈圈叉叉。因為棋盤是一個九宮格，或者說像漢字中的“井”字，所以得名井字棋；又因為一個玩家透過打圈，另一個玩家打叉來玩這個遊戲，所以得名為圈圈叉叉。本文稱其為三子棋，是因為在這個遊戲中，當玩家的棋子能夠三子成線時，即為獲勝，故名三子棋。

圖 2。1：三子棋盤

圖 2。2：一個 X 方取勝的例子

三子棋是最簡單的棋類遊戲，它只有 765 個可能局面，26830 個棋局。如果要實現一個人機對戰的三子棋遊戲，由於棋局的可能性並不多，完全可以使用窮舉法做到。但是這樣做，程式碼量並不少，而且對人類玩家來說，由於機器對手每次策略都一樣，所以趣味性不高。

本文展示的人工智慧程式的編寫，不僅大大縮減了程式碼量（因為不需要儲存取勝策略），而且由於程式的學習是一個動態過程，對於人類玩家的同樣的走法，程式可能會給予不同的迴應，這樣下棋的趣味性更高。

三、遊戲介面編寫

遊戲介面不涉及人工智慧部分，但卻是玩家必須要透過介面來與程式互動。本文選擇了網頁版介面，無需安裝即可使用，而且便於傳播。

要編寫優秀的網頁介面，有很多優秀的開發框架可供選擇。本文采用了 ReactJs【5】，不僅因為它是目前最優秀的前端框架之一，而且它的官方教程恰好提供了一個詳細的編寫井字棋遊戲的教程【6】。

按照教程編寫出來的介面是一個可以執行的井字棋遊戲，可以由兩人交替走子：

https：//codepen。io/gaearon/pen/gWWZgR？editors=0010

。

圖3。1：按照 ReactJs 官方教程編寫的遊戲介面

四、人工智慧

據維基百科【7】解釋，人工智慧（英語：Artificial Intelligence，縮寫為AI）也稱為機器智慧，指由人制造出來的機器所表現出來有智慧。通常人工智慧是指透過普通計算機程式來呈現人類智慧的技術。

本文聚焦在這個定義的後一段，即透過編寫一個普通的計算機程式來呈現人類智慧。

人工智慧的研究課題非常之多，其中之一是機器學習，本文所展示的程式，更精確地說，是一個機器學習程式。本文所要展示的程式開發步驟，也即機器學習程式的開發步驟。

五、機器學習

機器學習是人工智慧的一個分支【8】。人工智慧的研究歷史有著一條從以“推理”為重點，到以“知識”為重點，再到以“學習”為重點的自然、清晰的脈絡 。顯然，機器學習是實現人工智慧的一個途徑，即以機器學習為手段解決人工智慧中的問題。

1

、定義

通常有以下幾種定義：

機器學習是一門人工智慧的科學，該領域的主要研究物件是人工智慧，特別是如何在經驗學習中改善具體演算法的效能。

機器學習是對能透過經驗自動改進的計算機演算法的研究。

機器學習是用資料或以往的經驗，以最佳化計算機程式的效能標準。

一種更精確的教科書式的定義如下：

對於某類任務 T 和效能度量 P，如果一個計算機程式在 T 上以 P 衡量的效能隨著經驗 E 而自我改善，那麼我們稱這個計算機程式在從經驗 E 中學習。

比如具體到我們的井字棋遊戲，就是：對於學習下井字棋的計算機程式，它可以透過和自己下棋獲取經驗；它的任務是參與井字棋對弈；它的效能用它贏棋的能力來衡量。

圖 5。1：三子棋學習問題的抽象

2

、設計

那麼如何來設計一個機器學習系統呢？一般有以下幾個步驟：

圖 5。2：設計學習系統的一般步驟

2.1

、選擇訓練經驗

本程式選擇了兩種訓練經驗：

產生隨機合法的棋局：在本程式對外公開訪問之前，可以透過讓程式與一些隨機產生的合法棋局對弈，產生初級的智慧，然後再公開給使用者訪問。這樣比直接公開要好一些，因為直接公開，程式完全不具有智慧，會讓使用者失去興趣。

和玩家對弈：在程式對外公開後，隨著玩家與程式的對弈，程式繼續不斷調整自身內部的評估函式（目標函式）引數的權值。玩家在與程式對弈的過程中，可能會感覺程式越來越聰明，從而更加激發玩家的好奇與興趣。

當然，除了以上兩種訓練經驗，還可以選擇其他的訓練經驗，比如一個使用固定評估函式走子的棋局產生器。

2.2

、選擇目標函式

目標函式，也就是機器學習程式的評估函式，對程式的效能表現進行打分。大致地說，這個目標函式應該對好的表現打高分，對差的表現打低分。

具體到本三子棋程式，對於集合 B 中的任意棋局狀態 b，我們定義如下目標函式 V（b）：

如果 b 是一最終的勝局，那麼 V（b） =

π/2

；

如果 b 是一最終的負局，那麼 V（b） =

-π/2

；

如果 b 是一最終的和局，那麼 V（b） = 0；

如果 b 不是最終棋局，那麼 V（b） = V（b‘），其中 b’ 是從 b 開始雙方都採取最優對弈後可達到的終局。（這裡出現一個遞迴邏輯， 所以需要後面的一步：函式逼近演算法來計算這個函式值）

當然，你也可以選擇其他的目標函式，比如，如果是最終勝局，令 V（b）=100；如果是負局，令 V（b）=-100 等。如果是和局，令 V（b）=0 顯然是一個合適的選擇。那麼這裡為什麼選擇了勝局時，令 V（b）=

π/2

呢？

因為這裡做了一個假設：即棋局的表現，在達到終局前，是介於勝局與負局之間的，如果用一個連續函式來表示這種趨勢（向勝局或者向負局的趨勢），應該是如下圖所示的一個曲線：

圖 2。2：arctan 函式圖形（紅色曲線）

這很自然讓人聯想到 y=arctan（x） 這個反三角函式，而這個函式正好介於 -

π/2

與 π/2

之間，故採用它們分別做為負局和勝局的表現得分，這樣就省去了做函式變換的麻煩。

2.3

、選擇目標函式的表示

有了目標函式，如何將它表示出來，即如何將它表示成一系列自變數的函式形式呢？

首先，目標函式是受棋局的狀態所影響的，所以自變數肯定是棋局上的狀態。其次，不同的狀態對於目標函式的影響是不同的，即不同的自變數，其權重不同。

如何找到合適的自變數，以及將目標函式表示成這些自變數的什麼函式，沒有一定的標準。但是一旦確定了這個目標函式的表示，那麼機器學習的過程，就轉化成了一個函式調參的過程。

透過改變不同自變數的權重，將目標函式計算出來的值逼近給定的實驗資料（即經驗集合），即是機器學習的過程。

本學習程式把 V（b） 表示成對一個線性函式求反正切值（線性函式單調，但是無界。透過求反正切值，使得這個函式值滿足了我們的有界性要求）：V（b）=arctan（w0+w1x1+w2x2+w3x3+w4x4+w5x5），其中w0 到 w5 為數字係數，或者叫做權，由學習演算法來選擇。而x1 到 x5 為棋盤狀態值，權 w1 到 w5 決定了不同的棋盤特徵的相對重要性，而權 w0 為一個附加的棋盤狀態值常量。

再次強調，自變數的選擇並沒有一定的標準，這裡選擇的 5 個自變數，是經過一些不同的實驗之後，最後總結出來的可以達到很好效果但是數量又比較少的一個變數組合。有沒有可能選擇其他的變數組合來得到更好的效果，還值得進一步探討。

這裡的 5 個變數分別是：

x1

：棋盤上受到對方威脅的邊數（一共 8 條邊，如果一條邊上出現兩顆敵子並且沒有我方棋子，那麼這條邊形成了對我方的一個威脅），取值範圍是 0 到 8。

圖 2。3。1：

棋盤上對我方形成的一個威脅示意圖

x2

：壞交叉點數：如果兩條邊上各有一顆敵方棋子而沒有我方棋子，並且這兩條邊交叉，那麼這個交叉點稱為壞交叉點（不好的交叉點）。

圖 2。3。2：壞交叉點示意圖

x3

：機會邊數：如果有一條邊有我方兩顆棋子而沒有敵方棋子，那這條邊是一條機會邊。

圖 2。3。3：

機會邊示意圖

x4

：佔中優勢：如果中間格子是我方棋子，那麼我方佔據優勢，x4 記為 1；如果是空，則記為 0；如果是敵方棋子，則記為 -1。對三子棋稍作了解就會知道，中間格子的棋子更容易與其他格子裡的棋子連成一條線，故誰先佔據中間格子，誰在一定程度上就佔據了一些優勢。

圖 2。3。4：佔中示意圖

x5

：我方的贏面機會帶來的威脅數。如果我方某邊上已有兩顆棋子，另一格子為空。如果我方佔據這個空格就能贏，但是現在輪到對方走。如果對方佔據這個空格，不僅阻礙了我方贏棋的可能，還同時讓兩條邊以上擁有敵方的兩顆棋子而另外一格是空的這種情況，那麼下一步不管我方落子在哪格，對方總能贏，這就帶來了威脅。

圖 2。3。5：

我方贏面機會所帶來的潛在威脅

x1

到 x4 都很簡單直觀，而x5 則是高手走法，透過前面的鋪墊，在某一步，落一子而給對方造成兩條邊上的威脅。而在下一步中對方最多隻能防一條邊。

回顧：針對這個具體的三子棋學習任務，我們把它轉換成了一個學習目標函式表示中的係數（或說引數）w0 到 w5 的值的問題（調參問題）。

圖 2。3。6：問題的轉換

2.4

、選擇函式逼近演算法

這個過程也被稱作估計訓練值，就是選擇權重值的過程。我們可以從任意的權重值開始，然後不斷調整權值，直到找到一個比較好的權重值組合。

本程式採用了 LMS 最小均方法，對於每一個訓練樣例，它能把權值向減小這個訓練資料誤差的方向略為調整。

詳細地說，LMS 權值更新法則是這樣的【9】：

對於 每一個訓練樣例

六、應用程式架構

1

．域名：tictactoe.js.org

採用了 js。org 的二級域名 tictactoe，即三子棋的英文名稱。Js。org 提供免費的二級域名，尤其樂意為 js 應用提供服務，而本應用正好是一個純js 應用。

2.

系統型別：純靜態網站

託管在 Github Pages 上。Github Pages 非常適合託管靜態網站，而且是免費的。

2.1 ReactJs

第三章已經說明，本程式的遊戲介面基於 ReactJs 的經典教程。ReactJs是一款用來構建使用者介面的優秀的JavaScript庫，是由Facebook出品的開源框架。

2.2 Ant Design

Ant Design

是阿里推出的開源React元件庫，包含了豐富的介面互動元件以及優美的設計風格。

3.

原始碼

完整的原始碼託管在 github 上：

https：//github。com/Jeff-Tian/tic-tac-toe-ai

。這裡重點介紹一下前面幾章介紹的機器學習的關鍵步驟程式碼：

3.1

目標函式的表示

程式裡使用目標函式來對棋局打分：

getBoardScore

：

function

（bitmap， weights） {

weights = weights || Strategy。

getInitialWeights

（）；

let

{

lost

，

win

，

factors

} = Strategy。

getBoardStatus

（bitmap）；

if

（

lost

） {

return

{

factors

：

factors

，

namedFactors

： Strategy。

getNamedStrategy

（

factors

），

total

： -

Math

。

PI

/

2

}

}

if

（

win

） {

return

{

factors

：

factors

，

namedFactors

： Strategy。

getNamedStrategy

（

factors

），

total

：

Math

。

PI

/

2

}

}

let

score

=

Math

。

atan

（

factors

。

map

（（s， i） => s * weights［i］）。

reduce

（（prev， next） => prev + next，

0

））；

return

{

factors

：

factors

，

namedFactors

： Strategy。

getNamedStrategy

（

factors

），

total

：

score

}；

}

求出的分數即 score，注意這個分數是x1到x5與權重的加權和再求arctan，從而讓分數單調有界。2。3詳細地說明了x1到x5這5個自變數，在程式碼裡，將它們放在了一個factors數組裡。這個factors 是由

getBoardStatus

來計算的，這裡抽象成一個方法，好處是，如果要換自變數，那麼這個打分的函式不用改變。如前所述，自變數的挑選，並不是確定的。

3.2

檢查棋盤的邊

上面的程式碼中有一個重要的函式：

getBoardStatus

，它的核心是去檢查棋盤的邊，得到棋盤的狀態。在程式裡，棋盤被表示成一個長度為9的陣列，每個元素要麼是1、要麼是0、要麼是-1。分別表示當前宮格里是我方的棋子，為空以及敵方的棋子。棋盤一共8條邊，檢查棋盤的邊的函式是這樣的：

function

checkSides

（bitmap） {

let

d

=

0

；

let

dead

=

0

；

let

w

=

0

；

let

c

=

0

；

for

（

let

i

=

0

；

i

<

sides

。

length

；

i

++） {

let

side

= bitmap。

filter

（（_， j） =>

sides

［

i

］。

indexOf

（j） >=

0

）；

let

negatives

=

side

。

filter

（b => b === -

1

）；

let

zeros

=

side

。

filter

（b => b ===

0

）；

let

ones

=

side

。

filter

（b => b ===

1

）；

if

（

negatives

。

length

===

2

&&

zeros

。

length

===

1

） {

d

++；

}

if

（

negatives

。

length

===

3

） {

dead

++；

}

if

（

ones

。

length

===

3

） {

w

++；

}

if

（

ones

。

length

===

2

&&

zeros

。

length

===

1

） {

c

++；

}

}

return

{

danger

：

d

，

lost

：

dead

，

chance

：

c

，

win

：

w

}；

}

3.3

函式逼近演算法

函式逼近的過程，也即學習的過程。這裡表現為一個名字叫learn（）的函式。這個函式接收兩個引數，即上一棋局，以及當前棋局。注意之前2。2 提到，函式逼近演算法，是不斷用當前的權值，對新出現的棋局打分來估計前一棋局的分數。所以這個函式會使用同樣的權重對前後兩個棋局打分，並透過這個分數的差值，採用LMS方法來調整權重：

learn

（lastSquares， currentSquares） {

if

（！lastSquares） {

return

；

}

let

estimatedLastScore

= Judger。

getBoardScore

（lastSquares，

this

。

weights

）；

let

actualScore

= Judger。

getBoardScore

（currentSquares，

this

。

weights

）；

let

diff

=

actualScore

。

total

-

estimatedLastScore

。

total

；

for

（

let

i

=

0

；

i

<

estimatedLastScore

。

factors

。

length

；

i

++） {

this

。

weights

［

i

］ =

this

。

weights

［

i

］ +

0。1

*

diff

*

estimatedLastScore

。

factors

［

i

］；

}

}

4. CI/CD

：

採用了 Travis CI系統，只需要提交程式碼，Travis 會自動執行測試、分析程式碼。

然後釋出至Github pages。

七、評估以及後續工作：

本程式很好地演示了一個最簡單的人工智慧程式的編寫步驟，不需要任何複雜的AI框架，可以從0開始編寫。不過，仍然存在最佳化的可能性，比如：

簡化

對於目標函式的表示，有沒有更好的或者更簡潔的表示形式呢？是否可以進一步減少自變數的數量？

複雜化

除了簡化，還可以朝另一個方向發展，即迭代更復雜的遊戲。比如，擴充套件棋盤，或者擴充套件成五子棋等等。

趣味性

從遊戲趣味性上擴充套件，可以考慮增加一個使用者系統，開發出排行榜的功能，讓純靜態網站變得動態等。

八、參考文獻：

【1】

https：//zh。wikipedia。org/wiki/AlphaGo

【2】

https：//www。tensorflow。org/

【3】

https：//playground。tensorflow。org

【4】

https：//zh。wikipedia。org/wiki/%E4%BA%95%E5%AD%97%E6%A3%8B

【5】

https：//zh-hans。reactjs。org/

【6】

https：//zh-hans。reactjs。org/tutorial/tutorial。html

【7】

https：//zh。m。wikipedia。org/zh-cn/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD

【8】

https：//zh。m。wikipedia。org/wiki/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0

【9】［美］米歇爾（Mitchell， T。M。）。機器學習［M］。 曾華軍等譯。北京：機械工業出版社，2003。