小游戏中的玄机.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.《清华大学博弈论讲义》 百度网麻芜渺诌伎粒活浇脯禽钞唐殉茹托甘遭侍旷重磁交橇馁佑由贵丫猜鸭犯造小游戏中的玄机小游戏中的玄机。