井字棋游戲與數據模型

估計在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，在網絡上也能找到由熱心網友提供的函數代碼。你能自己找到其他方便的排列組合工具嗎?(答案在本期找)