前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家：点击跳转

?

2048大家都玩过，也有很多人考虑过，最高到底能玩到多大的数字。

也有的人会问，最高能玩到多大的分数，但是这个明显要复杂很多。

?

有个在线的2048做的还不错，手机电脑都可以玩，

而且只要打开，后面就再也不需要网络了，火车上面玩很方便

链接：http://2048game.com/

我的成绩：

这个游戏我还录了一个视频，8分钟完成2048

?

我的手机里面还安装了一个可以悔一步的版本的2048

可以悔一步的版本，比不能悔的版本要简单很多。

比如说，当只有一个空格的时候，很多时候，出现2就会game over，出现4就可以继续玩。

这样，利用悔一步的功能，可以不断尝试，直到出现4再继续玩。

当然，有的版本是game over之后就不能悔一步了

那就比这个版本稍微难一些，但是还是比不能悔的版本要简单一些。

我的成绩：

?

下面讨论2048问题的简化版

简化一：假设系统只会给出2，不会给出4

简化二：假设16个格子没有位置的限制，任何2个格子只要数相等就可以合并。

重定义操作：每次操作，可以同时合并若干对数，比如将2,2,4,4,8合并成4,8,8，

如果没有可以合并的数，就不合并，算一次不做任何改变的操作。

每次操作都会产生1个新的2

问题：这样的游戏最多可以玩出多大的数字？

?

首先列出2的幂，2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072

131072=2^17

下面我将证明，永远不可能玩到131072

定义一个全局状态：所有格子的数的和S

很明显，刚开始的时候S是4，每合并1次，S的值就会加2

假设某个时候出现了131072，那么S至少为131072

那么一定有某个时候，S=131070，表示成二进制是1111 1111 1111 1111 0

这个数，要想表示成2的幂的和，至少需要16个数即从2到65536这16个数。

而这个时候，没有多余的空格了，所以说，不可能玩到131072。

而且，65536是可以达到的。

?

下面讨论真正的2048，到底能玩到多大的数字。

按照上面的论述可以推出，如果2048永远只出2的话，是不可能玩到131072的。

但是真正的2048，是有可能出现4的，所以说，2048永远不可能玩到262144，但是有没有可能玩到131072很难用理论说明。

为了研究131072到底能不能达到，我意识到只能悔一步的版本无法满足我的要求，于是我开始玩第三种版本——无限悔棋版（下面是我的成绩）

APK下载：点击打开链接

?

其实，可以悔一步的版本和可以悔任意多步的版本，在理论上是效果一样的。

当我们考虑2048最多可以玩到多大的数字的时候，是这么想的：

每次出现的是2还是4是随机的，出现的位置也是随机的。

我们只需要考虑在所有情况中，对我们最有利的那一种即可。

也就是说，可以这样考虑，每次出现的是2还是4是由我们来定，每次出现的位置也由我们来定，这样的情况下最多可以玩到多大的数字。

不难发现，无论是可以悔一步的版本的2048，还是可以悔任意多步的，都和这个模型的等价的。

?

这个图说明131072是可以玩到的，也让人很容易相信，131072便是能玩出的最大数字了，要证明也简单，就像我上面证明的那样。

下面讨论最多能玩多少分。

虽然我已经玩到了终点，已经无法再玩了，但是分数却不是最高的。

2048的计分规则是，玩家通过合并得到1个数N，这个数就计分N

比如说，2个2合并得到4，就加4分，2个1024合并得到2048，就加2048分

所以要计算最高分需要注意一个问题，同样是4，如果是玩家合并2个2得到的，那就是4分，但是如果是自动给出的4，那是没有分的，也就是说，单看这16个格子里面有哪些数是无法判断准确的得分的。

不过，最高分对应的局面只有2种情况，最小的格子可能是2也可能是4，另外15个格子就一定是8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072无疑了。

为了计算最高分，可以再次假设每次给出的数都是2，如果还能这样玩出上述的局面的话，那就一定能得到最高分。

具体计算方法是，2没分，4对应4分，8对应16分，16对应48分，32对应128分，64对应320分，128对应768分，256对应1792分，512对应4096分，1024对应9216分，2048对应20480分，4096对应45056分，8192对应98304分，16384对应212992分，32768对应458752分，65536对应983040分，131072对应2097152分

?

所以从8到131072这15个格子的总分是3932160分，但是这个分数是不可达到的，因为如果每次都出2的话，是不可能玩出131072的，也就是

?

在玩出131072之前至少出1个4，

同理在玩出131072之后，在玩出65536之前至少出1个4，

在玩出131072和65536之后，在玩出32768之前至少出一个4

。。。。。。

在玩出131072,65536,32768......128,64,32,16之后，在玩出8之前至少出1个4，

所以2048的理论最高分是3932160-15*4=3932100分

这个应该是可达到的，但是很难在理论上证明。

下面我将编程+构造证明，3932100分是可以达到的，这样便证明了2048的最高分是3932100分。

?

我的证明工作分为3步：

一，构造数据

构造出1个多行数据，每一行对应2048的一个状态，第一行是初始状态（只有2个2），最后一行是最终状态（16个数分别是4,8,16......131072）

二，验证数据正确性

编写一个程序验证每一行到下一行的转化都是对的，符合2048的规则

三，计算得分

其实只要验证一共只出现过16个4，那么得分就是最高分3932100

?

一，构造数据

要想构造数据，首先需要自己编写一个2048的程序，只需要1个控制台的程序即可

?

0，需要的主要功能如下：

（1）对记事本进行读写，把每一个状态和操作写到记事本的一行，下一次玩的时候读取记事本即可接着玩

（2）显示游戏界面，读取键盘的上下左右键，如果操作合法的话，进行相应的操作

（3）每次操作之后，要给出1个数，包含3个数：行i，列j，在i行j列出2还是4

?

1，规定数据结构

每一行放20个数，对应int s[21];的后面20个数，第0个数废弃不用

第1-16分别对应游戏界面中的16个数，0代表空格

例如，当s[1]到s[16]分别为2 0 0 0 2 0 0 0 16 0 0 0 16 2 0 0时，对应的状态就是

s[17]对应玩家操作，也就是上下左右，-4是上，4是下，-1是左，1是右

具体说来，s[17]代表的是玩家从上一行对应的状态变成本行对应的状态所进行的操作

s[18]是行，范围是0-3，s[19]是列，范围是0-3，s[20]是新出的数。

也就是说，自上一行前面16个数对应的状态开始，玩家进行了s[17]对应的操作，然后系统在s[18]、s[19]对应的位置新出了一个数s[20]，然后状态就变成了本行前面16个数对应的状态。

以我玩的结果举例，前2行是

0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 4 0 0 2?

（第一行的后面4个数没有意义）

也就是说初始状态是

第二行后面的4 0 0 2表示，我进行了4对应的下操作，即往下滑，然后系统自动在第0行第0列新出1个2

那么此时新的状态就是

也就是对应第二行前面的16个数。

?

2，判断新出的数的位置和大小

首先大小，是2还是4，其实很容易确定，

整个游戏中出现的最后一个数，无论是2还是4都不重要，都无法得分，在此之前有15次是必须要出4，其他的时候都必须要出2，这样才能达到最高分。

这15个状态和其他所有的状态很容易区分出来，即如果有1个空格和15个不同的数，而且其中没有2，那么此时就必须出4

代码：

?

int newNum(int *p)
{
	int s = 0, k, num0 = 0;
	for (int i = 1; i <= 16; i++)
	{
		k = *(p + i);
		if ((s^k) < s)return 2;//非0数不重复，否则出2
		if ((s^k) == s)num0++;//统计空格数量
		if (s % 4)return 2;//没有2，否则出2
		s ^= k;
	}
	if (num0 == 1)return 4;
	return 2;
} newNum(int *p)
{
	int s = 0, k, num0 = 0;
	for (int i = 1; i <= 16; i++)
	{
		k = *(p + i);
		if ((s^k) < s)return 2;//非0数不重复，否则出2
		if ((s^k) == s)num0++;//统计空格数量
		if (s % 4)return 2;//没有2，否则出2
		s ^= k;
	}
	if (num0 == 1)return 4;
	return 2;
}

?

然后是位置

?

需要申明的是，这个程序并不是一般的2048游戏，但是也符合2048的规则，

这个程序的唯一作用就是用来构造数据。

所以，这个程序不需要随机算法来决定在哪个格子出新数。

只需要按照s[1]，s[2]，s[3]......s[16]的顺序依次查看哪里有空格，第一个发现的空格作为出新数的地方即可。

根据我玩2048的经验，这样应该是可以玩到最高分的，这一点我并没有去验证，因为这样的话构造数据的时间代价比较高，我引入了flag这个变量，这是在整个构造数据的过程中唯一需要修改代码的地方。

实际上，在构造整个数据的过程中，并不要求程序一直是不变的，在需要的时候，随时都可以修改程序然后接着构造数据。

?

3，读取键盘

键盘的方向键和数字字母键不同，数字字母键每个按键对应1个字符，而方向键每个按键对应2个字符，根据后面那个字符可以判断是哪个方向

代码：

?

char direction()//读取键盘的方向键
{
	int c1 = _getch(), c2 = _getch();
	if (c2 == 72)return 'u';
	if (c2 == 80)return 'd';
	if (c2 == 75)return 'l';
	if (c2 == 77)return 'r';
	return ' ';
} direction()//读取键盘的方向键
{
	int c1 = _getch(), c2 = _getch();
	if (c2 == 72)return 'u';
	if (c2 == 80)return 'd';
	if (c2 == 75)return 'l';
	if (c2 == 77)return 'r';
	return ' ';
}

?

?

?

其他的代码细节就不再解释了。

?

4，完整代码

?

#include<iostream>
#include <fstream>
#include<conio.h>
#include<string>
using namespace std;

void display(int *p)//显示游戏界面
{
	for (int i = 0; i < 4; i++)
	{
		printf("\n\n\n");
		for (int j = 0; j < 4; j++)printf("%8d", *(p + i * 4 + j + 1));
	}
	printf("\n\n\n");
}

char direction()//读取键盘的方向键
{
	int c1 = _getch(), c2 = _getch();
	if (c2 == 72)return 'u';
	if (c2 == 80)return 'd';
	if (c2 == 75)return 'l';
	if (c2 == 77)return 'r';
	return ' ';
}

int dif(char c)//每个方向的运动偏移
{
	if (c == 'u')return -4;
	if (c == 'd')return 4;
	if (c == 'l')return -1;
	if (c == 'r')return 1;
	return 0;
}

bool move(int *p, int dif)//p,p+d,p+2d,p+3d
{
	int a = *(p), b = *(p + dif), c = *(p + dif * 2), d = *(p + dif * 3); //往d的方向移动
	for (int i = 0; i < 3; i++)//先把0集中在起点处，然后就只有相邻的数才能合并了
	{
		if (d == 0)d = c, c = b, b = a, a = 0;
		if (c == 0)c = b, b = a, a = 0;
		if (b == 0)b = a, a = 0;
	}
	if (a == b && c == d)d *= 2, c = b * 2, b = 0, a = 0;
	else if (c == d)d *= 2, c = b, b = a, a = 0;
	else if (b == c)c *= 2, b = a, a = 0;
	else if (a == b)b *= 2, a = 0;
	//上面计算了移动之后的数值，下面和移动之前比较，看是否真的有移动
	if (*(p) == a && *(p + dif) == b && *(p + dif * 2) == c && *(p + dif * 3) == d)return false;
	*(p) = a, *(p + dif) = b, *(p + dif * 2) = c, *(p + dif * 3) = d;
	return true;
}

void move(int *p)//滑动
{
	int d = dif(direction());
	*(p + 17) = d;
	bool b = false;
	if (d == 4)for (int i = 1; i <= 4; i++)if (move(p + i, d))b = true;
	if (d == -4)for (int i = 13; i <= 16; i++)if (move(p + i, d))b = true;
	if (d == 1)for (int i = 1; i <= 13; i += 4)if (move(p + i, d))b = true;
	if (d == -1)for (int i = 4; i <= 16; i += 4)if (move(p + i, d))b = true;
	if (!b)move(p);
}

int newNum(int *p)
{
	int s = 0, k, num0 = 0;
	for (int i = 1; i <= 16; i++)
	{
		k = *(p + i);
		if ((s^k) < s)return 2;//非0数不重复，否则出2
		if ((s^k) == s)num0++;//统计空格数量
		if (s % 4)return 2;//没有2，否则出2
		s ^= k;
	}
	if (num0 == 1)return 4;
	return 2;
}

void new_num(int *p)//判断哪里可以出1个新数
{
	bool flag = false;//唯一可以修改的地方
	int sum = 0;
	for (int i = 1; i <= 16; i++)if (*(p + i) == 0)sum++;//统计空格数量
	if (sum < 2)flag = false;
	for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++)if (*(p + i * 4 + j + 1) == 0)
	{
		if (flag)
		{
			flag = false;
			continue;
		}
		*(p + 18) = i, *(p + 19) = j;
		*(p + 20) = newNum(p);
		*(p + i * 4 + j + 1) = *(p + 20);
		return;
	}
}

int main()
{
	system("COLOR F0");
	ifstream in("2048.txt");
	ofstream out("2.txt");
	string in_line;
	while (getline(in, in_line));//注意2048.txt最后一行不能是空行
	char line[200];
	for (int i = 0; i < in_line.length(); i++)line[i] = in_line[i];
	int s[21];
	sscanf(line, "%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d", s+1,s+2,s+3,s+4,s+5,s+6,s+7,s+8,s+9,s+10,s+11,s+12,s+13,s+14,s+15,s+16,s+17,s+18,s+19,s+20);
	while (true)
	{
		display(s);
		move(s);
		new_num(s);
		for (int i = 1; i <= 20; i++)out << *(s + i) << ' ';
		out << endl;
	}
	return 0;
}<iostream>
#include <fstream>
#include<conio.h>
#include<string>
using namespace std;

void display(int *p)//显示游戏界面
{
	for (int i = 0; i < 4; i++)
	{
		printf("\n\n\n");
		for (int j = 0; j < 4; j++)printf("%8d", *(p + i * 4 + j + 1));
	}
	printf("\n\n\n");
}

char direction()//读取键盘的方向键
{
	int c1 = _getch(), c2 = _getch();
	if (c2 == 72)return 'u';
	if (c2 == 80)return 'd';
	if (c2 == 75)return 'l';
	if (c2 == 77)return 'r';
	return ' ';
}

int dif(char c)//每个方向的运动偏移
{
	if (c == 'u')return -4;
	if (c == 'd')return 4;
	if (c == 'l')return -1;
	if (c == 'r')return 1;
	return 0;
}

bool move(int *p, int dif)//p,p+d,p+2d,p+3d
{
	int a = *(p), b = *(p + dif), c = *(p + dif * 2), d = *(p + dif * 3); //往d的方向移动
	for (int i = 0; i < 3; i++)//先把0集中在起点处，然后就只有相邻的数才能合并了
	{
		if (d == 0)d = c, c = b, b = a, a = 0;
		if (c == 0)c = b, b = a, a = 0;
		if (b == 0)b = a, a = 0;
	}
	if (a == b && c == d)d *= 2, c = b * 2, b = 0, a = 0