有兴趣做揭棋吗?

[miaosiSari]

您好! 我将您的elephant_pvs.py文件二次开发，用于揭棋:

https://github.com/miaosiSari/Jieqi

这款AI是基于您写的elephant_pvs.py程序开发的，效果一般般(我自己水平问题)，和我下大概四六开(我揭7水平)。不过这个AI还是学会了一些基本逻辑，比如优先翻动暗兵，暗炮进四等。考虑到我只在这款AI的算法设计部分花了不到一天时间，效果还是值得期待的。如果您有兴趣，可以交流一下揭棋版本的开发，揭棋是非完美博弈，挑战性更强。

[bupticybee]

挺有意思的版本，让我看看～我自己一直在研究非完美博弈 ps：GPL V3 的license并不是我本人的意图，是我参考（抄袭）的sunfish 的license，我基于sunfish开发所以使用

[miaosiSari]

0529版本修复了一些bug，棋力相比于v2版本有很大提高。

[bupticybee]

0529版本修复了一些bug，棋力相比于v2版本有很大提高。

我比较好奇，在搜索的时候不会看到未来揭开的子力么？

[miaosiSari]

不会的，mapping只用于UI，不用于AI。

AI会把揭开的子当成一个"不确定子"。红方的不确定子用'U'标记，黑方的不确定子用'u'标记 当前的算法做了一个粗略的假设, 即不确定子都不会移动，当个木桩杵在那里。不确定子在某处的价值等于该处所有可能的明子的加权平均。比如当前黑方还剩2个暗子，从1个车2个炮中均匀采样，还有一个子已经被吃掉(AI不知道是什么)。那么，不确定子在该处的价值就等于(车在该处的价值+炮在该处的价值*2)/(1+2) = (车在该处的价值+炮在该处的价值*2)/3。

AI同时也会计算吃掉暗子的变化。AI不知道将会吃到什么，但是它知道对方剩余暗子的集合，因为AI知道它过去吃到了什么子。所剩暗子的价值=对方剩余子力在所有位置的平均价值/折扣因子。折扣因子是一个大于1的超参数，目前看来1.5比较合适。折扣因子的作用是鼓励翻动明子。同样是炮，在底线睡大觉肯定不如翻出来作战。

我发现在揭棋游戏中搜索宽度的意义大于搜索深度。事实上，在揭棋中，搜索太深带来的积极作用是有限的，5层足够了(depth=5)。目前我正在考虑一种双递归搜索。大致的思路是，先搜索两层(调用alphabeta)，然后将两层后得到的盘面具体化，把不确定子按照概率全部变成明子(调用一个改进的evaluate函数), 变成明子 后再调用alphabeta函数完成三层搜索。伪代码如下: pseudocode.txt

[bupticybee]

不会的，mapping只用于UI，不用于AI。

AI会把揭开的子当成一个"不确定子"。红方的不确定子用'U'标记，黑方的不确定子用'u'标记 当前的算法做了一个粗略的假设, 即不确定子都不会移动，当个木桩杵在那里。不确定子在某处的价值等于该处所有可能的明子的加权平均。比如当前黑方还剩2个暗子，从1个车2个炮中均匀采样，还有一个子已经被吃掉(AI不知道是什么)。那么，不确定子在该处的价值就等于(车在该处的价值+炮在该处的价值2)/(1+2) = (车在该处的价值+炮在该处的价值2)/3。

AI同时也会计算吃掉暗子的变化。AI不知道将会吃到什么，但是它知道对方剩余暗子的集合，因为AI知道它过去吃到了什么子。所剩暗子的价值=对方剩余子力在所有位置的平均价值/折扣因子。折扣因子是一个大于1的超参数，目前看来1.5比较合适。折扣因子的作用是鼓励翻动明子。同样是炮，在底线睡大觉肯定不如翻出来作战。

我发现在揭棋游戏中搜索宽度的意义大于搜索深度。事实上，在揭棋中，搜索太深带来的积极作用是有限的，5层足够了(depth=5)。目前我正在考虑一种双递归搜索。大致的思路是，先搜索两层(调用alphabeta)，然后将两层后得到的盘面具体化，把不确定子按照概率全部变成明子(调用一个改进的evaluate函数), 变成明子 后再调用alphabeta函数完成三层搜索。伪代码如下: pesudocode.txt

你的理解很深入，我认为你这里说的太深没用可能由于暗子不动的假设太强了，这样搜索得越深其实过拟合风险越大，所以深度并无卵用

关于两层后得到的盘面具体化，本身是合理的，但是我比较担心的一点是如果随机具体化的话，是不符合纳什均衡的，可能得手动写一些规则，比如用一些悲观或者乐观预测，理论上只要加权的考虑了悲观情况和乐观情况，某种程度上也可能让ai从规则里涌现出来

[bupticybee]

不会的，mapping只用于UI，不用于AI。

AI会把揭开的子当成一个"不确定子"。红方的不确定子用'U'标记，黑方的不确定子用'u'标记 当前的算法做了一个粗略的假设, 即不确定子都不会移动，当个木桩杵在那里。不确定子在某处的价值等于该处所有可能的明子的加权平均。比如当前黑方还剩2个暗子，从1个车2个炮中均匀采样，还有一个子已经被吃掉(AI不知道是什么)。那么，不确定子在该处的价值就等于(车在该处的价值+炮在该处的价值2)/(1+2) = (车在该处的价值+炮在该处的价值2)/3。

AI同时也会计算吃掉暗子的变化。AI不知道将会吃到什么，但是它知道对方剩余暗子的集合，因为AI知道它过去吃到了什么子。所剩暗子的价值=对方剩余子力在所有位置的平均价值/折扣因子。折扣因子是一个大于1的超参数，目前看来1.5比较合适。折扣因子的作用是鼓励翻动明子。同样是炮，在底线睡大觉肯定不如翻出来作战。

我发现在揭棋游戏中搜索宽度的意义大于搜索深度。事实上，在揭棋中，搜索太深带来的积极作用是有限的，5层足够了(depth=5)。目前我正在考虑一种双递归搜索。大致的思路是，先搜索两层(调用alphabeta)，然后将两层后得到的盘面具体化，把不确定子按照概率全部变成明子(调用一个改进的evaluate函数), 变成明子 后再调用alphabeta函数完成三层搜索。伪代码如下: pesudocode.txt

我觉得你做的很好，但是我建议要至少需要量化每个版本更改后的实力差距，主观判断一来成本高（需要高质量人机对局），二来方差大，建议是有一个不同算法之间的对弈机制，精确计算出实力差距，这个可以参考我的这段代码 https://github.com/bupticybee/elephantfish/blob/e6e04d3a69a985fd7b225095e7c16973a2752664/test.py#L69

[miaosiSari]

等到年底经费足够了，就吃进两块显卡和一台强力工作站。用这台工作站和minmax算法做self-play，可以生成一些数据做supervised learning。目前它后手和我5.5 4.5开。

[bupticybee]

等到年底经费足够了，就吃进两块显卡和一台强力工作站。用这台工作站和minmax算法做self-play，可以生成一些数据做supervised learning。目前它后手和我5.5 4.5开。

既然说到了算法，我也想问两个问题 （1）alphabeta，MTD二分这两个是elephantfish里边的算法，而且在我的测试里MTD性能更优，为什么你现在的版本选择了alphabeta（pvs）而不是MTD？ （2）min-max是比较低级的算法，实际用的时候不太可能比alphabet和MTD好，为什么打算用minmax替换现有算法？

[bupticybee]

等到年底经费足够了，就吃进两块显卡和一台强力工作站。用这台工作站和minmax算法做self-play，可以生成一些数据做supervised learning。目前它后手和我5.5 4.5开。

既然说到了算法，我也想问两个问题 （1）alphabeta，MTD二分这两个是elephantfish里边的算法，而且在我的测试里MTD性能更优，为什么你现在的版本选择了alphabeta（pvs）而不是MTD？ （2）min-max是比较低级的算法，实际用的时候不太可能比alphabet和MTD好，为什么打算用minmax替换现有算法？

另外如果在意性能建议把python代码全部用c重写，可以快一个多数量级，至少同等时间思考层数可以多个一两层吧，随着你的改进，性能迟早会成为瓶颈

[miaosiSari]

目前还没有媲美商业软件的打算——时间有限呀。有个鹏飞揭棋做的很不错的，我花了500块买的，我的下不过他。 用C写再加上多进程，性能大幅提升，就是时间有点久，用C写就算把现在的全部重写一遍估计得几个月吧。关键是，python版本的代码尚未调到最忧。 我不知道MTD比PVS更快。。。我以为algorithms/文件夹里面的代码更高端。我在博弈程序方面是新手。 我用的alphabeta应该是基于minmax的，或者说是minmax系列算法，我这么理解的。

[bupticybee]

目前还没有媲美商业软件的打算——时间有限呀。有个鹏飞揭棋做的很不错的，我花了500块买的，我的下不过他。 用C写再加上多进程，性能大幅提升，就是时间有点久，用C写就算把现在的全部重写一遍估计得几个月吧。关键是，python版本的代码尚未调到最忧。 我不知道MTD比PVS更快。。。我以为algorithms/文件夹里面的代码更高端。我在博弈程序方面是新手。 我用的alphabeta应该是基于minmax的，或者说是minmax系列算法，我这么理解的。

嗯嗯，MTD好一些，但没有好很多，用pvs也无所谓，实际上algorithms里边的代码之所以呆在里边也是因为性能不够好

[miaosiSari]

我想请教一下，在没有空着裁剪的情况下，搜索层数是不是偶数比较好?如果是奇数，最后一步该ai走，ai可能走出个弃车砍炮的荒唐棋，然后得分还不低(因为最后评分的时候车还在盘面上，如果玩家再走一步就能把车吃掉)。

[bupticybee]

我想请教一下，在没有空着裁剪的情况下，搜索层数是不是偶数比较好?如果是奇数，最后一步该ai走，ai可能走出个弃车砍炮的荒唐棋，然后得分还不低(因为最后评分的时候车还在盘面上，如果玩家再走一步就能把车吃掉)。

毕竟双方都会有这个问题，最后一步应该来说不管是哪方行动都有可能导致估计不准，我印象里象眼（eleeye）里吃子是分吃有根子和无根子的，理论上两者分值肯定很不同，可能可以借鉴类似的逻辑去搞

[miaosiSari]

相比于商业程序(我自己买过一个九代专业版的旋风和鹏飞揭棋), 感觉您这个程序还是有点慢～。通过Code Review, 我个人认为您的代码写得非常好，我在想到底是哪里的问题? CPython肯定是一个大头, PyPy快不少，但也慢，毕竟都用Pyobject管理的。此外，商业软件多进程可能也是一个大头，Python都没有真正的多核多进程。最后，商业软件有后台思考，玩家走棋的时候电脑都思考的差不多了。但我也不知道会不会有其他因素。

大佬方便加个微信好友吗?

[bupticybee]

相比于商业程序(我自己买过一个九代专业版的旋风和鹏飞揭棋), 感觉您这个程序还是有点慢～。通过Code Review, 我个人认为您的代码写得非常好，我在想到底是哪里的问题? CPython肯定是一个大头, PyPy快不少，但也慢，毕竟都用Pyobject管理的。此外，商业软件多进程可能也是一个大头，Python都没有真正的多核多进程。最后，商业软件有后台思考，玩家走棋的时候电脑都思考的差不多了。但我也不知道会不会有其他因素。

大佬方便加个微信好友吗?

性能问题自然是一方面，改成cpp能快10倍多，但是肯定是不够的

继续优化这里涉及到的东西就很多了，包括局面评估，启发式剪枝算法，如果你真的感兴趣可以去看象眼的代码，有c++，javascript版本，javascript版本代码量比较少，可能对你会有启发作用，但是我一直没完全搞懂其js版本，我测试过象眼js版本同等搜索深度下棋力吊打elephantfish，我甚至去掉了js版本的开局库对比，一样吊打，所以elephantfish肯定还是有很多没优化完全或者有bug的地方

可以加下我微信892009517

[bupticybee]

关闭issue由于讨论已经结束