小游戏中的玄机.ppt

小游戏中的玄机——从六角棋到零和博弈 数学学院 宋旸南开大学第三届“数学之美”论坛逸事约翰约翰·冯冯·诺伊曼诺伊曼, 美国数学家，现代电子计算机创始人之一他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献六角棋（Hex)规则介绍：对弈的双方分别拥有棋盘上的一组对边轮流在六边形中间放置自己颜色棋子目的是要构筑一条由己方颜色棋子构成的，连接着自己所拥有的两条对边的不间断的链蓝方蓝方红方红方性质：游戏不可能出现平局1.游戏中不可能出现两方同时获胜2.游戏中一定会产生胜者不可能双赢，不可能双输——一胜一负意义:分输赢——两人零和博弈蓝方蓝方红方红方盗用策略Hex中与数学联系最紧密，最精彩的部分定理：在六角棋中，先走一方在采取正确的策略后总是可以获胜的疑问用“盗用策略”证明定理1.反证法：假定后走的一方B（蓝方）有一个必胜策略T策略T：一套规则，对A的每种走法都给出一种B的回应，使B最后获胜2. B采用策略T3.先走一方A（红方）可以采用如下的走法：走第一步时，他先在棋盘上任下一子从第二步起，他开始也按照T落子。

4.这个额外的子不会阻止先走一方实行策略T蓝方蓝方红方红方TTTT用“盗用策略”证明定理5.这样一来，先走一方可以赢得比赛，但后走一方实行必胜策略，也可以赢得比赛这与游戏没有平局的结论是矛盾的6.所以，后走一方不存在必胜策略7.既然后走一方没有必胜策略，那么无论他怎样走，理论上先走一方都存在一种策略击败他8.所以，先走一方有必胜策略对证明的几点说明：1.这是一个非构造性的证明步骤：假设——推出矛盾——假设不成立Eg:任意367个人中一定有生日相同的人假设：所有人的生日都不相同——有367个生日——不可能——一定有人生日不同2.A有必胜策略，这意味着什么？3.”窃取策略“名称的由来窃取策略的推广•A.H.Hales和R.J.Jewett——一类游戏•共同的特点：•1.游戏双方都有数量不加限制，源源供应的棋子•2.棋子一旦放到棋盘上就不能移动•3.每个局中人都要把他的棋子排成某种构型•4.这种构型对于游戏双方是相同的•在这些游戏中，先走的一方运用适当的策略一定可以取得至少平局的结果•适用：连城、搭桥、香农开关等窃取策略的意义数学家Oliver Cross：发现一个搭桥的获胜策略。

Alfred Lehman：有关香农开关游戏的理论但是，到目前为止关于六角棋的最好策略也仅可以适用于7×7的棋盘上，而推向市场的11×11棋盘至今也没有被成功破译历史：1942，Piet Hein，丹麦，“Polygon”1948，John Nash，普林斯顿，“John”，“Nash”1957，《科学美国人》，美国，“Hex”Nash:数学家的美丽心灵1994年诺贝尔经济学奖获得者著名的“纳什均衡”提出者从六角棋到博弈论事实上，六角棋是具有完全信息的、分输赢的两人零和博弈的一个精彩实例博弈论，又称对策论，是研究具有斗争或对抗性质的理论和方法，是数学中的一个新兴分支，也是运筹学的一个重要学科现在，零和博弈理论已经被用到彩票、期货等许多领域中去了结束语游戏，孩童的伴侣，大众的娱乐，放松的手段数学，人脑的产物，逻辑的王国，科学的明珠博弈论，正是游戏与数学这两样天差地别的事物碰撞产生的耀眼火花谁能想到，小小的游戏竟能暗藏玄机！谁又能想到，高深的数学竟能无孔不入的渗入到我们生活的方方面面！这，是游戏的魅力，更是数学的魅力六角棋游戏的其他变种“Y”型棋：棋盘由三角形组成，需要双方制造一条与棋盘三边都接触的纽带。

立体六角棋：棋盘模仿化学中的“C60”的晶体结构，双方需要用棋子围住一个格子美国地图上的六角棋：游戏把六边形的棋盘变成了一张美国地图，其他规则不变曾有人证明，只要在一开局时占住加利福尼亚州，你就一定可以获胜参考书目：1.《美丽心灵》 [美] 西尔维娅·娜萨 上海世纪出版集团2.《稳操胜券》（上、下） John Conway, Ricard Cuy, Elwyn.R.Berlekamp 上海教育出版社3.《解决问题的策略》 [德] A·恩格尔 上海教育出版社4.《数学迷宫》 郭凯声，王元凯编著 科学技术文献出版社5.《清华大学博弈论讲义》 百度网。