2048

提交答案题 Special Judge 提交数: 98, 通过率: 0%, 平均分: 0.31

题目描述:

2048 是最近十分风靡的一款小游戏。
我们先介绍一下实际游戏的规则:2048 游戏由 4x4 的矩阵构成。每个位置(方格内)可以放置不多于一个瓦片(tile),每个瓦片上标着一个值为 2 的幂的数。玩家每回合从上下左右中选择一个合法的方向(合法性将在稍后解释),这些瓦
片将尽可能向该方向移动,直至边界,并且保持顺序。若相互挤压(即相邻且相对位置平行于所选方向)的瓦片数字相同,则立即合并为一个瓦片,消失的瓦片立即不占据位置。每回合每个瓦片仅可合并一次,并且合并次序以沿玩家所选方向靠前者为先。一个方向合法当且仅当该选择的方向至少移动或合并一个瓦片,因此该操作后,矩阵上至少存在一个空白位置。开始游戏前或回合间,游戏程序会在空白处随机生成一个标着 2 或 4 的瓦片。当场上合成 2048 时游戏结束,玩家胜利;若玩家不能做出合法的移动,游戏结束,玩家失败。
现在,我们想让AI尽量获得更高的分数,请注意,本题中规则与实际游戏有所不同。游戏中玩家不知道随机生成瓦片的位置和大小,在本题中,我们给定随机算法,并且每次只生成标着 2 的瓦片,希望依此获得相当高的分数。


游戏规则样例:
出现左图所示的状态后,玩家选择向左移动,下方的三个 4 将会变为一个 8 和一个 4,由于左边两个 4 更靠近移动方向(左),故应合成最左侧一个 8 和第二左侧一个 4(见右图),由图可以判断出,游戏程序在回合间随机生成了一个 2
在右下角:

1645106968251386075.png                   1645106972850375256.png

2048 游戏所需的随机数为 0~15 的数字,分别代表从左到右、从上到下的依次编号的瓦片(见下图)。每次需要随机生成瓦片时,我们在随机数数列中逐个取数并对 16 取模,直至取到一个对应空当(而非已被瓦片占据的位置)的数为止。下次取随机数时应从上次选取数字的下一个开始。游戏开始时,我们随机生成2个瓦片。

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

典型的使用 C 和 Pascal 生成上述随机数序列的代码如下:

int MUL = 8221;
int seq;

void initSeed(int seed)
{
  seq = seed;
}

int getRand()
{
  return (seq = (seq * MUL) + (seq >> 16)) & 15; 
}

输出文件中请按顺序包含一组合法的操作,尽可能获得标记数字更大的瓦片。评分时将根据执行完毕后的最终状态评定。

“题解”页面的小程序可以帮助你检查你的输出文件并进行模拟。使用方法:在seed栏填入随机种子(1至20),在moves栏填入你的操作序列(如"LLL"),点击运行,即得到游戏最终状态。你也可以使用方向键正常进行游戏,你的操作序列会记录到moves栏。

输入格式:

本题没有输入文件,但我们在这里指定一组随机种子,第\(i\)题使用数值为\(i\)的随机种子(\(i=1, 2, \dots, 20\)),对应输出文件分别为 20481.out~204820.out。

输出格式:

在输出文件 20481.out~204820.out 中,第一行输出该题目对应的随机种子(注意文件名和种子顺序不要交换)。第二行按顺序列出操作(上下左右分别用大写字母 UDLR 表示)。

样例输出:

1
LLLLLDLLLRDULRRDRUUDRLURLURLLUDLLURLRLLULLLLL

下载附加文件

提示:

以上的样例是 20481.out 的一个合法输出。它可能并不能得到这个测试点的满分。

每个测试点单独评分,每个测试点权重相等。如果你的输出不合法或不满足要求,得分为 0,否则得该测试点满分。要求如下。
对于测试点 1-2:你的最终状态出现标记不小于 4096 的瓦片。
对于测试点 3-5:你的最终状态出现标记不小于 8192 的瓦片。
对于测试点 6-10:你的最终状态出现标记不小于 16384 的瓦片。
对于测试点 11-20:你的最终状态出现标记不小于 32768 的瓦片。

附加文件中包含本题原本的pdf版本。

你需要提交的文件为 20481.out, 20482.out, ..., 204820.out

时间限制: 1000ms
空间限制: 256MB

来源: 浙江省选2014day2t1