又是本人乙份人工智慧作業……首先道歉，從word貼到livewrter，好多格式沒了，也沒做**高亮……大家湊活著看……想做個好的人機對弈的五子棋，可以說需要考慮的問題還是很多的，我們將製作擁有強大ai五子棋的過程分為十四步，讓我來步步介紹。
第一步，了解禁手規則
做乙個五子棋的程式，自然對五子棋需要有足夠的了解，現在預設大家現在和我研究五子棋之前了解是一樣多的。以這個為基礎，介紹多數人不大熟悉的方面。五子棋的規則實際上有兩種：
有禁手和無禁手。由於無禁手的規則比較簡單，因此被更多人所接受。其實，對於專業下五子棋的人來說，有禁手才是規則。
所以，這裡先對「有禁手」進行一下簡單介紹：
五子棋中「先手必勝」已經得到了論證，類似「花月定式」和「浦月定式」，很多先手必勝下法雖然需要大量的記憶，但高手確能做到必勝。所以五子棋的規則進行了優化，得到了 「有禁手」五子棋。五子棋中，黑棋必然先行。
因此「有禁手」五子棋競技中對黑棋有以下「禁手」限制:「三三禁」:黑棋下子位置同時形成兩個以上的三；「四四禁」:
黑棋下子位置同時形成兩個以上的四；「長連禁」:六子以上的黑棋連成一線。黑棋如下出「禁手「則馬上輸掉棋局。
不過如果「連五」與「禁手」同時出現這時「禁手」是無效的。所以對於黑棋只有衝四活三（後面會有解釋）是無解局面。反觀白棋則多了一種獲勝方式，那就是逼迫黑棋必定要下在禁點。
為了迎合所有玩家，五子棋自然需要做出兩個版本，或者是可以進行禁手上的控制。
第二步，實現遊戲介面
這裡，我製作了乙個簡單的介面，但是，對於人機對弈來說，絕對夠用。和很多網上的精美介面相比，我的介面也許略顯粗糙，但，開發速度較高，僅用了不到半天時間。下面我們簡單看下介面的做法。
介面我採用了wpf，表現層和邏輯層完全分開，前台基本可以通過拖拽完成布局，這裡就不做過多介紹。根據介面截圖簡單介紹
窗體頂端
1處實際上市兩個漸變label的拼接，2、3是兩個label，4、5實際上是兩個button，但是沒有做事件響應。通過按鈕6、7、8、9 的控制，修改label和button的content屬性。也許有人會奇怪，為什麼button會絲毫看出不出有button的影子，這裡戰友whrxiao寫過乙個style如下
這裡我們把這個style稱為style1。介面邏輯上，將是否開始、是否禁手和是否電腦先行作為兩個全域性變數的布林型值，通過設定和判斷bool型值進行邏輯上的控制。中間的棋盤是個canvas，乙個15*15的grid放滿button並將每個button應用style1開始時候透明度設為0，也就是根本看不到，在下棋的時候改變button的背景和透明度，實現落子的效果，因為grid的位置關係，所以可看起來好像是下在橫豎的交線處。
第三步，進行輸贏判斷：
因為規則不同，「無禁手」和「有禁手」的輸贏判斷自然不同。先看無禁手：這個比較簡單，遍歷每個位置，然後從這個位置開始，分別判斷它的四個方向：
即橫、豎、左上到右下、左下到右上。每個方向從中間點開始，往兩邊數連子數，然後將兩個方向的連字數加和再加一（中間的棋子）。如果得到大於等於5，那麼就說明下子方贏棋。
對於有禁手的五子棋，輸贏判斷還需要判斷禁手，禁手的判定較為複雜。將待判斷點放入黑棋子。然後搜尋待判斷點周邊棋盤；還原棋盤；利用搜尋結果依次對各方向進行分析，判斷黑棋放入後所產生的棋型是否形成長連或形成某種四連或三連的的棋型。
若形成長連，判定為禁手，返回長連禁手標識。若形成某種四連或三連的棋型，該棋型統計數加1，再對下乙個方向進行判斷，直到各個方向分析結束。若四連棋型或三連棋型的統計數大於１，則返回為禁手。
其餘情況返回非禁手。
第四步：構造棋型估分
「有禁手」規則比較複雜，涉及到比較多下棋方面的技巧，而且對演算法的思路沒有絲毫影響，所以下面我們主要考慮無禁手規則下的ai設計。若設計好無禁手ai，只需要讓ai執黑時堅決不下到禁手點，就可以很快構造有禁手的ai。雖然這種方式沒有利用有禁手規則下的技巧，但這些技巧只需要修改下面所講到的估分函式即可。
我們可以將五子棋的連珠可以分為以下幾種：
成5：即構成五子連珠
活4：即構成兩邊均不被攔截的四子連珠。
死4：一邊被攔截的四子連珠
活3：兩邊均不被攔截的三字連珠
死3：一邊被攔截的三字連珠
活2：兩邊均不被攔截的二子連珠
死2：一邊被攔截的二子連珠
單子：四周無相連棋子
根據五子棋的技巧，可以將五子棋的棋型用連珠進行分類，分類過後我們按照威力給每種棋型打分。因為五子棋一次只落一子，因此很容易理解，雙活三和三活三的威力是一樣的，類似情況不多做解釋。程式中，我以100分為滿分，對棋型進行了以下打分：
成5, 100分
活4、雙死4、死4活3， 90分
雙活3， 80分
死3活3， 70分
死4， 60分
活3， 50分
雙活2， 40分
死3， 30分
活2， 20分
死2， 10分
單子 0分
有了估分方法，就有了五子棋ai的基礎，接下來就是一些博弈的方法了。
第五步：得到位置估分ai
單純應用棋譜以及對五子棋當前局勢的分析，對每步進行估分，程式中做如下工作：將每個位置進行分析，假設ai落子在該位置，用以上打分規則為ai打分,並將得到的分數加一。然後，假設玩家落子在該點，為玩家打分，然後將所有的分值彙總。
取最高分作為這個位置的估分，接下來就是取分數最高的位置下棋了。「位置估分」，下棋的時候，既可以考慮到自己攻擊對手，又能考慮到對對手的防禦，可以說，很多時候可以頂上考慮兩步的ai。作實驗，從網上**了乙個用博弈做的ai，和「位置估分」對下，結果是一勝一負。
誰先子，誰贏得勝利。而且一步估分毫無疑問是最快的，即使遍歷所有位置，也能很快的做出決策。
第六步：應用博弈樹，提高ai智慧型
做五子棋的博弈，自然會用到博弈樹，這裡我說下自己的思路。在對弈中,根據下一步由誰來走,ai對任何乙個局面根據前面估分方法給出乙個分數,我們把這個估分方法彙總成乙個評估函式，並返回分值。據此來選擇下一步的走法。
由於人和ai是輪流落子，可以將人的估分也算入，並將前面加負號。那麼，估值越大表明對ai越有利，估分越小則表明對ai越不利。那麼每次ai選擇都是從它可能的走法樹的某層節點，返回評估值中最大點。
而使用者總是從走法樹的某層節點中選擇最小點，從而形成一棵極大極小搜尋樹，然後根據深度優先搜尋，可以最後得到固定搜尋深度下的乙個最好的走法。我做了下試驗，單純應用博弈樹，可以在100ms之內讓ai考慮完整的兩步，由於組合**，當需要考慮三步的時候，就需要6s左右，4步就需要1分鐘。拿兩步來和一步估分作比較，雖然比較慢，但是確實有了一定智慧型。
第七步：考慮層數，提高ai智慧型
上面的設計對於返回值是統一處理的,但是，層數是個很重要的資訊.因為下棋時如果能2步獲勝,不應選擇4步獲勝。對於輸的棋型層數就更重要,ai必須盡可能拖延輸的時間，就有更大的可能讓ai化險為夷。
這樣，可以通過設定乙個dep值。深度約淺，dep越大，用dep和得到的得分相乘，得到搜尋節點的得分，再進行以上演算法，進一步提高ai的智慧型。
第八步：應用α-β剪枝，提高ai速度
在搜尋博弈樹的過程中，實際上搜尋有很多點是多餘的，例如下圖
圖中，方形框節點是該ai走,圓形框節點是該人走.比如c節點,它需要從e和f當中選取最大的值。目前已經得出e為2,當搜尋f節點時,因為f是人走的節點，那麼f需要從k l m中選取最小的，因為k已經是1，也就是說f<=1，那麼l，m就不需要搜尋，因此就發生了α剪枝。
然後看a節點，該人走了，需要從c和d中選取最小值，因為c節點是2，而g是7，那麼d至少是7。因此，d的其他節點不必再考慮，就發生如上圖所示的β剪枝。總結上面規律，我們可以得到剪枝方法如下：
當前為ai下棋節點：
α剪枝：如果當前節點的值不比父節點的前兄弟節點的大值大,則捨棄此節點。
β剪枝：如果當前節點子節點的值不比當前節點的前兄弟節點中的最小值小,則捨棄該子節點和該子節點的所有後兄弟節點。
當前為使用者下棋節點：
α剪枝：如果當前節點的某子節點的值不比當前節點的前兄弟節點中的最大值大,則捨棄該子節點和該子節點的所有後兄弟節點。
β剪枝：如果當前節點的子節點的值不比當前的父節點的前兄弟節點中的最小值小則捨棄此節點。
經過α-β剪枝，可以極大的減少搜尋的數量，很多時候，能把幾十億的搜尋數量，縮小到幾億，那麼，就可以把搜尋深度增1。
第九步：應用下棋範圍，提高ai速度
當前節點的子節點的數量和排列順序對於搜尋的速度起著至關重要的影響。根據五子棋的特點,可以產生乙個棋面搜尋範圍。記錄當前棋面所有棋子的最左最右最上最下點構成的矩形,我們認為下一步棋的位置不會脫離這個框3步以上。
這樣在棋子較少的時候，搜尋節點的數量大大減少。可以將ai的速度提高一倍左右。
第十步：利用棋型得分，提高ai速度
因為每種下法都對應一種得分，所以，可以每次只考慮當前得分前十的節點進行下一步搜尋，大大減少了搜尋範圍，可以進一步增加搜尋的深度。
第十一步：利用置換表，提高ai速度
我們一般用遞迴的方法實現博弈樹，但是，遞迴的效率是低的，而且很明顯，有很多重複搜尋的節點，所以，我們可以用乙個表，記錄下所有搜尋過節點的情況，然後只要遇到搜尋到的節點，就可以直接得到結果。置於這個「表」是什麼，就是乙個置換表，利用zobrist演算法，進行hash處理，使在表中查詢的時間大大縮短，這樣ai的速度又能提高乙個數量級。
第十二步：利用多執行緒，提高ai速度
我們其實可以利用多核技術，利用多個執行緒，讓演算法實現平行計算，提高ai的速度。我們在第一層用乙個執行緒分配器把第二層的候選節點分配給多個執行緒,每個執行緒包含著從第二層乙個候選節點開始的搜尋,然後等所有執行緒結束後,將所有執行緒的結果進行彙總,選出最大值。並行的程式，可以將速度提高一倍左右。
全校五子棋比賽策劃方案五子棋
全校五子棋比賽 閃耀青春，祝福濱海之第四屆五子棋 策劃 書社團名稱毅昕棋社 負責人柳志偉 2012年 10月25日 全校五子棋比賽策劃方案 活動名稱 閃耀青春，祝福濱海第四屆全校五子棋比賽 活動目的 1 為了迎接校園文化節和培養濱海學子的興趣愛好，豐富我們的校園文化生活，通過參加此次活動，從而延伸求...
五子棋技巧
五子棋是一種兩人對弈的純策略型棋類遊戲，是起源於中國古代的傳統黑白棋種之一。容易上手，老少皆宜，而且趣味橫生，引人入勝 不僅能增強思維能力，提高智力，而且富含哲理，有助於修身養性。安東是公認的世界上五子棋棋力最強的棋手，他有一套成熟的五子棋技巧理論，非常實用，本文就是這套五子棋技巧理論的 步驟 方法...
五子棋作文
最近，我一直都在學五子棋，終於，我覺得可以和外公下了！第一局 驕兵必敗 我勝券在握，搶先擺出了乙個三角形，心想 外公呀外公，這下您得跟著我團團轉了。一會兒，我的黑棋不斷下出 活三 拖四 我有些得意了，真是驕兵必敗呀！外公很快就擺出了 活三嵌四 啊！我當頭一棒。第二局 小心謹慎 我通過了剛才那局棋的教...