本篇文章给大家介绍一下使用Node.js如何实现蒙特卡洛树搜索，并用蒙特卡洛树搜索（MCTS）算法来玩一个给定规则的游戏，下面一起来看看吧！
|
本篇文章给大家介绍一下使用Node.js如何实现蒙特卡洛树搜索，并用蒙特卡洛树搜索（MCTS）算法来玩一个给定规则的游戏，下面一起来看看吧！
本文假设读者具备一定的计算机科学知识，尤其是数据结构中关于树结构的工作原理，还需要具备 JavaScript（ES6+）的中级知识。推荐学习：《nodejs 教程》】 本文的目标很简单： 实现蒙特卡洛树搜索（MCTS）算法来玩一个给定规则的游戏。 这整个过程将是指导性和实践性的，并且忽略掉性能优化的部分。我将会对链接的代码片段进行简要解释，希望你能跟上我的脚步并花一些时间理解代码中复杂难懂的部分。 让我们开始吧！ 创建骨架文件在 /** 代表游戏棋盘的类。 */
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在 /** 表示蒙特卡洛树搜索的类。 */
class MonteCarlo {
/** 从给定的状态中，反复运行 MCTS 来建立统计数据。 */
runSearch(state, timeout) {
// TODO
}
/** 从现有的统计数据中获取最佳的移动。 */
bestPlay(state) {
// TODO
// return play
}
}
module.exports = MonteCarlo在 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)先花点时间梳理一下代码吧。在脑海中搭建一个子版块的脚手架，然后尝试去明白一下这个东西。这是一个思维上的检查点，先确保你明白它是如何组合在一起的，如果感到无法理解，就请留言吧，让我看看我能为你做些什么。 找到合适的游戏在开发一个 MCTS 游戏智能体的背景下，我们可以把我们真正的程序看作是实现 MCTS 框架的代码，也就是 不过，为了测试我们的 MCTS 框架，我们需要选择一个特定的游戏，并使用该游戏运行我们的框架。我们希望看到 MCTS 框架在每个步骤中都做出对我们选择的游戏有意义的决策。 做一个井字游戏（
但是，井字游戏真的很无聊，不是吗？另外，你大概已经知道井字游戏的最佳策略，这就失去了一些吸引力。有这么多游戏可以选择，我们再选一个：四子棋（
在我们的实现中，我们将使用 Hasbro（孩之宝：美国著名玩具公司）的尺寸和规则，即是 6 行 7 列，其中垂直、水平和对角线棋子数相连为 4 就算胜利。棋子会从上方落下，并借助重力落在自底向上数的第一个空槽。 不过在我们继续讲述之前，要先说明一下。如果你有信心，你可以自己去实现任何你想要的游戏，只要它遵守给定的游戏 API。只是当你搞砸了，不能用的时候不要来抱怨。请记住，像国际象棋和围棋这样的游戏太复杂了，即使是 MCTS 也无法（有效地）独自解决；谷歌在 AlphaGo 中通过向 MCTS 添加有效的机器学习策略来解决这个问题。如果你想玩自己的游戏，你可以跳过接下来的两个部分。 实现四子棋游戏现在，直接将 虽然这不是本文的主要内容，但是你自己会如何构建呢？
注意，我们需要通过骨架文件 你可以独立思考完成或者直接使用我完成的 这是一个工作量很大的活，不是吗？至少对我来说是这样的。这段代码需要一些 JavaScript 知识，但应该还是很容易读懂的。最重要的工作在 我相信还有更好的方法。 运行四子棋游戏此时，我们将通过模拟 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 表示，这是为了方便 分析现在的状况我们已经实现一个带有 API 方法并且可以运行的游戏，这些 API 方法可以与
当然，我们还没有达到目的。刚才我们完成了一件非常重要的事情：让它设立一个切实的目标，并组成测试我们实现 MCTS 的核心模块。现在，我们进入正题。 实现蒙特卡洛树搜索在这里，我将按照 MCTS 详解中类似的组织方式，我也会在一些地方用自己的话来阐明某些观点。 实现搜索树节点
现在请你回顾树结构知识。MCTS 是一个树结构搜索，因此我们需要使用树节点。我们将在 /** 代表搜索树中一个节点的类。 */
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 })
}
}
...先再确认一下是否能够理解这些：
重要的是， 请注意，两个 现在我们将为 ...
/** 获取对应于给定游戏的 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方法可真多! 特别是， 通常你可以自己实现这些，也可以获取完成的 如果你刚获取到我完成的程序，请快速浏览一下源代码，就当是另一个心理检查点，重新梳理你的整体理解。这些都是简短的方法，你会在短时间内看懂它们。
尤其是 更新蒙特卡洛的类目前的版本是 monte-carlo-v1.js，只是一个骨架文件。该类的第一个更新是增加 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
}
...
...
/** 如果给定的状态不存在，就创建空节点。 */
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)
}
}
...最后，我们来到了算法的核心部分。引用第一篇文章的内容，以下是过程描述：
这四个阶段的算法反复运行，直至收集到足够的信息，产生一个好的移动结果。 ...
/** 从现有的统计数据中获得最佳的移动。 */
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 值最高的子节点，然后对所选子节点的子节点重复这个过程，以此类推。 当循环终止时，保证所选节点至少有一个未展开的子节点，除非该节点是叶子节点。这种情况是由调用函数 实现 MCTS 第二阶段：扩展
...
/** 第二阶段：扩展。随机展开一个未展开的子节点。 */
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
}
...再来看一下 那么如果是叶子节点，会发生什么呢？我们只需用在该节点中获胜的人进行反向传播 —— 无论是玩家 反向传播 实现 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
}
...因为这里没有保存任何东西，所以这主要涉及到 再看一下 实现 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这是影响下一次迭代搜索中选择阶段的部分。请注意，这假设是一个两人游戏，允许在 想一想，反向传播 实现最佳游戏选择
...
/** 从现有的统计数据中获得最佳的移动结果。 */
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
}
...需要注意的是，选择最佳玩法有不同的策略。这里所采用的策略在文献中叫做 实现统计自检和显示现在，你应该可以在当前版本 在 ...
// 工具方法
/** 返回该节点和子节点的 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这让我们可以查询一个节点及其直接子节点的统计数据。做完这些，我们就完成了 现在，将 接着运行 $ 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）的现状。 感谢你的阅读！
更多编程相关知识，请访问：编程入门！！ 以上就是浅谈Node.js如何实现蒙特卡洛树搜索的详细内容，更多请关注模板之家(www.mb5.com.cn)其它相关文章！ |
