围棋与数学

✍ dations ◷ 2025-06-29 12:41:25 #围棋,组合博弈论,趣味数学

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

相关

  • Addison-Wesley艾迪生维斯理(英语:Addison-Wesley),位于美国马塞诸塞州波士顿的图书出版商,以其出版的计算机科学领域教科书而广为人知。除了图书,Addison-Wesley还通过Safari Books Online发行
  • 生物相生物相(英语:Biota (ecology)),又译作生物群与地方生物志,是指一地区或时代的生物总合。地球上的生物相生活在生物圈里。一般来说,不会将人类放入生物相的分类中。
  • 威廉·佩特斯·霍比机场威廉·佩特斯·霍比机场(英语:William P. Hobby Airport,IATA代码:HOU;ICAO代码:KHOU;FAA代码:HOU)是美国休斯顿三大机场之一,是休斯顿地区最早建造的机场,在乔治·布什洲际机场建成前
  • 护良亲王护良亲王(1308年-1335年8月12日,延庆元年-建武二年七月二十三日),是镰仓时代后期至建武新政时期的人物,建武新政府的征夷大将军。父亲是后醍醐天皇,母亲是源师亲(日语:源師親)之女亲子
  • 亥姆霍兹定理亥姆霍兹定理可以指:
  • 威尔逊-巴甫效应钙II K线是低温恒星的吸收谱线中最明显的一条谱线。一条来自色球层的微弱发射线存在于中心。在1957年,奥林·威尔逊和M. K. 巴甫报告前述发射谱线的宽度和恒星的绝对星等之间
  • PANDORA (Kara迷你专辑)Kara Solo Collection2012《PANDORA》(韩语:판도라)是韩国流行女子组合KARA继2011年发行第三张正规专辑《STEP》后睽违一年于2012年8月22日再度发行的第五张迷你专辑。up and u
  • 阮文永阮文永(越南语:Nguyễn Văn Vĩnh,占语名:Po Klan Thu,?-1829年),是一位宾童龙占婆君主,1822年至1829年在位。 1807年(嘉隆六年)十月,阮文永被嘉隆帝任命为顺城镇副镇。1822年(明命三年),正
  • 普遍性 (物理学)在物理学中,普遍性(universality)说很多系统有相似的大规模数字属性,不依赖系统的小细节,例如临界指数。常见的是,系统在缩放极限表示普遍性。普遍性这个观念在动力学和其他数学分
  • 宗教大法官《宗教大法官》是杜思妥也夫斯基所著的《卡拉马佐夫兄弟》这本小说里的角色二哥无神论者伊凡所写的一出戏剧,出现在本书的第5卷第5章—宗教大法官。这个故事的背景设在16世纪