井字棋游戲與數(shù)據(jù)模型

陳　凱

估計在100位讀者中，有99位知道井字棋的玩法(假如不幸成為百里挑一，請用兩分鐘的時間上網(wǎng)了解一下弈棋規(guī)則)。在課堂上，簡單的井字棋編程通常只是繪制一個井字棋棋盤，兩位玩家輪流弈棋，由計算機(jī)判斷輸贏本篇內(nèi)容暫不涉及計算機(jī)與玩家對弈的人工智能，而是聚焦程序，研究其判斷玩家輸贏的過程。最常見的方法是，用二維數(shù)組存儲每一步弈棋的狀態(tài)，然后按橫線、豎線以及對角線的位置取出相應(yīng)數(shù)組空間中的數(shù)據(jù)，分析這8條線中是否有任意一條線同一棋子數(shù)為3。本文的問題是，能不能找到其他判斷輸贏的方法呢?

來自古老洛書的啟示

《周易·系辭上》載有“河出圖，洛出書”。傳上古時代，有神龜出洛水，殼上所繪圖(見右圖)稱洛書。洛書圖案中藏著眾多數(shù)學(xué)奧妙，本文只提及其中很容易看出的幻方特性，即其九宮中各點數(shù)縱橫與對角相加均為15，這個特性恰能用來解決井字棋輸贏判定的問題。

按洛書的點數(shù)分別為井字棋棋盤各個空格編號，玩家著子后，不需要以二維數(shù)組的方式存儲數(shù)據(jù)，只要記錄下每個玩家著子位置所對應(yīng)的洛書編號即可，設(shè)先者棋子為X，后者為○，下表是假想某局對弈局面的變化。

X與○的對弈過程可逐步存儲到兩個一維的數(shù)組中。到第四回合，X在對角線上實現(xiàn)了三子連排，雖然人腦很容易分辨出來，但計算機(jī)卻不具有天生的圖形判別優(yōu)勢，怎么辦呢?聯(lián)系洛書的幻方特性，可發(fā)現(xiàn)x所存儲的數(shù)組中的數(shù)據(jù)中，一、三、四這三個回合中的編號數(shù)相加等于15。于是，判斷三子連排的模式，實際上等同于判斷X或○所存儲數(shù)據(jù)中，哪一方先取得任意三個編號相加等于15的局面。接下來的難點就在于，完成一局井字棋對弈可能需要三個回臺、四個回合甚至五個回合，計算機(jī)如何知曉呢?應(yīng)該如何“任意”取出三個數(shù)據(jù)做加法呢?

“排排坐，吃果果”

計算機(jī)不具備人類的“直覺”，不過利用數(shù)學(xué)的排列組合以及CPU速度的“蠻勁”，就能窮盡所有“任意”的狀態(tài)了。例如，將X數(shù)組中存儲的“5、4、2、8”取出后，按各種可能的次序重新排列，于是得到“4、2、8、5”、“2、8、5、4”、“8、5、4、2”等共24種序列，任一序列中再取前三位數(shù)字相加，一旦發(fā)現(xiàn)其和為15，則可判為獲勝。不過，這樣的排列組合方案并不是效率最高的，你能對此進(jìn)行優(yōu)化嗎?

怎么樣進(jìn)行排列組合的編程呢?這本來需要耗費比較多的精力，但現(xiàn)在許多軟件開發(fā)工具都提供了功能強(qiáng)大的函數(shù)庫或類庫。例如，Python中的itertools中提供了permutations函數(shù)，Ruby中可使用permutation類，即使是Basic，在網(wǎng)絡(luò)上也能找到由熱心網(wǎng)友提供的函數(shù)代碼。你能自己找到其他方便的排列組合工具嗎?(答案在本期找)