IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 4, NO. 1, MARCH 2012 9
Algorithm 2 The UCT algorithm.
function UCTSEARCH(s
0
)
create root node v
0
with state s
0
while within computational budget do
v
l
TREEPOLICY(v
0
)
DEFAULTPOLICY(s(v
l
))
BACKUP(v
l
, )
return a(BESTCHILD(v
0
, 0))
function TREEPOLICY(v)
while v is nonterminal do
if v not fully expanded then
return EXPAND(v)
else
v BESTCHILD(v,C p)
return v
function EXPAND(v)
choose a 2 untried actions from A(s(v))
add a new child v
0
to v
with s(v
0
)=f(s(v),a)
and a(v
0
)=a
return v
0
function BESTCHILD(v,c)
return arg max
v
0
2children of v
Q(v
0
)
N(v
0
)
+ c
s
2lnN(v)
N(v
0
)
function DEFAULTPOLICY(s)
while s is non-terminal do
choose a 2 A(s) uniformly at random
s f(s, a)
return reward for state s
function BACKUP(v, )
while v is not null do
N(v) N (v)+1
Q(v) Q(v)+(v, p)
v parent of v
Algorithm 3 UCT backup for two players.
function BACKUPNEGAMAX(v,)
while v is not null do
N(v) N (v)+1
Q(v) Q(v)+
v parent of v
search in Algorithm 3. Similarly, the node reward value
Q(v) may be treated as a vector of values for each player
Q(v, p) should circumstances dictate.
3.3.2 Convergence to Minimax
The key contributions of Kocsis and Szepesv
´
ari [119],
[120] were to show that the bound on the regret of UCB1
still holds in the case of non-stationary reward distribu-
tions, and to empirically demonstrate the workings of
MCTS with UCT on a variety of domains. Kocsis and
Szepesv
´
ari then show that the failure probability at the
root of the tree (i.e. the probability of selecting a subop-
timal action) converges to zero at a polynomial rate as
the number of games simulated grows to infinity. This
proof implies that, given enough time (and memory),
UCT allows MCTS to converge to the minimax tree and
is thus optimal.
3.4 Characteristics
This section describes some of the characteristics that
make MCTS a popular choice of algorithm for a variety
of domains, often with notable success.
3.4.1 Aheuristic
One of the most significant benefits of MCTS is the
lack of need for domain-specific knowledge, making it
readily applicable to any domain that may be modelled
using a tree. Although full-depth minimax is optimal in
the game-theoretic sense, the quality of play for depth-
limited minimax depends significantly on the heuristic
used to evaluate leaf nodes. In games such as Chess,
where reliable heuristics have emerged after decades
of research, minimax performs admirably well. In cases
such as Go, however, where branching factors are orders
of magnitude larger and useful heuristics are much
more difficult to formulate, the performance of minimax
degrades significantly.
Although MCTS can be applied in its absence, sig-
nificant improvements in performance may often be
achieved using domain-specific knowledge. All top-
performing MCTS-based Go programs now use game-
specific information, often in the form of patterns (6.1.9).
Such knowledge need not be complete as long as it is
able to bias move selection in a favourable fashion.
There are trade-offs to consider when biasing move
selection using domain-specific knowledge: one of the
advantages of uniform random move selection is speed,
allowing one to perform many simulations in a given
time. Domain-specific knowledge usually drastically re-
duces the number of simulations possible, but may also
reduce the variance of simulation results. The degree
to which game-specific knowledge should be included,
with respect to performance versus generality as well as
speed trade-offs, is discussed in [77].
3.4.2 Anytime
MCTS backpropagates the outcome of each game im-
mediately (the tree is built using playouts as opposed
to stages [119]) which ensures all values are always up-
to-date following every iteration of the algorithm. This
allows the algorithm to return an action from the root at
剩余48页未读，继续阅读
ShayneLee8
- 粉丝: 22
- 资源: 4
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
