黑白棋开局。| 图源:日本最弱黑白棋AI对战平台最弱オセロ对局界面
• 只要落子和棋盘上任一枚己方的棋子在一条线上(横、直、斜线皆可)夹着对方棋子,就能将对方的这些棋子转变为己方棋子(翻面即可)。夹住的位置上必须全部是对手的棋子,不能有空格。并且,只有在可以翻转棋子的地方才可以下子。
• 一步棋可以在数个方向上翻棋,任何被夹住的棋子都必须被翻转过来,棋手无权选择不去翻某个棋子。必须是刚下的子夹住对方才能够给对方棋子翻面,因翻转对方棋子而夹住的棋子是不能被翻面的。
• 如果一方没有合法的棋步可下,就必须让对方继续下子,直到自己有合法的棋步为止。如果双方都没有合法的棋步可下,游戏就结束。
游戏结束时棋盘上棋子多的一方获胜。若棋数一样,则为和局。
策梅洛定理(Zermelo's theorem)与Solved game
对任何一种棋类的研究,都脱不开德国数学家策梅洛在1913年发表的著名定理:
在二人的有限游戏中,如果双方皆拥有完全的资讯,并且运气因素并不牵涉在游戏中,那先行或后行者当中必有一方有必胜/必不败的策略。
注意,很多人不能正确地理解该定理,甚至认为它不过是一句显而易见的废话。为了彰显定理的意义,请大家先思考一下“石头剪刀布”的游戏。
在无作弊的情况下,“石头剪刀布”是一种运气游戏,它也不存在任何必胜策略。那么我们凭什么可以认为,一个非运气游戏就一定有一方存在必胜/必不败策略呢?掺杂了运气成分的游戏和不掺杂运气成分的游戏诚然有本质上的不同,但这绝非显然,而是需要数学证明的。
这里提供一个便于理解的通俗化证明思路:我们假设对弈双方都是智慧无限的神仙。如果一方在某一步败了(比如象棋中被将死),那么他在悔一步棋之后仍然是必败,否则与我们的“无限智慧”矛盾(因为他上一步就走错了),依次类推,我们知道游戏的胜负在开局就已经决定了——也就是有一方有必胜策略。
实际上,策梅洛定理就是完全信息博弈论的基石。由此我们知道,每一种可在有限步数内结束的常规棋类游戏,都有一方是必胜或至少是必不败的。后续的问题就是:找出存在必不败策略的那一方。
当我们确认了某游戏里先手或后手一方存在必胜/必不败策略的时候,就说该游戏是solved game。目前solved game还没有统一的标准译名,但可以很自然地直接翻译成已解决或已破解游戏。
对于已破解游戏,还分出三种强度。
超弱解(ultra-weak solution):理论证明一方可以保证赢得游戏,或者游戏必然平局,但不需要给出具体的赢法或平局法。这种解法只需要借助数学工具分析游戏的抽象属性,而不需要穷举所有的可能性。
弱解(weak solution):给出一个算法,可以从游戏的初始状态开始,保证某个玩家赢得游戏,或者任何玩家都不会输掉游戏。这种解法通常需要穷举游戏树的所有分支,或者利用预先生成的数据库。
强解(strong solution):给出一个算法,可以从游戏的任何状态开始,给出最优的走法,无论之前的走法是否完美。这种解法需要穷举游戏树的所有节点,或者利用预先生成的数据库。
在1993年,五子棋得以破解。今年10月,黑白棋也获得了弱解。我们现在知道,如果两个拥有无限计算能力的神仙来下黑白棋,则他们必然是永远平局。换句话说,黑白棋是非常公平的棋类游戏。先手或后手一方,并未因此获得微弱的优势。这和高水准的黑白棋棋手的感觉一致。
同时,因为是弱解,来自日本初创AI研发企业Preferred Networks的生物信息学家和计算机科学家滝沢拓己还穷举了对弈双方的从开局开始的最佳策略。
(需要说明的是,人类并未破解围棋和国际象棋。虽然现在的下棋AI远比人类强大,但它们并没有找到最正确的走法。它们仅仅是找到了比我们人类更正确的走法。)
技术与意义
在计算机科学的襁褓时期,完全破解象棋等纯策略游戏就一直被认为是人类智慧的非凡成就。自那时以来,这也是人工智能(AI)领域的重大课题。早期的研究者包括查尔斯·巴贝奇(Charles Babbage)和克劳德·香农(Claude Elwood Shannon)。随着机器学习技术和计算能力的提升,人类制造出了拥有超高棋力的AI(如里程碑式的AlphaGo),但这些超强AI并不能完美地破解这些游戏。不久之前,人们还普遍认为黑白棋也太过复杂,无法被破解。所以它一直是人工智能领域里的一项宏伟挑战。
为了破解黑白棋,滝沢拓己用现代技术强化了上世纪90年代就已非常强大的下棋程序Edax,然后将任务分解成更易于管理的部分。他先分析了棋盘上剩下50个空位的情况,随后又考察了有36个空位时所有有意义的局势。他惊喜地发现,似乎现有算力足以支持弱解黑白棋。