外文翻译 - 俄罗斯方块的理论

0外文原文TheTheoryofTetrisHendrikJanHoogeboomandWalterA.KostersLeidenInstituteofAdvancedComputerScienceUniversiteitLeiden,TheNetherlandsfhoogebookostersgliacs.nl1IntroductionAnyalgorithmrequiresatheoreticalanalysis.Suchananalysismayaddressissueslikecomplexity(e.g.,NP-completeness9),decidabilityandpracticalpropertiesconcerningspecialcases.InthispaperwewouldliketodiscusstheTetrisgameinthislight.Wewillfirstdescribethegameandsomeofitsvariants,showNP-completenessofacertaindecisionproblemnaturallyattachedtothegameandthenprove(un)decidabilityinsomeothercases.WeconcludewithsomepracticaltopicsthatarisefromtheNP-completenessproof.ThispaperisbasedonaseriesofarticlesthatbeginswiththeoriginalNP-completenessproofofDemaine,HohenbergerandLiben-NowellfromMIT7,thatwaswell-noticedinthepopularpress.Theproofwassimplifiedin,leadingtoajointjournalpaper.Inand14theotherissuesmentionedaboveweredealtwith.Forfullproofswerefertothesepapers.Tetrisisaone-persongamewhererandompiecesconsistingoffourblocksfalldown,oneatatime,inanoriginallyemptyrectangulargameboard.Theplayerisallowedtorotateandhorizontallymovethefallingpiece.Ifanentirerowoftheboardisfilledwithblocks,itisremoved(“cleared”).Themainpurposeofthegameistokeeponplayingaslongaspossible.Thedecisionproblemunderconsiderationisessentiallythefollowing.Givenapartiallyfilledgameboard(referredtoasaTetrisconfiguration),andanorderedfiniteknownseriesofpieces,isitpossibletoplayinsuchawaythatthewholeboardiscleared?TheNP-1completenessproofisbyreduction.Itisshownthatinstancesoftheso-called3-PartitionproblemcanbetranslatedintoratherinvolvedTetrisconfigurations,wheresolutionscorrespondwithboardsthatcanbecleared.Theconfigurationsusedsuggestthequestionofconstructibility:whichconfigurationscanbereachedduringgameplay?Therathersurprisinganswerappearstobethatalmostanyconfigurationcanbereached,givensuitablepieces.Anotherissuehastodowithdecidability:iftheuserinteractionissomewhatbounded,isitthendecidablewhethercertainnaturalsetsofpiecesequencescontain“clearing”sequences?Allthesetopicswillbeaddressedinthesequel.2RulesThegameofTetrisisplayedonarectangularboardconsistingofsquare(initiallyempty)cells.Theboardisofxedwidthw4and,forourpurposes,ofunboundedheight.Sevengamepiecescanbeused,eachcoveringfourboardcells|fromnowonusuallycalledblocks;theyaredepictedbelow.Thesepiecesareknownas(fromlefttoright)Oorsquare,Jorleftgun,Lorrightgun,Iordash,Zorleftsnake,Sorrightsnake,andTortee:The“computer”generatesa(usuallyrandom)sequenceofpiecesthatdropdownfromthetopoftheboarduntiltheyrestontopof(partsof)previouslydroppedpiecesoronthebottomofthegameboard.Theuser/playercandeterminethepositionandorientationofthepiecesbyrotatingandmovingthemhorizontallywhiletheyfall.Wheneverallthecellsofarow(alsocalledline)ofthegameboardareoccupied,thelineiscleared;allblocksaboveitareloweredbyonerow(andnomore).Thisrowclearingcanhappenforseverallinessimultaneously.InTetristhepurposeusuallyistoclearasmanyrowsaspossiblegiventhegeneratedsequenceofpieces,whileavoidingtorunoutofspacevertically.AsthegameofTetrisitselfisfinitestate(andhencedecidable)whenplayedonaboardofgivenwidthandheight,hereweassumetheboardisofunboundedheight.Tetrishassomepeculiarimplementationdetails.Letusmentionafewexamples.1.IntheNP-completenessproofbelowitisessentialthatTetrispiecesthattouchthe2bottomofthegameboardorblocksfromotherpiecescanstillslidehorizontallybeforetheyare“fixed”.Insomeimplementationsthisishowevernotpossible,andpiecesarethenfixedimmediatelyaftertouchdown.TheNP-completenessproofmightstillholdforthisotherversion,butanewconstructionisnecessary,sincethecurrentonereliesonfillingoverhangswithhorizontallyslidingsquares.2.In7,2someattentionisgiventorotationmodels.Itisindeedaproblem,orratheraconvention,todescribewhich“holes”allowTetrispiecestopassthrough,perhapsinvolvingmeticulousintermediaterotations.Andwhenarepiecesstillallowedtorotate?Inthesequelwedonotrefertothisissueanymore,sincetheconstructionsinvolveddonotgiverisetoproblemsofthiskind.3.SomepeoplearesurprisedbyseeingfloatingblocksinTetrisconfigurations.Aswillbeshownlater,(nearly)everyconfigurationisconstructible,i.e.,canoccurduringregulargameplay.Thisincludessituationswhereblocksdonotrestonotherblocks,butjustremainfloating|onair,sotospeak.Thisisaconsequenceofthestrictlyappliedrulethatasoneormorelinesarecleared,theyareremovedfromthegameboard;blocksabovethesedisappearinglinespreciselyfalldownasmanylinesaswerecleared.Thisissuewillonlybeofimportanceinthesectionontheconstructionofconfigurations.3NP-completenessAsmentionedintheintroduction,weshallanalyzethecomplexityofsomedecisionproblemsrelatedtoTetris.WeshallalsolooselydescribetheproofofthemainNP-completenessresult.Precisedefinitions,theorems,proofsandrelatedresultscanbefoundin7,3,2.Inthissectionweconsiderthefollowingdecisionproblem,calledTetrisClearing:Instance.ATetrisgameboardpartiallyfilledwithblocks,andanorderedsequenceofTetrispieces.Question.Isitpossibletoplayinsuchawaythatthegameboardisleftemptyintheend?ItisnotdifficulttoseethatthisproblemisintheclassNP.WenowproveNP-hardness.As3mentionedbefore,theproofisbyreduction.Weusethe3-Partitionproblem:Instance.Ansequencea1，a2，.，a3sofpositiveintegersandapositiveintegerT,sothatT/4=1,and1=4和无限的高度组成。七个模块可以用，每一个模块覆盖四个单元格或者通常称为小格;对他们描述如下。这些块被称为（从左至右）O或square，J或leftgun，L或rightgun，I或dash，Z或leftsnake，S或rightsnake，和T或tee：生成一个序列（通常是随机的）块下降从顶部开始（部分）计时，直到他们到达先前降落模块的顶部或面板的底部。在模块下降过程中用户/玩家可确定块的位置和方向通过旋转和水平移动模块在模块到达底部之前。每当一个行上的所有单元格（也称13为线）被模块填满时，该行被清除，它上面的所有模块下降一行。这些行的清除是同时进行的。俄罗斯方块的目的通常是尽可能多的清除按序列生成的一整行，同时避免垂直空间用完。随着比赛进行，游戏（因此判定）在给定的宽度和高度的面板上玩，我们在这里假定板是无限的高度。俄罗斯方块有一些特有的实现细节。让我们举几个例子：1.NP完整性证明如下俄罗斯方块模块触碰游戏板的底部或在其他模块之前仍然可以水平滑动这在它们被安放之前是至关重要的，然而在某些情形下这是不可能的，模块出现后很快就着陆了。NP完整性的证明仍然是有效在某些的情形下，而一个全新的构想是非常必要的，因为当前模块太依赖于水平滑动区域。2.7.2给出了一些要注意的旋转模式。这确实是一个问题，或者更确切地说用一个惯例来描述，允许俄罗斯方块模块通过，也许涉及中间旋转。什么时候所有的模块可以旋转呢？在本文中我们没有提及到这个问题，因为所涉及的建义不会产生这种问题。3.有些人会感到惊讶当他们看到下一个要下落的选模块在俄罗斯方块候选块列表中时。（几乎）每个模块都能在游戏中有规律的出现。这也包括块不停留在其它的块上而仅仅在视图中出现，可以这么说。这是一个严格适用规则的结果，当一或多行被清除后，这些行的模块将从游戏面板上消失；消失的模块上面的模块将下降相应的距离。这个问题将仅仅是模块构成的重要部分。3NP-完整性在这里我们将分析一些在介绍中提到的有关俄罗斯方块决策问题的复杂性。我们将简单描述NP-完整性结果的证明。定理的证明和相关结果可以7，3，2中找到。在本节中，我们主要考虑了以下问题，被称着俄罗斯方块的清除：实例：一个俄罗斯方块游戏面板和一系列有序的俄罗斯方块模块。问题：是否能玩游戏当面板底为空时？这不是一个数据输入和输出的问题，而是一个NP类的问题。我们现在证明NP困难性。正如之前提到的，证据是在减少。在这里我们使用3分区的问题：实例：一个序列a1，a2，.，a3s正整数和一个正整数T，使T/4=1，和1=1）的空面板，当且仅当空面板的片数是2k+1的倍数且I型模块的数是偶数时。我们有一个直接的推论：定理：在正常的干预下，俄罗斯方块序列的组成仅由I型和O型且面板的宽度为10，这该组态的结果是可判定的。两块组件的排列位置对赢得比赛有很大的关联4。16让我们用一个稍微意外的结果结束本节。只限单个模块（其可以是在标准的俄罗斯方块模块中）俄罗斯方块在正常的干预下结果是可判定的，即使我们不这样（需要）明确地知道算法决定在每一个特定的情况下：定理：正常干预情况下，俄罗斯方块由一种模块组成在固定宽度的面板上，其结果是可知的。面板中的模块的数量和种类为游戏的组态提供了可靠的保证10。5可操作性NP完整性的证明需要由一个相当复杂的俄罗斯方块组态开始。它看上去就像一个很自然的问题形如这种组态是否会发生在正常游戏过程中，更一般的说：可能发生的是什么组态呢？答案有点令人吃惊：（几乎）任何组态都有可能显示出来！一个俄罗斯方块组态是一个游戏面板，其中一些小格是已经被填充了的。如果一个组态在一开始都不能用一系列的组件块按照移动和旋转来进行填充，则称这样的组态是不可被塑造的组态。在这中情况下，我们将证明，基本上每种合理组态都是可被塑造的。在处理各种面板宽度的情况下一些简单的条件应该是有用的。比如组态是，在面板的宽度w=13的情况下，可塑造的。我们建义用276个俄罗斯方块模块，清除（4276-25）/13=83的中间行。我们首先记住，面板的宽度w是4的倍数，在任何时候，面板中模块所占的小格个数都是4的倍数，每新增加一个模块都增加4个小格，因此清除一行则清除w个小格。显然，在任何可塑造的组态中小格的个数应该是4的倍数。同样，如果w+2是4的倍数，则小格数应该是2的倍数。这两个简单的限制只会同时出现一个：定理：使用合适的俄罗斯方块模块在宽度为w的空面板上塑造一个由P个小格组成的组态时，当且仅当组态满足下列条件时该组态才是一个可塑造：1、没有行是完全填满的，2、没有任何一行的下面行所包含的填充了的小格数是0个，3、如果w是4的倍数，那么p也是；如果w+2是4的倍数，则p也是。下一节专门给出定理的证明，给予一个明确的建义（见12执行一个Java小应用程序的形式）。在本文中，我们假设定理中所述的三个条件都得到满足。5.1建议在面板上构建一个网格状的组态模型。在14中给出了所有详细信息。对于每一行的构建分为两个阶段。首先，我们建立了一个平台，提供塑造组态的框架（它可以防止坠落的俄罗斯方块模块下降到较低的行）。一般的平台形式如下所示，图片在右侧。表示右下方为空的平台，一旦它被填充上，整排将被清除。该平台的建设需要清除3或7的中间行。左端产生的正方形块数在0到3之间，这被称为平台的状态。我们需要这样的状态目前占用或清除在过去的单元格的总数必须是4的倍数。第二阶段，该行重建阶段，我们在塑造顶部的后一行的组态平台时，采用6个额外的行。通常我们塑造连续的矩形在顶部是两列宽和六行高选用必要的单元格，从左至右进行。再次，然而，我们有4倍数的限制，这样我们用余块填充矩形。这种状态是17非常多的在矩形的左边第三列处。最后的矩形被设计来填充平台的最后角度和矩形的第六行，清除不属于组态的部分。有时，塑造中所需要的小格数不是4的倍数，我们必须考虑这种情况。我们设计一种三个小格在上面一个小格在下面的模块来解决这个问题。这种过度通过计算右侧来实现。这种过度被用来作为平台上下一行的起点。如果没有过度，我们通过放一横I在下一行上来开始（认为引入4倍的过度）。在奇数宽度的情况下，过度可以随时被删除。矩形的精确形式（对于每个状态，过度和小格的块数）是繁琐的，见14。要特别注意即时清除的矩形中间行。6结论到目前为止，我们已经讨论了几个问题以某种方式连接到的俄罗斯方块游戏中。事实上，一个众所周知的和易于理解的俄罗斯方块游戏拥有如此丰富的结构是令人惊讶。这显然是有深刻的数学思想，如之间的连接NP完整性和每一天的生活。这适合在更大的研究，其中许多图片游戏问题将得到解决，比照、1，6。许多问题保持开放。其中，人能想到的游戏规则的许多变种，但清除是其中最普遍的方式。7参考1E.R.Berlekamp,J.H.Conway,andR.K.Guy.WinningWaysforYourMathematicalplays.Volume1and2,AcademicPress,NewYork,1982.2R.Breukelaar,E.D.Demaine,S.Hohenberger,H.J.Hoogeboom,W.A.Kosters,andD.Liben-Nowell.TetrisisHard,EventoApproximate.InternationalJournalofComputa-tionalGeometryandApplications(IJCGA)14(2004)41-68.3R.Breukelaar,H.J.HoogeboomandW.A.Kosters.TetrisisHard,MadeEasy.TechnicalReport2003-9,LeidenInstituteofAdvancedComputerScience,2003.4J.Brzustowski.CanYouWinatTetris?MastersThesis,UniversityofBritishColumbia,1992.5H.Burgiel.HowtoLoseatTetris.MathematicalGazette81(1997)194-200.6E.D.Demaine.PlayingGameswithAlgorithms:AlgorithmicCombinatorialGameThe-ory.Proceedings26thInternationalSymposiumonMathematicalFoundationsofCom-puterScienceMFCS2001,J.Sgall,A.PultrandP.Kolman(editors),LectureNotesinComputerScience2136,pages18-32,2001.187E.D.Demaine,S.HohenbergerandD.Liben-Nowell.TetrisisHard,EventoApproximate.ComputingandCombinatorics,9thAnnualInternationalConference,T.WarnowandB.Zhu(editors),LectureNotesinComput