陈　凯

估计在100位读者中，有99位知道井字棋的玩法(假如不幸成为百里挑一，请用两分钟的时间上网了解一下弈棋规则)。在课堂上，简单的井字棋编程通常只是绘制一个井字棋棋盘，两位玩家轮流弈棋，由计算机判断输赢本篇内容暂不涉及计算机与玩家对弈的人工智能，而是聚焦程序，研究其判断玩家输赢的过程。最常见的方法是，用二维数组存储每一步弈棋的状态，然后按横线、竖线以及对角线的位置取出相应数组空间中的数据，分析这8条线中是否有任意一条线同一棋子数为3。本文的问题是，能不能找到其他判断输赢的方法呢?

来自古老洛书的启示

《周易·系辞上》载有“河出图，洛出书”。传上古时代，有神龟出洛水，壳上所绘图(见右图)称洛书。洛书图案中藏着众多数学奥妙，本文只提及其中很容易看出的幻方特性，即其九宫中各点数纵横与对角相加均为15，这个特性恰能用来解决井字棋输赢判定的问题。

按洛书的点数分别为井字棋棋盘各个空格编号，玩家着子后，不需要以二维数组的方式存储数据，只要记录下每个玩家着子位置所对应的洛书编号即可，设先者棋子为X，后者为○，下表是假想某局对弈局面的变化。

X与○的对弈过程可逐步存储到两个一维的数组中。到第四回合，X在对角线上实现了三子连排，虽然人脑很容易分辨出来，但计算机却不具有天生的图形判别优势，怎么办呢?联系洛书的幻方特性，可发现x所存储的数组中的数据中，一、三、四这三个回合中的编号数相加等于15。于是，判断三子连排的模式，实际上等同于判断X或○所存储数据中，哪一方先取得任意三个编号相加等于15的局面。接下来的难点就在于，完成一局井字棋对弈可能需要三个回台、四个回合甚至五个回合，计算机如何知晓呢?应该如何“任意”取出三个数据做加法呢?

“排排坐，吃果果”

计算机不具备人类的“直觉”，不过利用数学的排列组合以及CPU速度的“蛮劲”，就能穷尽所有“任意”的状态了。例如，将X数组中存储的“5、4、2、8”取出后，按各种可能的次序重新排列，于是得到“4、2、8、5”、“2、8、5、4”、“8、5、4、2”等共24种序列，任一序列中再取前三位数字相加，一旦发现其和为15，则可判为获胜。不过，这样的排列组合方案并不是效率最高的，你能对此进行优化吗?

怎么样进行排列组合的编程呢?这本来需要耗费比较多的精力，但现在许多软件开发工具都提供了功能强大的函数库或类库。例如，Python中的itertools中提供了permutations函数，Ruby中可使用permutation类，即使是Basic，在网络上也能找到由热心网友提供的函数代码。你能自己找到其他方便的排列组合工具吗?(答案在本期找)