博弈论总结（20260201）
<h1 id="博弈论">博弈论</h1><h2 id="icg-游戏">ICG 游戏</h2>
<p>若满足以下条件：</p>
<ol>
<li>
<p>游戏由两个人参与，两人轮流做出决策且必定对自己最有利；</p>
</li>
<li>
<p>当有一人无法做出决策时游戏结束，无法做出决策的人输，且无论两人如何决策，游戏都一定会结束（不会出现平局）</p>
</li>
<li>
<p>游戏中的同一个状态不可多次抵达，任意游戏者在某一确定状态下做出的决策只与当前状态有关，而与游戏者无关</p>
</li>
</ol>
<h2 id="dag-中的博弈">DAG 中的博弈</h2>
<p>根节点有一个棋子，两个游戏者轮流移动这颗棋子；</p>
<ul>
<li>
<p>若当前点没有后继点，则当前点为必败点；</p>
</li>
<li>
<p>若当前点的后继点存在必败点，则当前点为必胜点，否则为必败点；</p>
</li>
</ul>
<h2 id="sg-函数sprague-grundy">SG 函数（Sprague-Grundy）</h2>
<p>定义 $ mex(S) $ 为 最小的不属于集合 $ S $ 的非负整数</p>
<p>定义SG函数： $ SG(u) = mex ({ SG(v) }) $</p>
<p>性质：</p>
<ul>
<li>若SG函数值为0，则当前点必败，否则必胜；</li>
</ul>
<p>满足DAG上博弈的性质；</p>
<h2 id="sg-定理">SG 定理</h2>
<p><strong>游戏的和的SG函数值</strong> 等于 <strong>游戏的SG函数值的异或和</strong></p>
<h2 id="nim游戏各类变形">Nim游戏各类变形</h2>
<h3 id="nim">Nim</h3>
<blockquote>
<p>$ n $ 堆物品，每堆 $ a_i $ 个，两个玩家轮流取走任意一堆的任意个物品，不能不取，取到最后一个物品的人获胜</p>
</blockquote>
<p>若 $ (\bigoplus_{i=1}^{n} a_i) = 0 $ ，则先手必败，否则先手必胜</p>
<h3 id="k-nim">k-Nim</h3>
<blockquote>
<p>$ n $ 堆物品，每堆 $ a_i $ 个，两个玩家轮流取走最多 $ k $ 堆中的任意个物品，不能不取，取到最后一个物品的人获胜</p>
</blockquote>
<p>令 $ x $ 在二进制下第 $ i $ 位的值为 $ s(x)_i $</p>
<p>若 $ \forall i , (\sum_{j=1}^{n} s(a_j)_i ) \mod ( k + 1 ) = 0 $ ，则先手必败，否则先手必胜</p>
<h3 id="阶梯-nim">阶梯 Nim</h3>
<blockquote>
<p>$ n $ 堆物品，每堆 $ a_i $ 个，两个玩家轮流将任意一堆 $ k $ 中的任意个物品放入 $ k - 1 $ 中 ，不能不操作，无法操作的人输</p>
</blockquote>
<p>若 $ (\bigoplus_{i=1且i为奇数 }^{n} a_i) = 0 $ ，则先手必败</p>
<h3 id="anti-nim">Anti-Nim</h3>
<blockquote>
<p>$ n $ 堆物品，每堆 $ a_i $ 个，两个玩家轮流取走任意一堆的任意个物品，不能不取，取到最后一个物品的人失败</p>
</blockquote>
<ul>
<li>
<p>若 $ \forall i \in , a_i=1 且 (\bigoplus_{i=1}^{n} a_i) = 0 $ , 则先手必胜</p>
</li>
<li>
<p>若 $ \exists i \in , a_i > 1 且 (\bigoplus_{i=1}^{n} a_i) \neq 0 $ , 则先手必胜</p>
</li>
<li>
<p>否则先手必败</p>
</li>
</ul>
<h2 id="博弈论题目常用做题技巧">博弈论题目常用做题技巧</h2>
<ul>
<li>规约为经典模型（如 Nim 游戏），或经典模型变形</li>
<li>分类讨论</li>
<li>SG函数（胜败态）DP</li>
<li>寻找必胜策略然后从简单情况开始手玩</li>
<li>博弈思想：若当前状态对自己有利，必定会尽量维持当前局面，否则尽力改变</li>
</ul><br><br>
来源：https://www.cnblogs.com/ZFR-Blog/p/19560996
頁:
[1]