龙岩网站建设行情,杭州做外贸网站,移动端网站建设重点有哪些,网站建设相关基础实验总结前言 在上一节中#xff0c;我们初步了解了一下SG函数与SG定理。 今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理 首先从最基本的Anti-Nim游戏开始 Anti-Nim游戏是这样的 有两个顶尖聪明的人在玩游戏#xff0c;游戏规则是这样的#xff1a; 有\(n\)堆…前言 在上一节中我们初步了解了一下SG函数与SG定理。 今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理 首先从最基本的Anti-Nim游戏开始 Anti-Nim游戏是这样的 有两个顶尖聪明的人在玩游戏游戏规则是这样的 有\(n\)堆石子两个人可以从任意一堆石子中拿任意多个石子(不能不拿)拿走最后一个石子的人失败。问谁会胜利 博弈分析 Anti-Nim游戏与Nim游戏唯一的不同就是两人的胜利条件发生了改变不过这并不影响我们对结论的推导 对于这个游戏先手必胜有两种情况 当每堆石子都只有一个且游戏的SG值为\(0\)至少一堆石子多于一个且游戏的SG值不为\(0\)粗略的证明一下 游戏大概可以被分为\(3\)种情况 每堆只有一个石子当异或值为\(0\)时先手必胜当异或值不为\(0\)时先手必败只有一堆石子数大于1先手必胜经过分析不难发现先手可以对数量大于1的那堆石子下手脚从而构造出后手必败的状态 存在至少两堆石子数大于1当异或和为0时先手必败当异或和不为0时先手必败这一步的结论与Nim游戏非常相似同时它们的证明也非常相似大概就是从异或和为\(0\)的状态无论怎样都会变为异或和不为\(0\)的状态反过来从异或和不为\(0\)的状态总有一步能到达异或和为\(0\)的状态 推广 按照我们学习SG函数的思路我们是否可以把Anti-Nim游戏推广开来呢 答案是肯定的 定义Anti-SG游戏 Anti-SG游戏规定决策集合为空的游戏者赢其余规则与SG游戏相同 同时我们定义SJ定理 对于Anti-SG游戏如果我们规定当局面中所有单一游戏的SG值为0时游戏结束则先手必胜当且仅当 游戏的SG函数不为0且游戏中某个单一游戏的SG函数值大于1 游戏的SG函数为0且没有某个单一游戏的SG函数大于1 证明与SG函数类似 不追求完美的可以从DAG上归纳 追求完美的可以用模仿棋证明出该游戏的等价性然后推出该游戏是可数集合然后通过计算推出在模\(2\)意义下线性空间的基可以为\(nim(0),nim(1)\)最后归纳证明一个后继是若干Anti-nim游戏的游戏等价于\(mex(S)\) 例题 按照whx老师的说法 Anti-SG不怎么重要我至今为止就做到过一道题 那道题在这儿 题解 转载于:https://www.cnblogs.com/zwfymqz/p/8469856.html
