用于运行monte carlo树搜索的库,传统的或具有专家策略的
imparaai-montecarlo的Python项目详细描述
python3库,用于运行Monte Carlo tree search,通常是通过向下钻取到游戏结束状态,或者使用神经网络提供的专家策略。
- 版本:1.3.1
蒙特卡罗树搜索基础知识
monte carlo树搜索(mcts)算法可以帮助从许多选项中做出决策。它通过随机抽样少量路径并选择获胜概率最高的移动来避免探索每一个可能的选择。这通常适用于象棋等游戏,如果你想赢得比赛,知道下一步该怎么做是有用的。
mcts的工作原理是展开搜索树,找出如果选中,哪些移动(或子/后续状态)可能产生肯定的结果。在时间允许的情况下,算法继续探索树,总是稍微偏向那些已经被证明是有成效的或者探索较少的方向。当时间不剩时,选择探索最多的方向。
可以用两种不同的方法展开搜索树:
- traditional:对于每个正在评估的移动,至少有一个随机卷展到游戏的结束状态(例如赢、输、平),以便算法可以做出选择。
- expert policy(即神经网络):请一位专家(例如神经网络)询问哪一个动作最有可能产生积极的结果,而不是昂贵地一直滚动到游戏的结束状态。
要深入了解这个主题,请查看this article。
这个库
作为此库的用户,您只需提供:
- 查找每个搜索树节点的直接子节点的函数(称为
child_finder
) - 用于计算节点的最终状态结果的函数(称为
node_evaluator
) --(神经网络不需要)
用法
创建新的蒙特卡罗树:
fromchessimportGamefrommontecarlo.nodeimportNodefrommontecarlo.montecarloimportMonteCarlochess_game=Game()montecarlo=MonteCarlo(Node(chess_game))
根节点描述您当前的游戏状态。此状态稍后将在child_finder
和node_evaluator
中使用。
为了演示,我们假设您有一个通用的Game
库,它可以告诉您哪些移动是可能的,并允许您执行这些移动来更改游戏的状态。
传统蒙特卡罗
添加child_finder
和node_evaluator
:
defchild_finder(node):formoveinnode.state.get_possible_moves():child=Node(deepcopy(node.state))#or however you want to construct the child's statechild.state.move(move)#or however your library worksnode.add_child(child)defnode_evaluator(self,node):ifnode.state.won():return1elifnode.state.lost():return-1montecarlo.child_finder=child_findermontecarlo.node_evaluator=node_evaluator
child_finder
应该向传递到函数中的父节点添加任何子节点(如果有)。如果没有,则父项应处于结束状态,因此node_evaluator
应返回一个介于-1
和1
之间的值。
专家政策(AI)
如果您有一个专家策略,可以在生成子级时将其应用于子级,则库将认识到不需要将代价高昂的钻取设置为最终状态。如果您的神经网络同时为子节点生成专家策略值和为父节点生成win值,则可以完全跳过声明node_evaluator
。
defchild_finder(self,node):win_value,expert_policy_values=neural_network.predict(node.state)formoveinnode.state.get_possible_moves():child=Node(deepcopy(node.state))child.state.move(move)child.player_number=child.state.whose_turn()child.policy_value=get_child_policy_value(child,expert_policy_values)#should return a probability value between 0 and 1node.add_child(child)node.update_win_value(win_value)montecarlo.child_finder=child_finder
模拟并做出选择
运行模拟:
montecarlo.simulate(50)#number of expansions to run. higher is typically more accurate at the cost of processing time
模拟运行后,您可以要求实例做出选择:
chosen_child_node=montecarlo.make_choice()chosen_child_node.state.do_something()
选择新的根节点后,可以在montecarlo
实例上覆盖它,并从树中的新位置进行更多模拟。
montecarlo.root_node=montecarlo.make_choice()
如果你正在训练一个神经网络,你可能想对游戏的前n步做一个更具探索性的选择:
montecarlo.root_node=montecarlo.make_exploratory_choice()
这不会提供一个纯粹的随机选择,相反,它将是随机的,偏向于更探索的路径。
回合制环境
如果您正在建模基于回合的环境(例如两人棋盘游戏),请在每个节点上设置player_number
,以便选择过程可以反转子赢值:
node=Node(state)node.player_number=1
这个数字是多少并不重要(您可以使用1和2或5和6),只要它与其他节点一致。
调整发现因子
构建新的子节点时,可以更改首选查找的速率:
node=Node(state)node.discovery_factor=0.2#0.35 by default, can be between 0 and 1
这个数字越接近1,在以后的模拟中,发现将比证明的价值更受青睐。