题解：P16188 [ZJOI2014] 2048

· · 题解

P16188 题解

神秘 2048 小游戏编程题。

::::info[写在最前面]

省流：如果你想用 AI 模型生成本题代码，我建议不要尝试。

看到该题目，我直接把整个题面丢给豆包，得到了一个网页版 2048，支持搜索算法自动操作、导出操作序列。

我以为这把稳了，难道这就可以水一道黑题？然后我开了五个浏览器页面一起跑，出去玩了一会，回来发现电脑怎么这么烫！而且最快的一个页面才跑到 512。

要知道本题一共 20 个测试点，这种速度下去肯定要花很长时间，而且网页还需要渲染，导致实际速度更慢了。

想让豆包再帮我写一个 C++ 版本，但毕竟做题的人是我，不是豆包，所以我最终决定自己写一个。

如果你真的不想自己写，那么可以停止阅读该文章了，以豆包的实力可以切掉这道黑题。

现在，开始读题。

::::

题目大意

一句话题意：给你一个只生成 2 且每一步位置已知的 2048 游戏，每一步操作必须有意义（合成至少一个新方块或者造成至少一个方块移动），给出可以合成 32768 的操作序列。

部分分：4096、8192、16384。

题目思路

首先，2048 游戏的三个核心点就是：随机化、分数、移动判定。

由于本题只涉及生成 2 而不涉及生成 4，故不需要考虑随机化；本题也不需要考虑分数，只需要合成对应的方块，故不需要考虑分数；最后，只要是 2048，总要考虑移动逻辑的，所以本题的核心点就是移动操作（和配套的生成方块操作）。

下文可能读起来很顺畅，但是写这道题的时候我的思路并不顺畅，前后改了两三个小时才修好最基本的问题（调整移动策略的时间另算）。

1. 移动

根据题目大意，我们需要判断该操作是否合成新方块或者造成方块移动。注意每个方块每轮只可合并一次，所以还需要记录下每个方块在这一步移动中是否是合并而来，如果是合并而来则无法继续用于合并。我们可以记录下造成了多少次合成和移动，最后如果计数器 > 0，则该移动合法。

2. 生成

首先我们要保证有空位置，所以需要一个函数判断棋盘是否被填满。注意该函数与游戏失败函数不同，因为棋盘填满时也可以通过合成新方块来获得空位置，但棋盘填满时无法进行生成新方块操作。

写完这两部分，就可以支持给定种子和操作序列字符串，模拟最终棋盘状态了，也就是附件中 simulate 程序干的事情。

当然这里还可以再写一些其它函数，比如给定目标方块判断是否达成、计算棋盘方块最大值等。

这两部分代码如下。注：由于原代码过长，此处进行适量压行，此过程中可能出现误删大括号等问题，可能会无法编译，建议自己手打。

::::success[基本操作]

const int Mul = 8221;
int seq;
void initSeed(int seed) { seq = seed; }
int getRand() { return (seq = (seq * Mul) + (seq >> 16)) & 15; }
bool full(int board[4][4]) {
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            if(!board[i][j]) {
                return 0; } } }
    return 1; }
bool spawn(int board[4][4]) {
    bool ok = 0;
    while(!ok && !full(board)) {
        int now = getRand();
        if(!board[now / 4][now % 4]) {
            board[now / 4][now % 4] = 2;
            ok = 1;
            return 1; } }
    return 0; }
bool move(char c , int board[4][4]) {
    pair < int , bool > a[4][4];
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            a[i][j].first = board[i][j];
            a[i][j].second = 0; } }
    int cnt = 0;
    if(c == 'L') {
        for(int Round = 0 ; Round < 4 ; Round++) {
            for(int i = 0 ; i < 4 ; i++) {
                for(int j = 1 ; j < 4 ; j++) {
                    if(a[i][j].first != 0 && a[i][j - 1].first == 0) {
                        a[i][j - 1] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++; }
                    if(a[i][j].first != 0 && a[i][j].first == a[i][j - 1].first && !a[i][j].second && !a[i][j - 1].second) {
                        a[i][j - 1].first *= 2;
                        a[i][j - 1].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++; } } } } }
    if(c == 'R') {
        for(int Round = 0 ; Round < 4 ; Round++) {
            for(int i = 0 ; i < 4 ; i++) {
                for(int j = 2 ; j >= 0 ; j--) {
                    if(a[i][j].first != 0 && a[i][j + 1].first == 0) {
                        a[i][j + 1] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++; }
                    if(a[i][j].first != 0 && a[i][j].first == a[i][j + 1].first && !a[i][j].second && !a[i][j + 1].second) {
                        a[i][j + 1].first *= 2;
                        a[i][j + 1].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++; } } } } }
    if(c == 'U') {
        for(int Round = 0 ; Round < 4 ; Round++) {
            for(int i = 1 ; i < 4 ; i++) {
                for(int j = 0 ; j < 4 ; j++) {
                    if(a[i][j].first != 0 && a[i - 1][j].first == 0) {
                        a[i - 1][j] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++; }
                    if(a[i][j].first != 0 && a[i][j].first == a[i - 1][j].first && !a[i][j].second && !a[i - 1][j].second) {
                        a[i - 1][j].first *= 2;
                        a[i - 1][j].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++; } } } } }
    if(c == 'D') {
        for(int Round = 0 ; Round < 4 ; Round++) {
            for(int i = 2 ; i >= 0 ; i--) {
                for(int j = 0 ; j < 4 ; j++) {
                    if(a[i][j].first != 0 && a[i + 1][j].first == 0) {
                        a[i + 1][j] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++; }
                    if(a[i][j].first != 0 && a[i][j].first == a[i + 1][j].first && !a[i][j].second && !a[i + 1][j].second) {
                        a[i + 1][j].first *= 2;
                        a[i + 1][j].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++; } } } } }
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            board[i][j] = a[i][j].first; } }
    return cnt > 0; }
bool Operator(char c , int board[4][4]) {
    bool ok = move(c , board);
    spawn(board);
    return ok; }
bool check(int goal , int board[4][4]) {
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            if(board[i][j] >= goal) {
                return 1; } } }
    return 0; }
bool fail(int board[4][4]) {
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            if(board[i][j] == 0) {
                return 0; } } }
    for(int i = 0 ; i < 3 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            if(board[i][j] == board[i + 1][j]) {
                return 0; } } }
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 3 ; j++) {
            if(board[i][j] == board[i][j + 1]) {
                return 0; } } }
    return 1; }
int boardmax(int board[4][4]) {
    int maxx = 0;
    for(int i = 0 ; i < 4 ; i++) {
        for(int j = 0 ; j < 4 ; j++) {
            maxx = max(maxx , board[i][j]); } }
    return maxx; }

::::

3. 核心部分：Auto Play

如果手打的话，除非你会玩，不然可能 512 都难打出来。但是换到 OI 思维来说，这个东西完全可以让程序来干啊！

我们只需要状压四种操作，每次向后搜若干步，然后判断所有可能的移动方法中最优的一个。

所以这一部分需要再写一个模拟函数。注意这里并不是真正进行操作，所以需要存下模拟之前的随机数，在模拟完成后再将随机数改回来。

注意模拟过程中如果某一步无法移动，需要提前退出模拟函数，这里不要忘记把随机数改回来。

模拟函数代码如下。

::::success[模拟函数]

int Simulation(int opt , int board[4][4])
{
    int seq_pre = seq;
    int cnt = 0;
    while(opt)
    {
        char c = (opt % 4 == 0 ? 'L' : (opt % 4 == 1 ? 'R' : (opt % 4 == 2 ? 'U' : 'D')));
        bool ok = Operator(c , board);
        cnt += ok;
        if(!ok)
        {
            seq = seq_pre;
            return cnt;
        }
        opt /= 4;
    }
    seq = seq_pre;
    return cnt;
}

::::

然后我们发现还有最后一个问题：怎么判断两个状态哪个更优？

首先我们发现，一般玩 2048 时都会尽可能构造如下若干种情形（不一定涵盖全部情况，此处以合成 32768 举例）：

::::info[几种情况]

  1. 蛇形:

    16384 8192 4096 2048
    128 256 512 1024
    64 32 16 8
    空 2 2 4

    一种可行的操作序列为：\texttt{RRULLLURRRULLL}，最终 32768 出现在左上角。

  2. 递减形

    16384 8192 4096 2048
    1024 512 256 128
    64 32 16 8
    4 2 2 空

    一种可行的操作序列为：\texttt{RRURRRURRRURRR}，最终 32768 出现在右上角。

  3. 大数放在角落

    16384 4096 2048 8192
    1024 256 128 512
    64 16 8 32
    4 2 2 空

    一种可行的操作序列为：\texttt{LRULRRULRRURRR}，最终 32768 出现在右上角。本方法需要用新生成的 2 作为“垫子”调整每一层大数的位置。

因为我不玩 2048，所以不介绍其它方法。 ::::

然后我们发现，大数都集中在某个角落，我们可以钦定大数集中在左上角，据此给每一个位置设置一个权重，则左上角到右下角的权重应该阶梯式减小。如下给出一种权重分布图：

2000 1950 1900 1850
1600 1550 1500 1450
1200 1150 1100 1050
800 750 700 650

由于本题我决定采用第三种方法作为主要合成方法，所以还需要根据角落、棋盘边上分别赋权值，又因为大数在左上角，因此下面两行直接不赋权值，例如下表：

250 100 100 250
100 10 10 100
0 0 0 0
0 0 0 0

最终每个位置的权值为对应位置两权重相加再乘上每个位置的数字大小。

当然，不管使用什么方法，都需要考虑到一些其他因素。这里列出几种：

多找几个棋盘算一下这几个值，看看大体的数量级，再给这些值分别赋权重即可。

这里给出我的估价函数作为参考。

::::success[估价函数]

const double val[4][4] = {{2000 , 1950 , 1900 , 1850} , {1600 , 1550 , 1500 , 1450} , {1200 , 1150 , 1100 , 1050} , {800 , 750 , 700 , 650}};
const double val2[4][4] = {{250 , 100 , 100 , 250} , {100 , 10 , 10 , 100} , {0 , 0 , 0 , 0} , {0 , 0 , 0 , 0}};
double calc(int board[4][4])
{
    double score = 0;
    int maxx = 0 , empty = 0;
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            score += (val[i][j] + val2[i][j]) * board[i][j];
            maxx = max(maxx , board[i][j]);
            empty += (board[i][j] == 0);
        }
    }
    double smooth = 0;
    double potential = 0;
    for(int i = 0 ; i < 3 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            smooth -= pow(abs(log2(board[i][j] + 1) - log2(board[i + 1][j] + 1)) , 1.5);
            potential += (board[i][j] == board[i + 1][j]) * board[i][j];
        }
    }
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            smooth -= pow(abs(log2(board[i][j] + 1) - log2(board[i][j + 1] + 1)) , 1.5);
            potential += (board[i][j] == board[i][j + 1]) * board[i][j];
        }
    }
    return score * 100 + potential * 200 + smooth * 300 + maxx * 1000 + empty * 2000;
}

::::

最后我让豆包提供了一个自动输出到文件 1.out \sim 20.out 的代码，把这几部分放到一起，又上网查了一个覆盖标准输入输出的代码（说白了就是把每一步移动后的棋盘输出到对话框的同一个位置）。这样就可以实现全自动可视化生成操作序列了。

4. 调整

由于个人能力限制，该估价函数无法一遍通过所有测试点，大概会 WA 四五个的样子。下图为未经过调整前的评测结果，为防止图片挂掉再放一个提交链接：

因此还需要专门对合成失败的测试点进行调整，比如更换合成方法、增加搜索深度等。

观察发现 #11、#20 只合成到 8192，所以先删除最后 100 步，增加搜索深度至合成 16384，然后再正常搜索，即可转化为 AC 或剩下三个测试点的情况（合成到 16384，接近合成 32768）。

然后我们继续跑到死局，根据具体情况删除最后 200 \sim 500 步并增加搜索深度，这样虽然单步速度变慢，但需要跑的步数也减少了许多，所以可以通过。

最终给出通过结果和评测链接。

题目代码

只给出主要程序代码（包含自动输出和可视化合成）。

::::success[题目代码]

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
void gotoxy(int x , int y)
{
    COORD pos = {x , y};
    HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(hOut , pos);
}
const int Mul = 8221;
int seq;
void initSeed(int seed)
{
    seq = seed;
}
int getRand()
{
    return (seq = (seq * Mul) + (seq >> 16)) & 15;
}
bool full(int board[4][4])
{
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            if(!board[i][j])
            {
                return 0;
            }
        }
    }
    return 1;
}
bool spawn(int board[4][4])
{
    bool ok = 0;
    while(!ok && !full(board)) // 一定要加 !full(board)
    {
        int now = getRand();
        if(!board[now / 4][now % 4])
        {
            board[now / 4][now % 4] = 2;
            ok = 1;
            return 1;
        }
    }
    return 0;
}
bool move(char c , int board[4][4])
{
    pair < int , bool > a[4][4];
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            a[i][j].first = board[i][j];
            a[i][j].second = 0;
        }
    }
    int cnt = 0;
    if(c == 'L')
    {
        for(int Round = 0 ; Round < 4 ; Round++)
        {
            for(int i = 0 ; i < 4 ; i++)
            {
                for(int j = 1 ; j < 4 ; j++)
                {
                    if(a[i][j].first != 0 && a[i][j - 1].first == 0)
                    {
                        a[i][j - 1] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                    if(a[i][j].first != 0 && a[i][j].first == a[i][j - 1].first && !a[i][j].second && !a[i][j - 1].second)
                    {
                        a[i][j - 1].first *= 2;
                        a[i][j - 1].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                }
            }
        }
    }
    if(c == 'R')
    {
        for(int Round = 0 ; Round < 4 ; Round++)
        {
            for(int i = 0 ; i < 4 ; i++)
            {
                for(int j = 2 ; j >= 0 ; j--)
                {
                    if(a[i][j].first != 0 && a[i][j + 1].first == 0)
                    {
                        a[i][j + 1] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                    if(a[i][j].first != 0 && a[i][j].first == a[i][j + 1].first && !a[i][j].second && !a[i][j + 1].second)
                    {
                        a[i][j + 1].first *= 2;
                        a[i][j + 1].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                }
            }
        }
    }
    if(c == 'U')
    {
        for(int Round = 0 ; Round < 4 ; Round++)
        {
            for(int i = 1 ; i < 4 ; i++)
            {
                for(int j = 0 ; j < 4 ; j++)
                {
                    if(a[i][j].first != 0 && a[i - 1][j].first == 0)
                    {
                        a[i - 1][j] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                    if(a[i][j].first != 0 && a[i][j].first == a[i - 1][j].first && !a[i][j].second && !a[i - 1][j].second)
                    {
                        a[i - 1][j].first *= 2;
                        a[i - 1][j].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                }
            }
        }
    }
    if(c == 'D')
    {
        for(int Round = 0 ; Round < 4 ; Round++)
        {
            for(int i = 2 ; i >= 0 ; i--)
            {
                for(int j = 0 ; j < 4 ; j++)
                {
                    if(a[i][j].first != 0 && a[i + 1][j].first == 0)
                    {
                        a[i + 1][j] = a[i][j];
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                    if(a[i][j].first != 0 && a[i][j].first == a[i + 1][j].first && !a[i][j].second && !a[i + 1][j].second)
                    {
                        a[i + 1][j].first *= 2;
                        a[i + 1][j].second = 1;
                        a[i][j] = make_pair(0 , 0);
                        cnt++;
                    }
                }
            }
        }
    }
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            board[i][j] = a[i][j].first;
        }
    }
    return cnt > 0;
}
bool Operator(char c , int board[4][4])
{
    bool ok = move(c , board);
    spawn(board);
    return ok;
}
int Simulation(int opt , int board[4][4])
{
    int seq_pre = seq;
    int cnt = 0;
    while(opt)
    {
        char c = (opt % 4 == 0 ? 'L' : (opt % 4 == 1 ? 'R' : (opt % 4 == 2 ? 'U' : 'D')));
        bool ok = Operator(c , board);
        cnt += ok;
        if(!ok)
        {
            seq = seq_pre; // 记得重置 seq
            return cnt;
        }
        opt /= 4;
    }
    seq = seq_pre;
    return cnt;
}
const double val[4][4] = {{2000 , 1950 , 1900 , 1850} , {1600 , 1550 , 1500 , 1450} , {1200 , 1150 , 1100 , 1050} , {800 , 750 , 700 , 650}};
const double val2[4][4] = {{250 , 100 , 100 , 250} , {100 , 10 , 10 , 100} , {0 , 0 , 0 , 0} , {0 , 0 , 0 , 0}};
double calc(int board[4][4])
{
    double score = 0;
    int maxx = 0 , empty = 0;
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            score += (val[i][j] + val2[i][j]) * board[i][j];
            maxx = max(maxx , board[i][j]);
            empty += (board[i][j] == 0);
        }
    }
    double smooth = 0;
    double potential = 0;
    for(int i = 0 ; i < 3 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            smooth -= pow(abs(log2(board[i][j] + 1) - log2(board[i + 1][j] + 1)) , 1.5);
            potential += (board[i][j] == board[i + 1][j]) * board[i][j];
        }
    }
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            smooth -= pow(abs(log2(board[i][j] + 1) - log2(board[i][j + 1] + 1)) , 1.5);
            potential += (board[i][j] == board[i][j + 1]) * board[i][j];
        }
    }
    return score * 100 + potential * 200 + smooth * 300 + maxx * 1000 + empty * 2000;
}
bool check(int goal , int board[4][4])
{
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            if(board[i][j] >= goal)
            {
                return 1;
            }
        }
    }
    return 0;
}
bool fail(int board[4][4])
{
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            if(board[i][j] == 0)
            {
                return 0;
            }
        }
    }
    for(int i = 0 ; i < 3 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            if(board[i][j] == board[i + 1][j])
            {
                return 0;
            }
        }
    }
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            if(board[i][j] == board[i][j + 1])
            {
                return 0;
            }
        }
    }
    return 1;
}
int boardmax(int board[4][4])
{
    int maxx = 0;
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            maxx = max(maxx , board[i][j]);
        }
    }
    return maxx;
}
int board[4][4];
void solve(int n , string s)
{
    string filename = to_string(n) + ".out"; // 创建文件输出流，自动打开
    ofstream out(filename);
    out << n << endl;
    gotoxy(0 , 0);
    printf("Now solve n = %d\n" , n);
    vector < char > op;
    initSeed(n);
    memset(board , 0 , sizeof(board));
    spawn(board);
    spawn(board);
    if(s != "NULL")
    {
        for(char i : s)
        {
            Operator(i , board);
            op.push_back(i);
        }
    }
    int goal = (n <= 2 ? 4096 : (n <= 5 ? 8192 : (n <= 10 ? 16384 : 32768)));
    while(!check(goal , board) && !fail(board))
    {
        double maxx = -1e18;
        int best = -1 , move = -1;
        int Maxx = boardmax(board);
        int K = 2 * (Maxx <= 4096 ? 6 : (Maxx <= 16384 ? 7 : 8));
        for(int S = 0 ; S < (1ll << K) ; S++)
        {
            int b[4][4];
            for(int i = 0 ; i < 4 ; i++)
            {
                for(int j = 0 ; j < 4 ; j++)
                {
                    b[i][j] = board[i][j];
                }
            }
            int nowmove = Simulation(S , b);
            if(calc(b) > maxx && nowmove)
            {
                maxx = calc(b);
                best = S;
                move = nowmove;
            }
        }
        for(int Round = 0 , S = best ; Round < (move + 2) / 3 ; Round++ , S /= 4)
        {
            if(check(goal , board) || fail(board))
            {
                break;
            }
            char c = (S % 4 == 0 ? 'L' : (S % 4 == 1 ? 'R' : (S % 4 == 2 ? 'U' : 'D')));
            Operator(c , board);
            op.push_back(c);
            gotoxy(0 , 2);
            for(int i = 0 ; i < 4 ; i++)
            {
                for(int j = 0 ; j < 4 ; j++)
                {
                    printf("%-7d" , board[i][j]);
                }
                printf("\n\n");
            }
        }
    }
    gotoxy(0 , 2);
    for(int i = 0 ; i < 4 ; i++)
    {
        for(int j = 0 ; j < 4 ; j++)
        {
            printf("%-7d" , board[i][j]);
        }
        printf("\n\n");
    }
    for(char i : op)
    {
        out << i;
    }
    return ;
}
signed main()
{
    int n = 20;
    for(int i = 1 ; i <= n ; i++)
    {
        solve(i , "NULL");
    }
    return 0;
}

::::