俄罗斯方块--策略

本帖最后由 hbghlyj 于 2021-6-27 18:32 编辑

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

2^#

发表于 2021-6-27 05:26 | 只看该作者

本帖最后由 hbghlyj 于 2021-6-27 15:09 编辑

原文地址(很多处翻译得不好,有更好的翻译,还请指出

)
如果俄罗斯方块的生成遵循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）：
.........

TOP

hbghlyj

3^#

发表于 2021-6-27 15:24 | 只看该作者

本帖最后由 hbghlyj 于 2021-6-27 18:39 编辑

原文地址
致命的方块序列.即使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个洞,但不能同时进行.

TOP

返回列表回复发帖

俄罗斯方块--策略

[收藏此主题] [关注此主题的新回复]

[通过 QQ、MSN 分享给朋友]