首页笔记算法

一次尝试

# 起因

今天在某站网上冲浪的时候，看到了某个 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)∈{0,1,2,3,4}state(x,y) \in \{ 0, 1, 2, 3, 4 \} 表示该位置的状态

# 大概思路

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

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

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

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

# 观代码前提示

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

# 整体代码编写

# 数据储存

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

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

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

#define MAX_WIDTH 8
#define MAX_HEGIHT 8
struct Map {
    int width, height;
    uint8_t map[MAX_WIDTH][MAX_HEIGHT];
};

# 权值计算及状态存储

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

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

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

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

delta(map)=Σstate(x,y)≠05−state(x,y) delta(map) = \Sigma_{state(x,y) \ne 0} 5-state(x,y)

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

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

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

// 状态类
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 的痕迹...）：
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）：
struct BurstDrop {
    int y, x; // 当前位置
    enum Direction { Left, Up, Right, Down } dir; // 运动方向
};
# 算法框架
于是我们可以写下这么一个函数来计算下一个状态：
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 个方向的 “溅射水滴”
编写代码如下：
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：“水滴移动”
水滴移动则比较简单，遍历当前存在的水滴，进行位置更改，并判断是否碰壁或遇到非空格即可
代码如下：
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% 的空间，于是我对地图的储存结构体进行了如下更改：
struct Map {
    int width, height;
    std::bistet<MAX_WIDTH * MAX_HEIGHT * 3> map;
};
省略由于此处重构引入的其他部分代码变动，省略 20 分钟...
优化后内存倒是不算很吃紧了，但是依旧很慢啊..
# 优化 2：状态记忆化
这时我突然想到，可能两个不同的 “加水” 操作互相独立，前后顺序改变的情况下可以到达相同的新谱面。于是编写了基于地图的状态储存表：
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 * 算法的框架进行了小修改：
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 进行储存
    4.  
    首先方法 2 会有问题，因为对于 bitset 的哈希相同的两个不同地图，此方法会无法区分，故首先排除
     
    然后考虑方法 1 和 3, 明显方法 1 更简单，于是我们选择... 方法 3！
     
    其实我在写的时候没有考虑到方法 1，而且程序里面使用了访问 bitset 相邻几位数的操作，此时是挨个访问的，感觉很不优雅，于是我就手写了一个 bitset...
     
    不过倒是实现了这些功能：
     
    • 动态长度
    • 单点查询 / 修改
    • 区间查询 / 修改
     
    使用这个 bitset，我们就可以较为方便地将坐标所占的 6 个 bit 拼接在地图的 bitset 之后，组成一个整体作为 key 存于记忆化结构中。
     
    考虑到算法的实现方法及空间问题，程序中选择了只储存引起 “炸开” 动作的操作。如此即可在不占用过多空间，也不会带来过多性能损失的情况下实现记忆化。
     
    # 实测结果
     
    在完善了输入输出之后，对真实谱面进行了测试。
     
    对于如下谱面：
      
    输入的数据为：
     
    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 头文件
     程序源文件