马尔可夫【MDP】

Alice 和 Bob 正在玩一个 k 轮的石头剪刀布游戏。游戏开始时两位玩家各有恰好 3 张牌每张牌是石 头R、剪刀S或布P。每一轮游戏按照如下方式进行 1. 双方均可看见彼此手中的全部 6 张手牌。 2. Alice 先从她的手牌中选择一张牌打出。 3. Bob 在看到 Alice 打出的牌后选择自己的一张牌打出。 4. 根据标准规则判定胜负石头胜剪刀剪刀胜布布胜石头。相同则为平局。若 Alice 获胜她得 3 分若平局她得 1 分若 Bob 获胜她得 0 分。 5. 双方都将打出的牌丢弃并各自独立地以等概率获得一张新的石头、剪刀或布。 Alice 希望最大化自己的期望总得分Bob 希望最小化 Alice 的期望总得分。 给定游戏轮数 k、Alice 的初始手牌和 Bob 的初始手牌你需要求出双方都采取最优策略时Alice 的最 大期望总得分。 Input 输入的第一行包含一个整数 T (1 ≤ T ≤ 10 5 )表示测试数据组数。对于每组测试数据 第一行包含一个整数 k (1 ≤ k ≤ 10 9 )表示游戏轮数。 第二行包含一个长度为 3 的字符串由字符 R, S, P 组成表示 Alice 的初始手牌。 第三行包含一个长度为 3 的字符串由字符 R, S, P 组成表示 Bob 的初始手牌。 Output 对于每组测试数据输出一行包含一个实数表示 Alice 的最大期望总得分。 如果你的答案的绝对误差或相对误差不超过 10 −6则将被视为正确。形式化地设你的输出为 a标准 答案为 b当且仅当 |a−b| max(1,|b|) ≤ 10 −6 时你的输出会被接受。一、核心思路1. 状态表示去重石头剪刀布中手牌的顺序不影响结果。例如RSP、PSR、SPR是一样的。为了去重我们将手牌排序。Alice 的手牌排序后是一个非降序三元组例如{0, 0, 2}(R, R, P)。这样的组合只有 10 种数学上叫可重复组合(3C33−1​)10。我们将这 10 种组合编号为 0~9。全局状态Alice的状态 10 * Bob的状态。范围 0~99。2. 动态规划定义dp[i][zt]表示还剩下i轮游戏当前状态为zt时Alice 能获得的期望总得分。3. 博弈过程模拟DP转移对于状态zt还剩i轮Alice 出牌她手上有 3 张牌她尝试出第a张位置 0, 1, 2。Bob 出牌他知道 Alice 出了什么。他遍历自己手上的 3 张牌选择一张让 Alice得分最少的牌。弃牌与补牌双方各弃一张然后各自独立随机摸一张R/S/P。这里有 3×39种可能性。状态转移摸牌后手牌变化重新排序进入新状态zt剩余i-1轮。得分计算本轮得分 下一轮期望得分。由于 Bob 是后手且想最小化 Alice 得分内层取minAlice 想最大化得分外层取max。4. 处理巨大的 k线性外推k最大到 10e9不可能算这么多轮。观察发现当 i很大时每多一轮游戏期望得分的增加量趋于稳定就像物理中的匀速运动。我们计算前 1000 轮。计算平均每轮增加的分值 d通过计算第 1000 轮与第 999 轮的差值平均得到。对于 k1000使用公式dp[1000][zt](k−1000)×d。二、带详细注释的代码#include bits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define ld long double // 使用长双精度防止精度丢失 #define endl \n // 计时器用于调试性能 chrono::_V2::system_clock::time_point bg_clock,en_clock; const int N 1e3 10; // DP数组第一维大小预计算1000轮 ld dp[N][100]; // dp[i][zt]: 剩余i轮状态为zt时的期望得分 // 存储所有10种手牌组合排序后的 std::vectorarrayll, 3 card; // 映射手牌组合 - 索引 (0~9) maparrayll, 3, ll mp; ld d 0; // 稳态下平均每轮的得分增量 /** * brief 判断对局得分 * param a Alice出的牌 (0:R, 1:S, 2:P) * param b Bob出的牌 * return Alice的得分 (0, 1, or 3) */ ll check(int a, int b) { if (a b) { return 1; // 平局 } // (01)%31 (R beats S) // (11)%32 (S beats P) // (21)%30 (P beats R) if ((a 1) % 3 b) { return 3; // Alice赢 } return 0; // Alice输 } /** * brief 初始化函数生成状态空间并计算DP表 */ void init() { ll cnt 0; // 1. 生成所有非降序三元组共10种 // 例如 {0,0,0}, {0,0,1}, {0,1,1}...{2,2,2} for (int i 0; i 3; i) { for (int j i; j 3; j) { for (int k j; k 3; k) { card.push_back({i, j, k}); mp[{i, j, k}] cnt; cnt; } } } // 2. 动态规划计算 // i 代表剩余的轮数 for (int i 1; i N; i) { // 遍历所有100个状态 (Alice 10种 * Bob 10种) for (int zt 0; zt 100; zt) { ld resa -1e18; // Alice能获得的最大期望得分 // Alice尝试打出她手上的第a张牌 (0, 1, or 2) for (int a 0; a 3; a) { ld resb 1e18; // Bob操作后的结果他要最小化这个值 // Bob尝试打出他手上的第b张牌 for (int b 0; b 3; b) { ld sum 0; // 枚举双方随机补充的牌 (na: new Alice, nb: new Bob) for (int na 0; na 3; na) { for (int nb 0; nb 3; nb) { // 解析当前状态 zt // zt % 10 是 Alice 的状态索引, zt / 10 是 Bob 的状态索引 ll za zt % 10; ll zb zt / 10; // 获取当前手牌注意这里是拷贝因为要修改 auto cuna card[za]; // Alice current hand auto cunb card[zb]; // Bob current hand // Alice打出第a张牌并用新牌na填充该位置 cuna[a] na; // Bob打出第b张牌并用新牌nb填充该位置 cunb[b] nb; // 手牌重新排序因为顺序不影响后续状态 sort(cuna.begin(), cuna.end()); sort(cunb.begin(), cunb.end()); // 累加下一轮的期望得分 本轮即时得分 // dp[i-1][...]: 剩下 i-1 轮的期望 // check(...): 本轮得分 sum dp[i - 1][mp[cuna] 10 * mp[cunb]] check(card[za][a], card[zb][b]); } } // Bob选择让他付出代价最小的出牌即最小化sum resb min(resb, sum); } // Alice选择让她获益最大的出牌 // 注意resb 是9种情况的总和除以9才是期望值 resa max(resa, resb / 9.0); } dp[i][zt] resa; } } // 3. 计算稳态平均每轮收益 d // 假设当轮数很大时dp[i] - dp[i-1] 趋近于常数 d for (int i 0; i 100; i) { // 取第1000轮和第999轮的差值作为增量估计 d (dp[1000][i] - dp[999][i]); } d / 100; // 对所有100个状态取平均得到稳定的d } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); bg_clock chrono::high_resolution_clock::now(); cout fixed setprecision(15); // 设置高精度输出 int T 1; cin T; init(); // 一次性预处理所有数据 while (T--) { ll k; cin k; arrayll, 3 ca, cb; // current Alice/Bob hand string sa, sb; cin sa sb; // 将输入的字符转换为数字 (0:R, 1:S, 2:P) for (int i 0; i 3; i) { if (sa[i] R) ca[i] 0; if (sa[i] S) ca[i] 1; if (sa[i] P) ca[i] 2; if (sb[i] R) cb[i] 0; if (sb[i] S) cb[i] 1; if (sb[i] P) cb[i] 2; } // 排序匹配状态定义 sort(ca.begin(), ca.end()); sort(cb.begin(), cb.end()); // 计算当前状态编码 ll zt mp[ca] 10 * mp[cb]; if (k N) { // 如果k小于预计算的轮数直接查表 cout dp[k][zt] endl; } else { // 否则利用线性外推公式计算 // dp[1000][zt]: 前1000轮的得分 // (k-1000)*d: 剩余轮数按平均速度获得的得分 cout dp[1000][zt] (k - 1000) * d endl; } } en_clock chrono::high_resolution_clock::now(); auto duration_clock chrono::duration_castchrono::microseconds(en_clock - bg_clock); ld duration_count duration_clock.count() * 0.001; // cerr Time: duration_count ms endl; // 输出运行时间调试用 return 0; }三、这段代码为什么能过精度控制使用了long double和setprecision(15)远超题目要求的1e-6。状态压缩100个状态使得DP可行。外推合理性由于每轮结束后的随机补牌状态转移是无记忆的马尔可夫性。当轮数趋于无穷平均收益确实会收敛到一个固定值。用第1000轮的数据外推误差极小。博弈逻辑正确严格遵循了“Alice最大化Bob最小化”的零和博弈规则。原理讲解一、马尔可夫性一句话定义给定一个过程如果下一时刻的状态只取决于当前状态跟更早的历史无关这个过程就满足马尔可夫性。形式化写P(St1​∣St​,St−1​,…,S0​)P(St1​∣St​)回到这题当前状态 (Alice手牌, Bob手牌)下一轮手牌只由当前手牌 这轮谁出啥 随机补牌决定前 5 轮是怎么打到这个状态的完全不影响下一轮所以这是个马尔可夫过程。状态只有 100 个就叫有限状态马尔可夫链。二、马尔可夫链的几个性格一条链长什么样主要看三个属性不可约Irreducible从任意一个状态出发迟早能走到任意另一个状态。这题双方每轮都要弃牌随机补牌哪怕现在 Alice 全是 R、Bob 全是 P几轮之内总能变到任何其他组合因为补牌是独立的总有概率摸到想要的。则这条链是不可约的。非周期Aperiodic不存在一个强制的每隔几轮才回来的规律。这题有可能下一轮就回到同一个手牌组合运气好补回来一样的也可能隔几轮才回来。周期可以是 1。这条链是非周期的。遍历Ergodic 不可约 非周期 有限状态三条都占 →你这条链是遍历的。遍历——保证下面所有稳定的结论都成立。三、平稳分布 π最关键的结论遍历链有一个超级重要的定理存在唯一的分布 π(π0​,π1​,…,π99​)满足πPπ并且不管从哪个状态出发玩很多轮之后状态分布都会收敛到 π跟起点无关。π叫平稳分布平稳的意思是如果一开始按 π发手牌那之后每一轮的手牌分布都永远是 π。四、平均报酬定理代码外推题每轮有个即时奖励​ ri​在状态 i下 Alice 这轮的期望得分Bob 已经最优应对了。遍历链 常驻奖励有个定理叫平均报酬定理k→∞lim​kVk​(目i)​ρ:j0∑99​πj​rj​ρ就是长期平均每轮得分是个常数跟起点 i无关。更精细一点值函数可以拆成Vk​(i)kρhi​o(1)其中 hi​叫偏差bias只跟起点有关是常数。o(1)那项是残余随 k指数衰减。五、把代码里的变量对号入座数学符号你代码里的东西含义S100dp[][100]第二维状态数Pji​9 种补牌等概率转移概率ri​check(...) 下一轮dp里的即时部分单轮奖励π--平稳分布ρd平均每轮得分hi​dp[1000][i] - 1000*d的隐式估计偏差d (dp[1000][i] - dp[999][i]); // 对所有i平均 d / 100;数学上dp[1000][i]−dp[999][i]ρ(hi​−hi​)残留≈ρ再对所有 i平均一把残留更小 →用数值差分估 ρ。然后外推dp[1000][zt] (k-1000)*d // 1000*ρ h_zt 残 (k-1000)*ρ // k*ρ h_zt 残正好是 Vk​(zt)的近似。六、这套知识在竞赛里还用在哪马尔可夫链 平稳分布这套在算法竞赛里是一类题的通解题型例子随机游走求长期比例蚂蚁在图上爬问某条边被走的概率期望 DP 巨大轮数这题就是吸收态问题gamblers ruin、毒药糖果随机过程博弈Bob 后手通用套路建模状态证明/确认是马尔可夫链判遍历性​ → 有平稳分布 π小 k 直接 DP大 k要么像本题这样数值外推好写够用要么解 πPπ 得到精确 ρ再配偏差 h更稳适合 k 到 1e18 的题七、这题如果用正统 MDP 解法现在的代码 数值迭代 线性外推是工程师解法。正统 MDP / 马尔可夫报酬链解法会多两步策略迭代或值迭代得到最优策略下固定的转移 P∗和奖励 r∗解πP∗π→ 平稳分布ρπr∗(I−P∗1π)hr∗−ρ1→ 偏差答案 kρhi​−(P∗kh)i​大 k 时最后一项丢掉好处ρ 和 h 都是解析精确值不用赌1000 轮够不够稳。