lecture_10组合博弈入门

ACM程序设计杭州电子科技大学 刘春英 acm@

今天，

你

了吗？

2014-10-18

每周一星(10):

Lin2144

2014-10-18

第十一讲

组合博弈入门(Simple Game Theory)

2014-10-18

导引游戏(1) 玩家：2人； (2) 道具：23张扑克牌； (3) 规则：游戏双方轮流取牌； 每人每次仅限于取1张、2张或3张牌； 扑克牌取光，则游戏结束； 最后取牌的一方为胜者。

2014-10-18

基本思路？

请陈述自己的观点

2014-10-18

第一部分简单取子游戏 (组合游戏的一种)

2014-10-18

什么是组合游戏——(1) 有两个玩家； (2) 游戏的操作状态是一个有限的集合(比如： 限定大小的棋盘); (3) 游戏双方轮流操作； (4) 双方的每次操作必须符合游戏规定； (5) 当一方不能将游戏继续进行的时候，游戏 结束，同时，对方为获胜方； (6) 无论如何操作，游戏总能在有限次操作后 结束；2014-10-18 8

概念:必败点和必胜点(P点 & N点)

必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。

2014-10-18

必败(必胜)点属性(1) 所有终结点是必败点(P点); (2) 从任何必胜点(N点)操作，至少有 一种方法可以进入必败点(P点); (3)无论如何操作， 从必败点(P点)都 只能进入必胜点(N点).

2014-10-18

取子游戏算法实现——步骤1:将所有终结位置标记为必败点(P点);步骤2: 将所有一步操作能进入必败点(P点)的 位置标记为必胜点(N点) 步骤3:如果从某个点开始的所有一步操作都只能 进入必胜点(N点) ,则将该点标记为必败点 (P点) ; 步骤4: 如果在步骤3未能找到新的必败(P点), 则算法终止；否则，返回到步骤2。2014-10-18 11

课内练习:

Subtraction Games: subtraction set S = {1, 3, 4}

x : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14… Pos: P N P N N N N P N P N N N N P…

2014-10-18

实战练习…

kiki's game

2014-10-18

第二部分

Nim游戏

2014-10-18

Nim游戏简介(1) 有两个玩家； (2) 有三堆扑克牌(比如：可以分别是 5,7,9张); (3) 游戏双方轮流操作； (4) 玩家的每次操作是选择其中某一堆牌， 然后从中取走任意张； (5) 最后一次取牌的一方为获胜方；2014-10-18 15

2014-10-18

初步分析

(0, 0, 0)

P-position

(0, 0, x)(0, 1, 1) (0, k, k) (14, 35, 46)

N-positionP-position P-position ???17

2014-10-18

引入概念：Nim-Sum

定义: 假设 (xm · · · x0)2 和(ym · · · y0)2 的 nim-sum是(zm · · · z0)2,则我们表示成 (xm · · · x0)2 ⊕ (ym · · · y0)2 = (zm · · · z0)2, 这里，zk = xk + yk (mod 2)(k=0…m).

2014-10-18

定理一：对于nim游戏的某个位置(x1,x2,x3),当 且仅当它各部分的nim-sum等于0时(即 x1⊕x2⊕x3=0),则当前位于必败点。

定理一也适用于更多堆的情况~

2014-10-18

定理一的证明……

2014-10-18

思考(1):

有了定理一，如果判断某个游戏 的先手是输还是赢？

2014-10-18

本文来源：https://www.bwwdw.com/article/cqxe.html