Rumah > Artikel > hujung hadapan web > Perbincangan ringkas tentang cara Node.js melaksanakan carian pokok Monte Carlo
Perbincangan ringkas tentang cara Node.js melaksanakan carian pokok Monte Carlo
- 青灯夜游ke hadapan
- 2021-07-20 19:00:392132semak imbas
Artikel ini akan memperkenalkan kepada anda cara melaksanakan carian pokok Monte Carlo menggunakan Node.js dan menggunakan algoritma carian pokok Monte Carlo (MCTS) untuk bermain permainan dengan peraturan yang diberikan. Mari kita lakukannya bersama-sama .
Artikel ini menganggap bahawa pembaca mempunyai sedikit pengetahuan tentang sains komputer, terutamanya prinsip kerja struktur pokok dalam struktur data, dan juga perlu mempunyai JavaScript pengetahuan pertengahan (ES6). Pembelajaran yang disyorkan: "Tutorial nodejs"]
Matlamat artikel ini adalah mudah:
Melaksanakan algoritma Carian Pokok Monte Carlo (MCTS) untuk bermain permainan dengan diberikan peraturan.
Keseluruhan proses ini akan menjadi pengajaran dan praktikal, serta mengabaikan bahagian pengoptimuman prestasi. Saya akan memberikan penjelasan ringkas tentang coretan kod yang dipautkan dengan harapan anda akan mengikutinya dan mengambil sedikit masa untuk memahami bahagian kompleks kod tersebut.
Jom mulakan!
Cipta fail rangka
dalam game.js fail:
/** 代表游戏棋盘的类。 */
class Game {
/** 生成并返回游戏的初始状态。 */
start() {
// TODO
return state
}
/** 返回当前玩家在给定状态下的合法移动。 */
legalPlays(state) {
// TODO
return plays
}
/** 将给定的状态提前并返回。 */
nextState(state, move) {
// TODO
return newState
}
/** 返回游戏的胜利者。 */
winner(state) {
// TODO
return winner
}
}
module.exports = Game dalam monte-carlo.js fail:
/** 表示蒙特卡洛树搜索的类。 */
class MonteCarlo {
/** 从给定的状态中，反复运行 MCTS 来建立统计数据。 */
runSearch(state, timeout) {
// TODO
}
/** 从现有的统计数据中获取最佳的移动。 */
bestPlay(state) {
// TODO
// return play
}
}
module.exports = MonteCarlo Dalam fail 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)
// 从初始状态开始轮流进行游戏，直到有玩家胜利为止
while (winner === null) {
mcts.runSearch(state, 1)
let play = mcts.bestPlay(state)
state = game.nextState(state, play)
winner = game.winner(state)
}
console.log(winner)Luangkan sedikit masa untuk mengisih kod dahulu. Perancah subreddit dalam fikiran anda dan cuba memahaminya. Ini adalah pusat pemeriksaan mental Pastikan anda memahami bagaimana ia sesuai jika anda rasa anda tidak dapat memahaminya, sila tinggalkan mesej dan beritahu saya apa yang boleh saya lakukan untuk anda.
Cari permainan yang betul
Dalam konteks membangunkan ejen permainan MCTS, kami boleh memikirkan program sebenar kami sebagai kod yang melaksanakan rangka kerja MCTS, juga Hanya kod dalam fail monte-carlo.js. Kod khusus permainan dalam fail game.js boleh ditukar ganti dan pasang dan main, dan merupakan antara muka kami kepada rangka kerja MCTS. Kami pada asasnya mahu menjadi otak di sebalik MCTS, yang sepatutnya dijalankan pada mana-mana permainan. Lagipun, kami berminat dengan permainan umum.
Walau bagaimanapun, untuk menguji rangka kerja MCTS kami, kami perlu memilih permainan tertentu dan menjalankan rangka kerja kami menggunakan permainan itu. Kami ingin melihat rangka kerja MCTS membuat keputusan pada setiap langkah yang masuk akal untuk permainan yang kami pilih.
Bagaimana pula dengan membuat permainan tic-tac-toe (Tic-Tac-Toe)? Ia digunakan dalam hampir semua tutorial permainan pengenalan, dan ia mempunyai beberapa ciri yang sangat memuaskan:
- Semua orang pernah memainkannya sebelum ini.
- Peraturannya sangat mudah dan boleh dilaksanakan menggunakan algoritma.
- Ia mempunyai mesej sempurna yang pasti.
- Ia adalah permainan dua pemain konfrontasi.
- Ruang negeri adalah ringkas dan boleh dimodelkan secara psikologi.
- Kerumitan ruang keadaan sudah cukup untuk membuktikan kekuatan algoritma.
Tetapi, tic-tac-toe sangat membosankan, bukan? Selain itu, anda mungkin sudah mengetahui strategi terbaik untuk Tic-Tac-Toe, yang kehilangan sedikit daya tarikannya. Terdapat begitu banyak permainan untuk dipilih, bagaimana jika kita memilih satu lagi: catur empat keping (Connect Four)? Selain mungkin menikmati populariti yang lebih rendah daripada Tic-Tac-Toe, ia bukan sahaja mempunyai ciri-ciri yang disenaraikan di atas, tetapi mungkin juga memudahkan pemain untuk membina model mental ruang keadaan empat letupan.
Dalam pelaksanaan kami, kami akan menggunakan dimensi dan peraturan Hasbro (Hasbro: sebuah syarikat mainan terkenal Amerika), iaitu 6 baris dan 7 lajur, di mana menegak, Jika bilangan buah catur mendatar dan pepenjuru yang disambungkan ialah 4, ia dianggap sebagai kemenangan. Kepingan akan jatuh dari atas dan hinggap pada slot kosong pertama dari bawah ke atas dengan bantuan graviti.
Tetapi sebelum kita meneruskan, kita perlu menjelaskan sesuatu. Jika anda yakin, anda boleh melaksanakan mana-mana permainan yang anda inginkan sendiri, asalkan ia mematuhi API permainan yang diberikan. Hanya jangan mengeluh apabila anda kacau dan ia tidak berfungsi. Ingat, permainan seperti catur dan Go terlalu rumit untuk diselesaikan oleh MCTS (dengan berkesan) sendiri; Google menyelesaikannya dalam AlphaGo dengan menambahkan strategi pembelajaran mesin yang cekap pada soalan MCTS. Jika anda ingin bermain permainan anda sendiri, anda boleh melangkau dua bahagian seterusnya.
Melaksanakan permainan empat letupan
Sekarang, namakan terus game.js kepada game-c4.js dan kelas kepada Game_C4. Pada masa yang sama, cipta dua kelas baharu: State_C4 dalam state-c4.js untuk mewakili keadaan permainan dan Play_C4 dalam play-c4.js untuk mewakili peralihan keadaan.
Walaupun ini bukan kandungan utama artikel ini, bagaimanakah anda membinanya sendiri?
- 你会如何在
State_C4中表示一个游戏状态呢？ - 在
Play_C4中，你将如何表示一个状态转换（例如一个动作）呢？ - 你会如何把
State_C4、Play_C4和四子棋游戏规则 —— 用冰冷的代码放在Game_C4中吗？
注意，我们需要通过骨架文件 game-c4.js 中定义的高级 API 方法所要求的形式实现四子棋游戏。
你可以独立思考完成或者直接使用我完成的 play-c4.js、state-c4.js 和 game-c4.js 文件。
这是一个工作量很大的活，不是吗？至少对我来说是这样的。这段代码需要一些 JavaScript 知识，但应该还是很容易读懂的。最重要的工作在 Game_C4.winner() 中 —— 它用于在四个独立的棋盘中建立积分系统，而所有的棋盘都在 checkBoards 里面。每个棋盘都有一个可能的获胜方向（水平、垂直、左对角线或右对角线）。我们需要确保棋盘的三个面比实际棋盘大，方便为算法提供零填充。
我相信还有更好的方法。Game.winner() 的运行时性能并不是很好，具体来说，在大 O 表示法中，它是 O(rows * cols)，所以性能并不是很好。通过在状态对象中存储 checkBoards，并且只更新 checkBoards 中最后改变状态的单元格（也会包含在状态对象中），可以大幅改善运行时性能，也许你以后可以尝试这个优化方法。
运行四子棋游戏
此时，我们将通过模拟 1000 次四子棋游戏来测试 Game_C4。点击获取 test-game-c4.js 文件。
在终端上运行 node test-game-c4.js。在一个相对现代的处理器和最新版本的 Node.js 上，运行 1000 次迭代应该会在一秒钟内完成：
$ 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
二号棋手在内部用 -1 表示，这是为了方便 game-c4.js 的计算。用 2 代替 -1 的那段代码只是为了对齐棋盘输出结果。为了简便起见，程序只输出了一块棋盘，但它确实玩了另外的 999 次四子棋游戏。在单个棋盘输出之后，它应该输出一号棋手在所有 1000 盘棋中获胜的分数 —— 预计数值在 55% 左右，因为第一个棋手有先发优势。
分析现在的状况
我们已经实现一个带有 API 方法并且可以运行的游戏，这些 API 方法可以与 State 对象表示的游戏状态协同运行。我们现在的状况如何？
目标：实现蒙特卡洛树搜索（MCTS）算法来玩一个给定规则的游戏。
当然，我们还没有达到目的。刚才我们完成了一件非常重要的事情：让它设立一个切实的目标，并组成测试我们实现 MCTS 的核心模块。现在，我们进入正题。
实现蒙特卡洛树搜索
在这里，我将按照 MCTS 详解中类似的组织方式，我也会在一些地方用自己的话来阐明某些观点。
实现搜索树节点
为了存储从这些模拟中获得的统计信息，MCTS 从头开始建立了自己的搜索树。
现在请你回顾树结构知识。MCTS 是一个树结构搜索，因此我们需要使用树节点。我们将在 monte-carlo-node.js 的 MonteCarloNode 类中实现这些节点。然后，我们将在 MonteCarlo 中使用它来构建搜索树。
/** 代表搜索树中一个节点的类。 */
class MonteCarloNode {
constructor(parent, play, state, unexpandedPlays) {
this.play = play
this.state = state
// 蒙特卡洛的内容
this.n_plays = 0
this.n_wins = 0
// 树结构的内容
this.parent = parent
this.children = new Map()
for (let play of unexpandedPlays) {
this.children.set(play.hash(), { play: play, node: null })
}
}
...先再确认一下是否能够理解这些：
-
parent是MonteCarloNode父节点。 -
play是指从父节点到这个节点所做的Play。 -
state是指与该节点相关联的游戏State。 -
unexpandedPlays是Plays的一个合法数组，可以从这个节点进行。 -
this.children是由unexpandedPlays创建的，是Plays指向子节点MonteCarloNodes的一个 Map 对象（不完全是，见下文）。
MonteCarloNode.children 是一个从游戏哈希到对象的映射，包含游戏对象和相关的子节点。我们在这里包含了游戏对象，以便从它们的哈希中恢复游戏对象。
重要的是，Play 和 State 应该提供 hash() 方法。我们将在一些地方使用这些哈希作为 JavaScript 的 Map 对象，比如在 MonteCarloNode.children 中。
请注意，两个 State 对象应该被 State.hash() 认为是不同的 —— 即使它们有相同的棋盘状态 —— 如果每个对象通过不同的下棋顺序达到相同的棋盘状态。考虑到这一点，我们可以简单地让 State.hash() 返回一个字符串化的 Play 对象的有序数组，代表为达到该状态而下的棋。如果你获取了我的 state-c4.js，这个已经完成了。
现在我们将为 MonteCarloNode 添加成员方法。
...
/** 获取对应于给定游戏的 MonteCarloNode。 */
childNode(play) {
// TODO
// 返回 MonteCarloNode
}
/** 展开指定的 child play，并返回新的 child node。*/
expand(play, childState, unexpandedPlays) {
// TODO
// 返回 MonteCarloNode
}
/** 从这个节点 node 获取所有合法的 play。*/
allPlays() {
// TODO
// 返回 Play[]
}
/** 从这个节点 node 获取所有未展开的合法 play。 */
unexpandedPlays() {
// TODO
// 返回 Play[]
}
/** 该节点是否完全展开。 */
isFullyExpanded() {
// TODO
// 返回 bool
}
/** 该节点 node 在游戏树中是否为终端，
不包括因获胜而终止游戏。 */
isLeaf() {
// TODO
// 返回 bool
}
/** 获取该节点 node 的 UCB1 值。 */
getUCB1(biasParam) {
// TODO
// 返回 number
}
}
module.exports = MonteCarloNode方法可真多!
特别是，MonteCarloNode.expand() 将 MonteCarloNode.children 中未展开的空节点替换为实节点。这个方法将是四阶段的 MCTS 算法中阶段二：扩展的一部分，其他方法自行理解。
通常你可以自己实现这些，也可以获取完成的 monte-carlo-node.js。即使你自己做，我也建议在继续之前对照我完成的程序进行检查，以确保正常运行。
如果你刚获取到我完成的程序，请快速浏览一下源代码，就当是另一个心理检查点，重新梳理你的整体理解。这些都是简短的方法，你会在短时间内看懂它们。
尤其是 MonteCarloNode.getUCB1() 几乎是将上面的公式直接翻译成代码。这整个公式在上一篇文章中有详细的解释，再去看一下吧，这并不难理解，也是值得看的。
更新蒙特卡洛的类
目前的版本是 monte-carlo-v1.js，只是一个骨架文件。该类的第一个更新是增加 MonteCarloNode，并创建一个构造函数。
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 允许我们获取任何给定状态的节点，这将是有用的。至于其他的成员变量，将它们与 MonteCarlo 联系起来就很有意义了。
...
/** 如果给定的状态不存在，就创建空节点。 */
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)
}
}
...以上代码让我们可以创建根节点，还可以创建任意节点，这可能很有用。
...
/** 从给定的状态，反复运行 MCTS 来建立统计数据。 */
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)
}
}
...最后，我们来到了算法的核心部分。引用第一篇文章的内容，以下是过程描述：
在第 (1) 阶段，利用现有的信息反复选择连续的子节点，直至搜索树的末端。
接下来，在第 (2) 阶段，通过增加一个节点来扩展搜索树。
然后，在第 (3) 阶段，模拟运行到最后，决定胜负。
最后，在第 (4) 阶段，所选路径中的所有节点都会用模拟游戏中获得的新信息进行更新。
这四个阶段的算法反复运行，直至收集到足够的信息，产生一个好的移动结果。
...
/** 从现有的统计数据中获得最佳的移动。 */
bestPlay(state) {
// TODO
// 返回 play
}
/** 第一阶段：选择。选择直到不完全展开或叶节点。 */
select(state) {
// TODO
// 返回 node
}
/** 第二阶段：扩展。随机展开一个未展开的子节点。 */
expand(node) {
// TODO
// 返回 childNode
}
/** 第三阶段：模拟。游戏到终止状态，返回获胜者。 */
simulate(node) {
// TODO
// 返回 winner
}
/** 第四阶段：反向传播。更新之前的统计数据。 */
backpropagate(node, winner) {
// TODO
}
}接下来讲解四个阶段具体的实现方法，我们现在的版本是 monte-carlo-v2.js。
实现 MCTS 第一阶段：选择
从搜索树的根节点开始，我们通过反复选择一个合法移动，前进到相应的子节点来向下移动。如果一个节点中的一个、几个或全部合法移动在搜索树中没有对应的节点，我们就停止选择。
...
/** 第一阶段：选择。选择直到不完全展开或叶节点。 */
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
}
...该函数通过查询每个子节点的 UCB1 值，使用现有的 UCB1 统计。选择 UCB1 值最高的子节点，然后对所选子节点的子节点重复这个过程，以此类推。
当循环终止时，保证所选节点至少有一个未展开的子节点，除非该节点是叶子节点。这种情况是由调用函数 MonteCarlo.runSearch() 处理的，所以我们在这里不必担心。
实现 MCTS 第二阶段：扩展
停止选择后，搜索树中至少会有一个未展开的移动。现在，我们随机选择其中的一个，然后我们创建该移动对应的子节点（图中加粗）。我们将这个节点作为子节点添加到选择阶段最后选择的节点上，扩展搜索树。节点中的统计信息初始化为
0次模拟中的0次胜利。
...
/** 第二阶段：扩展。随机展开一个未展开的子节点。 */
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()。扩展是在检查 if (node.isLeaf() === false && winner === null) 时完成的。很明显，如果在游戏树中没有可能的子节点 —— 例如，当棋盘满了的时候，是不可能进行扩展的。如果有赢家的话，我们也不想扩展 —— 这就像说当你的对手赢了的时候你应该停止玩游戏一样明显。
那么如果是叶子节点，会发生什么呢？我们只需用在该节点中获胜的人进行反向传播 —— 无论是玩家 1，玩家 -1，甚至是 0（平局）。同样，如果在任何节点上有一个非空的赢家，我们只需跳过扩展和模拟，并立即与该赢家（1 或 -1 或 0）进行反向传播。
反向传播 0 赢家是什么意思？用 MCTS 真的可以吗？真的可以用，后面再细讲。
实现 MCTS 第三阶段：模拟
从扩张阶段新建立的节点开始，随机选择棋步，反复推进对局状态。这样重复进行，直到对局结束，出现赢家。在此阶段不创建新节点。
...
/** 第三阶段：模拟。游戏到终止状态，返回获胜者。 */
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
}
...因为这里没有保存任何东西，所以这主要涉及到 Game，而 MonteCarloNode 的内容不多。
再看一下 MonteCarlo.runSearch()，模拟是在与扩展一样的检查 if (node.isLeaf() === false && winner === null) 时完成的。原因是：如果这两个条件之一成立，那么最后的赢家就是当前节点的赢家，我们只是用这个赢家进行反向传播。
实现 MCTS 第四阶段：反转
模拟阶段结束后，所有被访问的节点（图中粗体）的统计数据都会被更新。每个被访问的节点的模拟次数都会递增。根据哪个玩家获胜，其获胜次数也可能递增。在图中，蓝节点赢了，所以每个被访问的红节点的胜利数都会递增。这种反转是由于每个节点的统计数据是用于其父节点的选择，而不是它自己的。
...
/** 第四阶段：反向传播。更新之前的统计数据。 */
backpropagate(node, winner) {
while (node !== null) {
node.n_plays += 1
// 父节点的选择
if (node.state.isPlayer(-winner)) {
node.n_wins += 1
}
node = node.parent
}
}
}
module.exports = MonteCarlo这是影响下一次迭代搜索中选择阶段的部分。请注意，这假设是一个两人游戏，允许在 node.state.isPlayer(-winner) 中进行反转。你也许可以把这个函数泛化为 n 人游戏，做成 node.parent.state.isPlayer(winner) 之类的。
想一想，反向传播 0 赢家是什么意思？这相当于一盘平局，每个访问节点的 n_plays 统计数据都会增加，而玩家 1 和玩家 -1 的 n_wins 统计数据都不会增加。这种更新的行为就像两败俱伤的游戏，将选择推向其他游戏。最后，以平局结束的游戏和以失败结束的游戏一样，都有可能得不到充分的开发。这并没有破坏任何东西，但它导致了当平局比输棋更可取时的次优发挥。一个快速的解决方法是在平局时将双方的 n_wins 递增一半。
实现最佳游戏选择
MCTS(UCT) 的妙处在于，由于它的不对称性，树的选择和成长逐渐趋向于更好的移动。最后，你得到模拟次数最多的子节点，那就是你根据 MCTS 的最佳移动结果。
...
/** 从现有的统计数据中获得最佳的移动结果。 */
bestPlay(state) {
this.makeNode(state)
// 如果不是所有的子节点都被扩展，则信息不足
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
}
...需要注意的是，选择最佳玩法有不同的策略。这里所采用的策略在文献中叫做 robust child，选择最高的 n_plays。另一种策略是 max child，选择最高的胜率 n_wins/n_plays。
实现统计自检和显示
现在，你应该可以在当前版本 index-v1.js 上运行 node index.js。但是，你不会看到很多东西。要想看到里面发生了什么，我们需要完成以下事情。
在 monte-carlo.js 文件中:
...
// 工具方法
/** 返回该节点和子节点的 MCTS 统计信息 */
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这让我们可以查询一个节点及其直接子节点的统计数据。做完这些，我们就完成了 MonteCarlo。你可以用你所拥有的东西来运行，也可以选择获取我完成的 monte-carlo.js。请注意，在我完成的版本中，bestPlay() 上有一个额外的参数来控制使用的最佳玩法策略。
现在，将 MonteCarlo.getStats() 整合到 index.js 中，或者获取我的完整版 index.js 文件。
接着运行 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 实现蒙特卡洛树搜索，希望大家喜欢。下一篇文章将介绍如何优化，以及蒙特卡洛树搜索（MCTS）的现状。
感谢你的阅读！
英文原文地址：https://medium.com/@quasimik/implementing-monte-carlo-tree-search-in-node-js-5f07595104df
原文作者：Michael Liu
更多编程相关知识，请访问：编程入门！！
Atas ialah kandungan terperinci Perbincangan ringkas tentang cara Node.js melaksanakan carian pokok Monte Carlo. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!