“十滴水”操作步骤求解算法的编写过程

一次尝试

起因

今天在某站网上冲浪的时候，看到了某个up（似乎暴露了平台？不过不要声张 /doge）在玩这款很早之前玩过的小游戏

突然觉得游戏的内在逻辑挺简单的，然后觉得，是不是可以写个程序计算一下最优解？

说干就干/doge

编写之前

写代码之前得有个大概的方向，于是我进行了如下几个操作（操作这个词在这里好像有点怪怪的？）

游戏规则

首先通过不停重开，我们发现游戏的规则如下：

  1. 每个格子有5种状态s（以及他们在程序中对应的数字）：
    • 0: 空格
    • 1: 小小水滴
    • 2: 小水滴
    • 3: 中水滴（？）
    • 4: 大水滴
  2. 界面右上角表示当前剩余的水滴数（操作步数）
  3. 通过鼠标点击格子可以扣除一点水滴，进行“加水”操作
  4. “加水操作”可以让格子的状态在5种状态间循环：
    • 空格->小小水滴
    • 一般的水滴->大一号的水滴
    • 大水滴->空格
  5. 在“加水”过程中，如果该格子经历的是”大水滴->空格”这一过程，则水滴会“炸开”，也即是自该格中心生成分别向上、下、左、右四个方向运动的“溅射水滴”
  6. “溅射水滴”进行匀速直线运动
  7. “溅射水滴”碰壁时消失
  8. “溅射水滴”在碰到非空格格子时，也会对其进行“加水”操作
  9. 当单次操作产生的“炸开”过程的数量（连击数）大于3时，当前剩余的水滴数增加连击数/3向下取整的值
  10. 棋盘清空则胜利，增加一水滴
  11. (叠个甲，这是计算使用的条件，非完全准确，就因此有时会出现计算状态与实操状态不一致的情况，有时间改改吧 /doge)程序中采用以下临界情况下的优先判断：
    • 当同一个大水滴爆裂生成的两滴溅射水滴分别遇到另一个水滴，同时进行“加水”操作，采用左、上、右、下的顺序进行计算
    • 先爆炸的水滴产生的溅射水滴优先计算

我们可以顺便定义一些函数，方便以后论证：

  • $state(x,y) \in \{ 0, 1, 2, 3, 4 \}$ 表示该位置的状态

大概思路

下一步明确要用什么主体算法。首先出现在我脑海里的是A*算法，于是，采纳！

虽然写到一半之后想到了AlphaGo，然后思考可能有相关的AI算法也可以实现吧？不过已经开始写了，而且这个算法还要现学，可能有点麻烦，于是就放弃了..

稍微计算了一下理论复杂度上限，Emm…

或许我们可以通过某种剪枝来优化速度呢，感觉可行 /doge

观代码前提示

由于程序前前后后进行了4次更改，虽然我在写总结的时候有注意这一点，但是文中的代码仍然可能会存在前后矛盾的情况。完整能运行的代码可见附录。

整体代码编写

数据储存

然后是界面数据的储存。上文介绍过每个格子都存在5种状态，那么我们可以使用一个二维数组对数据进行储存，每个元素先暂时使用uint8_t类型储存。虽然会浪费掉5个bit，不过最开始我倒是没有想那么多，优化都是后来的事情了…

由于记忆有点模糊，不清楚后续关卡地图大小是否会改变，故在编写代码时，地图长宽并未硬编码，而是使用一个宏进行代替。

界面储存代码（第一版）如下：

1
2
3
4
5
6
#define MAX_WIDTH 8
#define MAX_HEGIHT 8
struct Map {
    int width, height;
    uint8_t map[MAX_WIDTH][MAX_HEIGHT];
};

权值计算及状态存储

我们采用的算法是A*，其需要根据某个权值对状态进行排序。

考虑到游戏的目标即为通关，必要条件为水滴数不为0，且水滴数决定了我们的操作空间，故怕判断的首要依据则为：操作后剩余的水滴数最多。

由于连击加水滴这个规则很关键，所以在程序里应该鼓励连击，故第二个判断标准则为：连击数最多。由于存在除以3取整的操作，故修改为“增加的水滴数最多”。

然后考虑谱面因素。可以规定谱面的偏差值为：不考虑“炸开”这个规则时，把棋盘清空所需要的水滴数。用公式表示如下：

到这里其实可以看出，将状态1-4对应关系进行翻转可以方便计算。但我想到这一点时已经写完第一版程序了，故就按照当前的定义写下去了…

考虑到我们最终需要输出步骤，故还需要储存操作步骤。

由于状态和地图强关联，故我偷了个懒，直接让状态继承地图（实际工程不推荐，因为不满足“is a”条件），进行如下定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 状态类
class MapWithState : public Map {
    int bonus;  // 奖励的水滴数
    int step;   // 操作步数
    int map_score;  // 地图得分
    std::vector<std::pair<int, int>> operations;  // 操作表，元素为(y,x)的pair类型【注意y在前】
    // constructors...
    // functions...
};

// 比较类
class MapWithStateLess {
    public:
    constexpr bool operator()(const MapWithState& left,
                                const MapWithState& right) const {
        int dis = (left.step - left.bonus) - (right.step - right.bonus);
        if (dis != 0)
            return dis > 0;  // 优先比较剩余水滴数
        if (left.bonus != right.bonus)
            return left.bonus > right.bonus; // 其次为增加的水滴数
        return left.map_score > right.map_score;  // 再是偏差值
    }
};

总体框架

接下来就可以搭建一个初步的框架了，采用了A*的标准写法（个人限定版，很有Java的痕迹…）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct AStar {
    // 这里其实可以只返回operations来着
    MapWithState CalculateOperations(const Map& initial_map) {
        static std::priority_queue<MapWithState, std::vector<MapWithState>,
                                   MapWithStateLess>
            heap;
        while (heap.size())  // 为了安全，其实可以不加来着
            heap.pop();
        MapWithState initial_state = MapWithState::generate(initial_map);
        // 生成初始状态
        
        heap.push(initial_state);

        while (heap.size()) {
            // 取出权值最小的状态
            MapWithState m = heap.top();
            heap.pop();

            if (m.map_score == 0) {
                return m;
            }
            if (!stateMemory.isOutdated(m)) {
                for (int i = 0; i < m.height(); ++i) {
                    for (int j = 0; j < m.width(); ++j) {
                        // 生成下一个状态
                        MapWithState nextMap = generateNextMap(m, i, j);
                        nextMap.operations.push_back({i, j});
                        heap.push(nextMap);
                    }
                }
            }
        }
        return best;
    }
};

状态转移

思路建立

接下来是最为麻烦的一步，计算下一个状态。

（为什么说它最麻烦呢，是因为这一步没模板，是针对题目的代码部分…）

通过研究游戏规则，发现游戏的步骤可以抽象为两种操作：

  1. “加水”
  2. “炸开”后的“溅射水滴”的运动

添加结构-“溅射水滴”

由于“溅射水滴”的存在，我们需要对其进行储存（突然发现这句话很Engl-ish）：

1
2
3
4
struct BurstDrop {
    int y, x; // 当前位置
    enum Direction { Left, Up, Right, Down } dir; // 运动方向
};

算法框架

于是我们可以写下这么一个函数来计算下一个状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MapWithState generateNextMap(const MapWithState& m, int y, int x) {
    MapWithState nextMap(m);
    std::list<BurstDrop> drops;  // 储存当前存在的“溅射水滴”
    int combo = 0;  // 储存连击数

    // “加水”操作，修改地图，可能存在“炸开”的操作
    bool bursted = applyDrop(&nextMap, y, x, &drops);  
    
    if (bursted)
        ++combo;
    
    // 不断对当前存在的水滴进行一次“移动一格”的操作，可能存在“加水”操作
    while (drops.size()) {
        moveDrops(&nextMap, &drops, &combo);
    }

    // 状态更新
    ++nextMap.step;
    nextMap.bonus = combo / 3;
    nextMap.map_score = MapWithState::CalculateScore(nextMap);

    return nextMap;
}

接下来就是细分的“加水”操作和“移动一格”的操作了

细分步骤1：“加水”

“加水”可以理解为：若该格状态不为4，则将该格的状态进行加一；否则置零，并生成4滴朝向4个方向的“溅射水滴”

编写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool applyDrop(MapWithState* m, int y, int x, std::list<BurstDrop>* drops) {
    if (m->map[y][x] != 4) {
        ++m->map[y][x];
        return false;
    }

    m->map[y][x] = 0;
    drops->emplace_back(BurstDrop{y, x, BurstDrop::Down});
    drops->emplace_back(BurstDrop{y, x, BurstDrop::Left});
    drops->emplace_back(BurstDrop{y, x, BurstDrop::Up});
    drops->emplace_back(BurstDrop{y, x, BurstDrop::Right});
    return true;
}

细分步骤2：“水滴移动”

水滴移动则比较简单，遍历当前存在的水滴，进行位置更改，并判断是否碰壁或遇到非空格即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void moveDrops(MapWithState* m, std::list<BurstDrop>* drops, int* combo) {

    // 由于需要动态添加水滴，每一步只计算当前存在的水滴，故先储存当前水滴数，
    // 添加在list后面的新水滴则不计算
    int count = drops->size();

    for (auto itr = drops->begin(); count; --count) {
        
        // 移动水滴
        switch (itr->dir) {
            case BurstDrop::Left:  --itr->x; break;
            case BurstDrop::Up:    --itr->y; break;
            case BurstDrop::Right: ++itr->x; break;
            case BurstDrop::Down:  ++itr->y; break;
        }

        // 碰壁消失
        if (itr->x < 0 || itr->x >= m->width || itr->y < 0 ||
            itr->y >= m->height)
            itr = drops->erase(itr);
        
        // 加水操作
        else if (m->get(itr->y, itr->x) != 0) {
            bool bursted = applyDrop(m, itr->y, itr->x, drops);
            if (bursted)
                ++*combo;
            itr = drops->erase(itr);
        } else {
            ++itr;
        }
    }
}

自此我们的核心计算部分编写完成。

初步测试

到这一步差不多过去了三个小时（中间吃了顿饭），我编写了简单的控制台输入输出部分代码，并对小样例进行了测试，修改了几个bug。

然而当我尝试对6x6棋盘进行求解时，发现它卡住了…

打开任务管理器，发现CPU（这里指单核，没有进行多线程优化，虽然好像挺好做的来着）和内存占用都很高，于是准备进行优化。

优化

优化1: 地图储存格式压缩

考虑到内存吃紧，而地图储存的时候浪费了超过62.5%的空间，于是我对地图的储存结构体进行了如下更改：

1
2
3
4
struct Map {
    int width, height;
    std::bistet<MAX_WIDTH * MAX_HEIGHT * 3> map;
};

省略由于此处重构引入的其他部分代码变动，省略20分钟…

优化后内存倒是不算很吃紧了，但是依旧很慢啊..

优化2：状态记忆化

这时我突然想到，可能两个不同的“加水”操作互相独立，前后顺序改变的情况下可以到达相同的新谱面。于是编写了基于地图的状态储存表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class StateMemory {
    struct MapWithStateLess {
        size_t operator()(const MapWithState& left,
                            const MapWithState& right) const {
            // 标准的std::bitset并不提供小于运算符，但提供了hash函数，所以我
            // 最开始写这个Memory的时候使用的容器是std::unordered_set
            // 至于为啥，马上你就能看到了...只能说非常难受...
            return left.map_bits() < right.map_bits();
        }
    };

    std::set<MapWithState, MapWithStateLess> set;

    public:
    // 尝试更新set中每个地图的最优状态，状态优先度判断如前文所示
    // 由于地图一定相同，故不考虑第三点
    bool update(const MapWithState& m) {
        // ...
    }

    // 判断状态是否陈旧
    bool isOutdated(const MapWithState& m) const {
        // ...
    }
} stateMemory;

然后将A*算法的框架进行了小修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct AStar {
    // 这里其实可以只返回operations来着
    MapWithState CalculateOperations(const Map& initial_map) {
        // ...
        while (heap.size()) {
            // 取出权值最小的状态
            MapWithState m = heap.top();
            heap.pop();

            if (stateMemory.isOutdated(m)) // *** 新增
                continue;                  // *** 新增

            if (m.map_score == 0) {
                return m;
            }
            if (!stateMemory.isOutdated(m)) {
                for (int i = 0; i < m.height(); ++i) {
                    for (int j = 0; j < m.width(); ++j) {
                        // 生成下一个状态
                        MapWithState nextMap = generateNextMap(m, i, j);
                        nextMap.operations.push_back({i, j});
                        if (stateMemory.update(nextMap)) // *** 新增
                            heap.push(nextMap);
                    }
                }
            }
        }
        return best;
    }
};

优化3&4：状态转移求解的记忆化 & bitset区间访问/赋值

到这里的测试发现，程序的运行效率有了很大的提高，但是有时候在计算状态转移的时候，发现它会卡老半天，于是考虑进行状态转移这个过程的记忆化。

考虑到这个过程，输入的地图和“加水”坐标一定的情况下，输出的地图和连击数应该是一定的，故可以使用map一类的容器进行储存。

在这里我们就遇到了一个问题：由于储存的键值为{地图，坐标（合成为一个6bit整数）}，而地图采用的bitset没有比较函数，这一个二元组整体又没有hash函数

可以考虑的方法有：

  1. 对hash和坐标进行组合， 实现一个整体的hash函数，使用unordered_map进行储存
  2. 构造一个基于hash和坐标的比较函数，使用unordered_map进行储存
  3. 更改地图储存格式，使其实现比较函数，并将其与坐标进行组合（append），并使用map进行储存

首先方法2会有问题，因为对于bitset的哈希相同的两个不同地图，此方法会无法区分，故首先排除

然后考虑方法1和3,明显方法1更简单，于是我们选择…方法3！

其实我在写的时候没有考虑到方法1，而且程序里面使用了访问bitset相邻几位数的操作，此时是挨个访问的，感觉很不优雅，于是我就手写了一个bitset…

不过倒是实现了这些功能：

  • 动态长度
  • 单点查询/修改
  • 区间查询/修改

使用这个bitset，我们就可以较为方便地将坐标所占的6个bit拼接在地图的bitset之后，组成一个整体作为key存于记忆化结构中。

考虑到算法的实现方法及空间问题，程序中选择了只储存引起“炸开”动作的操作。如此即可在不占用过多空间，也不会带来过多性能损失的情况下实现记忆化。

实测结果

在完善了输入输出之后，对真实谱面进行了测试。

对于如下谱面：

输入的数据为：

1
2
3
4
5
6
7
6 6
3 4 2 2 3 2
0 0 0 0 2 3
0 4 2 0 2 3
2 1 2 3 3 1
2 4 0 3 3 0
4 2 4 1 1 1

程序运行输出如下：

运行时间大概在10s量级，虽说还是有点慢，不过已经可以使用了

不过由于临界条件的选取与实际情况有偏差，所以在少数情况下操作后生成的谱面与计算值会有些偏差，不过嘛…能跑就行 /doge

后记

通过上面的输出可以看到，程序完成的环节为根据字符输入的谱面，计算出相应的步骤。如果需要完成自动游玩的ai，则仍需要两个后续的程序：

  1. 图片->输入数据的识别程序
  2. 输出数据->操作的脚本程序

这一部分的话，就看我以后还有没有闲心做了吧

不过造轮子还蛮开心的 /doge

以上。

22/06/25 更新：

原来我一直没有上传更新后的部分吗/doge

附件

bitset头文件
程序源文件