溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Node.js如何實(shí)現(xiàn)蒙特卡洛樹(shù)搜索”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“Node.js如何實(shí)現(xiàn)蒙特卡洛樹(shù)搜索”吧！
本文的目標(biāo)很簡(jiǎn)單：
實(shí)現(xiàn)蒙特卡洛樹(shù)搜索（MCTS）算法來(lái)玩一個(gè)給定規(guī)則的游戲。
這整個(gè)過(guò)程將是指導(dǎo)性和實(shí)踐性的，并且忽略掉性能優(yōu)化的部分。我將會(huì)對(duì)鏈接的代碼片段進(jìn)行簡(jiǎn)要解釋，希望你能跟上我的腳步并花一些時(shí)間理解代碼中復(fù)雜難懂的部分。
讓我們開(kāi)始吧！
在 game.js 文件中：
/** 代表游戲棋盤(pán)的類。 */
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 文件中：
/** 表示蒙特卡洛樹(shù)搜索的類。 */
class MonteCarlo {
/** 從給定的狀態(tài)中，反復(fù)運(yùn)行 MCTS 來(lái)建立統(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)開(kā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)，先確保你明白它是如何組合在一起的，如果感到無(wú)法理解，就請(qǐng)留言吧，讓我看看我能為你做些什么。
在開(kāi)發(fā)一個(gè) MCTS 游戲智能體的背景下，我們可以把我們真正的程序看作是實(shí)現(xiàn) MCTS 框架的代碼，也就是 monte-carlo.js 文件中的代碼。在 game.js 文件中的游戲?qū)Ｓ么a是可以互換并且即插即用的，它是我們使用 MCTS 框架的接口。我們主要是想做 MCTS 背后的大腦，它應(yīng)該真的能在任何游戲上運(yùn)行。畢竟，我們感興趣的是一般性的游戲玩法。
不過(guò)，為了測(cè)試我們的 MCTS 框架，我們需要選擇一個(gè)特定的游戲，并使用該游戲運(yùn)行我們的框架。我們希望看到 MCTS 框架在每個(gè)步驟中都做出對(duì)我們選擇的游戲有意義的決策。
做一個(gè)井字游戲（Tic-Tac-Toe）怎么樣呢？幾乎所有的游戲入門(mén)教學(xué)都會(huì)用到它，它還有著一些非常令我們滿意的特性：
大家之前都玩過(guò)。
它的規(guī)則很簡(jiǎn)單，可以用算法實(shí)現(xiàn)。
它具有一份確定的完善的信息。
它是一款對(duì)抗性的雙人游戲。
狀態(tài)空間很簡(jiǎn)單，可以在心理上進(jìn)行建模。
狀態(tài)空間的復(fù)雜程度足以證明算法的強(qiáng)大。
但是，井字游戲真的很無(wú)聊，不是嗎？另外，你大概已經(jīng)知道井字游戲的最佳策略，這就失去了一些吸引力。有這么多游戲可以選擇，我們?cè)龠x一個(gè)：四子棋（Connect Four）怎么樣？除了可能比井字游戲享有更低的人氣外，它不僅有上面所列舉的特性，還可能讓玩家不那么容易地建立四子棋狀態(tài)空間的心理模型。
在我們的實(shí)現(xiàn)中，我們將使用 Hasbro（孩之寶：美國(guó)著名玩具公司）的尺寸和規(guī)則，即是 6 行 7 列，其中垂直、水平和對(duì)角線棋子數(shù)相連為 4 就算勝利。棋子會(huì)從上方落下，并借助重力落在自底向上數(shù)的第一個(gè)空槽。
不過(guò)在我們繼續(xù)講述之前，要先說(shuō)明一下。如果你有信心，你可以自己去實(shí)現(xiàn)任何你想要的游戲，只要它遵守給定的游戲 API。只是當(dāng)你搞砸了，不能用的時(shí)候不要來(lái)抱怨。請(qǐng)記住，像國(guó)際象棋和圍棋這樣的游戲太復(fù)雜了，即使是 MCTS 也無(wú)法（有效地）獨(dú)自解決；谷歌在 AlphaGo 中通過(guò)向 MCTS 添加有效的機(jī)器學(xué)習(xí)策略來(lái)解決這個(gè)問(wèn)題。如果你想玩自己的游戲，你可以跳過(guò)接下來(lái)的兩個(gè)部分。
現(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 中嗎？
注意，我們需要通過(guò)骨架文件 game-c4.js 中定義的高級(jí) API 方法所要求的形式實(shí)現(xiàn)四子棋游戲。
你可以獨(dú)立思考完成或者直接使用我完成的 play-c4.js、state-c4.js 和 game-c4.js 文件。
這是一個(gè)工作量很大的活，不是嗎？至少對(duì)我來(lái)說(shuō)是這樣的。這段代碼需要一些 JavaScript 知識(shí)，但應(yīng)該還是很容易讀懂的。最重要的工作在 Game_C4.winner() 中 —— 它用于在四個(gè)獨(dú)立的棋盤(pán)中建立積分系統(tǒng)，而所有的棋盤(pán)都在 checkBoards 里面。每個(gè)棋盤(pán)都有一個(gè)可能的獲勝方向（水平、垂直、左對(duì)角線或右對(duì)角線）。我們需要確保棋盤(pán)的三個(gè)面比實(shí)際棋盤(pán)大，方便為算法提供零填充。
我相信還有更好的方法。Game.winner() 的運(yùn)行時(shí)性能并不是很好，具體來(lái)說(shuō)，在大 O 表示法中，它是 O(rows * cols)，所以性能并不是很好。通過(guò)在狀態(tài)對(duì)象中存儲(chǔ) checkBoards，并且只更新 checkBoards 中最后改變狀態(tài)的單元格（也會(huì)包含在狀態(tài)對(duì)象中），可以大幅改善運(yùn)行時(shí)性能，也許你以后可以嘗試這個(gè)優(yōu)化方法。
此時(shí)，我們將通過(guò)模擬 1000 次四子棋游戲來(lái)測(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ì)齊棋盤(pán)輸出結(jié)果。為了簡(jiǎn)便起見(jiàn)，程序只輸出了一塊棋盤(pán)，但它確實(shí)玩了另外的 999 次四子棋游戲。在單個(gè)棋盤(pán)輸出之后，它應(yīng)該輸出一號(hào)棋手在所有 1000 盤(pán)棋中獲勝的分?jǐn)?shù) —— 預(yù)計(jì)數(shù)值在 55% 左右，因?yàn)榈谝粋€(gè)棋手有先發(fā)優(yōu)勢(shì)。
我們已經(jīng)實(shí)現(xiàn)一個(gè)帶有 API 方法并且可以運(yùn)行的游戲，這些 API 方法可以與 State 對(duì)象表示的游戲狀態(tài)協(xié)同運(yùn)行。我們現(xiàn)在的狀況如何？
目標(biāo)：實(shí)現(xiàn)蒙特卡洛樹(shù)搜索（MCTS）算法來(lái)玩一個(gè)給定規(guī)則的游戲。
當(dāng)然，我們還沒(méi)有達(dá)到目的。剛才我們完成了一件非常重要的事情：讓它設(shè)立一個(gè)切實(shí)的目標(biāo)，并組成測(cè)試我們實(shí)現(xiàn) MCTS 的核心模塊?，F(xiàn)在，我們進(jìn)入正題。
在這里，我將按照 MCTS 詳解中類似的組織方式，我也會(huì)在一些地方用自己的話來(lái)闡明某些觀點(diǎn)。
為了存儲(chǔ)從這些模擬中獲得的統(tǒng)計(jì)信息，MCTS 從頭開(kāi)始建立了自己的搜索樹(shù)。
現(xiàn)在請(qǐng)你回顧樹(shù)結(jié)構(gòu)知識(shí)。MCTS 是一個(gè)樹(shù)結(jié)構(gòu)搜索，因此我們需要使用樹(shù)節(jié)點(diǎn)。我們將在 monte-carlo-node.js 的 MonteCarloNode 類中實(shí)現(xiàn)這些節(jié)點(diǎn)。然后，我們將在 MonteCarlo 中使用它來(lái)構(gòu)建搜索樹(shù)。
/** 代表搜索樹(shù)中一個(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
// 樹(shù)結(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ì)象（不完全是，見(jiàn)下文）。
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)為是不同的 —— 即使它們有相同的棋盤(pán)狀態(tài) —— 如果每個(gè)對(duì)象通過(guò)不同的下棋順序達(dá)到相同的棋盤(pán)狀態(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
}
/** 展開(kāi)指定的 child play，并返回新的 child node。*/
expand(play, childState, unexpandedPlays) {
// TODO
// 返回 MonteCarloNode
}
/** 從這個(gè)節(jié)點(diǎn) node 獲取所有合法的 play。*/
allPlays() {
// TODO
// 返回 Play[]
}
/** 從這個(gè)節(jié)點(diǎn) node 獲取所有未展開(kāi)的合法 play。 */
unexpandedPlays() {
// TODO
// 返回 Play[]
}
/** 該節(jié)點(diǎn)是否完全展開(kāi)。 */
isFullyExpanded() {
// TODO
// 返回 bool
}
/** 該節(jié)點(diǎn) node 在游戲樹(shù)中是否為終端，
不包括因獲勝而終止游戲。 */
isLeaf() {
// TODO
// 返回 bool
}
/** 獲取該節(jié)點(diǎn) node 的 UCB1 值。 */
getUCB1(biasParam) {
// TODO
// 返回 number
}
}
module.exports = MonteCarloNode方法可真多!
特別是，MonteCarloNode.expand() 將 MonteCarloNode.children 中未展開(kāi)的空節(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')
/** 表示蒙特卡洛搜索樹(shù)的類。 */
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)系起來(lái)就很有意義了。
...
/** 如果給定的狀態(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 來(lái)建立統(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)
}
}
...最后，我們來(lái)到了算法的核心部分。引用第一篇文章的內(nèi)容，以下是過(guò)程描述：
在第 (1) 階段，利用現(xiàn)有的信息反復(fù)選擇連續(xù)的子節(jié)點(diǎn)，直至搜索樹(shù)的末端。
接下來(lái)，在第 (2) 階段，通過(guò)增加一個(gè)節(jié)點(diǎn)來(lái)擴(kuò)展搜索樹(shù)。
然后，在第 (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
}
/** 第一階段：選擇。選擇直到不完全展開(kāi)或葉節(jié)點(diǎn)。 */
select(state) {
// TODO
// 返回 node
}
/** 第二階段：擴(kuò)展。隨機(jī)展開(kāi)一個(gè)未展開(kāi)的子節(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
}
}接下來(lái)講解四個(gè)階段具體的實(shí)現(xiàn)方法，我們現(xiàn)在的版本是 monte-carlo-v2.js。
從搜索樹(shù)的根節(jié)點(diǎn)開(kāi)始，我們通過(guò)反復(fù)選擇一個(gè)合法移動(dòng)，前進(jìn)到相應(yīng)的子節(jié)點(diǎn)來(lái)向下移動(dòng)。如果一個(gè)節(jié)點(diǎn)中的一個(gè)、幾個(gè)或全部合法移動(dòng)在搜索樹(shù)中沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn)，我們就停止選擇。
...
/** 第一階段：選擇。選擇直到不完全展開(kāi)或葉節(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ù)通過(guò)查詢每個(gè)子節(jié)點(diǎn)的 UCB1 值，使用現(xiàn)有的 UCB1 統(tǒng)計(jì)。選擇 UCB1 值最高的子節(jié)點(diǎn)，然后對(duì)所選子節(jié)點(diǎn)的子節(jié)點(diǎn)重復(fù)這個(gè)過(guò)程，以此類推。
當(dāng)循環(huán)終止時(shí)，保證所選節(jié)點(diǎn)至少有一個(gè)未展開(kāi)的子節(jié)點(diǎn)，除非該節(jié)點(diǎn)是葉子節(jié)點(diǎn)。這種情況是由調(diào)用函數(shù) MonteCarlo.runSearch() 處理的，所以我們?cè)谶@里不必?fù)?dān)心。
停止選擇后，搜索樹(shù)中至少會(huì)有一個(gè)未展開(kāi)的移動(dòng)?，F(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ò)展搜索樹(shù)。節(jié)點(diǎn)中的統(tǒng)計(jì)信息初始化為
0次模擬中的0次勝利。
...
/** 第二階段：擴(kuò)展。隨機(jī)展開(kāi)一個(gè)未展開(kāi)的子節(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
}
...再來(lái)看一下 MonteCarlo.runSearch()。擴(kuò)展是在檢查 if (node.isLeaf() === false && winner === null) 時(shí)完成的。很明顯，如果在游戲樹(shù)中沒(méi)有可能的子節(jié)點(diǎn) —— 例如，當(dāng)棋盤(pán)滿了的時(shí)候，是不可能進(jìn)行擴(kuò)展的。如果有贏家的話，我們也不想擴(kuò)展 —— 這就像說(shuō)當(dāng)你的對(duì)手贏了的時(shí)候你應(yīng)該停止玩游戲一樣明顯。
那么如果是葉子節(jié)點(diǎn)，會(huì)發(fā)生什么呢？我們只需用在該節(jié)點(diǎn)中獲勝的人進(jìn)行反向傳播 —— 無(wú)論是玩家 1，玩家 -1，甚至是 0（平局）。同樣，如果在任何節(jié)點(diǎn)上有一個(gè)非空的贏家，我們只需跳過(guò)擴(kuò)展和模擬，并立即與該贏家（1 或 -1 或 0）進(jìn)行反向傳播。
反向傳播 0 贏家是什么意思？用 MCTS 真的可以嗎？真的可以用，后面再細(xì)講。
從擴(kuò)張階段新建立的節(jié)點(diǎn)開(kāi)始，隨機(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)檫@里沒(méi)有保存任何東西，所以這主要涉及到 Game，而 MonteCarloNode 的內(nèi)容不多。
再看一下 MonteCarlo.runSearch()，模擬是在與擴(kuò)展一樣的檢查 if (node.isLeaf() === false && winner === null) 時(shí)完成的。原因是：如果這兩個(gè)條件之一成立，那么最后的贏家就是當(dāng)前節(jié)點(diǎn)的贏家，我們只是用這個(gè)贏家進(jìn)行反向傳播。
模擬階段結(jié)束后，所有被訪問(wèn)的節(jié)點(diǎn)（圖中粗體）的統(tǒng)計(jì)數(shù)據(jù)都會(huì)被更新。每個(gè)被訪問(wèn)的節(jié)點(diǎn)的模擬次數(shù)都會(huì)遞增。根據(jù)哪個(gè)玩家獲勝，其獲勝次數(shù)也可能遞增。在圖中，藍(lán)節(jié)點(diǎn)贏了，所以每個(gè)被訪問(wèn)的紅節(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)于一盤(pán)平局，每個(gè)訪問(wèn)節(jié)點(diǎn)的 n_plays 統(tǒng)計(jì)數(shù)據(jù)都會(huì)增加，而玩家 1 和玩家 -1 的 n_wins 統(tǒng)計(jì)數(shù)據(jù)都不會(huì)增加。這種更新的行為就像兩敗俱傷的游戲，將選擇推向其他游戲。最后，以平局結(jié)束的游戲和以失敗結(jié)束的游戲一樣，都有可能得不到充分的開(kāi)發(fā)。這并沒(méi)有破壞任何東西，但它導(dǎo)致了當(dāng)平局比輸棋更可取時(shí)的次優(yōu)發(fā)揮。一個(gè)快速的解決方法是在平局時(shí)將雙方的 n_wins 遞增一半。
MCTS(UCT) 的妙處在于，由于它的不對(duì)稱性，樹(shù)的選擇和成長(zhǎng)逐漸趨向于更好的移動(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。
現(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。你可以用你所擁有的東西來(lái)運(yùn)行，也可以選擇獲取我完成的 monte-carlo.js。請(qǐng)注意，在我完成的版本中，bestPlay() 上有一個(gè)額外的參數(shù)來(lái)控制使用的最佳玩法策略。
現(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 ] ]完美！
感謝各位的閱讀，以上就是“Node.js如何實(shí)現(xiàn)蒙特卡洛樹(shù)搜索”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Node.js如何實(shí)現(xiàn)蒙特卡洛樹(shù)搜索這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼