lecture_10组合博弈入门

更新时间:2023-05-09 23:21:01 阅读量: 实用文档 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

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

Top