围棋与数学

✍ dations ◷ 2025-04-04 11:15:12 #围棋,组合博弈论,趣味数学

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

相关

  • 抗心律失常药抗心律失常药(英语:Antiarrhythmic agents)是一类用于抑制心脏非正常节律(心律失常)的药物,这些情况例如心房颤动、心房扑动、心室性心搏过速以及心室颤动。很多人试图将此类药物
  • 丘比特丘比特(拉丁语:Cupido,拉丁英文转写Cupid),又称埃莫(拉丁语:Amor),罗马神话中的小爱神,维纳斯的儿子,相对应于希腊神话的厄洛斯(希腊语:Έρως)。往往被塑造为手拿弓箭、背部长有一对翅
  • 透克氏症透克氏症(Turcot syndrome),是一种显性遗传的遗传性疾病,主要是具有家族遗传性大肠息肉症的患者并发中枢神经系统的肿瘤的发生,通常表现为神经胶质瘤。最早的病例是由加拿大外科
  • 希利莱维尼奥布尔希伊葡萄园(法语:Chilly-le-Vignoble),音译为"希伊勒维尼奥布勒",是法国汝拉省的一个市镇,位于该省西部,省会隆斯勒索涅市区西南,属于隆斯勒索涅区。该市镇总面积3.07平方公里,2009年
  • 分娩并发症分娩(childbirth)也称为生产,是指妇女怀孕之后,一个或多个胎儿离开母亲子宫,开始在子宫外生活的过程,可能是经由阴道的阴道分娩,也可能是剖宫产。全世界在2015年时有1.35亿人出生,其
  • 福冈圣菜福冈圣菜(日语:福岡 聖菜/ふくおか せいな  */?,2000年8月1日-)是日本偶像艺人,为女子偶像团体AKB48 Team B成员。神奈川县出身,所属经纪公司为AKS。
  • 2006年世界房车锦标赛墨西哥站2006年世界房车锦标赛墨西哥站是2006年度世界房车锦标赛的第六站赛事,正式比赛在2006年7月30日于墨西哥米格尔赛道上举行。这是第二次在墨西哥举行赛事。第一回合由N.Technol
  • 高级音频编码Apple containerRaw stream高级音频编码(英语:Advanced Audio Coding,AAC),出现于1997年,为一种基于MPEG-2的有损数字音频压缩的专利音频编码标准,由Fraunhofer IIS、杜比实验室、A
  • 交流发电机交流发电机(Alternator、Alternating Current Generator)是发电机的一种,它可将机械能转换成交流电形式的电能。发电机的结构主要分为定子(stator)和转子(rotor)两部分。定子即是发
  • 陈扬 (主持人)陈扬(1954年7月30日-),中国广东陆丰人。电台、电视台节目主持人,资深媒体评论人。其以言辞犀利、作风强硬、形象亲民、热爱广州而著称,深受广州市民欢迎。陈扬1954年于广州陆军医