用马尔可夫链进行建模游戏

用马尔可夫链建模玩游戏

使用“关上盒子”探索概率建模

介绍

从和朋友打牌到在轮盘赌桌上赢钱,一个精彩的游戏对大多数人来说是无法抗拒的诱惑力。但是不管多么有趣,在几次失败之后,即使是最乐观的玩家也禁不住要问:“游戏是不是偷偷摇过的?”对于那些对概率有一些了解的我们来说,不解答这个问题会感到非常不满意。在这篇文章中,我们将探讨一种用于回答这类问题的概率模型类型。具体来说,我将展示如何将马尔科夫链应用于游戏“关上盒子”,希望能激发你运用概率回答自己的游戏相关问题。

什么是马尔科夫链,它们与游戏有什么关系?

马尔科夫链是一种简单、广为研究的概率模型,可以对许多现实世界的随机过程进行建模。具体而言,马尔科夫链的目标是模拟一个概率事件序列,其中事件来自一个被称为状态的集合。为了实现这个目标,马尔科夫链在一个被称为过渡矩阵的矩阵中存储了在任意两个状态之间转换的概率。除了这些状态和过渡矩阵来指定随机过程的行为外,马尔科夫链的定义特征是马尔科夫性质。直观地说,该性质断言,在不考虑先前发生的状态序列是哪些的情况下,当前状态必须包含确定过渡到任何下一个状态的概率所需的必要信息。因此,任何满足此性质的随机过程都可以用马尔科夫链来建模,使其成为一个非常强大的工具。为了更好地理解这些概念和马尔科夫链的一般性,让我们来看一个简单游戏的例子:

假设你要进行一系列公平硬币抛掷的赌博。在游戏开始时,你以5美元开始,每次硬币抛掷之前你预测结果(正面或反面)。每次硬币抛掷,如果你猜对了,你赚1美元;如果你猜错了,你输1美元。游戏在你达到0美元或10美元时结束。

如果我们将游戏的状态定义为每次硬币抛掷后玩家的现金余额,那么马尔科夫性质成立,幸运的是,我们可以用马尔科夫链来模拟这个游戏!从图形上来看,我们可以将这个马尔科夫链的状态和过渡概率表示如下:

在上图中,橙色圆圈代表游戏状态,箭头代表状态之间的转换概率。请注意,所有的转换概率都是0.5,因为改变状态需要正确猜测公平硬币抛掷的结果。此外,状态0和10有一个指向自身的箭头,标有概率为1,因为它们是游戏的终止状态。

通过在本文的其余部分读完后,我敦促你回到这一部分,考虑如何回答上述所述的简单游戏的这些问题。

“关上盒子”游戏解析

为了真正探索与马尔科夫链概率建模相关的某些复杂性,我们将把精力集中在游戏“关上盒子”上。我在刷Instagram Reels时偶然发现了这个游戏,并对规则有一些模糊的理解,所以我决定去弄清楚赢的难度有多大。

Roland Scheicher / Roland Scheicher at German Wikipedia, Public domain, via Wikimedia Commons

Shut the Box是一款多人游戏,使用由九个方块(标有1到9的)和两个六面骰子组成的棋盘进行游戏。在每个玩家的回合中,所有的方块都处于竖立的状态。然后,两个骰子被掷出,玩家被允许将任何两个骰子的值相加得到的和与之相等的方块翻面。玩家重复这个掷骰子和翻面的过程,直到没有竖立的方块的子集的和等于两个骰子的和。此时,玩家的回合结束,他们的分数是棋盘上仍然竖立的方块的总和。在这个版本的游戏中,当所有玩家完成他们的回合后,得分最低的玩家被认定为获胜者。然而,如果一个玩家的回合结束是因为他们能够翻下所有的方块(即“shut the box”),他们自动赢得游戏。正是这个特定的规则引起了我的注意,因此将成为本篇文章的重点探讨。具体来说,我想回答的问题是,“shut the box”有多难?

使用马尔可夫链建模“Shut the Box”

从前文可以清楚地看出,我们现在应该将“Shut the Box”建模为一个马尔可夫链。虽然这可能看起来像一个直观的下一步,但我们要确保这是可能的,需要检查马尔可夫属性是否成立。为此,我们将定义此游戏的唯一状态为集合{1、2、3、4、5、6、7、8、9}的所有子集。这是因为在玩家的回合中的任何时刻都可以通过翻转和翻下的方块来唯一地描述这些状态。从数值上来看,我们可以将这些状态看作是9位二进制数(竖立的方块为1),共有2⁹个独特的状态。在这种状态定义下,马尔可夫属性成立,因为只有骰子的概率特性、当前状态和游戏规则决定了状态之间转换的概率。最重要的是,我们知道当前状态时,玩家回合中达到的之前状态对未来达到其他状态的概率没有影响。

现在,状态已经明确定义,并且我们已经确定了“Shut the Box”确实可以被建模为一个马尔可夫链,唯一剩下的要定义的元素是转移矩阵T。具体来说,Tᵢₖ(第i行第k列的条目)表示从状态i过渡到状态k的概率。在确定这些概率时,建模这个游戏的有趣复杂性就显现出来。

为了确定从一个状态过渡到另一个状态的概率,我们必须回答一个问题:“在游戏中必须发生什么行动才能导致状态改变?”对于我们感兴趣的游戏“Shut the Box”,决定下一个状态的有两个概率性行动:掷骰子和选择要翻面的方块。让我们先来研究骰子在状态i和状态k之间的过渡中的作用。我们首先将Sᵢ和Sₖ定义为分别包含状态i和状态k中竖立数字的集合。为了使从状态i过渡到状态k的概率非零,显然Sₖ必须是Sᵢ的真子集。这是因为在状态之间转换时,竖立的方块数量必须减少,并且一旦放下方块,就不能再翻起。在这种状态表示和Sₖ ⊂ Sᵢ的假设下,过渡过程中翻下的方块组成集合D = Sᵢ – Sₖ(Sᵢ中不在Sₖ中的元素)。

因此,此过渡发生的一个必要条件是掷骰子的点数之和必须等于D中元素的和。形式上,必须满足以下方程:

其中X₁和X₂是表示两个骰子的值的离散随机变量。如果我们将z作为D中元素的和,那么以上方程在使用两个六面骰子时成立的概率可以推导如下:

在z < 2或z > 12的情况下,从状态i转换到状态k的概率为零,因为不存在两个常规骰子的点数和等于z。

尽管填充转移矩阵的条目似乎只需要进行这种概率计算,但状态转换还需要玩家在掷骰子后从一组有效移动中选择。因此,要从状态i过渡到状态k,不仅骰子的点数总和需要等于z,还需要玩家选择翻转集合D中的方块,而不是可能有多种与骰子点数和一致的其他选项。

为了模拟人类策略的这个组成部分,我们将假设玩家在随机均匀地选择要翻转的可能方块集合。在此假设下,玩家选择状态k的概率为1/Nᵢₖ,其中Nᵢₖ是Sᵢ的非空子集的求和等于z的数量。

有了上述信息,我们现在可以正式定义转移矩阵的条目。转移矩阵中的每个条目表示两个事件发生的概率:

  1. 骰子的点数和等于z(事件1)
  2. 玩家随机选择翻转特定集合的方块,将状态从状态i转换为状态k(事件2)

因此,转移矩阵的条目可以定义如下:

重要的是要注意,上述转移矩阵的定义并未考虑玩家回合结束的概率。当玩家“关闭盒子”或在观察到骰子点数后无法翻转方块时,游戏会出现这种情况。在这两种情况下,1/Nᵢₖ是未定义的,因此它们必须单独处理。

根据上述状态的二进制表示,状态i = 0足以表示“关闭盒子”,因为所有方块都已翻转。由于这是游戏的“胜利”状态,我们可以修改转移矩阵,使得留在状态0的概率为1(即 T₀₀ = 1)。

最后,我们将添加一个“失败”状态(L),表示玩家回合由于“不幸”的骰子点数而结束。具体来说,为了将此状态纳入转移矩阵中,我们需要知道Sᵢ的子集之和没有等于X₁ + X₂(两个骰子的和)的概率。虽然可以明确计算此数量,但我们可以相对于其他转移矩阵值来定义它,如下所示:

因为转移矩阵中的每一行表示一组概率分布,它们必须等于1。此外,由于它是游戏的最终状态,离开该状态的概率为0。

通过上述关于准确转移概率的结果,我们现在能够利用马尔可夫链的一些重要特性来回答一个问题:「关闭盒子」有多难?具体来说,我们可以回答这个问题:一个玩家使用完全随机策略「关闭盒子」的概率是多少?

用Python计算“关闭盒子”的获胜概率

在尝试计算这个游戏的「胜/败」概率时,了解转移矩阵的用途是很重要的。对于马尔可夫链,转移矩阵使我们能够探索在单次转换后状态的概率分布如何通过矩阵-向量乘法演化。数学上,我们可以简单地写成:

其中T是转移矩阵,πₜ是表示经过t次转换后所有状态的概率分布的行向量。因此,鉴于我们已经知道当前处于任何状态的概率,我们可以回答以下问题:“选择任意一次掷骰后,我们以随机方式选择要翻转的方块,那么在任意一次掷骰后处于任何状态的概率是多少?”此外,利用对游戏初始状态(所有方块朝上)的确定性知识,我们可以轻松地定义π₀并递归地将其与T相乘,以确定任意数量的转换(投掷骰子+翻转方块)之后的状态分布。这个递归可以用以下闭式表达式重写为πₜ:

模拟「关闭盒子」的马尔可夫链具有两个最终状态:“胜利”和“失败”,一旦进入这些状态,就无法离开(也就是吸收状态)。
因此,我们可以确定在有限数量的转换后,所有状态的概率分布将收敛到这两个状态的分布。直观上来说,对于「关闭盒子」而言,这个说法强调了玩家的回合必须以“关闭盒子”或未能这样做而结束,因此玩家在一次回合中所能行动的步数是有限的。

要找到这个上限,注意到在每次掷骰后,玩家翻下一个方块,直到标有“1”的方块独自竖立,因此他们无法在下一次掷骰中“关闭盒子”。 这个行动序列总共需要9步才能达到最终状态,因为总共有9个方块。因此,解决胜/败概率就是将t ≥ 9并计算πₜ。计算πₜ后,玩家使用随机策略“关闭盒子”的概率是πₜ的第一个条目,因为它对应于所有方块都被翻下的状态(S₀)。此外,在状态分布收敛之前,可以从0开始重复演化状态分布的递归过程。此外,在这种情况下,还有更快的计算πₜ的方法,这些方法利用了吸收状态的存在和转移矩阵的特殊定义。在此文章中将不详细介绍,可以在这里了解更多: https://en.wikipedia.org/wiki/Absorbing_Markov_chain

为了在Python中计算胜/败概率,我们将完全依赖科学计算库Numpy。首先,我们定义游戏的方块数、骰子数和状态数,分别为9、2和513。

num_tiles = 9num_dice = 2num_states = (2**num_tiles)+1 #+1代表游戏结束/失败的状态

使用这些简单的参数,我们可以使用二进制字符串表示来生成每个状态的集合表示Sᵢ,如下所示。

# 生成所有可能的状态的表示tile_nums = [i for i in range(1, num_tiles + 1)]states = []for i in range(0, 2 ** num_tiles):
binary_rep = np.binary_repr(int(i),width=num_tiles) states.append([tile_nums[idx] for idx,a in enumerate(binary_rep) if a == '1'])

这里的Numpy二进制重现函数非常有用,它使用整数i生成状态的二进制表示。因此,通过找到这个字符串中的1的位置,我们可以确定状态i中哪些瓷砖是竖立的。

处理完状态表示后,我们使用以下代码生成转移矩阵:

# 生成转移矩阵transition_matrix = np.zeros((num_states, num_states))for i in range(num_states):  for j in range(num_states):    transition_matrix[i][j] = compute_transition_probability(i, j)  transition_matrix[i][num_states-1] = 1 - transition_matrix[i][:num_states-1].sum()  assert np.allclose(transition_matrix[i].sum(), 1), "转移矩阵不是随机的"

最后,使用转移矩阵回答这次探索的核心问题,即使用完全随机的策略,玩家“关上盒子”的概率是多少?为了做到这一点,我们必须定义初始分布π₀,涵盖所有状态,如下所示:

# 定义初始状态分布init_state_dist = np.zeros((1, num_states))init_state_dist[:, num_states-2] = 1

由于游戏始终以所有的瓷砖竖立开始,状态的分布是长度为513的行向量,所有条目都为零,除了第511个条目(以零为基的索引)放置了一个。因为511的二进制表示是字符串“111111111”,对应于所有瓷砖竖立的状态。

一旦定义了初始分布,可以使用公式πₜ = π₀Tᵗ来确定“关上盒子”的概率,其中t = 9,以找到状态中的收敛分布。同样,我们可以将t设置为9,因为π₉T = π₉,因此使用大于九的值会导致不必要的计算。实现此目标的代码如下:

# 计算并打印输和赢的概率t = 9multiple_transition_matrix = np.linalg.matrix_power(transition_matrix, t)final_dist = np.matmul(init_state_dist, multiple_transition_matrix)win_prob = final_dist[0, 0]lose_prob = final_dist[0, num_states-1]# 打印结果,保留4位小数print("赢的概率:{:.4f}".format(win_prob))print("输的概率:{:.4f}".format(lose_prob))

在此代码片段中,我们使用Numpy函数matrix_power和matmul(矩阵乘法)来分别计算T₉和π₉。使用这些结果,“关上盒子”的概率简单地存储为π₉的第一个元素,对应于没有竖立瓷砖的状态(二进制表示为’000000000’)。有了这个见解,我们最终知道,使用完全随机的策略,“关上盒子”的概率非常低(约为2%)!(下面报告了准确的概率值)。

上述代码和模型公式可以通过一些修改来支持支持任意数量的瓷砖和骰子的关上盒子变体。因此,我在下方可视化了赢的概率随骰子数量和瓷砖数量的变化:

结论

通过本文,我们探索了马尔可夫链及其在回答有关游戏“关上盒子”的问题中的具体应用。尽管你“关上盒子”的机会是100中的2,但我相信您使用概率建模来回答您最喜欢的游戏相关问题时,会取得更多成功。

除非另有说明,所有图片均为作者拍摄