围棋AI之路(三)UCT,进来之后才发现是地狱

xiaoxiao2021-03-01  2

照例还是先公布代码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程序而不是克制人类的。 相关资源:大学生计算机博弈-不围棋资料
转载请注明原文地址: https://www.6miu.com/read-3850142.html

最新回复(0)