游戏规则是点击两个或以上同色相邻连接方块进行消除，连接色块越多则单次得分越高，剩余色块越少，奖励分数越多，得分规则总结起来就是单次消除得分等于5*同色方块数的平方，剩余方块奖励得分等于2000-20*剩余块数的平方，这里剩余块数要小于等于十块，玩家需要在计分规则下每关拿到尽可能多的分数。
求解方法的设计有两种思路，要么全部解法搜一遍，要么用尝试探索的方式解出每一步，这里分为递归算法和贪心算法，递归算法就是搜索每种从头玩到底的情况，找最高分的解法，贪心算法求较优解，多尝试后面步骤，探索出能尽量拿高分的前面步骤。递归算法广度或深度优先，根节点返回最高分和相应步骤，缓存重负步骤和重复结果，实际经验，初始越有二十多种选择，最后五步越有两到三种选择，游戏大概在二十之三十五步内结束，保守估计分支总数不少于二十种，剪枝作用不大，每种分支几乎都是新情况。
贪心算法求近似最优，从后面有限随机尝试结果，推出前面应该点哪些步骤，特点是模拟人脑玩游戏的过程，在尝试中探索，逼近最优解，实现方式是当前局面模拟点一下，然后随机玩很多轮，探索出第一步点哪里最好，迈出第一步，到下一个局面进行同样的探索。但实践发现这种解法存在不足，对于最先点击的色块后面可能的排列组合过多，乱试几万次也只能覆盖千亿分之一的情况，这里就有了优化点，后盘优化空间小，单轮随机模拟后盘覆盖已足够全面，结果差不多。快速优化前盘空间，尝试越多就越容易找出前十步做的最好的色块点击顺序。
文章评论