围棋与数学

✍ dations ◷ 2025-09-17 03:26:16 #围棋,组合博弈论,趣味数学

围棋是世界上最流行的游戏之一。由于其规则优美而简单,围棋一直是数学研究的灵感来源。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万秒)。

相关

  • 主动脉瓣狭窄主动脉瓣狭窄(Aortic stenosis,简称AS或AoS)乃描述左心室通向主动脉的瓣膜口狭窄的现象。可能是由主动脉瓣(英语:aortic valve)的结构异常造成,或主动脉瓣的上游或下游解剖结构的异
  • 第八舰队第8舰队为昭和17年(1942年)7月14日日本海军编制成军之舰队。称呼为“外南洋部队”。日本军在新几内亚・所罗门群岛方面(外南洋)担当任务的舰队是由水上部队以及陆上部队所编成。
  • 乔·贝内特办公室角色列表包含了美国情景喜剧《办公室》里的主角、常驻配角、其他配角、客串明星等在剧中的身份及描述。
  • 伊斯兰司法局局长马来西亚回教司法局(马来语:Jabatan Kehakiman Syariah Malaysia,缩写:JKSM)是马来西亚联邦政府机构,负责协调马来西亚回教法院和回教司法机构的行政事务。该机构由马来西亚首席回
  • 电动门电动门(又称:伸缩门)为门和现代科技所结合的技术结晶,一般无须碰触或使力就可使门移动。因为门本身采用电力控制所以又有人称它为。电动门一般在公共场合中较常活动的围墙所使用
  • 多项式时间归约在计算复杂性理论中,多项式时间归约是指假设已有解决一个问题的子程序,利用它在多项式时间内(不考虑子程序运行所用时间)解决另一个问题的归约方法。多项式时间归约有几种不同类
  • 人脸检测人脸检测(face detection)是一种在任意数字图像中找到人脸的位置和大小的计算机技术。它可以检测出面部特征,并忽略诸如建筑物、树木和身体等其他任何东西。有时候,人脸检测也负
  • 朋克文化朋克(punk),又译“庞克”、“鬅客”。朋克文化是一种起源于1970年代的亚文化。最早源起于音乐界,但逐渐转换成一种整合音乐、服装与个人意识主张的广义文化风格。今天我们所见到
  • p-群在数学里,给定一质数,-群即是指一个其每个元素都有的次方阶的周期群。亦即,对每个群内的元素,都存在一个正整数使得的次方等于其单位元素。若是有限的,则其会和自身的阶为的次方
  • 摩尼教残经《摩尼教残经》,亦作《摩尼教经》,是英国考古学家斯坦因发现于莫高窟藏经洞的唐朝摩尼教遗书,为摩尼教敦煌汉语三经之一。现藏中国国家图书馆,编号BD00256。1911年,罗振玉因不确