数学知识很少被认为是游戏设计师所必需的。如果需要，学校水平就足够了。在大多数情况下都是如此。但有时，从数学中了解某些概念和方法可以让生活变得更轻松，并帮助你从不同的角度看待一些问题。
在本文中，我们将分析两个数学概念：马尔可夫链和随机游走。我会预先指出这篇文章更“通俗”而不是“科学”，因此，将省略一些关于如何推导公式的内容。
在理论之后，我们将讨论这些工具可能派上用场的示例案例，例如：
- 如果更多的箱子可以从箱子里出来，玩家将打开的箱子数量
- 抽一把剑需要花费的金币数量，如果剑能折断
- 赢得现金赛的概率
首先，让我们想象一个我们扮演炼金术士的游戏。我们的任务是收集新药水的原料：
这件事的独特之处在于：我们地点之间的道路可以将我们带到多个随机选择的目的地。
我们将道路表示如下：（位置 A → 位置 B：从位置 A 移动到位置 B 的概率）：
- 房子→棋场：0.8
- 房屋→巨魔的厕所：0.2
- 棋场→房子：0.5
- 国际象棋场 → 巨魔的厕所：0.3
- 棋场→太空河：0.2
- 巨魔的厕所→房屋：0.5
- 巨魔厕所→国际象棋场：0.2
- 巨魔厕所 → 太空河：0.3
- 太空河→棋场：0.5
- 太空河→太空河：0.5
请注意：每个位置的所有目的地概率之和等于 1。如果总和小于 1，则差值是从 A 转移到 A 的概率。如果大于，则肯定出了问题。
炼金术士去拿原料。问题是：两步之后，他到达太空河的概率是多少？
有两条通往河流的可能路径，包括两个步骤：
- 房子 → 棋场 → 太空河：0.8 ⋅ 0.2 = 0.16
- 房子 → 巨魔厕所 → 太空河：0.2 ⋅ 0.3 = 0.06
所以，炼金术士出现在河边的概率是 0.22。
好吧，如果我们想知道他在 10 步之后回到家的概率呢？100之后？这需要大量计算，而这正是马尔可夫链来拯救的地方！
马尔可夫链让我们介绍以下符号：
- S 是有限多个状态。在我们的例子中，这是多个位置：{House、Chess Field、Troll's Loo、Space River}。
- X ᵢ是第 i次转换后的状态，X ᵢ ∈ S。
- 移动是以给定概率将状态X ᵢ更改 为X ᵢ₊₁。
- 随机过程是一组状态 { X ₀ , X ₁ , X 2 , …, X ₙ₋₁ , X ₙ }，例如 {House, Chess Field, Space River, …, House}。
注意：下一个状态只取决于当前状态；就好像我们对过去的一切一无所知。这样的过程称为马尔可夫链。
如果仔细观察，您可能会猜到这实际上是一个有向图。它的峰值是位置，即来自 S 状态空间的元素。道路是图的边，其权重等于相应的概率。
让我们将其表示为表格：
表格显示为矩阵：
严格来说，我们有一个移动矩阵，其中：
- 线是现在，也就是Xᵢ的状态
- 列是未来，也就是Xᵢ₊₁的状态
- 元素 (i, j) 是从状态Xᵢ в Xⱼ转移的概率
矩阵本身是正方形的，并且由于它反映了所有可能的移动，因此行的总和为 1。
小提醒：
- aᵢⱼ为矩阵元素，其中i为行号，j为列号
- 您只能对一种大小的矩阵求和。在这种情况下，添加具有相同索引的元素
- 只有当第一个矩阵的列数等于第二个矩阵的行数时，矩阵的乘积才被定义。当矩阵 A 的第 i行乘以 B 的第 j列时，我们得到cᵢⱼ，它们一起形成一个新的矩阵 C
任何随机变量（例如Xᵢ）都有一个分布。在我们的例子中，我们可以将其表示为 N 维的行向量，其中 N 是 S 多个的基数。如果状态仅传递到自身，则称为吸收状态。
流浪的炼金术士让我们回到炼金术士和他的冒险。我要重申：我们想知道他在一定次数的移动后会在他家的概率。
我们总共有四个地点——因此，幂 S = 4。炼金术士也从家里开始旅程。在这里，我们获得随机变量X ₀的分布并将其表示为行向量X ₀′：
当X ₀′乘以T 时，我们得到X ₁′ - X ₁ 行分布向量：
此行向量显示炼金术士在一步之后出现在每个位置的概率。此外，当X ₁′ 乘以 T 时，我们得到X ₁′, X ₂ 行分布向量：
注意：
提示：
在= MMULT()的帮助下，可以在 Google 表格或 Excel 中将矩阵相乘。
因此，每步t的分布是初始分布和转移矩阵的t次方的乘积：
在这里，生成的行向量的第一个元素是t 次移动后回到家的概率——问题解决了！
有趣的事实：
在 n → ∞ 处的极限T ⁿ 将给出在无限步之后处于状态j的概率，其中j是第 j列。这也称为平衡（稳态）。状态的价值也可以解释为无论初始状态如何，都将花费在其中的时间。在这种情况下，时间以百分比衡量：
在实践中，我们通常对事件发生的概率比对其分布更感兴趣。至于过程，命中概率。例如，命中集合 S 的子集 A 的概率。
为了方便起见，让我们通过索引来表示位置：
- 房子
- 棋场
- 巨魔的厕所
- 太空河
假设 A = {4}，并且初始状态i = 1，在这种情况下，命中概率是他从 House 到达 Space River 的概率。
假设游戏中开始了为期一周的汹涌河流事件，从而使炼金术士无法旅行。现在空间河是吸收状态，因为如果炼金师去了那里，他就出不来了。
新的移动矩阵：
如果我们假设 A 是吸收态，则hᵢ是吸收概率。
让我们应用以下公式：
有关如何使用公式的提示：
1. 让我们从第一个到最后一个遍历每个状态i ，用状态索引将它们表示为h ：
1.1 如果i在集合A中，hᵢ等于1。«倒字母E»表示属于，划掉一个表示不属于。例如i =1（即一个House）不在A中，因为A= {4}。
1.2 如果i不在集合 A 中，我们将i等于移动概率i → j的总和乘以相应的hⱼ，这对我们来说仍然是未知的。
2. 我们得到一组耦合的h，即一个线性方程组，其中未知变量为hᵢ。从某种意义上说，这是一所学校x。
让我们使用替换方法或任何其他方法找到每个hᵢ 。在表中，这是使用更复杂的方法完成的。结果要尽可能小，但同时系统的每一个值都不能小于0。
让我们对 h14 进行计算：
为每个州完成此操作后，我们得到：
因此，无论炼金术士从什么状态开始，他都一定会在河边结束。相当期待！
迫在眉睫的台阶此外，人们可能经常对事件的预期值感兴趣，而不是对事件的概率感兴趣。对于随机过程，这是从初始状态到给定状态的过渡时间（预期命中时间）。时间是一种抽象，可以是一个步骤，一个动作，无论我们想要什么。命中时间通常也称为到达时间。若A为吸收态，则该时间也称为吸收时间。
让我们使用以下公式：
同样，结果应该尽可能小，但同时，系统的每个值都不应小于 0。
问题：炼金术士经过多少步后会被困在河里？
让我们为m1写一个计算：
对每个州都这样做后，我们得到：
因此，事实证明，在大约 8 步之后，炼金术士将被困在河中 — 37/5 接近 7，但让我们保持乐观（而且，正如实践所示，最好将数字四舍五入）。
我们在幕后隐藏的内容：
我没有展示所有公式的推导。尽管如此，在接下来的部分中，将对类似公式的推导进行论证——它们有助于独立推理。
随机游走想象炼金术士现在正在制作魔法药水，并考虑以下情况：
- 炼金术士的初始生命值为 1，最大生命值为 5
- 他可以制作恢复 1 生命值的再生药水
- 有时他做的药水不好；它会降低健康 -1
- 做出好的药水和坏的药水的概率是相等的
- 生命值为 0 时，炼金术士死亡，生命值为 5 时，回合结束
问题：比赛多久结束？也就是说，炼金术士会灭亡还是能够完全恢复健康？
在这里，随机游走为我们提供了帮助（这些通常可以被视为马尔可夫链的特例）。当然，并非每个马尔可夫链都是随机游走，反之亦然，因为为了说明这一点，随机游走可以有无限多个状态。
简单来说，随机游走是描述由一组随机步骤组成的路径的数学对象。重要的是要理解路径是某种抽象实体，实际上可能与真实路径没有任何关系。
在这里，用数学术语来说，描述了一个简单的有限对称随机游走，因为你只能移动到相邻的值——例如，你不能立即将健康值从 2 降低到 0。同时，它从下方和下方都受到限制从上面看，减少和增加的概率是相等的。
让我们考虑完全恢复健康的情况。为了尝试找到一种模式，让我们从简单的场景开始。在最基本的情况下，他连续喝下 4 杯正确制作的药水。在这里，我们得到概率：
如果一瓶药水需要 1 点生命值？为了方便起见，我们假设公式、图表和数字中的所有绿色都是不好的药水，比如一些有毒的颜色，而红色的是好的，比如一颗明亮的心。
必须用好药水抵消坏药水才能最大程度地恢复健康。只有 3 种这样的情况，具体取决于我们何时饮用劣质药水：
随着不良药水数量的增加，可能的选择数量也会增加。计算它们的一种选择是以图表的形式表示所有内容。
对于 8 种药水（其中 2 种不好），我们得到 8 种可能的路径：
有两个问题：
- 我们可以服用多少药水？5？12？
- 是否可以在不使用图表的情况下进行分析计算？
我们知道我们需要通过饮用n种药水来恢复 4 点生命值（如果我们从 1 点开始，最大值为 5） 。在这种情况下，我们得到：
- m = 4，作为需要恢复的健康
- p，好药水的数量
- (n - p)，坏药水的数量
因此，如果p是奇数，他将无法用这么多药水完全恢复健康。知道好药水的数量，我们就可以很容易地找到坏药水。例如，对于总数 8，我们得到：
任何恢复健康的尝试都是一组药水，例如{good, bad, good, …, bad}。在我们的例子中，这样的一组包含 8 个药水，其中 2 个是坏的。所以，为了得到我们的答案，计算没有重复的组合数就足够了。
让我提醒你一个公式：
整个画面中遗漏了很多内容，但我们似乎设法涵盖了这里的主要主题。感谢阅读，我希望这可以向设计人员展示一些解决某些问题的新工具，也许这篇文章可以为一些读者积极地锻炼和锻炼一些大脑。
哦，是的，所有这些都可以使用蒙特卡洛方法来计算——但首先，那会很无聊，其次，了解结果背后的原因是有用的，而不是认为它们是理所当然的。此外，还需要能够编写简单的脚本！
不要害怕数学，进化，制作好游戏！
