参赛程序思路

kiraja

很久之前楼主参加过一次五子棋比赛，不过效率极低，算一步可以二十分钟，而且放现在看也是依托💩山所以这次干脆直接重写了





主要的思路和之前一样，就是算杀，不断地去搜索进攻点（和防守点）来找到一个必胜的策略

由于之前的算杀搜索每一层都把可以用到的进攻点考虑进去，所以会出现大量冗余的计算：比如说我有5个进攻点，在不考虑新增进攻点的情况下，在第一层选择1个进攻点第二层还有4个进攻点，所以时间复杂度可以达到O(n!)，可以说是烂到不能再烂了

所以这次花了大量功夫在搜索优化和剪枝上，一开始我只允许下一层搜索只用上一步进攻新增出来的进攻点，效率一下子高了很多，可以轻松算10层，但是会频频出现漏算的情况，所以把可用进攻点拓宽了一下，把和上一个进攻点相关的进攻点，即在一条线上距离也不超过5的进攻点，也加进下一层的搜索，虽然可能有极小部分情况漏算，但和楼主下还是爆杀楼主了，测试下来10层有些情况会需要10秒以上，但7层还是比较快的


算杀方面进攻搜索还是比较简单，难点在于优先级判断，比如有一些白子的防守点正好也可以让其形成活3，那么黑棋要继续进攻只有两种可能：继续搜索冲四以上价值的进攻点，或者搜索还是进攻点的活3防守点，这种优先级判断可以说是非常重要，确保了算杀的正确性，楼主也花了相当时间在这上面（有很多种情况要考虑）

虽然bug感觉都解决掉了，但其实算杀还有非常多的优化和提升空间，比如形成33、34、44的前一步也可以作为一个进攻点，还有如果搜索到达最大深度可以评估一下局势而不是直接返回失败，由于时间问题（以及不想再改另依托快变成💩山的代码）就没去实现


最后是布局，在布局方面楼主做的相当草率，基本上就是看每个空可以让黑子形成多少个活二以上的棋形，然后选择最多的，如果有相同就再看白子，这使得AI执黑时主要去进攻而执白去防守，还有就是出现防守点时看哪一些防守点会让对手可以算杀，可以就扔掉，如果没有可用防守点就报错（在防守点找一个算杀可能稍微低点的，但是效果并不好，而且楼主下不赢所以不太好debug）

算法方面肯定不是最吊的，比赛也证实了，不过我感觉我做的一个比较好的点反而是游戏运行设计，算杀可能会模拟几百几千种可能所以如果要在算法里加打印信息可能会一下子打印一堆无用的信息，所以我用了些技巧可以让我很方便地在棋盘上看每一步算杀搜索和debug（点一下棋盘就跳到下一步），如果有感兴趣的话我之后可以分享一下，对于非搜索类算法应该也适用

Ray

帮顶 正确的算杀对提升棋力帮助很大