一种基于线性代数的对“多次占卜2重新排序牌库”的证明方法

  • # 万智牌
  • # 万智牌扩画
  • # 炉石传说
  • # 炉石卡组攻略

 

      前言

      小突兔这么可爱,玩会儿《炉石传说》怎么了?

      小突兔通过某种神秘的方法(也许是无限沙德沃克...)不断触发着【间谍机器人】的战吼,小突兔能通过这种方法重新排序对手的牌库吗?

         小突兔这么可爱,玩会儿万智牌怎么了?

         小突兔操控【巫惑井】和四块地,坟场中有一张生物【吞世龙】和另一张生物【乙太精怪】,小突兔想要施放【尸变】结附于坟场中的【吞世龙】达成组合技,小突兔能够通过多次触发【巫惑井】的进场异能占卜2重新排序(按任意顺序)牌库,然后支付4点费用把小突兔想要的前两张牌抓起来吗?

      又到了新一届的《羊毛杯EDH数学建模竞赛》,这次裁判抛出的奖励是给出证明过程的小突兔可以免费领取最新T2系列的中文补充包,众所周知,【不吸食致幻油墨的牌手都只能度过相对失败的一生】,为了尽可能吸食烁油,早日完化升天,因此有必要对“多次占卜2重新排序牌库”进行建模论证。

      证明

      建模过程如下:

      对于按照既定顺序排序的edh牌库(99张),我们总可以按照编号的方式,将其编码为一列向量,其结果如下:

 

      对于随机打乱的牌库(记为列向量A),我们可以随意选取一种随机状态,通过如下形式进行表达:

       对于多次【占卜2】,我们可以通过如下矩阵对其进行描述,【占卜2】的异能可以分为下列3种情况的组合:

全保留(单位阵)

将第一张放在牌库底

(置换矩阵2,记为M2)

将第一张和第二张调换位置

(置换矩阵3,记为M3)

      例如,我们想全部保留,此时,下一时刻(进行一步操作后的牌库状态)可以表示为: 

       例如,我们想将第一张放置牌库底,此时,下一时刻(进行一步操作后的牌库状态)可以表示为: 

        例如,我们想将第一张和第二章交换位置,此时,下一时刻(进行一步操作后的牌库状态)可以表示为: 

       例如,我们想把两张都放到下方,那么下一时刻(进行一步操作后的牌库状态)可以表示为: 

       例如,我们想把第二张放到下方,第一张留在牌库顶,那么下一时刻(进行一步操作后的牌库状态)可以表示为:  

       考虑到全部保留的状态是单位阵点乘A向量,不改变向量本身。因此,占卜2的操作可以视作是置换矩阵2置换矩阵3的组合后的多次运算结果。

      对列向量的重新排序,可以等价于交换列向量中任意两个元素的位置,同时保证其他元素的位置不变。这里的等价是显然的,如果需要【a元素】在【1的位置】,【b元素】在【2的位置】....【x元素】在【99的位置】....。那么只要交换【a元素】和【1号位置】的元素,再交换【b元素】和2号位置的元素,依次类推即可完成排序。我们把等价后的结论,记为“结论1”

      于是“多次占卜2对牌库进行重新排序的问题”,就等价于“多次占卜2可以调换牌库中任意两张牌的位置,且其他牌位置不变”。

      下面,我们构造一个已经进行编码的列向量A表示牌库,其中,p和q都是>1且<99的整数;

       我们的目标是使得A变成目标向量B,其中仅有下标为p和q的元素交换了位置,即: 

      这里,我们可以通过以下步骤完成这一目标:

      ① 将X1到Xp-1的元素依次交换至向量末端,这一步可以表达为:用【置换矩阵2】经过(p-1)次作用于向量A达到状态;

       ② 将Xp+1到Xq-1的元素依次和Xp换位置(置换矩阵3),每次换位置后交换至向量末端(置换矩阵2),这一步可以表达为: 

        ③ 将Xp交换至向量末端(置换矩阵2),其表达式为: 

       ④ 将Xq+1到X99的元素依次和Xq换位置(置换矩阵3),每次换位置后交换至向量末端(置换矩阵2),表达式为: 

         ⑤ 同上一步,继续将X1到Xp-1的元素依次和Xq换位置,每次换位置后交换至向量末端,表达式为: 

       此时,不难注意到,步骤⑤产生的结果向量和步骤①结束时的结果极为相似,其中仅有Xp和Xq换了位置。 

       ⑥ 将X1到Xp-1的元素依次和Xq换位置(置换矩阵3),每次换位置后交换至向量末端(置换矩阵2),表达式为: 

 

        可以看到,此时结果已经达到最初目标,实现了在其他元素位置不改变的情况下,仅改变了Xp和Xq的位置。 

         将其推广至列向量元素数量为n(牌库数量为n)的一般表达式,其结果为:

       以下是一个从由【X1】到【X11】共11个元素构成的列向量,假设我们需要交换X6(红色)和X9(蓝色)的位置,通过上述运算,编程后我们可以得到如下算例: 

import numpy as np

 

a = np.array([1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11]).reshape((-1,1))

print("a_0 =" , a.T)

 

 

m_2 = np.array([[0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1] ,

                [1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0]])

 

m_3 = np.array([[0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0] ,

                [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1]])

 

n = 11

p = 6  

q = 9

 

a_1 = np.dot(np.linalg.matrix_power(m_2 , p-1) , a)

print("a_1 =" , a_1.T)

 

a_2 = np.dot(np.linalg.matrix_power(np.dot(m_2 , m_3) , q-p-1) , a_1)

print("a_2 =" , a_2.T)

 

a_3 = np.dot(m_2 , a_2)

print("a_3 =" , a_3.T)

 

a_4 = np.dot(np.linalg.matrix_power(np.dot(m_2 , m_3) , n-q) , a_3)

print("a_4 =" , a_4.T)

 

a_5 = np.dot(np.linalg.matrix_power(np.dot(m_2 , m_3) , p-1) , a_4)

print("a_5 =" , a_5.T)

 

a_6 = np.dot(np.linalg.matrix_power(m_2 , n-p+1) , a_5)

print("a_6 =" , a_6.T)

其输出结果为:

 说明推导过程正确,以流程图的形式进行展示,可以得到下图:

        据前文等价后的“结论1”,我们可以证明,“在有限次占卜2的异能下,牌手可以重新排序自己的牌库”

     群论视角下的占卜2

       上述过程中不难看出,【置换矩阵2】和【置换矩阵3】自身可以表达为一个为置换群,因此两个置换群的群元可以生成整个置换群。这是关于Cayley定理的推论:“每个有限群都是某一个有限置换群的子群。”

      Cayley定理(所有字都认识但合在一起完全看不懂系列):

     FAQ:

      Q:如果我参加羊毛杯,我能在比赛中使用并简化上述组合技吗?

      A:经《第81届羊毛杯行星理事大会》研讨决定,沿用威世智规则宪法的原判不变。即此类非常见且非典型组合技在其操控者使用对应套牌参赛前,必须先向有关部门(裁判组织)提前备案和说明。具体内容见附件1:《关于使用非常见组合技的报备流程及说明》。

 

      Q:文章太长不看,这个证明太复杂了,还有更好的简化方法可以简化此类组合技吗?

      A:赛前有目的的引导你的对手使用控制类套牌,并提醒他尽可能反击任何会产生占卜类效应的卡牌及异能。

   最后

      重症声明: 本人是一只小突兔,仅代表小突兔文明对上述问题的看法,约等于通篇胡说八道,可能不具任何实际意义,证明的过程如有笔误,恳请各位大师指正。

      祝愿每位牌手都能享受万智牌的对局,希望大家积极参加羊毛杯,加入羊毛杯的大家庭中,这是一个学术氛围浓厚的集体,也是一个奖品丰厚的赛事,每只小突兔在这里都能找到属于自己的快乐!

 AI最懂小突兔XP系列.jpg 

 

 

11月8日 发布于北京
全部评论 23条
按时间排序

还没有评论

63 23