潍坊网站建设 潍坊做网站,wordpress加载图片的速度,河北省建设机械协会网站,常州做网站的公司组合博弈入门
组合游戏
要求
有两个玩家#xff1b;游戏的操作状态是一个有限的集合#xff08;比如#xff1a;限定大小的棋盘#xff09;#xff1b;游戏双方轮流操作#xff1b;双方的每次操作必须符合游戏规定#xff1b;当一方不能将游戏继续进行的时候#xf…组合博弈入门
组合游戏
要求
有两个玩家游戏的操作状态是一个有限的集合比如限定大小的棋盘游戏双方轮流操作双方的每次操作必须符合游戏规定当一方不能将游戏继续进行的时候游戏结束同时对方为获胜方无论如何操作游戏总能在有限次操作后结束。
必败点和必胜点P点N点
必败点P点上一个选手Previous player将取胜的位置成为必败点。
必胜点N点下一个选手Next player将取胜的位置成为必胜点。
必败必胜点属性 所有终结点是必败点P点 从任何必胜点N点操作 至少有一种方法可以进入必败点P点 无论如何操作从必败点P点都只能进入必败点P点。
取子游戏的算法实现
步骤1将所有终结位置标记为必败点P点
步骤2将所有一步操作能进入必败点P点的位置标记为必胜点N点
步骤3如果从某个点开始的所有一步操作都只能进入必胜点N点则将该点标记为必败点P点
步骤4如果在步骤3未能找到新的必败P点则算法终止否则返回到步骤2。
NIM游戏
NIM游戏是组合博弈中的经典游戏。游戏场景如下有若干堆石子每堆石子的数量都是有限的游戏双方轮流从某一堆中取走任意数量的石子至少取1个取走最后一个石子的玩家获胜。
NIM游戏的二进制证明
设游戏中有 n n n 堆石子各堆石子数分别为 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an。将这些石子数都表示成二进制形式。
定义NIM - 和为 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n a_1\oplus a_2\oplus\cdots\oplus a_n a1⊕a2⊕⋯⊕an ⊕ \oplus ⊕ 表示按位异或运算。 定理NIM游戏中当且仅当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n 0 a_1\oplus a_2\oplus\cdots\oplus a_n 0 a1⊕a2⊕⋯⊕an0 时当前局面为必败局面当 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1\oplus a_2\oplus\cdots\oplus a_n\neq0 a1⊕a2⊕⋯⊕an0 时当前局面为必胜局面。 证明 终结局面当所有堆石子数都为 0 0 0 时 0 ⊕ 0 ⊕ ⋯ ⊕ 0 0 0\oplus0\oplus\cdots\oplus0 0 0⊕0⊕⋯⊕00此时是必败局面。 必胜局面可转化为必败局面若 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n k ≠ 0 a_1\oplus a_2\oplus\cdots\oplus a_n k\neq0 a1⊕a2⊕⋯⊕ank0则 k k k 的二进制表示中至少有一位为 1 1 1。在 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 中一定存在一个 a i a_i ai其对应的二进制位上也为 1 1 1。通过从第 i i i 堆中取走一定数量的石子使得取走后这堆石子数变为 a i ′ a_i ai′满足 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i − 1 ⊕ a i ′ ⊕ a i 1 ⊕ ⋯ ⊕ a n 0 a_1\oplus a_2\oplus\cdots\oplus a_{i - 1}\oplus a_i\oplus a_{i1}\oplus\cdots\oplus a_n0 a1⊕a2⊕⋯⊕ai−1⊕ai′⊕ai1⊕⋯⊕an0。 必败局面只能转化为必胜局面若 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n 0 a_1\oplus a_2\oplus\cdots\oplus a_n 0 a1⊕a2⊕⋯⊕an0假设从第 i i i 堆取走石子后变为 a i ′ a_i ai′那么 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i − 1 ⊕ a i ′ ⊕ a i 1 ⊕ ⋯ ⊕ a n ≠ 0 a_1\oplus a_2\oplus\cdots\oplus a_{i - 1}\oplus a_i\oplus a_{i1}\oplus\cdots\oplus a_n\neq0 a1⊕a2⊕⋯⊕ai−1⊕ai′⊕ai1⊕⋯⊕an0。因为异或运算的性质决定了改变其中一个数后异或和必然改变。
SG函数
对于一个组合游戏的每个状态 x x x定义其SG函数值 S G ( x ) SG(x) SG(x)。 计算方法 首先对于所有的终结状态 x x x S G ( x ) 0 SG(x)0 SG(x)0。 对于非终结状态 x x x设 x x x 能通过一步操作到达的所有状态为 y 1 , y 2 , ⋯ , y k y_1,y_2,\cdots,y_k y1,y2,⋯,yk则 S G ( x ) m e x ( { S G ( y 1 ) , S G ( y 2 ) , ⋯ , S G ( y k ) } ) SG(x)mex(\{SG(y_1),SG(y_2),\cdots,SG(y_k)\}) SG(x)mex({SG(y1),SG(y2),⋯,SG(yk)})其中 m e x mex mex 函数是求一个集合中未出现的最小非负整数。例如若集合为 { 0 , 1 , 3 } \{0,1,3\} {0,1,3}则 m e x ( { 0 , 1 , 3 } ) 2 mex(\{0,1,3\}) 2 mex({0,1,3})2。 作用
当一个组合游戏可以拆分为多个子游戏时整个游戏的胜负情况可以通过各个子游戏的SG函数值的异或和来判断。设整个游戏由 n n n 个子游戏组成每个子游戏的当前状态对应的SG函数值分别为 S G 1 , S G 2 , ⋯ , S G n SG_1,SG_2,\cdots,SG_n SG1,SG2,⋯,SGn则当 S G 1 ⊕ S G 2 ⊕ ⋯ ⊕ S G n 0 SG_1\oplus SG_2\oplus\cdots\oplus SG_n 0 SG1⊕SG2⊕⋯⊕SGn0 时当前游戏局面为必败局面当 S G 1 ⊕ S G 2 ⊕ ⋯ ⊕ S G n ≠ 0 SG_1\oplus SG_2\oplus\cdots\oplus SG_n\neq0 SG1⊕SG2⊕⋯⊕SGn0 时当前游戏局面为必胜局面。这使得我们可以将复杂的组合游戏分解为简单子游戏来分析胜负情况。
组合游戏的并
定义组合游戏的并是指将多个组合游戏同时进行的一种游戏形式。假设有 k k k 个组合游戏 G 1 , G 2 , ⋯ , G k G_1, G_2, \cdots, G_k G1,G2,⋯,Gk组合游戏的并 G G 1 G 2 ⋯ G k G G_1 G_2 \cdots G_k GG1G2⋯Gk。在游戏 G G G 中玩家的一步操作是在 G 1 , G 2 , ⋯ , G k G_1, G_2, \cdots, G_k G1,G2,⋯,Gk 中的某一个游戏中进行一步合法操作。
SG 定理对于组合游戏的并 G G 1 G 2 ⋯ G k G G_1 G_2 \cdots G_k GG1G2⋯Gk其某状态的 S G SG SG 值等于各个子游戏在相应状态下 S G SG SG 值的异或和即 S G ( G ) S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G k ) SG(G)SG(G_1)\oplus SG(G_2)\oplus\cdots\oplus SG(G_k) SG(G)SG(G1)⊕SG(G2)⊕⋯⊕SG(Gk)。这个定理非常重要它使得我们可以通过分别计算各个子游戏的 S G SG SG 值再求异或和来判断组合游戏并的胜负情况。
以下是一个简单示例代码展示如何利用 SG 定理计算组合游戏的并的胜负情况假设已有 sg 函数用于计算单个游戏状态的 S G SG SG 值
#includebits/stdc.husing namespace std;// 假设已经有了计算单个游戏 SG 值的函数 sgint sg(int state) {// 具体实现省略根据实际游戏规则编写return 0; }计算组合游戏的并的 SG 值int combinedSG(int numGames, int* states) {int result 0;for (int i 0; i numGames; i) {result ^ sg(states[i]);}return result;}// 判断胜负示例函数void determineWinner(int numGames, int* states) {int combinedSgValue combinedSG(numGames, states);if (combinedSgValue 0) {cout 当前局面为必败局面 endl;}else {cout 当前局面为必胜局面 endl;}}int main() {int numGames 3; // 假设有 3 个子游戏int states[3] {1, 2, 3}; // 各个子游戏的状态determineWinner(numGames, states);return 0;}
