Smarthings事脉顺-业务建模的目标

关键字：程序开发

UCT是怎么走对征子的呢？
我想，elife前辈的话一定是对的，否则，MC法不可能有目前的领先地位，一定是有某些地方我们还没有理解到位，出了差错。
关于我提出的问题，其实不仅仅是征子的问题，征子只是我用来说明问题的例子，我的问题是：一个导致必胜的着手,一定是在后续的各种任意下法中,胜率最高的着手吗?
我还不知道我的思路哪里出了问题，仅仅是相信elife的结论性判断，并不能立即帮助我解决我的算法问题，我还得继续找问题的原因。
先从正面理解一下：一个导致必胜的着手,一定会是在后续的各种任意下法中,胜率最高的着手，难道不是吗?
这里面可能有概念偷换问题：

一个我们看起来必胜的着手，尽管导致从它开始，直到取得最终胜利的路径，在最极端的情况下，可能只有唯一的1条，虽然和其他可能的行棋路经相比，这条路经 可能是万亿分之一的选择，也许考虑其他的所有路径确实会发现导致失败的路径数更多，但这种“最终导致胜利的路径的多少“和“模拟下棋得到胜利次数的多少” 也许并不是同一个概念。如果我们偷换了这两个概念，就会得到象我之前得到的那种令人疑惑的结果。

为什么这么说？
MC法确实是在已经生成的博弈树上当前结点的所有后续结点中，选择胜率最高的结点为生成着手来决定下一步棋走在哪里的,这容易使我们理解为决定下一着手的唯一依据,就是最高胜率的子结点是谁?你一定会问,难道不是吗?

当然是的,但是,我们有没有想过,一个结点可能发展的后续子子孙孙的结点是个天文数字,凭什么就让某些结点出现在博弈树上,而其他结点就要无情地被"冷落 "呢?(严格地说,UCT算法不是在剪枝,而是在冷落或培植相关的枝),这个"凭什么"的理由,不是比"子结点胜率"更优先的决定着手选择的理由吗?如果 你是一个仅仅在理论上存在的结点,但没有在博弈树上得到"定点"培养的机会,那么,你就压根不可能出现在博弈树上,虽然理论上有很多路会经过你,而且从你 之后也有很多路可走,但这些只是"可能存在的路"而已,对"实际发生的胜率"有什么影响呢?没有任何影响.
而只有那些已经出现在博弈树上的后续结点和未来实际出现在博弈树上的后续结点,才可能对子结点的胜率产生影响.

后续子结点是如何产生的以及其胜率是如何得到计算的,才是决定后续着手的关键原因.这些工作是在下类似17000盘这么个数量巨大的模拟对局的过程中完成的.对这个过程,我原先有这么个误解:认为在模拟对局中,每走一步棋,都会试图在博弈树上去添加新的结点(只要这步棋对应的结点还没有出现在博弈树上),这个误解是致命的,Dlgo曾经成功地启发我走出了这个误解.

实际上,只有在模拟对局中,遇到了某个已经建立的而且访问过[已选择过这个结点进行过一次脱离博弈树的随机对局(所有结点的第一次访问一定是这样发生的)]的"端"结点(没有子结点,但模拟对局还没有终止)的时候,才会去为这个端结点,建立一层后续的子结点,在这层新建的子结点中,随机选择一个结点(这个结点就发生了首次被访问的事件)作为继续前进的路径后,随后的随机对局过程就不再博弈树上进行了,也不再影响博弈树了,只有最终输赢的结果会影响已经走过的路径上的结点的胜率.
因为生成一个着手,要从生成前的博弈树上的结点开始,模拟下17000多盘棋,所以,在

下过前面的具有"开闯新路"性质(为博弈树某个结点新增一层子结点)的一局棋后(开路后那局棋就转到随机对局中去了),后续的模拟对局,开始就会沿着前面对局已经开辟的道路选择前进的方向了,这时候的选择,就不完全是随机选择了,而是根据经过调整的前面累积得到的胜率数(UCT值)来选择了,所以,第二个要搞清楚的概念区别是:模拟对局和随机对局不是一回事,随机对局是模拟对局的一部分,是在模拟对局遇到"端结点"之后独立于博弈树所进行的部分.
而每一次进行的模拟对局都会返回谁胜谁负的结果,这个结果,就会影响对局过程在博弈树上经历过的结点的被访问次数和取胜次数,从而影响各层结点的胜率.
等到1700盘模拟对局全部结束后,这时候,就只要简单地选择下一个胜率最高的着手作为应对着手了,随后等待对手下棋,对手下的棋一定会出现在博弈树上, 而且一定会被访问过(为什么?有问的我包回答,暂时不展开分析),所以,再下一步生成着手的时候,只要找到和对手下的上一步棋对应的结点就可以了.

搞清楚了博弈树产生的过程和胜率的来由后,再来看原来的问题,就好理解了.用一个比喻来理解可能会更形象.比如：
假设两个天老爷举行下雨比赛,他们能下的雨有两种，一种金雨，很贵，很少；一种普通雨，很多，很便宜。谁能把他的金子雨最先全流到大海，就算谁赢,那么, 聪明一点的老天爷就会想到,他应该在下这每粒滴金雨之前，下很多的普通雨，探明最好的河该怎么流，那么，聪明的老天应该把这很多的普通雨更多地撒向什么地 方呢?
刚开始,地上没有河,老天只好乱下普通雨，后来出现一段河流，也是先前下的雨流出来的，所以，后面下的雨就尽量靠近已经产生的河，就更好，但也不能全下在 原来的河里面，因为，没准还有更近更快的河道还没有被发现，所以要调整下雨的地点，尽量靠近河，但也要照顾河边从来没有下过雨的地方，让那些地方也可以尝 试流一流水，如果成功，那些地方今后自然能成为主流。等这段河到了头，比赛还没有结束的话，老天爷就只好又往后乱下一阵雨了，直到已经发现最好的河床，就 把下一颗金雨，下进这个河床，最终找到大海为止。

所以，虽然地上可能存在的河床路径的数量是个天文数字，老天爷不一定要把整个地面都变成河流，才能取得胜利，聪明一点的老天，总是一边选择走最好的河床， 一边选择靠近原来的最好的河床去探索新的河床，如果地面上确实存在一个地势最低，最直通往大海的河床，这个河床迟早会被聪明的老天发现，然后，越流河越 宽，而其他可能的河床，自然就被冷落了。

导致全局必胜的少有的着手路径,比如关键征子,就是这样的好"河床",最终会被很快地自然发现的.