标签: monte-carlo-tree-search

TLDR

MCTS代理程序的实现在本地运行时没有错误，相对于启发式驱动的minimax，成功率达到了40％以上，但自动分级器却没有通过-这是提交项目之前的要求。自动平地机抛出IndexError: Cannot choose from an empty sequence。我正在寻找最有可能引发此异常的代码方面的建议。

嗨，我目前停留在这个项目上，我需要在2个星期的时间内完成该项目，然后才能完成所注册的程序的清理。我已经完成的任务是在两个国际象棋骑士之间的隔离游戏中实现一个代理，以与启发式驱动的minimax代理进行对抗。完整的游戏实施细节可以在这里找到。对于我的项目，将使用位板编码在9 x 11的板上玩游戏。我的MCTS实现非常简单，紧随本文（第6页）提供的伪代码。

本质上，一般的MCTS方法包括这4个部分，它们分别由CustomPlayer类中的以下嵌套函数实现：

1. 选择-tree_policy
2. 扩展-best_child，扩展
3. 模拟-default_policy

4. 反向传播-backup_negamax，update_scores

   import math
   import random
   import time
   import logging
   
   from copy import deepcopy
   from collections import namedtuple
   
   from sample_players import DataPlayer
   
   
   class CustomPlayer(DataPlayer):
       """ Implement your own agent to play knight's Isolation
       The get_action() method is the only required method for this project.
       You can modify the interface for get_action by adding named parameters
       with default values, but the …

   Run Code Online (Sandbox Code Playgroud)

因此，我使用 UCT 在蒙特卡罗树搜索算法中实现了转置表。这允许保持游戏状态的累积奖励值，无论在整个树中在何处以及多少次遇到它。这提高了收集到的特定游戏状态信息的质量。

唉，我注意到这给 UCT 的开发与探索选择阶段带来了某些问题。简而言之，分配给某个州的 UCT 分数会考虑访问父州的次数与访问子州（我们为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，当将状态从转置表拉入树的新创建的分支时，该比率完全不正常，子状态已被访问大量次（从树中的其他位置）并且父状态已被访问被访问的次数要少得多，这在技术上应该是不可能的。

因此，使用换位表并保留状态的累积奖励值有助于算法的利用部分做出更好的选择，但同时它会以潜在有害的方式扭曲算法的利用部分。您知道有什么方法可以解决这个意外问题吗？

我在一定程度上理解算法的工作原理.我不完全理解的是算法是如何在实践中实际实现的.

我有兴趣了解一个相当复杂的游戏(也许是象棋)的最佳方法.即递归方法？异步？同时？平行？分散式？数据结构和/或数据库？

- 我们期望在一台机器上看到什么类型的限制？(我们可以同时在多个核心上运行......也许是gpu？)

- 如果每个分支都会产生一个全新的游戏,(这可能达到数百万)我们如何保持整个系统的稳定？我们如何重用已经播放的分支？

我正在尝试实现蒙特卡洛树搜索来在Python中玩井字棋。我目前的实现如下：

我有一个 Board 类来处理井字游戏板的更改。棋盘的状态由 2x3x3 numpy 数组表示，其中 2 个 3x3 矩阵中的每一个都是二进制矩阵，分别表示 X 的存在和 O 的存在。

class Board:
  '''
  class handling state of the board
  '''

  def __init__(self):
    self.state = np.zeros([2,3,3])
    self.player = 0 # current player's turn

  def copy(self):
    '''
    make copy of the board
    '''
    copy = Board()
    copy.player = self.player
    copy.state = np.copy(self.state)
    return copy

  def move(self, move):
    '''
    take move of form [x,y] and play
    the move for the current player
    '''
    if np.any(self.state[:,move[0],move[1]]): return
    self.state[self.player][move[0],move[1]] = …

我已经为 4 人游戏实现了 MCTS，该游戏运行良好，但当游戏结束移动位于实际树中而不是在推出中时，我不确定我是否理解扩展。

在游戏开始时，游戏获胜/失败的位置只能在推出中找到，我了解如何对这些进行评分并将它们传播回树上。但随着游戏的进行，我最终找到了一个由 UCB1 选择的叶节点，它无法扩展，因为它是一个失败的位置，不允许任何移动，因此没有任何东西可以扩展，也没有游戏可以“推出”。目前，我只是将此视为最后剩下的玩家的“胜利”，并为他们反向传播胜利。

然而，当我查看访问统计信息时，该节点被重新访问了数千次，因此显然 UCB1“选择”多次访问该节点，但实际上这有点浪费，我是否应该反向传播除单个节点之外的其他内容赢得这些“永远获胜”的节点？

我对此进行了很好的谷歌搜索，但找不到太多提及它的内容，所以我是否误解了某些东西或遗漏了一些明显的东西，“标准”MCTS教程/算法甚至没有提到树中的游戏结束节点作为特殊情况，所以我担心我误解了一些基本的东西。

为了让其他人轻松地帮助我， 我将所有代码都放在此处https://pastebin.com/WENzM41k ，它将在2个代理相互竞争时开始。

我正在尝试实现Monte Carlo树搜索以在Python中播放9板tic-tac-toe。游戏规则类似于常规的井字游戏，但带有9个3x3子板。最后一块的放置位置决定放置一块子板。这有点像最终的井字游戏，但如果赢得了一个分牌，游戏就会结束。

我正在尝试学习MCTS，并且在这里找到了一些代码：http : //mcts.ai/code/python.html

我在网站上使用了节点类和UCT类，并添加了我的9局井字游戏状态类和一些其他代码。所有代码都在这里：

from math import log, sqrt
import random
import numpy as np
from copy import deepcopy


class BigGameState:
    def __init__(self):
        self.board = np.zeros((10, 10), dtype="int8")
        self.curr = 1
        self.playerJustMoved = 2 # At the root pretend the player just moved is player 2 - player 1 has the first move

    def Clone(self):
        """ Create a deep clone of this game state.
        """
        st = BigGameState()
        st.playerJustMoved = self.playerJustMoved
        st.curr = …

我有一个“门牌号”的优先队列。我从优先级队列中（即对应优先级值最低的门）得到隔壁门号，然后开门。门后可能有礼物，也可能没有。根据礼物的存在/不存在，更新此门号的优先级，并将其放回优先级队列。然后我重复一遍，打开隔壁的门号，依此类推。

假设每扇门都有不同的礼物补货率（即有些可能每天都收到新礼物，有些则根本没有），我应该如何更新优先级值以最大化我找到的礼物数量？也就是说，我想最大化我有礼物打开的门与没有礼物打开的门的比例。

我应该指出，补货率不能保证随着时间的推移而固定/存在随机变化。但我可以在这里简化假设。

这对我来说几乎像是一个蒙特卡洛问题，只是我探索一个节点（门）的次数越多，它的期望值就越低。（当然，没有要构建的树；我们只需要计算 depth-1 节点的值。）

最简单的方法是跟踪上次优先级 (LP) 和当前优先级 (CP)，其中 delta = CP - LP。如果我们找到礼物，则设置下一个优先级 NP = CP + delta - 1；否则设置 NP = CP + delta + 1。我猜这是可行的，但它的优化似乎相当缓慢。

或者我们可以有一个乘法值：NP = CP + delta *shrink 或 NP = CP + delta *grow，其中shrink < 1 和grow > 1。这就是我目前所拥有的，它似乎可以正常工作几个月，但现在我遇到了一些门被背对背打开的情况（即打开门 D，找到礼物，放回优先队列，D 现在再次成为最佳选择，当然没有找到礼物，现在放回去在优先级较差的队列中），这看起来很糟糕。作为参考，我使用了shrink = 0.9 和grow = 1.3。

是否有数学公式（如蒙特卡罗）表达探索门的最佳方式？

尝试使用像这样的 YouTube 视频和论文来学习 MCST。

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf

然而，除了高级理论解释之外，我并没有多少运气来理解细节。这是上面论文的一些引述和我的问题。

1. 选择阶段：MCTS 迭代选择当前状态得分最高的子节点。如果当前状态是根节点，那么这些孩子首先来自哪里？你不会有一棵只有一个根节点的树吗？只有一个根节点，您是否会立即进入扩展和模拟阶段？

2. 如果 MCTS 在选择阶段选择得分最高的子节点，那么在沿着树的级别向下时，您永远不会探索其他子节点甚至可能是全新的子节点？

3. 节点的扩展阶段如何发生？上图中，为什么不选择叶子节点而是决定给叶子节点添加一个兄弟节点呢？

4. 在模拟阶段，随机策略用于为两个玩家选择合法的移动，直到游戏终止。这种随机策略是否是一种硬编码行为，并且您基本上是在模拟中掷骰子以选择每个玩家之间轮流直到最后的可能动作之一？

5. 我的理解是从单个根节点开始，通过重复上述阶段将树构建到一定深度。然后你选择第二级得分最好的孩子作为你的下一步。您愿意构建的树的大小基本上是您的硬 AI 响应要求，对吗？因为在构建树时，游戏将停止并计算这棵树。