mcts下载 - mcts源码下载

使用 Python 代码的蒙特卡洛树搜索 (MCTS) 算法教程。应用MCTS为简单游戏创建AI。

在本教程中，我们将解释蒙特卡罗树搜索算法和代码的每个部分。最近我们应用MCTS来开发我们的游戏。

该代码是通用的，仅假设您熟悉基本的 Python。我们已经针对我们的游戏进行了解释。如果你想将它用于你的项目或游戏，你将不得不稍微修改我下面提到的功能。

以下是该游戏的 Playstore 链接：Sudo Tic Tac Toe。

我们的游戏规则（模式1）如下：

该游戏像数独一样在 9 x 9 的网格上进行。
这个大的 9 × 9 网格被分成 9 个较小的 3 × 3 网格（局部板）。
游戏的目标是赢得 9 个本地棋盘中的任何一个。
你的举动决定了人工智能必须在哪个本地棋盘上采取行动，反之亦然。
例如，您在本地 5 号棋盘的位置 1 下棋。这将迫使 AI 在本地棋盘 1 号下棋。
普通井字游戏的规则适用于当地棋盘。

为什么选择MCTS？

正如您所看到的，这款游戏具有非常高的分支因子。对于第一步，整个棋盘都是空的。所以有81个空位。第一回合有 81 种可能的动作。对于第二回合，应用规则 4，它有 8 或 9 种可能的移动。

对于前 2 个动作，这会产生 81*9 = 729 种可能的组合。因此，随着游戏的进行，可能的组合数量会增加，从而产生高分支因子。对于我们游戏的两种模式来说，分支因子都非常高。对于具有如此高分支因子的游戏，不可能应用极小极大算法。 MCTS 算法适用于此类游戏。

另外，正如您在玩游戏时所看到的那样，人工智能采取行动所需的时间大约只有一秒钟。因此 MCTS 运行速度很快。 MCTS 已应用于这两种游戏模式。

下面我们用Python演示MCTS代码。首先我们需要导入 numpy 和 defaultdict。

 import numpy as np
from collections import defaultdict

定义 MCTS 类，如下所示。

 class MonteCarloTreeSearchNode ():
    def __init__ ( self , state , parent = None , parent_action = None ):
        self . state = state
        self . parent = parent
        self . parent_action = parent_action
        self . children = []
        self . _number_of_visits = 0
        self . _results = defaultdict ( int )
        self . _results [ 1 ] = 0
        self . _results [ - 1 ] = 0
        self . _untried_actions = None
        self . _untried_actions = self . untried_actions ()
        return

构造函数用于初始化以下变量。

state ：对于我们的游戏，它代表棋盘状态。通常棋盘状态由数组表示。对于普通的 Tic Tac Toe，它是一个 3 x 3 的数组。
Parent ：对于根节点来说它是 None ，对于其他节点来说它等于它的派生节点。正如您从游戏中看到的，第一回合它是“无”。
Children ：它包含当前节点的所有可能的操作。对于我们游戏的第二回合，这是 9 或 8，具体取决于您的移动位置。
Parent_action ：对于根节点无，对于其他节点，它等于其父节点执行的操作。
_number_of_visits : 当前节点被访问的次数
结果：这是一本字典
_untried_actions ：表示所有可能操作的列表
action ：必须执行的移动。

类由以下成员函数组成。除main()函数外，以下所有函数都是成员函数。

 def untried_actions ( self ):

    self . _untried_actions = self . state . get_legal_actions ()
    return self . _untried_actions

返回给定状态下未尝试的操作的列表。我们游戏的第一回合有 81 种可能的动作。第二回合是 8 或 9。这在我们的游戏中有所不同。

 def q ( self ):
    wins = self . _results [ 1 ]
    loses = self . _results [ - 1 ]
    return wins - loses

返回胜利 - 损失的差值

 def n ( self ):
    return self . _number_of_visits

返回每个节点被访问的次数。

 def expand ( self ):
	
    action = self . _untried_actions . pop ()
    next_state = self . state . move ( action )
    child_node = MonteCarloTreeSearchNode (
		next_state , parent = self , parent_action = action )

    self . children . append ( child_node )
    return child_node

根据所执行的操作，从当前状态生成下一个状态。在此步骤中，所有可能的状态都将附加到 Children 数组并返回 child_node。当前状态可能出现的状态都被追加到children数组中，并返回与该状态对应的child_node。

 def is_terminal_node ( self ):
    return self . state . is_game_over ()

这用于检查当前节点是否是终端。当游戏结束时到达终端节点。

 def rollout ( self ):
    current_rollout_state = self . state
    
    while not current_rollout_state . is_game_over ():
        
        possible_moves = current_rollout_state . get_legal_actions ()
        
        action = self . rollout_policy ( possible_moves )
        current_rollout_state = current_rollout_state . move ( action )
    return current_rollout_state . game_result ()

从当前状态开始，模拟整个游戏，直到出现游戏结果。返回该游戏结果。例如，如果结果获胜，则结果为 1。否则，如果结果失败，则结果为 -1。如果平局则为 0。如果整个游戏是随机模拟的，即在每个回合从一组可能的移动中随机选择移动，则称为轻游戏。

 def backpropagate ( self , result ):
    self . _number_of_visits += 1.
    self . _results [ result ] += 1.
    if self . parent :
        self . parent . backpropagate ( result )

在此步骤中，节点的所有统计信息都会更新。直到到达父节点，每个节点的访问次数加1。如果结果为1，即获胜，则获胜加1。否则，如果结果为失败，则失败增加 1。

 def is_fully_expanded ( self ):
    return len ( self . _untried_actions ) == 0

所有动作都从_untried_actions中一一弹出。当它变空时，即大小为零时，它就完全扩展了。

 def best_child ( self , c_param = 0.1 ):
    
    choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
    return self . children [ np . argmax ( choices_weights )]

一旦完全展开，该函数就会从子数组中选择最好的子数组。公式中的第一项对应于开发，第二项对应于探索。

 def rollout_policy ( self , possible_moves ):
    
    return possible_moves [ np . random . randint ( len ( possible_moves ))]

从可能的移动中随机选择一个移动。这是随机播放的示例。

 def _tree_policy ( self ):

    current_node = self
    while not current_node . is_terminal_node ():
        
        if not current_node . is_fully_expanded ():
            return current_node . expand ()
        else :
            current_node = current_node . best_child ()
    return current_node

选择要运行推出的节点。

 def best_action ( self ):
    simulation_no = 100
	
	
    for i in range ( simulation_no ):
		
        v = self . _tree_policy ()
        reward = v . rollout ()
        v . backpropagate ( reward )
	
    return self . best_child ( c_param = 0. )

这是最佳动作函数，它返回与最佳可能移动相对应的节点。上面的代码完成了展开、模拟和反向传播的步骤。

 def get_legal_actions ( self ): 
    '''
    Modify according to your game or
    needs. Constructs a list of all
    possible states from current state.
    Returns a list.
    '''

 def is_game_over ( self ):
    '''
    Modify according to your game or 
    needs. It is the game over condition
    and depends on your game. Returns
    true or false
    '''

 def game_result ( self ):
    '''
    Modify according to your game or 
    needs. Returns 1 or 0 or -1 depending
    on your state corresponding to win,
    tie or a loss.
    '''

 def move ( self , action ):
    '''
    Modify according to your game or 
    needs. Changes the state of your 
    board with a new value. For a normal
    Tic Tac Toe game, it can be a 3 by 3
    array with all the elements of array
    being 0 initially. 0 means the board 
    position is empty. If you place x in
    row 2 column 3, then it would be some 
    thing like board[2][3] = 1, where 1
    represents that x is placed. Returns 
    the new state after making a move.
    '''

 def main ():
    root = MonteCarloTreeSearchNode ( state , None , action )
    selected_node = root . best_action ()
    return

这是 main() 函数。初始化根节点，调用best_action函数获取最佳节点。这不是该类的成员函数。所有其他函数都是该类的成员函数。

MCTS 包含 4 个步骤：

精选

这个想法是不断选择最好的子节点，直到我们到达树的叶节点。选择此类子节点的一个好方法是使用 UCT（应用于树的置信上限）公式：

	wi/ni + c*sqrt(t)/ni

wi = 第 i 步棋后获胜的次数
ni = 第 i 次移动后的模拟次数
c = 探索参数（理论上等于√2）
t = 父节点的模拟总数

扩张：

当它无法再应用 UCT 来查找后继节点时，它会通过附加叶节点中的所有可能状态来扩展博弈树。

模拟：

扩展后，算法任意选择一个子节点，并从所选节点开始模拟整个游戏，直到达到游戏的结果状态。如果在播放过程中随机选取节点，则称为轻播放。您还可以通过编写质量启发式或评估函数来选择重度播放。

反向传播：

一旦算法到达游戏结束，它就会评估状态以确定哪个玩家获胜。它向上遍历到根并增加所有访问节点的访问分数。如果该位置的玩家赢得了比赛，它还会更新每个节点的获胜分数。

设计你的游戏：

如果您打算制作自己的游戏，您将不得不考虑以下问题。

您将如何表示您的游戏状态？想想我们游戏的初始状态。
您的游戏的最终游戏条件是什么？将其与我们游戏的最终游戏条件进行比较。
您将如何在游戏中获得法律诉讼？尝试为我们游戏的第一步采取法律行动。

须藤井字棋

如果您有任何疑问或建议，请随时通过 [email protected] 与我们联系

展开

mcts

使用 Python 代码的蒙特卡洛树搜索 (MCTS) 算法教程。应用MCTS为简单游戏创建AI。

为什么选择MCTS？

构造函数用于初始化以下变量。

精选

扩张：

模拟：

反向传播：

设计你的游戏：

waymo open dataset

SmartTube

Sunamu

viptools for eslam

MySchedule.py

VITAident

chat.petals.dev

GPT Prompt Templates

GPTyped

waymo open dataset

SmartTube

Sunamu

wp functions

slugify

termwind