本篇文章給大家介紹一下使用Node.js如何實(shí)現(xiàn)蒙特卡洛樹搜索，并用蒙特卡洛樹搜索（MCTS）算法來玩一個(gè)給定規(guī)則的游戲，下面一起來看看吧！

本文假設(shè)讀者具備一定的計(jì)算機(jī)科學(xué)知識(shí)，尤其是數(shù)據(jù)結(jié)構(gòu)中關(guān)于樹結(jié)構(gòu)的工作原理，還需要具備 JavaScript（ES6+）的中級(jí)知識(shí)。推薦學(xué)習(xí)：《nodejs 教程》】

本文的目標(biāo)很簡(jiǎn)單：

實(shí)現(xiàn)蒙特卡洛樹搜索（MCTS）算法來玩一個(gè)給定規(guī)則的游戲。

這整個(gè)過程將是指導(dǎo)性和實(shí)踐性的，并且忽略掉性能優(yōu)化的部分。我將會(huì)對(duì)鏈接的代碼片段進(jìn)行簡(jiǎn)要解釋，希望你能跟上我的腳步并花一些時(shí)間理解代碼中復(fù)雜難懂的部分。

讓我們開始吧！

創(chuàng)建骨架文件

在 game.js 文件中：

/** 代表游戲棋盤的類。 */ class Game {    /** 生成并返回游戲的初始狀態(tài)。 */   start() {     // TODO     return state   }    /** 返回當(dāng)前玩家在給定狀態(tài)下的合法移動(dòng)。 */   legalPlays(state) {     // TODO     return plays   }    /** 將給定的狀態(tài)提前并返回。 */   nextState(state, move) {     // TODO     return newState   }    /** 返回游戲的勝利者。 */   winner(state) {     // TODO     return winner   } }  module.exports = Game

在 monte-carlo.js 文件中：

/** 表示蒙特卡洛樹搜索的類。 */ class MonteCarlo {    /** 從給定的狀態(tài)中，反復(fù)運(yùn)行 MCTS 來建立統(tǒng)計(jì)數(shù)據(jù)。 */   runSearch(state, timeout) {     // TODO   }    /** 從現(xiàn)有的統(tǒng)計(jì)數(shù)據(jù)中獲取最佳的移動(dòng)。 */   bestPlay(state) {     // TODO     // return play   } }  module.exports = MonteCarlo

在 index.js 文件中：

const Game = require('./game.js') const MonteCarlo = require('./monte-carlo.js')  let game = new Game() let mcts = new MonteCarlo(game)  let state = game.start() let winner = game.winner(state)  // 從初始狀態(tài)開始輪流進(jìn)行游戲，直到有玩家勝利為止 while (winner === null) {   mcts.runSearch(state, 1)   let play = mcts.bestPlay(state)   state = game.nextState(state, play)   winner = game.winner(state) }  console.log(winner)

先花點(diǎn)時(shí)間梳理一下代碼吧。在腦海中搭建一個(gè)子版塊的腳手架，然后嘗試去明白一下這個(gè)東西。這是一個(gè)思維上的檢查點(diǎn)，先確保你明白它是如何組合在一起的，如果感到無法理解，就請(qǐng)留言吧，讓我看看我能為你做些什么。

找到合適的游戲

在開發(fā)一個(gè) MCTS 游戲智能體的背景下，我們可以把我們真正的程序看作是實(shí)現(xiàn) MCTS 框架的代碼，也就是 monte-carlo.js 文件中的代碼。在 game.js 文件中的游戲?qū)Ｓ么a是可以互換并且即插即用的，它是我們使用 MCTS 框架的接口。我們主要是想做 MCTS 背后的大腦，它應(yīng)該真的能在任何游戲上運(yùn)行。畢竟，我們感興趣的是一般性的游戲玩法。

不過，為了測(cè)試我們的 MCTS 框架，我們需要選擇一個(gè)特定的游戲，并使用該游戲運(yùn)行我們的框架。我們希望看到 MCTS 框架在每個(gè)步驟中都做出對(duì)我們選擇的游戲有意義的決策。

做一個(gè)井字游戲（Tic-Tac-Toe）怎么樣呢？幾乎所有的游戲入門教學(xué)都會(huì)用到它，它還有著一些非常令我們滿意的特性：

• 大家之前都玩過。
• 它的規(guī)則很簡(jiǎn)單，可以用算法實(shí)現(xiàn)。
• 它具有一份確定的完善的信息。
• 它是一款對(duì)抗性的雙人游戲。
• 狀態(tài)空間很簡(jiǎn)單，可以在心理上進(jìn)行建模。
• 狀態(tài)空間的復(fù)雜程度足以證明算法的強(qiáng)大。

但是，井字游戲真的很無聊，不是嗎？另外，你大概已經(jīng)知道井字游戲的最佳策略，這就失去了一些吸引力。有這么多游戲可以選擇，我們?cè)龠x一個(gè)：四子棋（Connect Four）怎么樣？除了可能比井字游戲享有更低的人氣外，它不僅有上面所列舉的特性，還可能讓玩家不那么容易地建立四子棋狀態(tài)空間的心理模型。

在我們的實(shí)現(xiàn)中，我們將使用 Hasbro（孩之寶：美國著名玩具公司）的尺寸和規(guī)則，即是 6 行 7 列，其中垂直、水平和對(duì)角線棋子數(shù)相連為 4 就算勝利。棋子會(huì)從上方落下，并借助重力落在自底向上數(shù)的第一個(gè)空槽。

不過在我們繼續(xù)講述之前，要先說明一下。如果你有信心，你可以自己去實(shí)現(xiàn)任何你想要的游戲，只要它遵守給定的游戲 API。只是當(dāng)你搞砸了，不能用的時(shí)候不要來抱怨。請(qǐng)記住，像國際象棋和圍棋這樣的游戲太復(fù)雜了，即使是 MCTS 也無法（有效地）獨(dú)自解決；谷歌在 AlphaGo 中通過向 MCTS 添加有效的機(jī)器學(xué)習(xí)策略來解決這個(gè)問題。如果你想玩自己的游戲，你可以跳過接下來的兩個(gè)部分。

實(shí)現(xiàn)四子棋游戲

現(xiàn)在，直接將 game.js 改名為 game-c4.js，將類改名為 Game_C4。同時(shí)，創(chuàng)建兩個(gè)新類：State_C4 在 state-c4.js 中表示游戲狀態(tài)，Play_C4 在 play-c4.js 中表示狀態(tài)轉(zhuǎn)換。

雖然這不是本文的主要內(nèi)容，但是你自己會(huì)如何構(gòu)建呢？

• 你會(huì)如何在 State_C4 中表示一個(gè)游戲狀態(tài)呢？
• 在 Play_C4 中，你將如何表示一個(gè)狀態(tài)轉(zhuǎn)換（例如一個(gè)動(dòng)作）呢？
• 你會(huì)如何把 State_C4、Play_C4 和四子棋游戲規(guī)則 —— 用冰冷的代碼放在 Game_C4 中嗎？

注意，我們需要通過骨架文件 game-c4.js 中定義的高級(jí) API 方法所要求的形式實(shí)現(xiàn)四子棋游戲。

你可以獨(dú)立思考完成或者直接使用我完成的 play-c4.js、state-c4.js 和 game-c4.js 文件。

這是一個(gè)工作量很大的活，不是嗎？至少對(duì)我來說是這樣的。這段代碼需要一些 JavaScript 知識(shí)，但應(yīng)該還是很容易讀懂的。最重要的工作在 Game_C4.winner() 中 —— 它用于在四個(gè)獨(dú)立的棋盤中建立積分系統(tǒng)，而所有的棋盤都在 checkBoards 里面。每個(gè)棋盤都有一個(gè)可能的獲勝方向（水平、垂直、左對(duì)角線或右對(duì)角線）。我們需要確保棋盤的三個(gè)面比實(shí)際棋盤大，方便為算法提供零填充。

我相信還有更好的方法。Game.winner() 的運(yùn)行時(shí)性能并不是很好，具體來說，在大 O 表示法中，它是 O(rows * cols)，所以性能并不是很好。通過在狀態(tài)對(duì)象中存儲(chǔ) checkBoards，并且只更新 checkBoards 中最后改變狀態(tài)的單元格（也會(huì)包含在狀態(tài)對(duì)象中），可以大幅改善運(yùn)行時(shí)性能，也許你以后可以嘗試這個(gè)優(yōu)化方法。

運(yùn)行四子棋游戲

此時(shí)，我們將通過模擬 1000 次四子棋游戲來測(cè)試 Game_C4。點(diǎn)擊獲取 test-game-c4.js 文件。

在終端上運(yùn)行 node test-game-c4.js。在一個(gè)相對(duì)現(xiàn)代的處理器和最新版本的 Node.js 上，運(yùn)行 1000 次迭代應(yīng)該會(huì)在一秒鐘內(nèi)完成：

$ node test-game-c4.js  [ [ 0, 0, 0, 0, 0, 0, 2 ],   [ 0, 2, 0, 0, 0, 0, 2 ],   [ 0, 1, 0, 1, 2, 1, 2 ],   [ 0, 2, 1, 2, 2, 1, 2 ],   [ 0, 1, 1, 2, 1, 2, 1 ],   [ 0, 1, 2, 1, 1, 2, 1 ] ] 0.549

二號(hào)棋手在內(nèi)部用 -1 表示，這是為了方便 game-c4.js 的計(jì)算。用 2 代替 -1 的那段代碼只是為了對(duì)齊棋盤輸出結(jié)果。為了簡(jiǎn)便起見，程序只輸出了一塊棋盤，但它確實(shí)玩了另外的 999 次四子棋游戲。在單個(gè)棋盤輸出之后，它應(yīng)該輸出一號(hào)棋手在所有 1000 盤棋中獲勝的分?jǐn)?shù) —— 預(yù)計(jì)數(shù)值在 55% 左右，因?yàn)榈谝粋€(gè)棋手有先發(fā)優(yōu)勢(shì)。

分析現(xiàn)在的狀況

我們已經(jīng)實(shí)現(xiàn)一個(gè)帶有 API 方法并且可以運(yùn)行的游戲，這些 API 方法可以與 State 對(duì)象表示的游戲狀態(tài)協(xié)同運(yùn)行。我們現(xiàn)在的狀況如何？

目標(biāo)：實(shí)現(xiàn)蒙特卡洛樹搜索（MCTS）算法來玩一個(gè)給定規(guī)則的游戲。

當(dāng)然，我們還沒有達(dá)到目的。剛才我們完成了一件非常重要的事情：讓它設(shè)立一個(gè)切實(shí)的目標(biāo)，并組成測(cè)試我們實(shí)現(xiàn) MCTS 的核心模塊。現(xiàn)在，我們進(jìn)入正題。

實(shí)現(xiàn)蒙特卡洛樹搜索

在這里，我將按照 MCTS 詳解中類似的組織方式，我也會(huì)在一些地方用自己的話來闡明某些觀點(diǎn)。

實(shí)現(xiàn)搜索樹節(jié)點(diǎn)

為了存儲(chǔ)從這些模擬中獲得的統(tǒng)計(jì)信息，MCTS 從頭開始建立了自己的搜索樹。

現(xiàn)在請(qǐng)你回顧樹結(jié)構(gòu)知識(shí)。MCTS 是一個(gè)樹結(jié)構(gòu)搜索，因此我們需要使用樹節(jié)點(diǎn)。我們將在 monte-carlo-node.js 的 MonteCarloNode 類中實(shí)現(xiàn)這些節(jié)點(diǎn)。然后，我們將在 MonteCarlo 中使用它來構(gòu)建搜索樹。

/** 代表搜索樹中一個(gè)節(jié)點(diǎn)的類。 */ class MonteCarloNode {    constructor(parent, play, state, unexpandedPlays) {          this.play = play     this.state = state      // 蒙特卡洛的內(nèi)容     this.n_plays = 0     this.n_wins = 0      // 樹結(jié)構(gòu)的內(nèi)容     this.parent = parent     this.children = new Map()     for (let play of unexpandedPlays) {       this.children.set(play.hash(), { play: play, node: null })     }   }    ...

先再確認(rèn)一下是否能夠理解這些：

• parent 是 MonteCarloNode 父節(jié)點(diǎn)。
• play 是指從父節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所做的 Play。
• state 是指與該節(jié)點(diǎn)相關(guān)聯(lián)的游戲 State。
• unexpandedPlays 是 Plays 的一個(gè)合法數(shù)組，可以從這個(gè)節(jié)點(diǎn)進(jìn)行。
• this.children 是由 unexpandedPlays 創(chuàng)建的，是 Plays 指向子節(jié)點(diǎn) MonteCarloNodes 的一個(gè) Map 對(duì)象（不完全是，見下文）。

MonteCarloNode.children 是一個(gè)從游戲哈希到對(duì)象的映射，包含游戲?qū)ο蠛拖嚓P(guān)的子節(jié)點(diǎn)。我們?cè)谶@里包含了游戲?qū)ο?，以便從它們的哈希中恢?fù)游戲?qū)ο蟆?/p>

重要的是，Play 和 State 應(yīng)該提供 hash() 方法。我們將在一些地方使用這些哈希作為 JavaScript 的 Map 對(duì)象，比如在 MonteCarloNode.children 中。

請(qǐng)注意，兩個(gè) State 對(duì)象應(yīng)該被 State.hash() 認(rèn)為是不同的 —— 即使它們有相同的棋盤狀態(tài) —— 如果每個(gè)對(duì)象通過不同的下棋順序達(dá)到相同的棋盤狀態(tài)?？紤]到這一點(diǎn)，我們可以簡(jiǎn)單地讓 State.hash() 返回一個(gè)字符串化的 Play 對(duì)象的有序數(shù)組，代表為達(dá)到該狀態(tài)而下的棋。如果你獲取了我的 state-c4.js，這個(gè)已經(jīng)完成了。

現(xiàn)在我們將為 MonteCarloNode 添加成員方法。

  ...    /** 獲取對(duì)應(yīng)于給定游戲的 MonteCarloNode。 */   childNode(play) {     // TODO     // 返回 MonteCarloNode   }    /** 展開指定的 child play，并返回新的 child node。*/   expand(play, childState, unexpandedPlays) {     // TODO     // 返回 MonteCarloNode   }    /** 從這個(gè)節(jié)點(diǎn) node 獲取所有合法的 play。*/   allPlays() {     // TODO     // 返回 Play[]   }    /** 從這個(gè)節(jié)點(diǎn) node 獲取所有未展開的合法 play。 */   unexpandedPlays() {     // TODO     // 返回 Play[]   }    /** 該節(jié)點(diǎn)是否完全展開。 */   isFullyExpanded() {     // TODO     // 返回 bool   }    /** 該節(jié)點(diǎn) node 在游戲樹中是否為終端，     不包括因獲勝而終止游戲。 */   isLeaf() {     // TODO     // 返回 bool   }      /** 獲取該節(jié)點(diǎn) node 的 UCB1 值。 */   getUCB1(biasParam) {     // TODO     // 返回 number   } }  module.exports = MonteCarloNode

方法可真多!

特別是，MonteCarloNode.expand() 將 MonteCarloNode.children 中未展開的空節(jié)點(diǎn)替換為實(shí)節(jié)點(diǎn)。這個(gè)方法將是四階段的 MCTS 算法中階段二：擴(kuò)展的一部分，其他方法自行理解。

通常你可以自己實(shí)現(xiàn)這些，也可以獲取完成的 monte-carlo-node.js。即使你自己做，我也建議在繼續(xù)之前對(duì)照我完成的程序進(jìn)行檢查，以確保正常運(yùn)行。

如果你剛獲取到我完成的程序，請(qǐng)快速瀏覽一下源代碼，就當(dāng)是另一個(gè)心理檢查點(diǎn)，重新梳理你的整體理解。這些都是簡(jiǎn)短的方法，你會(huì)在短時(shí)間內(nèi)看懂它們。

尤其是 MonteCarloNode.getUCB1() 幾乎是將上面的公式直接翻譯成代碼。這整個(gè)公式在上一篇文章中有詳細(xì)的解釋，再去看一下吧，這并不難理解，也是值得看的。

更新蒙特卡洛的類

目前的版本是 monte-carlo-v1.js，只是一個(gè)骨架文件。該類的第一個(gè)更新是增加 MonteCarloNode，并創(chuàng)建一個(gè)構(gòu)造函數(shù)。

const MonteCarloNode = require('./monte-carlo-node.js')  /** 表示蒙特卡洛搜索樹的類。 */ class MonteCarlo {        constructor(game, UCB1ExploreParam = 2) {     this.game = game     this.UCB1ExploreParam = UCB1ExploreParam     this.nodes = new Map() // map: State.hash() => MonteCarloNode   }    ...

MonteCarlo.nodes 允許我們獲取任何給定狀態(tài)的節(jié)點(diǎn)，這將是有用的。至于其他的成員變量，將它們與 MonteCarlo 聯(lián)系起來就很有意義了。

  ...    /** 如果給定的狀態(tài)不存在，就創(chuàng)建空節(jié)點(diǎn)。 */   makeNode(state) {     if (!this.nodes.has(state.hash())) {       let unexpandedPlays = this.game.legalPlays(state).slice()       let node = new MonteCarloNode(null, null, state, unexpandedPlays)       this.nodes.set(state.hash(), node)     }   }    ...

以上代碼讓我們可以創(chuàng)建根節(jié)點(diǎn)，還可以創(chuàng)建任意節(jié)點(diǎn)，這可能很有用。

  ...    /** 從給定的狀態(tài)，反復(fù)運(yùn)行 MCTS 來建立統(tǒng)計(jì)數(shù)據(jù)。 */   runSearch(state, timeout = 3) {      this.makeNode(state)      let end = Date.now() + timeout * 1000     while (Date.now() < end) {        let node = this.select(state)       let winner = this.game.winner(node.state)        if (node.isLeaf() === false && winner === null) {         node = this.expand(node)         winner = this.simulate(node)       }       this.backpropagate(node, winner)     }   }    ...

最后，我們來到了算法的核心部分。引用第一篇文章的內(nèi)容，以下是過程描述：

• 在第 (1) 階段，利用現(xiàn)有的信息反復(fù)選擇連續(xù)的子節(jié)點(diǎn)，直至搜索樹的末端。

• 接下來，在第 (2) 階段，通過增加一個(gè)節(jié)點(diǎn)來擴(kuò)展搜索樹。

• 然后，在第 (3) 階段，模擬運(yùn)行到最后，決定勝負(fù)。

• 最后，在第 (4) 階段，所選路徑中的所有節(jié)點(diǎn)都會(huì)用模擬游戲中獲得的新信息進(jìn)行更新。

這四個(gè)階段的算法反復(fù)運(yùn)行，直至收集到足夠的信息，產(chǎn)生一個(gè)好的移動(dòng)結(jié)果。

  ...    /** 從現(xiàn)有的統(tǒng)計(jì)數(shù)據(jù)中獲得最佳的移動(dòng)。 */   bestPlay(state) {     // TODO     // 返回 play   }    /** 第一階段：選擇。選擇直到不完全展開或葉節(jié)點(diǎn)。 */   select(state) {     // TODO     // 返回 node   }    /** 第二階段：擴(kuò)展。隨機(jī)展開一個(gè)未展開的子節(jié)點(diǎn)。 */   expand(node) {     // TODO     // 返回 childNode   }    /** 第三階段：模擬。游戲到終止?fàn)顟B(tài)，返回獲勝者。 */   simulate(node) {     // TODO     // 返回 winner   }    /** 第四階段：反向傳播。更新之前的統(tǒng)計(jì)數(shù)據(jù)。 */   backpropagate(node, winner) {     // TODO   } }

接下來講解四個(gè)階段具體的實(shí)現(xiàn)方法，我們現(xiàn)在的版本是 monte-carlo-v2.js。

實(shí)現(xiàn) MCTS 第一階段：選擇

從搜索樹的根節(jié)點(diǎn)開始，我們通過反復(fù)選擇一個(gè)合法移動(dòng)，前進(jìn)到相應(yīng)的子節(jié)點(diǎn)來向下移動(dòng)。如果一個(gè)節(jié)點(diǎn)中的一個(gè)、幾個(gè)或全部合法移動(dòng)在搜索樹中沒有對(duì)應(yīng)的節(jié)點(diǎn)，我們就停止選擇。

  ...      /** 第一階段：選擇。選擇直到不完全展開或葉節(jié)點(diǎn)。 */   select(state) {      let node = this.nodes.get(state.hash())     while(node.isFullyExpanded() && !node.isLeaf()) {        let plays = node.allPlays()       let bestPlay       let bestUCB1 = -Infinity        for (let play of plays) {         let childUCB1 = node.childNode(play)                             .getUCB1(this.UCB1ExploreParam)         if (childUCB1 > bestUCB1) {           bestPlay = play           bestUCB1 = childUCB1         }       }       node = node.childNode(bestPlay)     }     return node   }    ...

該函數(shù)通過查詢每個(gè)子節(jié)點(diǎn)的 UCB1 值，使用現(xiàn)有的 UCB1 統(tǒng)計(jì)。選擇 UCB1 值最高的子節(jié)點(diǎn)，然后對(duì)所選子節(jié)點(diǎn)的子節(jié)點(diǎn)重復(fù)這個(gè)過程，以此類推。

當(dāng)循環(huán)終止時(shí)，保證所選節(jié)點(diǎn)至少有一個(gè)未展開的子節(jié)點(diǎn)，除非該節(jié)點(diǎn)是葉子節(jié)點(diǎn)。這種情況是由調(diào)用函數(shù) MonteCarlo.runSearch() 處理的，所以我們?cè)谶@里不必?fù)?dān)心。

實(shí)現(xiàn) MCTS 第二階段：擴(kuò)展

停止選擇后，搜索樹中至少會(huì)有一個(gè)未展開的移動(dòng)。現(xiàn)在，我們隨機(jī)選擇其中的一個(gè)，然后我們創(chuàng)建該移動(dòng)對(duì)應(yīng)的子節(jié)點(diǎn)（圖中加粗）。我們將這個(gè)節(jié)點(diǎn)作為子節(jié)點(diǎn)添加到選擇階段最后選擇的節(jié)點(diǎn)上，擴(kuò)展搜索樹。節(jié)點(diǎn)中的統(tǒng)計(jì)信息初始化為 0 次模擬中的 0 次勝利。

  ...    /** 第二階段：擴(kuò)展。隨機(jī)展開一個(gè)未展開的子節(jié)點(diǎn)。 */   expand(node) {      let plays = node.unexpandedPlays()     let index = Math.floor(Math.random() * plays.length)     let play = plays[index]      let childState = this.game.nextState(node.state, play)     let childUnexpandedPlays = this.game.legalPlays(childState)     let childNode = node.expand(play, childState, childUnexpandedPlays)     this.nodes.set(childState.hash(), childNode)      return childNode   }    ...

再來看一下 MonteCarlo.runSearch()。擴(kuò)展是在檢查 if (node.isLeaf() === false && winner === null) 時(shí)完成的。很明顯，如果在游戲樹中沒有可能的子節(jié)點(diǎn) —— 例如，當(dāng)棋盤滿了的時(shí)候，是不可能進(jìn)行擴(kuò)展的。如果有贏家的話，我們也不想擴(kuò)展 —— 這就像說當(dāng)你的對(duì)手贏了的時(shí)候你應(yīng)該停止玩游戲一樣明顯。

那么如果是葉子節(jié)點(diǎn)，會(huì)發(fā)生什么呢？我們只需用在該節(jié)點(diǎn)中獲勝的人進(jìn)行反向傳播 —— 無論是玩家 1，玩家 -1，甚至是 0（平局）。同樣，如果在任何節(jié)點(diǎn)上有一個(gè)非空的贏家，我們只需跳過擴(kuò)展和模擬，并立即與該贏家（1 或 -1 或 0）進(jìn)行反向傳播。

反向傳播 0 贏家是什么意思？用 MCTS 真的可以嗎？真的可以用，后面再細(xì)講。

實(shí)現(xiàn) MCTS 第三階段：模擬

從擴(kuò)張階段新建立的節(jié)點(diǎn)開始，隨機(jī)選擇棋步，反復(fù)推進(jìn)對(duì)局狀態(tài)。這樣重復(fù)進(jìn)行，直到對(duì)局結(jié)束，出現(xiàn)贏家。在此階段不創(chuàng)建新節(jié)點(diǎn)。

  ...      /** 第三階段：模擬。游戲到終止?fàn)顟B(tài)，返回獲勝者。 */   simulate(node) {      let state = node.state     let winner = this.game.winner(state)      while (winner === null) {       let plays = this.game.legalPlays(state)       let play = plays[Math.floor(Math.random() * plays.length)]       state = this.game.nextState(state, play)       winner = this.game.winner(state)     }      return winner   }    ...

因?yàn)檫@里沒有保存任何東西，所以這主要涉及到 Game，而 MonteCarloNode 的內(nèi)容不多。

再看一下 MonteCarlo.runSearch()，模擬是在與擴(kuò)展一樣的檢查 if (node.isLeaf() === false && winner === null) 時(shí)完成的。原因是：如果這兩個(gè)條件之一成立，那么最后的贏家就是當(dāng)前節(jié)點(diǎn)的贏家，我們只是用這個(gè)贏家進(jìn)行反向傳播。

實(shí)現(xiàn) MCTS 第四階段：反轉(zhuǎn)

模擬階段結(jié)束后，所有被訪問的節(jié)點(diǎn)（圖中粗體）的統(tǒng)計(jì)數(shù)據(jù)都會(huì)被更新。每個(gè)被訪問的節(jié)點(diǎn)的模擬次數(shù)都會(huì)遞增。根據(jù)哪個(gè)玩家獲勝，其獲勝次數(shù)也可能遞增。在圖中，藍(lán)節(jié)點(diǎn)贏了，所以每個(gè)被訪問的紅節(jié)點(diǎn)的勝利數(shù)都會(huì)遞增。這種反轉(zhuǎn)是由于每個(gè)節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)是用于其父節(jié)點(diǎn)的選擇，而不是它自己的。

  ...    /** 第四階段：反向傳播。更新之前的統(tǒng)計(jì)數(shù)據(jù)。 */   backpropagate(node, winner) {     while (node !== null) {       node.n_plays += 1       // 父節(jié)點(diǎn)的選擇       if (node.state.isPlayer(-winner)) {         node.n_wins += 1       }       node = node.parent     }   } }  module.exports = MonteCarlo

這是影響下一次迭代搜索中選擇階段的部分。請(qǐng)注意，這假設(shè)是一個(gè)兩人游戲，允許在 node.state.isPlayer(-winner) 中進(jìn)行反轉(zhuǎn)。你也許可以把這個(gè)函數(shù)泛化為 n 人游戲，做成 node.parent.state.isPlayer(winner) 之類的。

想一想，反向傳播 0 贏家是什么意思？這相當(dāng)于一盤平局，每個(gè)訪問節(jié)點(diǎn)的 n_plays 統(tǒng)計(jì)數(shù)據(jù)都會(huì)增加，而玩家 1 和玩家 -1 的 n_wins 統(tǒng)計(jì)數(shù)據(jù)都不會(huì)增加。這種更新的行為就像兩敗俱傷的游戲，將選擇推向其他游戲。最后，以平局結(jié)束的游戲和以失敗結(jié)束的游戲一樣，都有可能得不到充分的開發(fā)。這并沒有破壞任何東西，但它導(dǎo)致了當(dāng)平局比輸棋更可取時(shí)的次優(yōu)發(fā)揮。一個(gè)快速的解決方法是在平局時(shí)將雙方的 n_wins 遞增一半。

實(shí)現(xiàn)最佳游戲選擇

MCTS(UCT) 的妙處在于，由于它的不對(duì)稱性，樹的選擇和成長逐漸趨向于更好的移動(dòng)。最后，你得到模擬次數(shù)最多的子節(jié)點(diǎn)，那就是你根據(jù) MCTS 的最佳移動(dòng)結(jié)果。

  ...      /** 從現(xiàn)有的統(tǒng)計(jì)數(shù)據(jù)中獲得最佳的移動(dòng)結(jié)果。 */     bestPlay(state) {      this.makeNode(state)      // 如果不是所有的子節(jié)點(diǎn)都被擴(kuò)展，則信息不足     if (this.nodes.get(state.hash()).isFullyExpanded() === false)       throw new Error("Not enough information!")      let node = this.nodes.get(state.hash())     let allPlays = node.allPlays()     let bestPlay     let max = -Infinity      for (let play of allPlays) {       let childNode = node.childNode(play)       if (childNode.n_plays > max) {         bestPlay = play         max = childNode.n_plays       }     }      return bestPlay   }    ...

需要注意的是，選擇最佳玩法有不同的策略。這里所采用的策略在文獻(xiàn)中叫做 robust child，選擇最高的 n_plays。另一種策略是 max child，選擇最高的勝率 n_wins/n_plays。

實(shí)現(xiàn)統(tǒng)計(jì)自檢和顯示

現(xiàn)在，你應(yīng)該可以在當(dāng)前版本 index-v1.js 上運(yùn)行 node index.js。但是，你不會(huì)看到很多東西。要想看到里面發(fā)生了什么，我們需要完成以下事情。

在 monte-carlo.js 文件中:

  ...        // 工具方法    /** 返回該節(jié)點(diǎn)和子節(jié)點(diǎn)的 MCTS 統(tǒng)計(jì)信息 */   getStats(state) {      let node = this.nodes.get(state.hash())     let stats = { n_plays: node.n_plays,                    n_wins: node.n_wins,                    children: [] }          for (let child of node.children.values()) {       if (child.node === null)          stats.children.push({ play: child.play,                                n_plays: null,                                n_wins: null})       else          stats.children.push({ play: child.play,                                n_plays: child.node.n_plays,                                n_wins: child.node.n_wins})     }      return stats   } }  module.exports = MonteCarlo

這讓我們可以查詢一個(gè)節(jié)點(diǎn)及其直接子節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)。做完這些，我們就完成了 MonteCarlo。你可以用你所擁有的東西來運(yùn)行，也可以選擇獲取我完成的 monte-carlo.js。請(qǐng)注意，在我完成的版本中，bestPlay() 上有一個(gè)額外的參數(shù)來控制使用的最佳玩法策略。

現(xiàn)在，將 MonteCarlo.getStats() 整合到 index.js 中，或者獲取我的完整版 index.js 文件。

接著運(yùn)行 node index.js：

$ node index.js  player: 1 [ [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ] ] { n_plays: 3996,   n_wins: 1664,   children:     [ { play: Play_C4 { row: 5, col: 0 }, n_plays: 191, n_wins: 85 },      { play: Play_C4 { row: 5, col: 1 }, n_plays: 513, n_wins: 287 },      { play: Play_C4 { row: 5, col: 2 }, n_plays: 563, n_wins: 320 },      { play: Play_C4 { row: 5, col: 3 }, n_plays: 1705, n_wins: 1094 },      { play: Play_C4 { row: 5, col: 4 }, n_plays: 494, n_wins: 275 },      { play: Play_C4 { row: 5, col: 5 }, n_plays: 211, n_wins: 97 },      { play: Play_C4 { row: 5, col: 6 }, n_plays: 319, n_wins: 163 } ] } chosen play: Play_C4 { row: 5, col: 3 }  player: 2 [ [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 1, 0, 0, 0 ] ] { n_plays: 6682,   n_wins: 4239,   children:     [ { play: Play_C4 { row: 5, col: 0 }, n_plays: 577, n_wins: 185 },      { play: Play_C4 { row: 5, col: 1 }, n_plays: 799, n_wins: 277 },      { play: Play_C4 { row: 5, col: 2 }, n_plays: 1303, n_wins: 495 },      { play: Play_C4 { row: 4, col: 3 }, n_plays: 1508, n_wins: 584 },      { play: Play_C4 { row: 5, col: 4 }, n_plays: 1110, n_wins: 410 },      { play: Play_C4 { row: 5, col: 5 }, n_plays: 770, n_wins: 265 },      { play: Play_C4 { row: 5, col: 6 }, n_plays: 614, n_wins: 200 } ] } chosen play: Play_C4 { row: 4, col: 3 }  ...  winner: 2 [ [ 0, 0, 2, 2, 2, 0, 0 ],   [ 1, 0, 2, 2, 1, 0, 1 ],   [ 2, 0, 2, 1, 1, 2, 2 ],   [ 1, 0, 1, 1, 2, 1, 1 ],   [ 2, 0, 2, 2, 1, 2, 1 ],   [ 1, 0, 2, 1, 1, 2, 1 ] ]

完美！

總結(jié)

本文主要講述如何使用 Node.js 實(shí)現(xiàn)蒙特卡洛樹搜索，希望大家喜歡。下一篇文章將介紹如何優(yōu)化，以及蒙特卡洛樹搜索（MCTS）的現(xiàn)狀。

感謝你的閱讀！

英文原文地址：https://medium.com/@quasimik/implementing-monte-carlo-tree-search-in-node-js-5f07595104df

原文作者：Michael Liu