Python實現AI五子棋

公衆號：Charles的皮卡丘
做者：Charles算法

開發工具：
Python版本：3.6.4
相關模塊：
graphics模塊。函數

環境搭建：
安裝Python並添加到環境變量便可。工具

原理簡介：
對於五子棋這樣的博弈類AI，很天然的想法就是讓計算機把當前全部可能的狀況都嘗試一遍，找到最優的落子點。這裏有兩個問題：
（1）如何把全部可能的狀況都嘗試一遍；
（2）如何定量判斷某落子點的優劣。
對於第一個問題，其實就是所謂的博弈樹搜索，對於第二個問題，其實就是所謂的選擇評估函數。評估函數的選取直接決定了AI算法的優劣，其形式也變幻無窮。能夠說，每一個評估函數就是一個選手，對不一樣的棋型每一個選手天然有不一樣的見解和應對措施，固然他們的棋力也就所以各不相同了。
但博弈樹搜索就比較固定了，其核心思想無非是讓計算機考慮當前局勢下以後N步全部可能的狀況，其中奇數步（由於如今輪到AI下）要讓AI方的得分最大，偶數步要讓AI方的得分最小（由於對手也就是人類，也能夠選擇最優策略）。
固然這樣的搜索其計算量是極大的，這時候就須要剪枝來減小計算量。例以下圖：

其中A表明AI方，P表明人類方。AI方搜索最大值，人類方搜索最小值。所以Layer3的A1向下搜索的最終結果爲4，Layer3的A2向下搜索，先搜索Layer4的P3，得到的分值爲6，考慮到Layer2的P1向下搜索時取Layer3的A1和A2中的較小值，而Layer3的A2搜索完Layer4的P3時，其值就已經必大於Layer3的A1了，就沒有搜索下去的必要了，所以Layer3到Layer4的路徑3就能夠剪掉了。
上述搜索策略其實質就是：
minimax算法+alpha-beta剪枝算法。
瞭解了上述原理以後，就能夠本身寫代碼實現了。固然實際實現過程當中，我作了一些簡化，但萬變不離其宗，其核心思想都是同樣的。開發工具

視頻演示：
https://mp.weixin.qq.com/s/Y9...spa

源代碼：
關注公衆號：Charles的皮卡丘，回覆「AI五子棋」獲取。
視頻