如何使用Python編寫一個(gè)國(guó)際象棋AI程序

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

　　AI 部分總述

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

?

　　生成棋步樹

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

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

　　變量moveTree一開始是個(gè)空l(shuí)ist，隨后它裝入MoveNode類的實(shí)例。第一個(gè)循環(huán)后，它只是一個(gè)擁有沒(méi)有父結(jié)點(diǎn)、子結(jié)點(diǎn)的MoveNode的數(shù)組，也就是一些根節(jié)點(diǎn)。第二個(gè)循環(huán)遍歷moveTree，用populateNodeChildren函數(shù)給每個(gè)節(jié)點(diǎn)添加子節(jié)點(diǎn)：

　　這個(gè)函數(shù)是遞歸的，并且它有點(diǎn)難用圖像表達(dá)出來(lái)。一開始給它傳遞了個(gè)MoveNode對(duì)象。這個(gè)MoveNode對(duì)象會(huì)有為1的深度，因?yàn)樗鼪](méi)有父節(jié)點(diǎn)。我們還是假設(shè)這個(gè)AI被設(shè)定為深度為2。因此率先傳給這個(gè)函數(shù)的結(jié)點(diǎn)會(huì)跳過(guò)第一個(gè)if語(yǔ)句。

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

　　如果不是將死或者和棋，那么legalMoves變量中的所有棋步都被加入當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)中作為MoveNode，然后函數(shù)被調(diào)用來(lái)給這些子節(jié)點(diǎn)添加他們自己的MoveNode。