围棋AI之路（三）UCT，进来之后才发现是地狱

照例还是先公布代码http://download.csdn.net/source/913373

以及编译好的可执行程序，下载地址：http://download.csdn.net/source/913515

前面介绍的UCT算法听起来很诱人，但是只有你真正去实验一下你才知道原来有这么多问题。

理论上，UCT是一个一致的算法，它可以随着模拟次数的增加而自然提高棋力，而且理论上，它还可以计算到任意深度，而且理论上，它是天然支持并行计算的。

但是，看看它华丽的外衣下面隐藏着哪些东西吧：

一、模拟速度和内存问题

目前的模拟速度是让我满意的，但是内存跟不上，9路棋盘上的5万局模拟+UCT选择，也只需要1秒多时间，10万局也就差不多3秒钟，但是，如果我想持续进行120秒的模拟，1G的内存也是不够用的。

给我的感觉这个算法需要的内存比并行运算更重要，两个CPU分别模拟5万次和1个CPU独自模拟10万次，结果是不同的。如果我有64位的内存，我觉得这个算法的前景会很可观。

随后我自己想了一种方法来在有限的内存中模拟较长的时间，就是发现内存将要用完时，把胜率不佳的子树砍掉。但是这个改动破坏了算法的一致性，我用围棋试验的结果就是，AI超喜欢把棋连成一根长棍，而且走棋过程中自我感觉良好，快终局时胜率突然下降到投子认负。这应该就是瞎砍树导致模拟结果失去意义了。

二、模拟的收敛性

这么来定义这个收敛性吧，如果一番模拟下来，所有子节点都差不过，没有什么突出的，这就是收敛性差，反之，有少量节点的表现很突出，那么这个模拟的收敛性就好。

纯发散的模拟在五子棋中就是一例：我为五子棋模拟定的简单规则就是随便下，成五则胜。但是模拟结果几乎毫无意义，导致棋盘中间的子的胜率和棋盘边缘的没什么差别。我只好把模拟规则改一下，双方模拟的时候，只在对方和己方棋子的周围随机下棋，AI的棋力马上得到提高，不过这和MC的精神是相冲突的。

另外影响收敛性的还有一个因素，你怎么为节点打分？

目前有两种打分策略：输赢都计分和只记赢局的分。前者收敛性好，但使得AI的行为非常保守，后者收敛性差，而且使得AI冒进。

冒进的例子就是五子棋中，对手活三，AI也活三。

保守的例子还是围棋中的把棋连成棍。

三、模拟的深度

深度和广度是有矛盾的，为了模拟的深一点，AI就要抛弃一些点，这和传统博弈程序是一致的，如前面说的五子棋的模拟，仅局限在棋子周围，则模拟深度很容易就达到9步，但是这样一来，AI就漏掉了有一定间隔的好手了。但是如果把“周围”的范围放宽，模拟深度又上不去。

至今困扰我的两个问题，不知道是不是与深度有关：

问题一，为什么五子棋中AI在自己棋势很好的时候，总是不挡对方的活三呢？

问题二，为什么围棋中，AI能征吃对方的子，但是它自己老做出逃征子(术语:ladder)的事呢？

四、模拟的置信度

在为一个节点做模拟时，是只模拟一次还是模拟多次呢？这在代码中称为节点的成熟度(mature)。如果次数少，则结果的置信度很成问题，次数太多，深度深度又成问题。

而且我发现，围棋中，次数少时效果较好，而五子棋中则是次数多一点效果比较好。

五、接下来怎么改进

在UCT的深渊中挣扎，代码被改的一团糟，因为太多参数可调，搞的写程序变成了做测试。现在我还有几根救命稻草可用。

1 不知道能不能找到完美的砍树算法，使得在节点内存不够时的砍树不要造成太大影响。

2 把树换成图来存储节点，也就是UCG，不知道能有多大帮助。

3 并行，是多个单元独立维护各自的树，还是通过线程互斥让它们更新同一棵树呢？我总觉得多个单元独立运算就像是狼群去和虎斗一样，对它没什么信心。

4 AMAF，算是UCT的一种改进，据说能用较少的模拟次数来得到更多的结果。

5 还有一种思路是将模拟中出现的难解局面抛给对方，自己只选择容易处理的局面，不过这种思路似乎更像是克制MC程序而不是克制人类的。