最近我用Python做了一個國際象棋程序并把代碼發布在Github上了。這個代碼不到1000行，大概20%用來實現AI。在這篇文章中我會介紹這個AI如何工作，每一個部分做什么，它為什么能那樣工作起來。你可以直接通讀本文，或者去下載代碼，邊讀邊看代碼。雖然去看看其他文件中有什么AI依賴的類也可能有幫助，但是AI部分全都在AI.py文件中。

　　AI 部分總述

　　AI在做出決策前經過三個不同的步驟。首先，他找到所有規則允許的棋步（通常在開局時會有20-30種，隨后會降低到幾種）。其次，它生成一個棋步樹用來隨后決定最佳決策。雖然樹的大小隨深度指數增長，但是樹的深度可以是任意的。假設每次決策有平均20個可選的棋步，那深度為1對應20棋步，深度為2對應400棋步，深度為3對應8000棋步。最后，它遍歷這個樹，采取x步后結果最佳的那個棋步，x是我們選擇的樹的深度。后面的文章為了簡單起見，我會假設樹深為2。

?

　　生成棋步樹

　　棋步樹是這個AI的核心。構成這個樹的類是MoveNode.py文件中的MoveNode。他的初始化方法如下：

　　這個類有五個屬性。首先是move，即它包含的棋步，它是個Move類，在這不是很重要，只需要知道它是一個告訴一個起子往哪走的棋步，可以吃什么子，等等。然后是children，它也是個MoveNode類。第三個屬性是parent，所以通過它可以知道上一層有哪些MoveNode。pointAdvantage屬性是AI用來決定這一棋步是好是壞用的。depth屬性指明這一結點在第幾層，也就是說該節點上面有多少節點。生成棋步樹的代碼如下：

　　變量moveTree一開始是個空list，隨后它裝入MoveNode類的實例。第一個循環后，它只是一個擁有沒有父結點、子結點的MoveNode的數組，也就是一些根節點。第二個循環遍歷moveTree，用populateNodeChildren函數給每個節點添加子節點：

　　這個函數是遞歸的，并且它有點難用圖像表達出來。一開始給它傳遞了個MoveNode對象。這個MoveNode對象會有為1的深度，因為它沒有父節點。我們還是假設這個AI被設定為深度為2。因此率先傳給這個函數的結點會跳過第一個if語句。

　　然后，決定出所有規則允許的棋步。不過這在這篇文章討論的范圍之外，如果你想看的話代碼都在Github上。下一個if語句檢查是否有符合規則的棋步。如果一個都沒有，要么被將死了，要么和棋了。如果是被將死了，由于沒有其他可以走的棋步，把node.move.checkmate屬性設為True并return。和棋也是相似的，不過由于哪一方都沒有優勢，我們把node.pointAdvantage設為0。

　　如果不是將死或者和棋，那么legalMoves變量中的所有棋步都被加入當前結點的子節點中作為MoveNode，然后函數被調用來給這些子節點添加他們自己的MoveNode。