《小游戏中的玄机.ppt》由会员分享，可在线阅读，更多相关《小游戏中的玄机.ppt（16页珍藏版）》请在三一文库上搜索。
1、小游戏中的玄机,从六角棋到零和博弈 数学学院 宋旸,南开大学第三届“数学之美”论坛,逸事,约翰冯诺伊曼, 美国数学家，现代电子计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。,六角棋（Hex),规则介绍：,对弈的双方分别拥有棋盘上的一组对边。 轮流在六边形中间放置自己颜色棋子 目的是要构筑一条由己方颜色棋子构成的，连接着自己所拥有的两条对边的不间断的链。,蓝方,蓝方,红方,红方,性质：游戏不可能出现平局,1.游戏中不可能出现两方同时获胜。 2.游戏中一定会产生胜者。 不可能双赢，不可能双输一胜一负 意义:分输赢两人零和博弈,蓝方,蓝方,红方,红方,盗
2、用策略,Hex中与数学联系最紧密，最精彩的部分 定理：在六角棋中，先走一方在采取正确的策略后总是可以获胜的。 疑问,用“盗用策略”证明定理,1.反证法：假定后走的一方B（蓝方）有一个必胜策略T。 策略T：一套规则，对A的每种走法都给出一种B的回应，使B最后获胜。 2. B采用策略T。 3.先走一方A（红方）可以采用如下的走法：走第一步时，他先在棋盘上任下一子。从第二步起，他开始也按照T落子。 4.这个额外的子不会阻止先走一方实行策略T。,蓝方,蓝方,红方,红方,T,T,T,T,用“盗用策略”证明定理,5.这样一来，先走一方可以赢得比赛，但后走一方实行必胜策略，也可以赢得比赛。这与游戏没有平局的
3、结论是矛盾的。 6.所以，后走一方不存在必胜策略。 7.既然后走一方没有必胜策略，那么无论他怎样走，理论上先走一方都存在一种策略击败他。 8.所以，先走一方有必胜策略。,对证明的几点说明：,1.这是一个非构造性的证明。 步骤：假设推出矛盾假设不成立。 Eg:任意367个人中一定有生日相同的人。 假设：所有人的生日都不相同有367个生日不可能一定有人生日不同。 2.A有必胜策略，这意味着什么？ 3.”窃取策略“名称的由来。,窃取策略的推广,A.H.Hales和R.J.Jewett一类游戏 共同的特点： 1.游戏双方都有数量不加限制，源源供应的棋子。 2.棋子一旦放到棋盘上就不能移动。 3.每个局
4、中人都要把他的棋子排成某种构型。 4.这种构型对于游戏双方是相同的。 在这些游戏中，先走的一方运用适当的策略一定可以取得至少平局的结果。 适用：连城、搭桥、香农开关等。,窃取策略的意义,数学家Oliver Cross：发现一个搭桥的获胜策略。 Alfred Lehman：有关香农开关游戏的理论。 但是，到目前为止关于六角棋的最好策略也仅可以适用于77的棋盘上，而推向市场的1111棋盘至今也没有被成功破译。,历史：,1942，Piet Hein，丹麦，“Polygon” 1948，John Nash，普林斯顿，“John”，“Nash” 1957，科学美国人，美国，“Hex”,Nash:数学家的
5、美丽心灵,1994年诺贝尔经济学奖获得者 著名的“纳什均衡”提出者,从六角棋到博弈论,事实上，六角棋是具有完全信息的、分输赢的两人零和博弈的一个精彩实例。 博弈论，又称对策论，是研究具有斗争或对抗性质的理论和方法，是数学中的一个新兴分支，也是运筹学的一个重要学科。 现在，零和博弈理论已经被用到彩票、期货等许多领域中去了。,结束语,游戏，孩童的伴侣，大众的娱乐，放松的手段。 数学，人脑的产物，逻辑的王国，科学的明珠。 博弈论，正是游戏与数学这两样天差地别的事物碰撞产生的耀眼火花。谁能想到，小小的游戏竟能暗藏玄机！谁又能想到，高深的数学竟能无孔不入的渗入到我们生活的方方面面！这，是游戏的魅力，更是
6、数学的魅力。,六角棋游戏的其他变种,“Y”型棋：棋盘由三角形组成，需要双方制造一条与棋盘三边都接触的纽带。 立体六角棋：棋盘模仿化学中的“C60”的晶体结构，双方需要用棋子围住一个格子。 美国地图上的六角棋：游戏把六边形的棋盘变成了一张美国地图，其他规则不变。曾有人证明，只要在一开局时占住加利福尼亚州，你就一定可以获胜。,参考书目：,1.美丽心灵 美 西尔维娅娜萨 上海世纪出版集团 2.稳操胜券（上、下） John Conway, Ricard Cuy, Elwyn.R.Berlekamp 上海教育出版社 3.解决问题的策略 德 A恩格尔 上海教育出版社 4.数学迷宫 郭凯声，王元凯编著 科学技术文献出版社 5.清华大学博弈论讲义 百度网,