俄罗斯方块--策略

hbghlyj

AI算出最致命的下一块,不限时间,每个移动均可撤销.
hatetris地址
有多种AI供选择:
HATETRIS, the original and worst
all 4x1 pieces, all the time
Brzustowski(1992)
Burgiel (1997)
其中hatetris是最智能的,而且会提供全部7种块来刁难你(当然,S和Z最难所以出现最多),因此难度最大.
all 4x1 pieces是无难度的,每次只提供4×1.
Brzustowski和Burgiel好像是只提供S和Z.
这些算法(除了第2个无脑4×1外 )都是跟据玩家的反应来选择下一个生成的方块的,没有任何随机性,所以玩家的操作可以用base 2048编码记录下来,用于replay和演示
---------
技巧:造阶梯形,最佳是两个阶梯的底端相接,比如\begin{align*}▢&▢▢▢\\
&▢▢
\end{align*}可以放两种(z和s),还有最左端留▢防z且上一行最右占满时在上两行从右向左连续叠s并消去整行
如果是方形就交错放,下面是base编码是5分的
ݸටໃঅஶƣໃם௨ಅƘݹமɦଈݚЦقෆऎ௨ദȣݹસقถݹષفІݹஶΟາɕ௨ചഫɝЗѻ൧ݹ௨൲ȜȠƐࢪժݒɷඞϼɒѺવՋຍଡуOȝ௧Ϫ൧ܡߛfඍݏࡑඥʨ൫ࠉಧƦߢࠒѮฮࠅħڂషݎ୦Ϻɍ
下面也是个5分的:
ݸටໃঅஶƣໃם௨ಅƘݹமɦଈݚЦقෆऎ௨ദȣݹસقถݹષفІݹஶΟາɕ௨ചഫɝЗѻ൧ݹ௨൲ȜȠƐࢪթчள੬تݡ௨ಬНݫЩඪࢩݪԥഠͳݶԬѼເञञvબچ௧ʦІףذఢƼѲळοຽसڴضÐɞసಀϿࢪתЕฆڇϣΒθ
下面也是个5分的
ݸටໃঅஶƣໃם௨ಅƘݹமɦଈݚЦقෆऎ௨ദȣݹસقถݹષفІݹஶΟາɕ௨ചഫɝЗѻ൧ݹ௨൲ȜȠƐࢪթчள੬تݡ௨ಬНݫЩඪࢩݪԥഠͳݶԬѼເञञvફڣஶѮฎұࢷٮЅஈЩೱ൧ॾƓطɲݾத߈ϽऍமQԠॹƘ3
换成早期的AI就容易多了,比如下面对于Burgiel是53分(后期是Z,S轮流,如同2楼所分析的那样)
హقະए௨චnݸƐڈໃݚ௨ඪඍݹహටະࡥԥගŒݹஜѼໃঅ௧ڏ൵ݹԦق໓ວ௨پషݹࢴౚܘɛ௨ගɑݹࢸටဉஈষڀໃݚעƅໃɛ௨තрݹமɤໃة౫ඤɑݹࢲۇفݶ౧قະߞذ೯Іݶవටଠݹ௬৩ຽಱ௨డໃމ௨پಭݷభටหɝƐචІݚԥගÐݹࢶق໒ݹࢻپଈݻƐචƖݹસஶໃњ௨ڈໃݬЭقݕݹવටฅஈ௩ɦІѧ௨౾ܘףۑටܡঐ௨ೱඍݸ൙ටଣ๐थ୮ຽߤݹටฅڢ௨ഋܘњ௨ಀඍܭ௨ೱܔࡉ௨ངଈݿذ൝ܒਙƐචØແࢴكƘݹบ౾ܘܯޜقฅ୬бටݭɣభටПѧ௩Ѳ༠ݹஜYܤݹహߩ໐ݸఢ੬ଭܭɷ೯ໃљ௧༦ܘɥવටݕށƐಀගݺɷಅະࡉ௨ڏଈࠇஜϺ༠ђಳ౾ܘɡۑಀмݎસ৩ลя౻චJݺޛ൜ಊɟऄலະࠇ௭ඤІɡݣ೯ಊף௫ඤɑѧ௮੬Лݬذසฅஉ௩Ѹ໗অ౻پಊږ௩Ⱦαວభඪڪٽࢸ೯ܒॿసم൧ɛஜشКєدٴล๐ഺɦܒࢲமƞЄಲઽຕ૭प

下面对于Brzustowski是33分
ౚටฅԓ௨౾Ȼݹஜɦໃݺƃقକਘ௨౾ಽݹചQາɒ౦شVށЩචÐݺmقܧٽஜƃІןЩ෨ແࠇ௰൜ܒঅಬϺໃףݫටฅஈமѸໃރ௨ඪධݹࢴටໄໂ௨ඪܘݺݸقໄఫ௨ڏ൧ݹলටลແ௨ඪජݹமϺຽঅ௧ٴໃןСට༨ཧணঋඤहϢඨІʥଅΟແऄ௨ڄໃײ௨൜ಸݹৎقທݮఒலໃף௧ڈແঀԦɨໂঌ௨೯ȣܭЬقЖݸಈඨƙɕࢲටЫܭذ൝ධܭذಅະࠇஜɦІɡݣ൝ܘঅࢳඨÐܭݻ൝ƙɕభಅໄஆಈ൜ಭם௰൝ඍנ௬ॴܤݪدڐໄɒసغЄࢭಏؾƊɛமQลஈࢷϽଆऎ௭චƖݿமɤଘމಒฃ༩ސఅكɭ
-------------
HATETRIS30行!!世界纪录
-------------
3维俄罗斯方块

hbghlyj

原文地址(很多处翻译得不好,有更好的翻译,还请指出 )
如果俄罗斯方块的生成遵循7个1包,7个1包的原则(I,J,L,O,S,T,Z为1包,每包内部随机排列,即7!种排列,英文是7-bag randomizer),且提供3个"预览"方块(preview),且允许手动"搁置"1个方块(hold),我们就有完备的永生策略:
将表格分为左4列,中间2列,右4列.
S,T,Z放在左4列,I放在中间2列,L,J,O在右4列.
STZ循环:4包一循环.(以下的"第i个T"指"第i,i+4,i+8...包中的T")
这个技术不需要任何"预览"方块,但需要允许手动"搁置"方块.

第一个Z必须在第一个T的后面(因为Z是封死的,S不会把T封死,所以S和T谁先谁后都行),必要时用hold来调序

第二个/第三个T不能是同一包里的第一块,必要时用hold来调序

第二个T必须和第三个T必须放在diagonally adjacent的位置(即,有1个公共顶点,但没有公共边)

第四个T必须在最后,用于封顶

LJO循环:1包一循环.
根据方块的顺序,需要使用不同的构造.为了选择合适的方块,至少需要预览5个方块(最坏情况是隔着4个STZI才能看到下一个L或J或O).或者,也可以只用3个预览和"巧妙"地使用 Hold.
O第一个出的情况(OJL, OLJ)

O第三个出的情况(JLO, LJO)

O第二个出的情况(下图所示是JOL.其镜像就是LOJ)

为了使STZ与LJO循环的Hold需求不冲突,需要使用一些高级技巧:
最坏情况下的包的配置,例如H?XX?X?和H?XXX?.其中“H”表示一个必须被搁置才能遵循STZ循环的方块.LJO循环中的被搁置方块用“?”表示,其余部分用“X”表示.使用3个预览和Hold,在第二件进入屏幕之前只能看到前4件. 这意味着您只能看到 H?XX,并且只知道 LJO 循环的第一部分. 因为必须将 H搁置,所以您被迫在不知道 LJO 循环其余部分的顺序的情况下做出决定. 如果 O 首先出现,则您可以按照上述步骤操作而不会出现问题. 剩下的情况你会遇到这样的困难:
不可能的 O 放置（例如 HLXXJXO、HLXXXJO）：
.........

hbghlyj

原文地址
致命的方块序列.即使Hold, kicks和"预先知道全部方块序列"也无济于事.甚至对于100列宽和40行高的表格也存在致命的方块序列.
由交替序列的 S 和 Z  (SZSZSZSZ...) 组成的俄罗斯方块游戏总是会在70,000 个方块之前结束。
以下部分将涵盖完整的证明。但首先，让我们通过查看左墙附近所有可能的 S 和 Z 摆放来说明证明背后的主要思想。

所有这些放置有什么共同点？添加到第一列的块不可能比添加到第二列的块多。 因此，第一列中的块永远不会多于第二列中的块。 这也意味着某些“特殊”的放置只能进行有限次否则第一列和第二列之间的高度差异过大。
证明的第1步:最多有120个S和Z被放置在特殊位置。
这里的"特殊放置"，是指横放的方块,或竖放且最左边的块在偶数列的方块。列从1到 10（从左到右）编号。

设$B_i$为第i列中的已占用方格的总数。设$H_i $为横放且横贯第(i-1)、i和(i+1)列的S和Z块的数量。设$V_i $为竖放且横贯第i和(i+1)列的S和Z块的数量。则对于 1...10中的每个i都成立$B_i = 2·V_{i-1} + 2·V_i + H_{i-1} + 2·H_i + H_{i+1}$
$V_0 = 0, V_{10} = 0, H_{0} = 0, H_1 = 0, H_{10} = 0, H_{11} = 0.$
比较相邻列中的已占用的方格数.对每个i=1...9有$B_{i+1} - B_i = ( 2·V_{i+1} + H_{i+1 }+ H_{i+2} ) - ( 2·V_{i-1 }+ H_{i-1 }+ H_i )$
化为
$2·V_{i+1} + H_{i+1} + H_{i+2} = ( B_{i+1} - B_i ) + ( 2·V_{i-1 }+ H_{i-1 }+ H_i )$   (☆)
$2·V_{i-1} + H_{i-1} + H_i = ( B_i - B_{i+1 }) + ( 2·V_{i+1 }+ H_{i+1} + H_{i+2 })$   (☆☆)
由于我们的矩阵有 20 行高，有$ B_{i+1 }- B_i $≤ 20 和$ B_i - B_{i+1 }≤ 20$。
用 (☆) 并从左侧开始,得
$ i=1:   2·V_2 + H_2 + H_3 = ( B_2 - B_1 ) + ( 2·V_0 + H_0 + H_1 ) ≤ 20 + 0 = 20$      (1)
$ i=3:   2·V_4 + H_4 + H_5 = ( B_4 - B_3 ) + ( 2·V_2 + H_2 + H_3 ) ≤ 20 + 20 = 40$    (2)
用 (☆☆) 并从右侧开始,得
$i=9:   2·V_8 + H_8 + H_9 = ( B_9 - B_{10} ) + ( 2·V_{10} + H_{10} + H_{11} ) ≤ 20 + 0 = 20$   (3)
$i=7:   2·V_6 + H_6 + H_7 = ( B_7 - B_8 )  + (  2·V_8 + H_8 + H_9   ) ≤ 20 + 20 = 40$    (4)
将(1), (2), (3), (4)相加得
$2·( V_2 + V_4 + V_6 + V_8 ) + ( H_2 + H_3 + H_4 + H_5 + H_6 + H_7 + H_8 + H_9 ) ≤ 20 + 40 + 20 + 40 = 120$
所以$ V_2 + V_4 + V_6 + V_8 + H_2 + H_3 + H_4 + H_5 + H_6 + H_7 + H_8 + H_9 ≤ 120$
所以最多有120个S和Z被放置在特殊位置.

证明的第2步:每放置240个方块就一定会产生一个洞或一个特殊放置。
洞表示空方格。上述条件意味着所有棋子必须竖放在 5 条通道中，每条通道 2 列宽且最左边的列的序号是奇数。

假设初始表面的形状是这样的，S 块有 3 个通道，Z 块有 2 个通道。让我们考虑一个12 个方块的序列。为了不违反条件，我们必须将6个S块放在S通道上，将 6 个 Z 块放在 Z 通道上。平均而言，即每个 S 道 2 件，每个 Z 道 3 件。这意味着高度差（Z 道的平均高度减去 S 道的平均高度）每 12 条增加 2。高度差将始终介于 -20 和 +20 之间，因为游戏在 20 行高的表格上进行。如果从-20 开始，我们将在 240 块后达到 +20。此时下一个 Z 块必须放在 S 道上。 120 块的限制也适用于所有其他通道组合。

下图所示是用一个Z块填掉2个洞:

证明的第3步: 游戏将在290·240块之前结束。
在第 1 步中，我们已经看到特殊放置的数量是有限的（120 个）。在第 2 步中，我们已经看到我们被迫进行特殊放置（因为我们不能留下无限的洞）。结合这些结果，我们得出游戏必在有限块内结束。我们还需要证明290·240块是上限。我们假设,每当必须留下洞时,进行一个非特殊放置,正好留下2个洞。我们将其称为方向变化（在 Z 道上放置 S 块，或在S道上放置Z块）(在证明的第 2 步中，在 40 块落下之后留下的每个洞要么是方向改变，要么是特殊放置,所以没有这个假设也可以证明相同的上限,只是措辞复杂)。首先，注意每个特殊位置不能填充超过 2 个洞，因此至多填掉 2·120 = 240 个洞。然而,表格不能包含超过 100 个由方向变化产生的洞。所以方向变化的数量限制在 170 次。这也将方向变化和特殊放置的总数限制为 170+120=290。每 240 件必导致这两者之一。这得出了 290·240 = 69,600 件的上限。

↑水平特殊放置可以露出2个不同列的洞.另一方面,如果没有其他特殊放置,将挖得不够深足以清除这两列顶部的2个洞.

↑垂直特殊放置可以露出或清除2个洞,但不能同时进行.

hbghlyj

open.library.ubc.ca/soa/cIRcle/collections/ubctheses/831/items/1.0079748

Tetris was first released exactly 37 years ago in 1984. In 1992, John Brzustowski proved in his graduate thesis that it was mathematically impossible to play an infinite game of Tetris as the game is statistically doomed to end.