简单博弈论小游戏(博弈论十大经典游戏)

简单博弈论小游戏

那么每个position或者是P-position或者是N-position,而且可以通过定义计算出来。

通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

，其中一方肯定有必胜策略。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。这种分析方法有一种很形象的名字叫做

NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只有黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

博弈论十大经典游戏

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必赢。

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次都可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达下个局面连有向边。

设G1,G2,Gm是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1,G2,Gn的和。

博弈论经典案例100例

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G)=SG(s)。

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1，y2，yk，定义SG(x)为x的后继节点y1，y2，yk的SG函数值构成集合在执行mex(S)运算的结果，即：