“2048”游戏中的最值探究

“2048”游戏中的最值探究侯智谦屈彦辰麻润朗长春吉大附中实验学校摘要本文研究与热门游戏“2048”相关的几个最值问题,用组合数学的视角,利用“2048”游戏中的规律,对一定条件下操作步数和游戏得分中的最值做出较精确的估计ABSTRACTTHISPAPERDISCUSSESSOMEPROBLEMSABOUT“2048”GAMEWITHTHEMETHODSOFCOMBINATORICSANDTHEHIDDENLAWSIN“2048”GAME,SOMEMOREACCURATERESULTSABOUTTHEMINIMUMANDMAXIMUMOFTHENUMBEROFMOVESANDTHESCOREAREDONE12048游戏简介“2048”是一款比较流行的数字游戏,最早由GABRIELECIRULLI于2014年3月20日发行,游戏开始时出现两个数字2或4,玩家每次可以选择上下左右其中一个方向去滑动,每滑动一次,所有的数字方块都会往滑动的方向靠拢,系统也会在空白的地方随机出现一个数字2几率90或4几率10,相同数字的方块在靠拢相撞时会相加,同时得到与合成的新数字相等的分数不断的叠加最终拼凑出2048这个数字就算成功12基本定义为后文讨论方便，本部分定义一些将要频繁用到的名词。定义1没有经过合成,直接出现的4叫做游离4特别的,开局时出现的4也是游离4定义2开局时给出的两个数以及每次出现的新数都是2的游戏,或者说从不出现游离4的游戏,叫做理想游戏,反之称为实际游戏定义3游戏盘面中出现2048或另外指定的数字时称为胜利,这个被指定的称为目标N2N数字定义4游戏恰好胜利时,除目标数字外的其他数字叫做额外数字定义5当无法再进行操作时,即所有方格都填满,且任意两个有公共边的方格中的数字均不相同时,游戏结束,此时的累计得分叫做最终得分注胜利与结束是两个不同的概念,二者之间既不充分也不必要定义6从游戏开始到某时刻累计得到的分数,叫做该时刻的实时得分,用S表示胜利时的实时得分叫做胜利得分定义7为合成某一数字所必需的或4构成的数字序列叫做合成链为使2N12,N合成顺利进行,另外需要一个2或4,用来引发合成链从引发合成链的这一步到合成的操作称为链操作2N定义8某一步操作后,盘面上所有数字之和叫做该局面的特征和,用M表示定义9从游戏开始到某一局面为止,产生的游离4的个数叫做游离数,用K表示3最值探究2048游戏本质上是一个操作变换问题随着游戏的进行,操作的总步数以及游戏的得分为不断累积的两个量以下结合这两个量的变化规律探究一定条件下的最值问题31与操作步数有关的最值问题操作步数是游戏时长的定量指标,达到不同的局面所需的操作步数不尽相同操作步数与局面的关系可以由下面的定理概括定理1形成某一局面时操作的步数由该局面本身的数字分布以及该局面的游离数决定,与操作顺序无关证明考虑每一步操作后的特征和M的变化,据规则,数字的移动与合成不改变M值,而新出现的数字使M加上2或4设该局面游离数为K,则出现2的次数为,由于除2K开始时的两个数外,每一次出现2或4对应一步操作,故总操作步数为,与操作顺序无关结合定理1,我们研究与操作步数有关的最值问题命题12048实际游戏最多能够操作131052步，理想游戏最多能操作65533步。证明对于这个问题,我们首先考虑结束时的盘面,由于盘面上只有16格,故最长只能容纳长度为15的合成链,另一格用来引发合成链,对于实际游戏,其最大可能数字为4,则盘面上可能出现的最大数字为131072此时剩余15格,同上可知可能出现的次大数字为65536,以此类推,可知盘面出现下左图局面时,操作达到极限,无法再移动,此时有,由于盘面上每一个数的合成最终都需要一个4来引发,故有,172640IM16K由定理1得总操作步数为131052对于理想游戏,下右图为极限局面,由定理1得总操作步数为655336137IK必须指出,与操作步数有关的问题是整体性的,可能某一步操作合成多个数字,也可能某一步操作只是单纯的移动,没有合成,因此各个合成链在操作步骤上相互影响,不能简单求和计算总步数维基百科中有错误结论1310381,疑为按照合成链单独计算所致下面讨论胜利的最小操作步数命题2理想游戏中合成方块至少需要操作的步数为,实际游2N123N16N戏为4N317为证明此结论,我们先给出一条引理引理对于一局以为目标数字的理想游戏,胜利时的额外数字之和至少为2N2N证明事实上,考虑的合成链,每一步链操作产生的2到最后只能用于合成额外数,而理想游戏的合成链长度为N,其链操作共有步,故额外数字之和至少为N1N命题2的证明由于胜利时,理想游戏中,代入定理1的操作步数2M0K公式中即得不难看出,实际游戏合成与理想游戏合成的最小操作步数是相等的1N2N事实上,对于盘面数字之和相同的局面,由定理1知,游戏过程中的游离4越多,操作步数越少,故实际游戏中的最小操作步数必须在每步都出现4时取到将这样的实际游戏中盘面出现的每个数都减半,等效于一局理想游戏,且原游戏合成等效于新游戏合成,故1N2N二者步数相等。特别地，当N11,合成方块，实际游戏至少需要519步，理想2112048游戏至少需要1032步。32与游戏得分有关的最值问题得分是衡量玩家游戏水平的重要定量指标,而且比起操作步数,玩家们更加关注得分的高低熟悉游戏的玩家都知道,2048游戏胜利时的得分一般在2000021000分之间,而不同水平玩家的最终得分各异本节研究与最终得分和胜利得分相关的最值问题这些问题,有的已被广2481625612864325121024204840966553632768163848192481632512256128641024204840968192131072655363276816384大2048玩家们研究过,对于正确的结果,我们从另外的角度给予说明,对于错误的或不精确的结果,我们给予纠正或更精确的估计为研究方便,我们先定义特征分值的概念定义10理想游戏中合成方块的过程中导致的得分叫做方块的特征分值2N2N命题3方块的特征分值为2N1证明显然,2的特征分值为零考虑一个方块的合成过程,必须要经过两个,四个2N12N,个4出现时间及次序不确定这些过程,由于每次产生的新数都是2,根据游NN戏规则,上述过程导致的得分为故我们12244NNNNN有方块的特征分值为2N2特征分值的存在,意味着实时得分受局面的约束进一步来说,理想游戏的实时得分就是各个方块特征分值之和事实上,计分规则决定了各个合成链中得分互不影响,相互独立,因而可以直接加和计算总分值对于实际游戏,我们用定理2概括类似的关系定理2形成某一局面时的实时得分S由该局面本身以及该局面的游离数决定,与操作顺序无关证明记为该局面时方块的个数,若是理想游戏,则实时得分即为各个方块特征分值NA2N之和,即但实际游戏中游离4不计分,故实际的实时得分应当从上述和式17NN中减去4K,即有,与操作顺序无关1742NNSKA我们首先讨论最终得分的最值最终得分的最大值,可以结合前文中的极限局面,用定理2的公式求出作为被玩家们广泛研究并不断挑战的一个问题,在此直接给出结论实际游戏最终得分最大值为3932100维基百科中误作39321561,疑为漏减游离4所致,理想游戏最终得分最大值为1835012最终得分的最小值,对于实际游戏当然是0分,结束时盘面交错出现2和4即可然而,理想游戏中没有游离4,故必然有合成得分以下我们研究理想游戏最终得分的最小值命题4理想游戏最终得分的最小值是48对于得48分的情形,我们先给出一种操作22424242左左2左2242424242左2左2下222244242224424224442左下左2左2左2下24424242422424242242422424424424224上24上2422上24224242242422422424244242424242424224上2424左2424左2424424242424222424242242224442424242424442422424下2422上2424下2424242424442424248242242224222424424242422422下24244248424824242424箭头上方是移动的方向,方格中用红色表示新出现的数字,下同另一方面,考虑结束时的盘面,同样的数字不能超过八个否则必有两个相邻,游戏没有结束,有以下可能情形存在16或更大的数,由于16的特征分值已达48分,故此时得分48若至少有两个8且为最大数,由于2最多为八个,其余的数只能为4,此时得分56若只有一个8且为最大数,剩余15个数只能为七个2和八个4,或七个4和八个2,前者得分为48,后者得分为44盘面上4为最大数,只能2和4交错出现,得分为32以下只需证明得分为32和44的两种情形不能成立对于32分的情形,结束时盘面只能为2和4交错出现,如右图所示若最后出现的2是加粗的2,则上一步只能为左移,且移动之前第二行不能顺次为2,2,2,4否则无论上一步为何种情形,操作后都有相邻的2剩余,不可能故只能为空,4,2,4如下左图,由于纵向三列总存在相邻的相同数字,不可能为上下移动的结果,故此前的移动只能为左右移动,不能出现一横行顺次为2,2,2,4或4,2,2,2,这不可能,并且最迟在倒数第五步时即出矛盾若最后出现的2是右下角的2,则由对称性,可设上一步为左移,此时同可证其不成立对于44分的情形,结束时上图中其中某个4变为8,考虑生成这个8的一步,由知这步必在最后四步之中否则将这个8等效为4可得中五步内可能不出矛盾,不妨设其为左右移2424424224244242上下下动,则移动前该行顺次为4,4,2,4或4,2,4,4,由盘面2和4交错排列的特性可知,此时局面横向纵向均有相邻的4下右图为一种情形,再向前推一步时无解下面我们研究胜利时的最小得分命题52048的最小胜利得分实际游戏为18432,理想游戏为20488。证明这个问题我们也推广到一般情形这也是一个被玩家们广泛研究的问题,但得出的结果实际游戏,理想游戏在某些情形不精确,在此我们给出精确的估2N21N计考虑目标数字的得分,对于理想游戏就是其有效分值,对于实际游戏,当这个N21N都由游离4合成时,可得胜利得分的下界为然而,额外2N42NN数字也可能有得分对于实际游戏,当时,可以控制额外数字2和4交错排列,315此时额外数字得零分,最小胜利得分即为,以下以为例给出控制过程2N1,5本节的构造只给出链操作,下一节中将定性说明第一图的蛇形排列可以达到14N422321684下321688左6442464128256512641282565123步641282565128192409620481024819240962048102481924096204810244224224264424下424右424641282565121281282565123步24210248192409620481024819240962048102481924096204810242422422424244下4242左4242242102424243步24248192409620481024819240962048204816384242对于的情形,以下简述操作要点,详见附录31N额外数字2和4交替排列,每次的新数出现在前一行的末尾按移动方向如有必要,下移之前加一步左右移动称为腾挪,将最右左列上面的2或4移走第一次下移以后,左右移动时新出现的数字要考虑下一次腾挪后的阵型,保证腾挪后2和4交替排列15N4428422424424224244244242442424244242右左左2步6432168右6432168下6432161625612851210242561285121024256128512102416384819240962048163848192409620481638481924096204842242242646424右12824下424256128512102425612851210242562565121024163848192409620481638481924096204816384819240962048以下同的情形指对额外数的处理,下同的情况比较复杂,但可以说明1N167N取不到事实上,假设能够取到,那么额外数字不能合成得分,每步操作至多有一2次合成,且新出现一个数,故移动过程中空白格数不减少,且由初始局面知最多一个不妨设最后一步为左右移动,考虑最后的一次上下移动,由于空间限制,可能有如下几类情形字母表示与邻格不相同的数字注意,此三图的上一步必为左右移动,否则空间不足以排列合成链,故左图不可能成立中图下移一步后,出现横向的三个2或三个4相连,下一步移动时必然合成得分,此不可能右图中,上一步只能为左移,新出现的数只能是加粗的4此数也可能在右上角,但不能为2,否则下一步移动时两个2合并为4,向前推一步时,出现两个空白格,也不可能据此可以说明时,胜利得分最小值为,时,若额外数仅16N16975081N得4分,则只能合成一次,进而最多出现一个空白格,同上可知不可能实现,则胜利得分最小值为以下给出此二例的链操作172589064482216222128643216右128643216下128643232512256102420482步5122561024204851225610242048327681638481924096327681638481924096327681638481924096以下同的情形15N蓝色的4由连续的3步中前两步出现的2合成,7下同4481624322422561286432右2561286432下25612864321024512204840963步1024512204840961024512204840968192163843276865536819216384327686553681921638432768655362424244242DABCD244422224C4ABCD242424224C4ABCD421286464251225610242048327681638481924096左左2步242224224225625624右51224下22241024512204840961024512204840961024102420484096819216384327686553681921638432768655368192163843276865536以下与的情形类似1N对于理想游戏,不妨设游戏胜利前的最后一步操作为左右移动,注意以下事实横向的相邻方格都是2的最多只能有一对,且其中有一个为最后出现的,否则这两个2会在左右移动时合并成4每一个大于等于4的数字的左右两侧,除中所述的一对相邻2以下简称相邻2外,各只能有一个2若多个大于等于4的数字共行,该行显然至多有两个2额外数字之和的最小值受引理1约束称胜利时有大于等于4的数字的行为A类行,否则为B类行,则除相邻2外,A类行中至多有两个2,B类行中至多有一个2I当额外数字有8或更大的数时,由于8的特征分值为16分,故胜利得分16NII当额外数字只有2时,A类行只有一个,B类行有三个,加上一对相邻2,2的个数最多为6个,额外数之和,由引理1知当时,假设能取到分,则7N78额外数只能有6个2,不妨设最后一步为左移,可能的排列情形有如下两种其中,加粗的2是最后出现的,可能出现在任一行的末尾无论哪一图,前面的操作中,必然有上下移动而左图已经不可能,因为上下移动后数字不可能“悬浮”在中间的行对于右图,向前推一步,目标数字所在行是2,32,32,2,再前面的操作中,若为左右移动,新出现的2只能是左右两个,不可能是上面三个中的某一个,前推到上下移动的一步时无解因此,当时,胜利得分最小值为,从“蛇形6N21N排列”见下节出发,每步移动后新出现的2不在同一行最后一个除外即可,以为例6简述如下2右下2左2222423步23216843216843216886422其中,底行的两个2在最后两步出现III当额外数字除2外只有一个4时,A类行最多两个,另两个为B类行,可知2最多有7个,额外数之和,这要求7110N因此,当时,胜利得分最小值为,以为例给出链操作0N2410N22左42下22242424204820484096281921638432768655362226422222226422左左4816324816328816325122561286451225612864512256128642242右242下21616322步642425122561286451225612864512256128128222左22422步24225122562562102422IV当额外数字除2外只有两个4时,A类行最多三个,另一个为B类行,可知2最多有8个,额外数之和,这要求当时,若两个4分别在两行,仿II813N可证不能成立如下左图,若两个4在一行,则该行至多两个2,4096所在行至多两个2,另两行至多各一个2,加上容许的相邻2,至多7个如右图,矛盾因此,当时,胜利得分最小值为,以为例给出链操作12N218N12N228422左1622下2221632641283步1632641283232641282048102451225620481024512256204810245122562224242右242下2464641282步2562422048102451225620481024512256204810245125122242242409622V当额外数字除2外只有三个4时,四行可以全部是A类行,2最多有9个,额外数之和,这要求,但当时不能成立如图,与IV类似39016N224224224096222224242409622242242242232768222242242423276822右左左2步因此,当时,胜利得分最小值为,以为例给出链操作135N21N15N2242282226432168右6432168下6432161612825651210242步12825651210241282565121024163848192409620481638481924096204816384819240962048422442464642左1282下422212825651210241282565121024256256512102416384819240962048163848192409620481638481924096204824242242424左424右24245125121024102410242048163848192409620481638481924096204816384819240962048222242左242右242242424242步2424163848192409640961638481928192222327682VI当时,胜利得分最小值为,链操作如下16N1659830622482416242128643216右128643216下128643232256512102420483步2565121024204825651210242048327681638481924096327681638481924096327681638481924096242224244212864642右1281282左256222565121024204825651210242048256512102420483276816384819240963276816384819240963276816384819240964222424242424右2424上32768424512512102420483步409616384819281923276816384819240963276816384819240962424232768424下422232768226553644422222左2步右下左下左2步顺便指出,对于此问题,理想游戏的情形要比实际游戏复杂得多,没有实际游戏中那么强的规律性,对于不同的N,链操作截然不同,时甚至颠覆了传统的蛇形合成路线,可见16N2048游戏的灵活性33蛇形排列与最值构造前两节我们讨论了几个最值问题,但除了问题3以外,都没有全部给出取到最值的构造,而且由于步骤繁多,也不可能完整列出操作步骤本节我们结合2048游戏中一条常用的技巧蛇形排列,定性说明这样的操作步骤的存在性众所周知,要合成一个比较大的数字如2048,4096甚至更大,通常的做法是将比目标数字小的2的方幂按照递降等比数列的顺序蛇形排列,最后由N一个较小的数字引发整个合成过程如右图,从两个2出发沿S形路线逐步合成,最终可得到2048右图是最简单的蛇形排列的阵形,其中只有一条合成链以及一个用来引发合成链的数字2,称这样的阵型为简单蛇形排列当然,游戏中并非总能顺利的排出蛇形排列,通常会见到以下的几种阵型,每一行之内的数字顺序有所颠倒,而由它们也能够合成目标数字这样的阵型与蛇形排列等效,称为广义蛇形排列如果一个广义蛇形排列与简单蛇形排列等效,则称之为广义简单蛇形排列下面的几个图均为广义简单蛇形排列我们指出,任何的简单蛇形排列都能够达到,而且为达到这样的局面,只需使用恰能排下该局面的最少行数称为占用行数不妨假设由下至上逐行排列,对占用行数归纳只占用一行的情形,结论成立220040204220442082208402842284428822A402A422A442A822A842上述序列中,每个四位数表示一行内从左向右的数字排布,0代表空位,A代表16,而每一步操作均为向左移动假设占用K行以内的均成立,当占用行时,设目标数字为,则1K2N458KNK首先可以按照一行的排法将底行排满,此时,底行的最小数字,由归纳假设知可用X上面不超过K行合成X注意出现简单蛇形排列即等效于能够合成目标数字,使上下两行的X重合,下移即可在底行出现2X重复这样的操作,直至底行饱和即恰为四数,此时在上面的K行内排出的简单蛇形排列,与底行相接构成1234,NN42N的简单蛇形排列,且整个过程只使用行1取,这样的操作也存在,但由于恰少一格用来容纳引发131072合成链的2,故理想7游戏得到极限局面后游戏结束实际游戏最后一格用4代替2引发合成链,可继续进行下去,直至实际游戏的极限局面,游戏结束,问题1的构造已解决由于的简单蛇形排列的特征N42281632641024512256128422643216810245122561284228163264102451212825642232816641024512128256和为,由定理1知已操作步,而由简单蛇形排列出发还需步合成,总操2N12N1N2N作步数恰为,问题2的构造解决3对于命题5的构造,实际游戏由于第一图之前每一步都出现4,故将所有数减半后第一图与理想游戏的简单蛇形排列等效时的第一图虽为广义简单蛇形排列,但也可以由157N上面的证明得到存在性对于理想游戏,我们也可以直接从简单蛇形排列出发,构造出各个N对应的链操作,详见附录4总结本文研究了有关2048游戏操作步数和最终得分在一定条件下的最值问题,现将有关结果列举于下I操作步数的最值条件结束,最大值结束,最小值胜利,最小值2N实际游戏131052144317理想游戏655332516N未在正文中讨论,但可由终局局面及定理1推得II胜利时实时得分最小值及结束时得分最值2NN实际游戏理想游戏N实际游戏理想游戏N实际游戏理想游戏2048153617961419660821300438169358441001542598445876443248108192922016917508983056596128111843220488171966088不存在6256320124096045064结束最小0487640772139011298316结束最大39321001835012当然,这里仅仅是从组合最值的角度,对2048游戏中的一些问题进行研究关于2048游戏的问题还有很多,作为有胜负的游戏,自然要问是否存在必胜策略针对这个问题有人设计出了“EVIL2048”,每一步操作后新生成的数都在对玩家“最不利”的位置上尽管在普通的2048游戏中合成出2048较为容易,且大量的玩家都已做到,然而,没有人能够在“EVIL2048”中合成出2048,也没有人对2048必胜策略的存在性给予否定,这说明2048的必胜策略问题仍然是个谜此外,游戏中的数字排布,最终得分的期望值,2和4出现频率对游戏的影响,等等,都是可以进一步研究的对象附录一命题5的构造1实际游戏的链操作非常容易,只需按正文中的要点操作即可,以下只以为例简述39N9N表格中上面的行闲置不用,故略去44816右24216下2424左242425612864323步256128643225612864323步5122