南开大学第三届“数学之美”论坛 小游戏中的玄机 ——从六角棋到零和博弈 数学学院 宋旸.

Presentation on theme: "南开大学第三届“数学之美”论坛 小游戏中的玄机 ——从六角棋到零和博弈 数学学院 宋旸."— Presentation transcript:

1 南开大学第三届“数学之美”论坛 小游戏中的玄机 ——从六角棋到零和博弈 数学学院 宋旸

2 逸事 约翰·冯·诺伊曼, 美国数学家，现代电子计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。
六角棋（Hex)

3 规则介绍： 对弈的双方分别拥 有棋盘上的一组对 边。 轮流在六边形中间 放置自己颜色棋子
目的是要构筑一条 由己方颜色棋子构 成的，连接着自己 所拥有的两条对边 的不间断的链。 蓝方 红方 红方 蓝方

4 性质：游戏不可能出现平局 1.游戏中不可能出现 两方同时获胜。 2.游戏中一定会产生 胜者。 不可能双赢，不可能 双输——一胜一负
意义:分输赢——两人 零和博弈 蓝方 红方 红方 蓝方

5 盗用策略 Hex中与数学联系最紧密，最精彩的部分 定理：在六角棋中，先走一方在采取正确的策 略后总是可以获胜的。 疑问

6 用“盗用策略”证明定理 1.反证法：假定后走的一方 B（蓝方）有一个必胜策略T。
策略T：一套规则，对A的每 种走法都给出一种B的回应， 使B最后获胜。 2. B采用策略T。 3.先走一方A（红方）可以 采用如下的走法：走第一步 时，他先在棋盘上任下一子。 从第二步起，他开始也按照 T落子。 4.这个额外的子不会阻止先 走一方实行策略T。 蓝方 红方 T T T T 红方 蓝方

7 用“盗用策略”证明定理 5.这样一来，先走一方可以赢得比赛，但后 走一方实行必胜策略，也可以赢得比赛。这 与游戏没有平局的结论是矛盾的。
6.所以，后走一方不存在必胜策略。 7.既然后走一方没有必胜策略，那么无论他 怎样走，理论上先走一方都存在一种策略击 败他。 8.所以，先走一方有必胜策略。

8 对证明的几点说明： 1.这是一个非构造性的证明。 步骤：假设——推出矛盾——假设不成立。 Eg:任意367个人中一定有生日相同的人。
假设：所有人的生日都不相同——有367个生 日——不可能——一定有人生日不同。 2.A有必胜策略，这意味着什么？ 3.”窃取策略“名称的由来。

9 窃取策略的推广 A.H.Hales和R.J.Jewett——一类游戏 共同的特点： 1.游戏双方都有数量不加限制，源源供应的棋子。
2.棋子一旦放到棋盘上就不能移动。 3.每个局中人都要把他的棋子排成某种构型。 4.这种构型对于游戏双方是相同的。 在这些游戏中，先走的一方运用适当的策略一定可以取得至少平局的结果。 适用：连城、搭桥、香农开关等。

10 窃取策略的意义 数学家Oliver Cross：发现一个搭桥的获胜策略。 Alfred Lehman：有关香农开关游戏的理论。
但是，到目前为止关于六角棋的最好策略也仅 可以适用于7×7的棋盘上，而推向市场的 11×11棋盘至今也没有被成功破译。

11 历史： 1942，Piet Hein，丹麦，“Polygon” 1948，John Nash，普林斯顿，“John”， “Nash”
1957，《科学美国人》，美国，“Hex”

12 Nash:数学家的美丽心灵 1994年诺贝尔经济学 奖获得者 著名的“纳什均衡” 提出者

13 从六角棋到博弈论 事实上，六角棋是具有完全信息的、分输赢的 两人零和博弈的一个精彩实例。
博弈论，又称对策论，是研究具有斗争或对抗 性质的理论和方法，是数学中的一个新兴分支， 也是运筹学的一个重要学科。 现在，零和博弈理论已经被用到彩票、期货等 许多领域中去了。

14 结束语 游戏，孩童的伴侣，大众的娱乐，放松的手段。 数学，人脑的产物，逻辑的王国，科学的明珠。
博弈论，正是游戏与数学这两样天差地别的事 物碰撞产生的耀眼火花。谁能想到，小小的游 戏竟能暗藏玄机！谁又能想到，高深的数学竟 能无孔不入的渗入到我们生活的方方面面！这， 是游戏的魅力，更是数学的魅力。

15 六角棋游戏的其他变种 “Y”型棋：棋盘由三角形组成，需要双方制造 一条与棋盘三边都接触的纽带。
立体六角棋：棋盘模仿化学中的“C60”的晶体 结构，双方需要用棋子围住一个格子。 美国地图上的六角棋：游戏把六边形的棋盘变 成了一张美国地图，其他规则不变。曾有人证 明，只要在一开局时占住加利福尼亚州，你就 一定可以获胜。

16 参考书目： 1.《美丽心灵》 [美] 西尔维娅·娜萨 上海世纪出 版集团
1.《美丽心灵》 [美] 西尔维娅·娜萨 上海世纪出 版集团 2.《稳操胜券》（上、下） John Conway, Ricard Cuy, Elwyn.R.Berlekamp 上海教育出版社 3.《解决问题的策略》 [德] A·恩格尔 上海教育 出版社 4.《数学迷宫》 郭凯声，王元凯编著 科学技术 文献出版社 5.《清华大学博弈论讲义》 百度网