Monthly Archives: June 2010

SG 函数有什么用？ 假定我们有 n 个游戏图，G1 = (X1, F1),G2 = (X2, F2), . . . ,Gn = (Xn, Fn)。可以将它们结合成一个新图，G = (X,F)。X = X1×· · ·×Xn 笛卡尔乘积。X 是个 n 元组 (x1, . . . , xn)，对于 i，xi ∈ Xi。对于 x = (x1, … Continue reading →

前面几节谈到的游戏可以用图理论来描述，考虑一个图 G = (X, F)；其中 X 是顶点，也是先前游戏中可能的态势。F 是一个函数，对于 X 中的任意一个 x，F(x) 的值都出现在 X 中，对于 X 的一个元素 x，F(x) 的含义是一个玩家从 x 出发可以移动到的局势。 对于一个两人的类似前面的游戏而言，可以在一个如此这样的图上进行博弈，首先指定一个起始点 x0，并使用下面的规则： （1）玩家 I 从 x0 开始首先移动； （2）玩家交替移动； （3）在 x 态势时，玩家要将态势转移到另一个态势 y，其中 y 是 F(x) 中的元素。 为简单起见，假定图中不存在环，元素个数为 n，其中最长的一条路径也不超过 n。那么对于前面我们分析的减法游戏，其中 S … Continue reading →

从取石子游戏（Bash Game）到多堆的尼姆博弈是一个大进步，尼姆博弈的就是把取石子中的 1 堆变成了多堆。游戏者轮流从某一堆棋子中取走一个或者多个（这里暂时不限定每次最多能取几个），最后不能再取的就是输家。当指定相应数量时，一堆这样的棋子称作一个尼姆堆。 这里假定是 3 堆。 其实现在这个问题的一部分解决了——任意多堆的相同个数的 Nim 堆。而且很容易知道，（0,N,N）一定是必败态，如果有仔细尝试的话，可以发现（1,2,3）也是必败态，那到底有什么规律呢？ 命题：(a,b,c) 是必败态等价于 p(a, b, c) = a xor b xor c = 0 ( xor 是异或运算) 如果我们面对的是一个非奇异局势 (a，b，c)，要如何变为奇异局势呢？假设 a < b< c,我们只要将 c 变为 a xor b,即可，因为有如下的运算结果: 要将 c 变为 … Continue reading →

大致上是这样的：有两堆石子，不妨先认为一堆有 10，另一堆有 15 个，双方轮流取走一些石子，合法的取法有如下两种： 1、在一堆石子中取走任意多颗； 2、在两堆石子中取走相同多的任意颗； 约定取走最后一颗石子的人为赢家，求必胜策略。 两堆石头地位是一样的，我们用余下的石子数（a,b）来表示状态，并画在平面直角坐标系上。和前面类似，（0，0）肯定是 P 态，又叫必败态或者奇异局势。（0,k）,（k,0）,（k,k） 系列的节点肯定不是 P 态，你面对这样的局面一定会胜，只要按照规则取一次就可以了。再看 y = x 上方未被划去的格点，（1，2）是 P 态。k > 2 时，（1，k）不是 P 态，比如你要是面对（1，3）的局面，你是有可能赢的。同理，（k，2），（1 + k，2 + k）也不是 P 态，划去这些点以及它们的对称点，然后再找出 y = x 上方剩余的点，你会发现（3，5）是一个 P 态，如此下去，如果我们只找出 a b[k]，那么，取走 b - … Continue reading →

本节进入正题。 简单的取拿游戏 一堆石子（或者其它的什么东西），下面是简单的取拿游戏规则： 两名玩家，称为 I 和 II； 有一堆石子，一共 21 个； 一次移动操作包括取走 1 个，2 个，或者 3 个石子，至少得取走 1 个，至多取走 3 个。 玩家 I 先开始，交替取，不可不取。 取走最后一个石子的获胜。

一批文章： http://hi.baidu.com/liveroom/blog/category/%B2%A9%DE%C4%C2%DB http://blog.csdn.net/logic_nut/archive/2009/10/21/4706649.aspx http://blog.csdn.net/logic_nut/archive/2009/10/22/4711489.aspx http://yjq24.blogbus.com/tag/%E5%8D%9A%E5%BC%88/ http://hi.baidu.com/%C3%D7%C0%BCloveac/blog/category/%B2%A9%DE%C4 http://hi.baidu.com/somnuslove/blog/item/d24567e91761b234b80e2da5.html http://www.cppblog.com/sdfond/archive/2010/02/06/107364.aspx http://www.math.ucla.edu/~tom/Game_Theory/Contents.html http://hi.baidu.com/%C3%D7%C0%BCloveac/blog/item/b7d8f316600004084a90a7d7.html http://hi.baidu.com/%C3%D7%C0%BCloveac/blog/item/a9ec4a876de1c33766096e42.html http://blog.sina.com.cn/s/blog_51cea4040100h3l9.html http://blog.sina.com.cn/s/blog_51cea4040100h3wl.html http://hi.baidu.com/feng5166/blog/category/%B2%A9%DE%C4%D7%A8%CC%E2 记住翻硬币问题： http://yoyo.is-programmer.com/posts/8355.html http://www.cut-the-knot.org/blue/tt.shtml http://3214668848.blog.163.com/blog/static/4876491920104333514987/ http://3214668848.blog.163.com/blog/static/48764919200910214719169/

有五个理性的海盗，A, B, C, D 和 E，找到了100个金币，需要想办法分配金币。 海盗们有严格的等级制度：A 比 B 职位高，B 比 C 高，C 比 D 高，D 比 E 高。 海盗世界的分配原则是：等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配，包括提议人。并且在票数相同的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，然后由下一个最高职位的海盗提出新的分配方案。

囚徒困境是博弈论的非零和博弈中具代表性的例子，反映个人最佳选择并非团体最佳选择。虽然困境本身只属模型性质，但现实中的价格竞争、环境保护等方面，也会频繁出现类似情况。