uct算法

Ⅰ uct算法和蒙特卡洛算法的区别

他们有类似之处，但差别也不校 蒙特卡洛算法是数值计算方法，原理是利用随机数来解决计算问题。与它对应的是确定性算法。也就是说该种算法属于随机算法，得到的解是近似解。 而遗传算法、粒子群、模拟退火虽然也是随机近似算法，但这三种都是仿...

Ⅱ |阿尔法核心技术

一、 AlphaGo的两大核心技术
MCTS(Monte Carlo Tree Search)
MCTS之于围棋就像Alpha-Beta搜索之于象棋，是核心的算法，而比赛时的搜索速度至关重要。就像深蓝当年战胜时，超级计算机的运算速度是制胜的关键因素之一。

MCTS的4个步骤：Selection，Expansion，Evaluation(rollout)和Backup
MCTS的并行搜索：
(1) Leaf Parallelisation
最
简单的是Leaf Parallelisation，一个叶子用多个线程进行多次Simulation，完全不改变之前的算法，把原来的一次
Simulation的统计量用多次来代替，这样理论上应该准确不少。但这种并行的问题是需要等待最慢的那个结束才能更新统计量；而且搜索的路径数没有增
多。
(2) Root Parallelisation
多个线程各自搜索各自的UCT树，最后投票
(3) Tree Parallelisation
这是真正的并行搜索，用多个线程同时搜索UCT树。当然统计量的更新需要考虑多线程的问题，比如要加锁。
另
外一个问题就是多个线程很可能同时走一样的路径（因为大家都选择目前看起来Promising的孩子），一种方法就是临时的修改
virtual loss，比如线程1在搜索孩子a，那么就给它的Q(v)减一个很大的数，这样其它线程就不太可能选择它了。当然线程1搜索完了之后要记
得改回来。
《A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm》使用了一种lock-free的算法，这种方法比加锁的方法要快很多，AlphaGo也用了这个方法。
Segal
研究了为什么多机的MCTS算法很难，并且实验得出结论使用virtual loss的多线程版本能比较完美的scale到64个线程(当然这是单机一个
进程的多线程程序）。AlphaGo的Rollout是用CPU集群来加速的，但是其它的三个步骤是在一台机器完成的，这个就是最大的瓶颈。

Ⅲ 求UCT算法伪代码【类c或者纯汉语或者纯英语】，详细明白就可以，谢谢~~

MoGo计算机围棋程序使用的UCT算法的伪代码
function playOneSequence(rootNode)
node[0] := rootNode; i := 0;
do
node[i+1] := descendByUCB1(node[i]);
i := i+1;
while node[i] is not first visited;
createNode(node[i]);
node[i].value := getValueByMC(node[i]);
updateValue(node,-node[i].value);
end function;
摘自徐心和教授的<计算机围棋博弈的最新发展>

uct的文章去google学术搜索搜国外的,围棋(Go)方向的有很多