用矩阵探索魔表的复原
本帖最后由 blueten 于 2021-3-15 21:21 编辑0 前言 魔表是WCA的官方比赛项目，比较冷门，参与人数不多，但是学习起来却非常容易，即便是初学者也能在很短的时间学会复原。目前针对魔表的研究并不多，即便是高手使用的复原方法基本上也只是在初级方法的基础上做了一些小的调整而已。本文通过建立数学模型来对魔表进行求解，并据此对魔表的复原方法进行探索。 本帖最后由 blueten 于 2021-4-12 21:11 编辑
1 术语 首先，我们对魔表的指针、立柱和转动表示方法进行说明。 魔表一共有2个面（这里称之为F面和B面），4个立柱，18个指针，其中角上的指针都是互相关联的，因此实际上我们只需要关注14个指针的变动，这14个指针的名字见下图。 本文将抬起立柱对应的外轮称之为F轮，按下立柱对应的外轮称之为B轮。 转动表示法参考“李老豆”在魔表预算法教程中的方法——A(f, b)。其中f表示F轮的转动点数，b表示B轮的转动点数；数字是正数则表示顺时针，负数则表示逆时针。A表示立柱的状态，共16种，分别为： （01）UR：ur立柱抬起，其他三个按下； （02）DR：dr立柱抬起，其他三个按下； （03）DL：dl立柱抬起，其他三个按下； （04）UL：ul立柱抬起，其他三个按下； （05）U：ul、ur立柱抬起，其他两个按下； （06）R：ur、dr立柱抬起，其他两个按下； （07）D：dr、dl立柱抬起，其他两个按下； （08）L：dl、ul立柱抬起，其他两个按下； （09）UR-DL：ur、dl立柱抬起，其他两个按下； （10）UL-DR：ul、dr立柱抬起，其他两个按下； （11）ur：ur立柱按下，其他三个抬起； （12）dr：dr立柱按下，其他三个抬起； （13）dl：dl立柱按下，其他三个抬起； （14）ul：ul立柱按下，其他三个抬起； （15）ALL：四个立柱都抬起； （16）all：四个立柱都按下。 本帖最后由 blueten 于 2021-3-15 22:53 编辑
2 数学模型 16种立柱状态中，除了all只有B轮、ALL只有F轮以外，其他14种状态都同时存在F轮和B轮，因此外轮一共有30种转动方法。在下表中我列出了这30种转动方法对需要调整的14个指针的影响，其中“1”、“-1”、“0”分别表示指针的转动与外轮转动方向相同、相反、无关。 魔表一共有14个指针需要调整，在没有跳步的情况下，一次拨动只能调整1个指针，因此需要拨动14次才能完全复原。我们假设某一指针打乱后的初始点数为β，14次转动对该指针的影响分别为a1,a2,a3,…,a14，14次转动的点数分别为x1,x2,x3,…,x14，则我们可以得到如下关系式： 以此类推，对于全部14个指针都能列出类似的关系式，我们将得到如下的方程组： 上述方程组可以表示成的Ax+β=12N形式，其中，，，。 我们称A为变换矩阵，x为操作向量，β为初始状态向量（14个分量按表从上到下的顺序排列）。 令N=0，则方程简化为Ax+β=0，可解得 至此，魔表的复原便简化为一个14阶线性非齐次方程组的求解。|A|=0时方程无解，|A|≠0时方程有唯一解。如果你对数学原理不感兴趣，那么可以直接跳到第5节，那里有本文探索出的新方法。 本帖最后由 blueten 于 2021-3-15 21:25 编辑
3 对初级复原法建模 初学者复原魔表的步骤一般为 （1）将一面的四个棱指针与中心指针对齐； （2）将中心指针和四个棱指针调整至零点； （3）翻面后，将这一面的四个棱指针与中心指针对齐； （4）将所有指针对齐； （5）将所有指针调整至零点。 我们将翻面后的面定为F面，翻面前的定为B面，则以上步骤对应的操作分别为： 第1步：U(0,x1)、R(0,x2)、D(0,x3)、L(0,x4)； 第2步：all(x5)； 第3步：U(x6,0)、R(x7,0)、D(x8,0)、L(x9,0)； 第4步：ur(x10,0)、dr(x11,0)、dl(x12,0)、ul(x13,0)； 第5步：ALL(x14)。 我们从表1中将以上14个操作对应的变换列抽取出来组成变换矩阵： 求其负逆矩阵得 将负逆矩阵和初始状态向量代入方程的解即可求得操作向量x，再将x的各个分量转换成转动表示法的形式，即可得到魔表的解法。 例打乱公式：UR0+ DR2- DL2+ UL4+ U2+ R5- D4-L5+ ALL5+ y2 U4- R2- D1+ L5- ALL5+ UR UL 由图可知，初始状态向量，代入中可解得操作向量，通过加减12将所有的分量调整到-5~6之间，可得。将其整理成复原步骤——U(0,-4) R(0,5) D(0,6) L(0,-1) all(1) U(4,0) R(2,0) D(-1,0) L(5,0)ur(2,0) dr(0,0) dl(-4,0) ul(-2,0) ALL(-1)，操作一下你会发现这就是初学者常用的解法。 本帖最后由 blueten 于 2021-4-22 23:54 编辑
4 探索其他复原方法 为了改进现在的复原方法，我们可以从3个方面着手——转动次数、立柱状态变换次数和翻面。减少转动次数目前只能寄希望于跳步，尽管已经证明魔表的上帝之数是12，但是目前我们还没有在12次转动之内复原魔表的能力。那么我们就只能从减少立柱状态变换次数和不翻面这两个方面来探索了。 想要做不翻面，难度没有想象的那么大，能够盲拧一个十字其实就可以做到不翻面，但这是有风险的，很容易DNF。 由于魔表的操作满足交换律，因此将同样立柱状态的复原步骤合并，就可以减少立柱状态变换次数。以上一节所述的初级方法为例，第1步和第3步的复原步骤中，立柱状态完全一样，那么我们就可以将解法合并为——U(4,-4)R(2,5) D(-1,6) L(5,-1) all(1) ur(2,0) dr(0,0) dl(-4,0) ul(-2,0) ALL(-1)。这样一来，立柱状态变换次数由14次减少到了10次。（这其实就是“李老豆”的“魔表预算法”。） 还能不能再合并下去呢？至少上面的这个方法不能了，剩下的6个立柱状态都不一样。 16种立柱状态中，除了all只有B轮、ALL只有F轮以外，其他14种状态都同时存在F轮和B轮。那么我们可不可以从这14种状态中，选择7种状态，每种状态下都转动F轮和B轮，完成魔表的复原呢？如果可以，那么我们就将立柱状态变换次数由14次减少到了7次。 从14种状态中选择7种状态，一共有3432种组合，但并不是每种组合都能复原魔表。第2节中的结论告诉我们，当变换矩阵A是奇异矩阵时，这种组合是不能复原魔表的。除此之外，魔表又是高度对称的（上下对称、左右对称、前后对称、两个斜对称、中心对称），剩下的那些满足条件的组合中还可以排除对称情况。笔者精力有限，没有对这3432种状况进行逐一分析，希望能有数学和编程方面高手能助我一臂之力。 在此我就只介绍我发现的一种组合——L、R、UL、DR、ur、dl、UL-DR，从表1中将这7个立柱状态的14个操作对应的变换列抽取出来组成变换矩阵。
求其负逆矩阵得
还以上一节中的打乱为例，将负逆矩阵与初始状态向量代入中，并将所有的分量调整到-5~6之间，可得。 将其整理成复原步骤——L(1,5) R(3,-3) UL(4,-1) DR(-1,6) ur(-4,6) dl(0,-4) UL-DR(2,-2)，操作一下你会发现魔表复原了。这说明这一节的思路是可行的。 笔者在此只验证了其中一种组合的情况，剩下的三千多种组合中或许还能找到与此组合不同构的可解组合。 本帖最后由 blueten 于 2021-3-15 22:30 编辑
5 矩阵探索方法在速拧中的应用
以上是理论分析，但我们终究还是要回到实际复原上。如果我们能计算出操作向量，那么不但可以将立柱状态变换次数降至7次，还能避免翻面。但是显然15秒的观察内我们根本做不到这一点。从上一节我们得到的矩阵来看，最后两行一共有7个非零项，也就是说我们需要计算2次7个数字的加减法。对于这样的项，显然我们只能通过初学者常用的“对齐”的方式来操作。因此UL-DR这个立柱状态必须放在最后。
另有4行是4个非零项，显然我们也没有时间全部计算，因此也需要尽可能多地使用“对齐”方式。而且如果想要不翻面的话，涉及到背面的“对齐”就只能自己预先计算了。此外，为了更好地变换立柱状态，我们也需要对立柱状态的先后顺序进行一定的安排。
还以上一节中的方法为例。
我们先将矩阵解法表示成算式的形式。
现在，我来介绍一下怎么用这个组合复原魔表：
（1）L状态：转动F轮使DF与RF对齐，转动B轮bL点；
（2）UL状态：转动F轮和B轮使CF、RF、DF、DR对齐；
（3）R状态：转动F轮使UF与LF对齐，转动B轮bR点；
（4）DR状态：转动F轮和B轮使CF、LF、UF、UL对齐；
（5）ur状态：转动F轮fur点，转动B轮bur点；
（6）dl状态：转动B轮bdl点，再转动F轮使UR与DL对齐；
（7）UL-DR状态：转动F轮和B轮使所有指针指向零点。
（注：也可以将R和DR放到L和UL前面，ur和dl也可以互换。）
这种方法下，我们只需要计算5个点数——bL、bR、fur、bur、bdl，除了fur是4个数字相加减外，其他4个点数都是2个数字相减。另外的9个点数都可以靠“对齐”来解决。而且由于已经预先计算转动点数，本方法不需要翻面。对于速算能力比较强的选手来说，还是能够在观察时间内计算出5个数字的。
如果你觉得以自己的能力无法在观察阶段算出这5个数字，或者你觉得不翻面没有足够的把握复原魔表，那么你可以选择在前4个立柱状态完成后翻面，之后的ur、dl和UL-DR状态，翻面后会变成UL、DR和UL-DR状态，你会发现只要重复翻面前UL、DR和UL-DR状态的做法就可以完成复原，而这个方法只需要计算下面这2个数字，这一点对于大多数人来说应该都是轻而易举的。
此外，在上面的立柱状态的顺序下，变动立柱状态需要按动立柱的次数仅为10~12次，远远少于目前常用的复原方法：
（1）打乱→L（或R）（0~2次）：
（2）L→UL，按下dl立柱（1次）；
（3）UL→R，按下ul立柱，抬起ur和dr立柱（3次）；
（4）R→DR，按下ur立柱（1次）；
（5）DR→ur，抬起ul和dl立柱（2次）；
（6）ur→dl，按下dl立柱，抬起ur立柱（2次）；
（7）dl→UL-DR，按下ur立柱（1次）。
而且，无论是否翻面，我们都只在最后的UL-DR状态才会将指针都指向零点，因此在前面的6个立柱状态下，你甚至可以无视魔表的朝向。
对比一下初级方法、“李老豆”的预算法和本文中的两种矩阵法，我们发现，除了计算数字的个数比较多以外，矩阵法在另外三个指标上都优于初级方法和预算法。
本帖最后由 blueten 于 2021-3-15 22:45 编辑
6 结语 本文通过建立数学模型得出了用矩阵计算魔表解法的方法，并介绍了根据此方法找到的一种复原方法，该方法大大提升了魔表的操作效率。但本文只验证了3432种组合形式中的一种，在那些还未验证的方案中或许还有更好的组合形式等待发掘。希望能有数学和编程方面的高手来继续我未完成的工作，也希望能有魔表的玩家尝试一下这种方法，或许这种方法能在魔表速拧上起到很大的作用，使魔表的成绩有飞速的提升。蓝十 2013ZHAN412021年3月14日
仔细想想，考完研到现在也就5年，线性代数的东西基本都还给老师了。现在想求个逆求个转置都得现查公式，颇多感慨。
数学与魔方结合的力作，先mark为敬，有时间一定仔细拜读
高技术力贴！强！ 真厉害！回头我也试试:):)
页:
[1]
2