围棋与数学

✍ dations ◷ 2025-08-22 11:54:39 #围棋,组合博弈论,趣味数学

围棋是世界上最流行的游戏之一。由于其规则优美而简单,围棋一直是数学研究的灵感来源。11世纪的中国学者沈括在《梦溪笔谈》中估计,围棋所有可能的局面数量为 10172 左右。近年来,约翰·H·康威在对围棋的研究中发明了超现实数,并促进了组合博弈论(英语:combinatorial game theory)的发展(“围棋微数字”就是它在围棋中使用的一个具体示例)。

广义围棋是在 的棋盘上进行的,在广义围棋的给定位置确定赢家的计算复杂性主要取决于打劫规则。

围棋的复杂性“几乎”是在PSPACE内的,这是因为在对弈的非打劫阶段,每一手都是不可逆的,只有通过吃子才有可能出现重复的棋形,使得复杂性提高。

没有打劫的话,围棋是PSPACE困难的。 这是通过把PSPACE完全的TQBF(真量化布尔公式)简化到广义地理(英语:generalized geography),到平面广义地理,到最高3阶的广义地理,最后简化到围棋棋盘位置。

有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过 n 2 {\displaystyle n^{2}} 的棋局数量,包括在实际中不可能下出的棋局,Tromp和Farnebäck分别给出 10480 的下限和 101710 的上限。人们听到最多的所有可能的棋局数量为 10700, 这个数字是361手棋的简单排列(361! = 10768)得出的。另一个常见的推导是假设每一手棋都有 n 个选择,总共 L 手棋,那么棋局总量就是 NL。就比如在某些职业对局中能够见到的一局棋400手,按照这种方法算出来就是 361400(101023)种可能的棋局。

所有可能的对局总数是棋盘大小和手数的函数。虽然大多数棋局都在400手以内,甚至200手都不到,但棋局是有可能更长的。

所有可能的对局总数可以通过多种方式从棋盘大小估算,有些方式会比另外一些更严格。最简单的,棋盘大小的简单排列 (N)L,没有考虑到非法吃子,以及非法的盘面。令 N 为棋盘大小(19×19=361),L 为最长的棋局长度,NL 构成了下界。在Tromp/Farnebäck的论文中给出了更精确的限制。

10700 这个数字对于200手以内的所有棋局来说是一种高估,但对361手以内的所有棋局来说是一种低估。而4700万手的棋,在一秒一手、每天下16个小时的情况下,也要下2¼年(一年有3100万秒)。

相关

  • 中国水危机中国给水排水系统的建设随着中国经济与科技的高速发展日新月异、成果斐然,但距其完善又任重道远。随着中国城市化进程的逐步加快与城乡贫富差距的进一步扩大,以及水资源短缺、
  • 比利牛斯山比利牛斯山,位于欧洲西南部,山脉东起于地中海,西止于大西洋,分隔欧洲大陆与伊比利亚半岛,也是法国与西班牙的天然国界,山中有小国安道尔。长435公里,宽80-140公里,一般海拔在2000米以
  • 拖鞋兰5个,详见内文Cordula Raf. Menephora Raf. Stimegas Raf.拖鞋兰属(学名:Paphiopedilum),俗称兜兰、拖鞋兰、仙履兰、芭菲尔鞋兰,是兰科下的一个属。属名Paphiopedilum来自希腊文Pa
  • 类型电台类型电台或类型化电台(英语:Radio Format),有时也称为“类型节目”(Programming Format),描述的是某个广播电台节目内容的整体性质归属。类型电台淡化了电台节目之间的区别,为特定的
  • 文森特 (消歧义)文森特可以指:作为人名,文森特还可能指:
  • 方若望方若望(Bishop Emmanuel-Jean-François Verrolles, M.E.P.1805年4月12日-1878年4月29日),天主教满洲宗座代牧区首任主教,巴黎外方传教会会士。1805年4月12日,方若望出生在法国Ven
  • 回环回环(loopback)指将电子信号、数据流等原样送回发送者的行为。它主要用于对通信功能的测试。回环网卡(Loopback adaptor),是一种特殊的网络接口,不与任何实际设备连接,而是完全由软
  • 极品飞车:无间追踪《极品飞车:最高通缉》(Need For Speed: Most Wanted),是艺电(EA)推出的《极品飞车》系列赛车游戏之一,于2005年11月15日开始在美国推出。游戏结合竞速、逃避警方追捕、子弹时间,以
  • 屋顶棱镜屋顶棱镜通常就是能经由反射作用将光线行进方向只是单纯的改变90 °的光学棱镜的总称或代名词。经由两个平面反射和翻转的图像会在光轴上交会并向侧面翻转。单独的普罗棱镜
  • 述异记 (祖冲之)述异记,南朝齐祖冲之所撰志怪小说集。祖冲之,字文远,范阳郡迺县(今河北省涞水县)人,南北朝数学家。历仕南朝宋、南朝齐两朝,任南徐州迎从事、娄县令、长水校尉等职。《述异记》此书