围棋与数学

✍ dations ◷ 2025-04-26 13:29:45 #围棋,组合博弈论,趣味数学

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

相关

  • 黑曲霉黑曲霉(学名:Aspergillus niger)是属于散囊菌目发菌科曲霉属的一种真菌,可生长在土壤、粮食、药材、虫体、枯枝落叶、动物粪便、地下电缆麻、猕猴桃汁、霉腐物及各种材料的基物
  • 缩略语缩写(英语:Abbreviation(Abbrev),来自拉丁语 brevis,意为“短”),在语言学里是一种词语或短语的简易形式,又称省略、缩略语、缩写词。缩写大部分时候等同于简称,但它们之间有细微的差
  • 郑洞天郑洞天(1944年5月-),籍贯河南罗山,生于重庆,中国电影导演,1966年毕业于北京电影学院导演系,1976年回到北京电影学院导演系任教。1982年执导的电影《邻居》获第2届中国电影金鸡奖最佳
  • 氯化亚金氯化亚金(氯化金(I)),又称一氯化金。是金元素的一种氯化物,化学式为AuCl。氯化亚金可以通过三氯化金的热分解来制备。虽然更高温度下如果氯气的压强合适它可以保持稳定,但是它在
  • Motion JPEGMotion JPEG(M-JPEG或MJPEG,Motion Joint Photographic Experts Group,FourCC:MJPG)是一种影像压缩格式,其中每一帧图像都分别使用JPEG编码。M-JPEG常用在数字相机和摄像头之类的
  • 黎遂球黎遂球(1602年-1646年),字美周,号迦陵,番禺(今广州番禺板桥乡)人。于广东省城豪贤路出世。自幼聪慧,师从陈子壮。天启六年(1626年)县试冠其曹,天启七年(1627年)举人,再试不第。与徐汧、吴伟
  • 康树华康树华(1926年8月27日-2014年2月7日),黑龙江省绥化人,中华人民共和国犯罪学家。1948年,毕业于东北教育学院教育系,1954年调入北京大学法律系任教。1962年至1977年,供职于北京大学图
  • 加利福尼亚岛加利福尼亚岛指的是欧洲人从16世纪开始的很长时间内持有的一个错误概念:加利福尼亚(实指现在的下加利福尼亚半岛)不是北美洲本土的一部分,而是一个与大陆分离的并由一个现在被认
  • 肯普法《肯普法》(日语:けんぷファー;英语/德语:Kämpfer(源自德语中"战士"一词))是筑地俊彦撰写,Senmu绘插画的轻小说作品,由Media Factory的MF文库J出版发行,中文版由尖端出版社代理发行
  • 岑长倩岑长倩(?-691年)荆州人。唐朝宰相,邓国公。岑文叔之子,早年失去双亲,由叔父岑文本抚养,曾任兵部侍郎,永淳元年(682年)四月进为同中书门下平章事,参与朝政。凤阁舍人张嘉福与洛州人王庆