马尔可夫链与状态机概率

问题：概率可以"无限"（p.525–526）

原书开宗明义：第 22 章与第 25 章是全书数学最重的两章，对设计师并非必需，不喜欢矩阵可跳过。此前的概率题都能"数结果 ÷ 可能性空间"精确求解，但有一类问题计数会趋于无穷。例子是一个虚构法术"魔法橡皮筋"：造成 1 点伤害，然后掷 d10，1–2 结束，否则再加 1 点并继续掷。伤害为 1 的概率 20%，为 2 的概率 $0.8\times0.2=16\%$，为 3 的概率 12.8%……理论上可无限大。可以蒙特卡洛模拟或算前几百项近似，但也有精确方法。

矩阵与列向量（p.526–528）

矩阵就是方括号里的一张数表；列向量是只有一列的矩阵。矩阵乘列向量：结果的第 $i$ 个元素是矩阵第 $i$ 行与列向量逐项相乘再求和，例如

$\begin{bmatrix}4&5&2\\3&1&3\\0&-1&1\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}4x+5y+2z\\3x+y+3z\\-y+z\end{bmatrix}$

矩阵也可简写线性方程组（第 25 章解非传递机制时会用到）。矩阵运算的一般性质见 齐次坐标与矩阵约定。

状态机（p.528–529）

状态机由状态（圆圈）和带条件的转移（箭头）组成，有初始状态，可能有终止状态。实际使用的都是有限状态机 (FSM)，但理论上状态可以无限——魔法橡皮筋就是一个无限状态机：状态 $n$ 表示已造成 $n$ 点伤害，每个状态以 80% 进入 $n+1$、20% 结束。转移条件不一定是概率：原书的潜行游戏守卫在"巡逻→（听到声音）→搜索→（看到玩家）→攻击"之间切换，30 秒没发现/跟丢就退回上一级，没有终止状态。程序实现上的状态机见 状态模式与有限状态机。

把状态机转成转移矩阵（p.529–532）

若所有转移都是概率，状态机可写成矩阵：每一列是当前状态，每一行是下一个状态，元素是从该列转到该行的概率，因此每列之和为 1（任何时刻恰处于一个状态）。原书的三状态例子：状态 1 必定转到 2；状态 2 各以 1/2 转到 1 或 3；状态 3 以 1/3 转到任一状态（含自身）。下图是这个状态机，箭头上是转移概率。

stateDiagram-v2
    [*] --> S1
    S1 --> S2: "100%"
    S2 --> S1: "50%"
    S2 --> S3: "50%"
    S3 --> S1: "1/3"
    S3 --> S2: "1/3"
    S3 --> S3: "1/3"

对应的转移矩阵 $M$ 与初始列向量（从状态 1 出发）：

$M=\begin{bmatrix}0&\tfrac12&\tfrac13\\1&0&\tfrac13\\0&\tfrac12&\tfrac13\end{bmatrix},\quad v_0=\begin{bmatrix}1\\0\\0\end{bmatrix},\quad v_{n+1}=Mv_n$

$v_1=(0,1,0)$，$v_2=(\tfrac12,0,\tfrac12)$，$v_3=(\tfrac16,\tfrac46,\tfrac16)$……反复用"本轮分布 × 同一矩阵"得到下轮分布，就是马尔可夫链（以数学家马尔可夫命名）。约 13 次迭代后收敛到 $(0.3,0.4,0.3)$，再乘矩阵不再变化，称为稳态 (steady state)：长期看 30% 时间在状态 1 和 3、40% 在状态 2——很难凭直觉猜到。若这是潜行游戏守卫的状态、转移是每单位时间的估计概率，就能知道守卫在各状态停留的比例并据此调整。

（本 wiki 核对：稳态满足 $Mv=v$，代入 $(0.3,0.4,0.3)$ 第一行 $0.4/2+0.3/3=0.3$、第二行 $0.3+0.1=0.4$，成立。）

案例：蛇梯棋（Chutes & Ladders，p.533–537）

棋盘 1–100 格，掷 d6 前进，停在梯子底爬上、停在滑梯顶滑下，必须恰好落在 100 才赢，掷超了原地不动。传统棋盘 9 架梯子（1→38、4→14、9→31、21→42、28→84、36→44、51→67、71→91、80→100）和 10 条滑梯（16→6、47→26、49→11、56→53、62→19、64→60、87→24、93→73、95→75、98→78）。

• 状态数：100 格 + 棋盘外起点 − 10 个滑梯顶 − 9 个梯子底（停不住）= 82 个状态，转移矩阵 82×82 且非常稀疏（每列最多 6 个 1/6）。
• 读出指标：终止状态概率首次大于 0 的回合是最短对局（第 7 回合，极不可能）；首次超过 0.5 是中位数（32 回合）；把相邻两回合的累积概率相减得到"恰好在该回合结束"的概率，乘回合数求和是均值；该曲线的峰值是众数（22 回合）。均值明显大于中位数和众数，说明有少数极长的对局拉高了均值。
• 用途：改规则（取消"恰好落在 100"）、增删滑梯/梯子后重算即可比较。一般滑梯拉长、梯子缩短游戏，但不绝对——紧挨大梯子之前的滑梯反而可能缩短平均时长。也可以额外统计每条滑梯/梯子的使用频率（对《大富翁》这类玩家根据对手落点概率做决策的游戏更实用）。
• 多人：上述是单人数据。四人对局在第一个人到达 100 时结束，回合数会显著低于 32，但每回合四人行动，总耗时更长。把四人状态全部纳入矩阵需 $4\times82^4\approx1.8$ 亿个状态、矩阵约 $3.3\times10^{16}$ 个元素，超出普通电脑内存；可行的办法是把单人"在第 $n$ 回合结束"的分布当作加权骰子，掷四次取最小值并蒙特卡洛重复；若要排出名次则取相应的次序统计量。
• 棋盘设计（脚注 1）：几乎每格都在至少一条滑梯或梯子的射程内，最大的滑梯和梯子各自把玩家放在对方之前，便于大起大落在一两回合内被抹平；90–100 区间有三条滑梯（93、95、98），因"恰好到达"规则玩家会在 98 附近反复停留，是全盘最危险的区域。虽然对成人缺乏能动性，棋盘显然是为最大化戏剧性反转而设计的。
• 防死循环（脚注 2）：蒙特卡洛模拟要加保险（如 500 步未结束就记为 500），正式游戏里也一样：一个"极不可能但可能"的无限循环，调概率时一不小心就会变得常见。

原书问题（均值）：原书称平均约 35 回合。本 wiki 用上面列出的同一套棋盘与规则建 101 状态矩阵迭代 3000 回合，得到最短 7 回合、中位数 32 回合、众数 22 回合（与原书一致），但均值约 39.2 回合；约 35.8 回合是取消"恰好落在 100"规则后的均值（此时中位数 29、众数 20）。原书的均值数字可能出自不同的规则设定或截断，读者可用上述梯子/滑梯表自行复算。

案例：Yahtzee 全力追五同（p.537–543）

5d6，可保留任意骰子重掷两次。假设玩家只追求五同（Yahtzee），总是保留"最多相同"的那组、重掷其余，决策完全由局面决定。首掷各牌型的组合数（分母 $6^5=7776$）：

合计正好 7776——这是检查有无重复计数或遗漏的好办法。按"最多相同的骰子数"合并为 5 个状态（1 同/对/三同/四同/五同），转移矩阵为

$\begin{bmatrix}\tfrac{720}{7776}&0&0&0&0\\ \tfrac{5400}{7776}&\tfrac{120}{216}&0&0&0\\ \tfrac{1500}{7776}&\tfrac{80}{216}&\tfrac{25}{36}&0&0\\ \tfrac{150}{7776}&\tfrac{15}{216}&\tfrac{10}{36}&\tfrac56&0\\ \tfrac{6}{7776}&\tfrac{1}{216}&\tfrac1{36}&\tfrac16&1\end{bmatrix}$

对角线以上全为 0（不会退回更低状态）；对子重掷 3 颗：三颗都中 $1/216$，恰中两颗 $3\cdot\frac16\cdot\frac16\cdot\frac56=15/216$，进入三同有两条路——恰中一颗 $75/216$ 或三颗彼此相同但不同于原对子 $5/216$，共 $80/216$；留在原状态用 1 减其余得 $120/216$。三次掷骰后五同概率约 4.6%，四同约四分之一，三同近一半。多给一次重掷（共 4 次）概率翻倍超过 10%；共 10 次时首次超过 50%，即 5d6 凑五同的掷骰次数中位数为 10。（本 wiki 用同一矩阵复算：3 次 4.60%，4 次 10.06%，9 次 48.6%，10 次 55.6%，与原书一致。）

原书问题（脚注 3）：一局 13 个类别都追五同，"失败一次的概率是 1 − 0.460 = 0.954"应为 1 − 0.046 = 0.954（成功率是 4.6% 而非 46%）；其后 $0.954^{13}\approx0.542$、至少成功一次约 0.458 的结论正确。另外一对的计数段把第三个位置误写为"B"，应为"D"。

案例：《Risk》的递归（p.543–547）

规则前提：进攻获胜后至少要在出发地留 1 支军队、且参战军队都必须移动，所以每块领土里有 1 支军队不计入攻击力，下文的兵力都只算"第一支以外"的军队。进攻方每支额外军队掷 1 颗骰（最多 3 颗），防守方最多 2 颗，最大点与最大点、次大点与次大点比较，平局算防守方赢。可能性空间最多 $6^5=7776$，可以在电子表格里暴力枚举（脚注 4：小问题暴力法精确、易写、少 bug，不必嫌它不优雅）。单次掷骰结果：

任何情况下多掷骰都对自己有利，因此总是掷满。整场战斗的胜率用递归：把当前局面按每种结果化归为更小的局面，直到已知情形（1 对 1 胜率 15/36）。例如 2 攻 1：$\frac{125}{216}+\frac{91}{216}\cdot\frac{15}{36}\approx0.754$；2 对 2：$\frac{295}{1296}+\frac{420}{1296}\cdot\frac{15}{36}\approx0.36$；7 对 5 = $\frac{2890}{7776}W(7,3)+\frac{2611}{7776}W(6,4)+\frac{2275}{7776}W(5,5)$。在表格里写好前几行列后向下、向右填充即可。

部分结果（进攻方胜率）：1v1 0.417、2v2 0.363、3v3 0.470、4v4 0.477、5v5 0.506、4v2 0.785、4v3 0.642、6v4 0.745、6v5 0.638、10v10 0.568。结论：

• 兵力相等时，4 对 4 以下防守方占优（赢平局），5 对 5 以上进攻方占优（3 对 2 掷骰的微弱优势累积）；兵力更多时进攻方甚至在略少时占优，如 17 攻 19。（本 wiki 递归复算：17v19 胜率约 0.504，10×10 表与原书逐项一致。）
• 增援决策：一支援军放在"4 攻 2"变成"4 攻 3"使进攻胜率降约 14%，放在"6 攻 4"变"6 攻 5"只降约 11%，前者更划算。这类计算正是数字版 AI 应做的。
• 设计含义：小规模战斗利于防守，开局各方倾向于占据边界少的大洲（南美、澳洲）固守吃奖励；后期大量援军使概率偏向进攻，形成把游戏推向结束的正反馈（见 反馈回路）。

练习中的要点（p.547–555）

• 讨论题 1–3：自建一个五状态 FSM（标出初始/终止状态与转移概率），转成转移矩阵，再用马尔可夫链看是否到达稳态、何时到达终止状态的概率超过 50%。
• 讨论题 4–6：押 1 美元抛硬币，正面输掉、反面赌注翻三倍并可选择离开或继续，只能玩一次——建成无限状态机并用马尔可夫链追踪期望收益；每次继续的期望值都为正，但一直继续必然输光，留作悖论讨论。
• 讨论题 7–10：找一个自己玩过、可用本章方法分析的系统，提出具体问题（如完成任务的平均回合数、某行动的平均收益），建状态机与转移矩阵并求解。（提取文本缺第 7 题，本 wiki 渲染 PDF 第 589 页核对补全。）
• 支线引言：马尔可夫链是"正向"推进重复转移，递归是"反向"把复杂事件化归为简单事件；不只用于纯运气游戏，在可能性空间已知、未来局面未知的策略游戏里也可用来构造最优 AI。
• 支线 22.1《雷暴 (Thunderstorm)》（德国儿童骰子游戏）：状态 = 罚分 0–5 × 骰子数 1–6 再加终止状态；只剩一颗骰子时（原书称）平均失败约四次才有人掷出 1 让全部骰子回到场上，简单规则却有张弛起伏的节奏（节奏见第 12 章）。练习：单人版以"被淘汰前掷骰总次数"为分数求均值/中位数/众数；替代挑战只以骰子数为状态求稳态和每回合吃罚分的概率，并用 $N$ 人局总罚分介于 $6(N-1)$ 与 $6(N-1)+5$ 之间估计局长；终极挑战比较两人及多人局各座次的先后手优劣。
• 支线 22.2《Hi Ho! Cherry-O》：d7 转盘（+1~+4、−1、−2、清零），11 个状态；终极挑战是改权重或改效果使单人中位数为 10 回合，并比较哪种方法更容易。
• 支线 22.3：魔法橡皮筋的代数解 $D=1+0.8D\Rightarrow D=5$（本 wiki 求解：几何分布期望 $1/0.2=5$）。
• 支线 22.4：把第 17 章 Kill the Elf（战士每回合必中 1 伤，法师 1/6 概率打 6 伤）改用状态机（状态 = 法师命中次数）精确求解，找出 1–1000 之间使双方胜率最接近 1:1 的目标伤害。
• 支线 22.5：50d6 赛马（首掷一方 6、一方 1）的精确解，状态为两人点差，首掷后在状态 5，每回合变化 −5~+5；50 回合版有 −240 到 250 共 491 个状态，十回合简化版有 −40 到 50 共 91 个状态，画出"首掷 6 者"胜率随回合的变化。
• 支线 22.6：6 张牌（3 黑 3 红）中出现连续两张黑牌的概率，状态 =（剩余黑, 剩余红, 当前连黑数），用递归累加到达终止状态的概率（本 wiki 递归求得答案为 4/5）；终极挑战是 8 副牌鞋里出现连续 10 张"十点牌"的概率，需编程递归求解。

原书问题（支线 22.6）：

1. 状态 $(a,b,c)$ 中 $a,b\in\{0..3\}$、$c\in\{0..2\}$，最多 $4\times4\times3=48$ 个状态，原书写成 "= 192"；其后的编号 $12a+3b+c$ 最大为 47，也与 48 一致。
2. 8 副牌共 416 张，32 张 A + 256 张 2–9 = 288 张"非十点牌"（原书自己在括号里也写了 288 个 0），所以初始状态应为 (128, 288, 0) 而不是原书的 (128, 256, 0)。状态数约 $129\times289\times10\approx37$ 万，与原书"约 40 万"量级一致。

原书问题（支线 22.1）："只剩一颗骰子时平均约失败四次"与几何分布不符。每次成功率 $p=1/6$，首次成功前失败次数的均值为 $(1-p)/p=5$；中位数为 3（$1-(5/6)^4\approx0.518$）。"约四次"既不是均值也不是中位数，作为粗略说法可以，但若当作平均值应为 5 次（本 wiki 计算）。

取舍与适用场景

• 马尔可夫链适合无记忆（下一步只取决于当前状态）的随机过程：棋盘移动、守卫 AI 状态、重掷类机制、伤害链。需要记忆的东西必须编进状态（如支线 22.6 的"当前连黑数"），状态数会随之膨胀。
• 多人组合状态呈指数爆炸（蛇梯棋四人约 1.8 亿状态），此时改用单人分布 + 蒙特卡洛。
• 正向迭代（马尔可夫链）回答"$n$ 步后在哪"；反向递归回答"从这里出发最终赢的概率"。小空间直接暴力枚举最可靠。
• 无限过程在实现中要设上限，防止意外的死循环。