祝贺北理工/六子棋遐想

2009-05-19

时隔半年再闻喜讯,在西班牙潘普洛纳市刚刚结束的第14届ICGA国际计算机(棋类)奥林匹克大赛中,北京理工大学软件学院2006级本科生崔皓、李亮、林思然、王锐坚开发的六子棋程序“中国深度”一举夺得金牌。北理工其他几支日本将棋、幻影围棋等队伍也分获多枚银牌和铜牌。

从2006年北理工学生初涉全国计算机博弈比赛,到2007年获得六子棋全国亚军,再到2008年的国际亚军以及这一次的国际冠军,北理工已经在计算机博弈领域有所积淀,初步形成了一个优势项目。我代表已经毕业的北理工第一代计算机博弈选手再次向你们表示衷心的祝贺!

诚然,棋类博弈只是人工智能中的一个子领域。在对手不断改进、黑马不断涌现的情况下,保持自己程序的常胜地位是难上加难。对非职业选手来说,夺得国际冠军来之不易。他们在这一过程中获得的,不只是精通某类问题的特定解法,而是借助对算法的研究培养了一种偏数学、偏逻辑的共性思维能力。对计算机、软件专业的学生来说,这比一块奖牌要实在得多。


六子棋发明人吴毅成教授在其论文《A New Family of k-in-a-row Games》中定义了K子棋:Connect(m, n, k, p, q),其中棋盘大小为m×n,先手方第一步下q个棋子,以后双方每步各下p个棋子,先将k子连成一线者为胜利。他在此基础上说明了前人已经证明过的五子棋[Connect(15, 15, 5, 1, 1)]的不公平性以及六子棋[Connect(19, 19, 6, 2, 1)]的公平性和复杂度(衡量可玩性)。我认为他提出用这个q来化解先手优势是较为创新的,尽管此前的棋类实践中早已有贴目、让子之类的规则,但专门拿出这个q,在公平性的形式化证明中还是很有一般意义的。

K子棋还可能有什么创新的思路呢?容易想到的改变棋盘的形状和维度,很早就有这类实践或产品了,比如3-D Tic-Tac-Toe。或者是增加游戏人数(参数u),三个人在纸上下五子棋想必很多人都尝试过。另外,由那个q也容易联想到,可以将p、q合并为一个函数p(t)或p(u, t),代表第t手,或第u个玩家的第t手可以下几个棋子。类似的想法还有k(u)等。

2007年我在和吴双同学研究六子棋时,就有一个想法:K子棋的各项参数能否突破自然数的限制?如果这些参数取负数、分数乃至无理数、复数,是不是可以发明一类新的游戏?即使不能得到一种现实中可玩的游戏,是否可以在计算机上模拟呢(例如Magic Cube 4D)?如果不能模拟,那么是不是可以作为一种纯抽象的数学游戏或思维游戏呢?如果把这种东西作为游戏太耗神,那么能否用作对其它领域事物的一种建模,为其它问题的描述或解决提供方法呢?想想看,指数函数的自变量是自然数时可以直观地表示连乘,但它扩展到实数域、复数域后,用于复分析,成为了重要的数学工具。整数维度可以描述物理空间,但分数维度在解释分形理论时同样有实际意义。分数维空间中的无理数个玩家进行的复数子棋,或许真的是某种现实事物的数学模型。有兴趣的朋友来研究一下吧!