小游戏中的玄机

小游戏中的玄机从六角棋到零和博弈 数学学院 宋旸南开大学第三届“数学之美”论坛逸事约翰约翰冯冯诺伊曼诺伊曼,美国数学家，现代电子计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。六角棋（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：有关香农开关游戏的理论。但是，到目前为止关于六角棋的最好策略也仅可以适用于77的棋盘上，而推向市场的1111棋盘至今也没有被成功破译。历史：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.清华大学博弈论讲义 百度网