http://www.cnblogs.com/zcsor/archive/2012/07/11/2586336.html
剛剛完善了評價函數，這真是一個痛苦的過程。當然，所謂完善是現階段的，因為它已經可以正常工作了，才稱之為完善。從今天開始進行這個連載，當第三部分（基石）發布之後，我會把以前發的兩篇刪除。
首先，我們來認識一下“引擎”。實際上，這是一種人工智能，在國際象棋等等一些“信息完畢”的遊戲中，早就實現了“計算機下棋的程序“，這些程序可以稱之為”引擎“。也就是說，我們的連載的目標是實現一個五子棋的AI。實際上，網絡上有很多這樣或那樣的”引擎“，但是我可以非常負責的告訴大家，用VB.NET寫的、國內的、各種棋類的幾乎沒有開源的，估計不開源的也極少，用其他語言寫的開源的，水平都不敢恭維，尤其是很多作者對傳統的剪裁根本就沒有理解或者理解是錯誤的。所以，寫了這篇連載，主要是為了讓用VB.NET並且有這方面興趣的童鞋能夠有一個參考，而我本身也是研究了”象棋小巫師“這一引擎的源碼之後，寫的這一系列的連載，其中非常多的東西都是參考其源碼甚至照搬來的。建議訪問http://www.xqbase.com/來學習相關知識。
國際象棋的引擎起源很早，所以它對各種”信息完備“的遊戲的引擎開發都具有非常重要的借鑒意義。中國象棋的引擎就是如此，而且現在已經有非常厲害的象棋引擎，象棋巫師本身的棋力也是很高的，當然，和象棋旋風等一些頂尖的象棋引擎相比，還有一些差距。那麼，什麼是”信息完備“的遊戲呢？通俗一點說，就是知道對方有什麼子！當然，對方也知道我們都有什麼子。說白了，就是明棋。例如，國際象棋，中國象棋，五子棋，黑白棋（奧賽羅），獸棋，井字棋等等，不勝枚舉；而像軍旗、各種翻棋等等就不屬於這個範疇了。
“信息完備”的遊戲，在開發引擎時，基本上都是使用剪裁的方式來進行搜索，我們搜索的越深，那麼棋力應該越強。就像人類棋手下棋時一樣，往往分析的步數越多，那麼他下的越好。有些觀點認為計算機下棋與人類棋手下棋思考方式有著根本性的差異，我本人不贊同這種觀點：無論是計算機，還是人類棋手，都是在搜索，並且是非常相似的。下面來解釋一下我的觀點：
1、實現界面和位棋盤
2、我的五子棋引擎如何評價局面
3、基石——超出邊界的alpha-beta剪裁
4、接近人類的思考方式——迭代加深、棋盤剪裁、空招剪裁、衝棋延伸
5、重點問題重點分析——靜態搜索
6、記住曾經的思考——置換錶
這是我們的五子棋引擎中使用的各種技術，這些技術都是為了提高搜索速度、準確度而服務的。除了位棋盤和思考方式無關之外，其他的都是與思考方式有關的：
2、我的五子棋引擎如何評價局面
評價局面，無論是計算機還是人類，都必須要做的，這是最根本的東西，它體現了這種棋類游戲的“規則”。在我的五子棋引擎中評價函數是一個比較長的函數：
首先，對棋型進行模板匹配——因為人類棋手也是要識別哪些棋型勝利，哪些棋型失敗，哪些棋型發展潛力比較大，哪些棋型要衝，哪些要堵
然後，綜合考慮各個棋型——當對方衝4，我們怎麼辦？當對方活4，我們是不是成5，如果不成，那很遺憾，我們輸了，這也意味著對方活4之前我們走的那步棋（甚至前幾步）是臭棋。這樣，我們就可以給一步棋打分，當然，計算機是用確實的分數來體現的，而人類棋手是以“分數”排序來體現的。可無論如何，我們的程序還是會把走法按分值排序，因為這有利於剪裁，而剪裁越合理（理想狀況下剪裁掉全部不合理走法，剩下的合理走法會很少），那麼下一步要搜索的走法就越少，可以節省更多的時間來搜索更多的步數。
程序的思考和人類棋手的思考驚人的一致。
3、基石——超出邊界的alpha-beta剪裁
人類棋手會首先找到幾種可能的走法，然後再繼續分析，如果我這樣走，對方怎麼走呢？如果對方這樣走，那麼我怎麼走呢？當發現一步棋演變若干次之後，對自己不利，那人類棋手就會捨棄這種走法。這就是剪裁。
程序的做法，和人類棋手是完全一樣的。
4、接近人類的思考方式——迭代加深、棋盤剪裁、空招剪裁、衝棋延伸
人類棋手首先會考慮當前局面下，自己認為最好的走法（對其進行深入思考），然後考慮其他走法是否好過前面的走法
程序也是這樣，搜索1層，進行排序，然後從最好招法進行深入搜索
人類棋手下棋時，不會考慮離棋子很遠的位置，例如棋都集中在中間時往角上下一個子明顯是不明智的，尤其是五子棋這種“咬得很緊”的棋類，那樣做明顯是在自殺。
我的程序在生成全部走法時，從位棋盤生成一個“合理棋盤”，它包含了所有棋子周圍的3格。
人類棋手經常會考慮，對方下一步會走什麼棋更有利？
程序在評價每一步棋時，會在搜索之前，進行“空步剪裁”，以期知道對方的“好棋”，並且評價這個“好棋”是不是會給自己造成致命的結果，從而提出應對策略。
人類棋手下棋時，會首先考慮對方是不是已經要殺死自己了？例如，對方有一個活3，那很明顯，人類棋手立刻立馬上馬意識到去堵或者衝比對方更快達到5的棋，為什麼，因為他知道自己如果沒有更好的棋再不堵上對方那就輸了！
程序也是這樣，當被沖的時候，就分析自己是不是比對方衝的更接近5，如何封堵對方的棋？當然，這裡可能涉及到自己衝棋是否能同時解決對方的成棋並獲得更有利局面。但如論無核這都是更深層搜索所要解決的問題，也就是“衝棋延伸”——針對沖棋的情況，進行更深入的搜索，深入程度甚至有可能達到把棋盤下滿！
5、重點問題重點分析——靜態搜索
人類棋手在預測若干步之後，確認某一步棋更好，如果是高手還會想一想，這步好棋若干步之後，對方還有沒有什麼招數呢，自己能不能產生殺招？也就是檢查一下自己的思考是否有什麼漏洞，對這步棋進行更深入的考慮，這往往是落子之前最後一道工序了。
程序也是這樣，當進行alpha-beta剪裁得到一個滿意的結果之後，會進入靜態搜索，以期驗證若干步之後，對方確實不會出現翻盤的情況，而自己盡可能給對方造成更多的麻煩，甚至殺死對方。
6、記住曾經的思考——置換錶
人類棋手是有記憶的，這包括剛才他分析過的各種可能，也包括以往積累下類各種經驗（例如什麼棋型必勝，如何走必勝）。
程序也可以這樣做：
短期記憶：把分析過的局面記錄下來，那麼當”這種局面剛才我已經分析了！“的時候，可以不必再次分析，而直接取出分析結果。
以往經驗：使用開局庫，殘局庫等技術來實現。
--------------------------------------------------------------------------------
先把這一個傳上來，關於局面評價的72向量和綜合比較、超出邊界的alpha-beta剪裁如何說明更清楚還得再考慮一下，以免表述的不清楚。因為這兩部分的代碼是整個代碼中最核心最重要也是最長的。僅僅是下一集更新的源碼就超過600行。當然了，邏輯是非常非常清晰的，因為很多都是重複的邏輯內容——硬編碼模板就這樣哎。而超出邊界的alpha-beta剪裁，是整個程序中最難理解的部分，說難理解不僅是因為遞歸，更重要的是這種剪裁的思想。剩餘的各個部分都非常好理解，編碼也很少了。就像將軍延伸和空步剪裁也就十行八行的代碼就實現了。而靜態搜索只是照著alpha-beta剪裁代碼稍微一改而已。好了，不多說閒話。
注：從這一篇開始都會對實現的內容首先進行解釋，然後傳本集的完整源碼，源碼都是VB2010編寫的。
一、位棋盤
1、為什麼用位棋盤
按照通常我們的做法，可以用數組board(224)，數據類型可以是byte,integer等，但是我們浪費很多存儲空間，當然這還不是主要問題，主要問題是速度太慢。原因很簡單，尋址遠慢於從integer中取某一位。
2、如何實現位棋盤
我們需要一個225位的數據類型，這種長度的數據類型是沒有的，所以可以用integer數組來實現。幸好，VB.NET給我們提供了bitarray類，而這個類的內部實現實際上也是用integer數組的。但是問題也隨之而來：1位只能是0或者1，而我們要表示白棋、黑棋、空三種數據，怎麼辦？其實很好解決，可以用2字代表一個位置，或者使用2個bitarray。我的程序採取第二種辦法：
Private wBitArr As BitArray
Private bBitArr As BitArray
3、如何操作位棋盤
直接上代碼：
'位棋盘
Public Class mBitBoard
'用bitarray代替byte数组，提高读写速度。（bitarray内部实现是用integer数组，每一个元素是32字节，所以寻址速度要比用byte数组快很多）
'0=白方，1=黑方，2=空
Private wBitArr As BitArray
Private bBitArr As BitArray
'15*15的棋盘。
Sub New()
wBitArr = New BitArray(225)
bBitArr = New BitArray(225)
End Sub
'设置棋子
Sub [Set](index As Integer, value As Integer)
If value = 0 Then
wBitArr.Set(index, True)
ElseIf value = 1 Then
bBitArr.Set(index, True)
Else
bBitArr.Set(index, False)
wBitArr.Set(index, False)
End If
End Sub
'获取棋子
Function [Get](index As Integer) As Integer
If wBitArr.Get(index) Then Return 0
If bBitArr.Get(index) Then Return 1
Return 2
End Function
End Class
很清晰吧。這個類在後來進行了一些小的修改——增加了一個函數。當然這不是我們現在要討論的問題。好了，現在已經有了棋盤的表示方法，那麼我們來實現界面。其實界面簡單得不能再簡單了：
二、五子棋界面
1、搜索或者自己畫棋盤和棋子
2、獲取棋子偏移量、棋子大小、棋盤大小
3、根據mBitBoard實例繪製棋子
我實現的時候在窗體上面畫了一個panel，命名為pnlBoard。而後寫了這樣一個函數：
'繪製棋子
Private Sub pnlBoard_Paint(sender As System.Object, e As System.Windows.Forms.PaintEventArgs) Handles pnlBoard.Paint
e.Graphics.DrawImage(My.Resources._2064, Point.Empty)
For i As Integer = 0 To 224
If ucpcSquares.Get(i) = 1 Then e.Graphics.DrawImage(bb, New Point((i Mod 15) * cs.Height, (i \ 15) * cs.Height) + co)
If ucpcSquares.Get( i) = 0 Then e.Graphics.DrawImage(bw, New Point((i Mod 15) * cs.Height, (i \ 15) * cs.Height) + co)
Next
End Sub
首先繪製棋盤圖像，然後繪製棋子。
下子的代碼是這樣的：
'下子
Private Sub pnlBoard_MouseDown(sender As Object, e As System.Windows.Forms.MouseEventArgs) Handles pnlBoard.MouseDown
Dim sdr = CType(sender, Panel)
'鼠標坐標轉棋盤坐標
Dim p As Point = e.Location - co
pX \= cs.Width
pY \= cs.Height
'下一個白子
If e.Button = Windows.Forms.MouseButtons.Left Then
ucpcSquares.Set(pY * 15 + pX, 0)
'更新顯示
pnlBoard_Paint(sdr, New PaintEventArgs( sdr.CreateGraphics, sdr.DisplayRectangle))
End If
End Sub
很簡單不是嗎。
Public Class Form1
'黑白棋子
Private bb As Bitmap
Private bw As Bitmap
'棋子偏移
Private co As Point = New Point(5, 5)
'棋子大小
Private cs As Size = New Size(25, 25)
'位棋盘
Private ucpcSquares As mBitBoard
Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
'初始化棋子
Dim resbmp As Bitmap = New Bitmap(My.Resources._7041, cs.Width * 4, cs.Height)
Dim allbmp As Bitmap = New Bitmap(resbmp.Width \ 2, resbmp.Height)
'获取棋子图像
For y As Integer = 0 To allbmp.Height - 1
For x As Integer = 0 To allbmp.Width - 1
If resbmp.GetPixel(x + allbmp.Width, y).ToArgb = Color.Black.ToArgb Then allbmp.SetPixel(x, y, resbmp.GetPixel(x, y))
Next
Next
bb = allbmp.Clone(New Rectangle(0, 0, allbmp.Width / 2, allbmp.Height), allbmp.PixelFormat)
bw = allbmp.Clone(New Rectangle(allbmp.Width / 2, 0, allbmp.Width / 2, allbmp.Height), allbmp.PixelFormat)
'==========================开局棋型可在这里设置==============================
ucpcSquares = New mBitBoard()
ucpcSquares.Set(7 * 15 + 7, 1)
End Sub
'绘制棋子
Private Sub pnlBoard_Paint(sender As System.Object, e As System.Windows.Forms.PaintEventArgs) Handles pnlBoard.Paint
e.Graphics.DrawImage(My.Resources._2064, Point.Empty)
For i As Integer = 0 To 224
If ucpcSquares.Get(i) = 1 Then e.Graphics.DrawImage(bb, New Point((i Mod 15) * cs.Height, (i \ 15) * cs.Height) + co)
If ucpcSquares.Get(i) = 0 Then e.Graphics.DrawImage(bw, New Point((i Mod 15) * cs.Height, (i \ 15) * cs.Height) + co)
Next
End Sub
'下子
Private Sub pnlBoard_MouseDown(sender As Object, e As System.Windows.Forms.MouseEventArgs) Handles pnlBoard.MouseDown
Dim sdr = CType(sender, Panel)
'鼠标坐标转棋盘坐标
Dim p As Point = e.Location - co
p.X \= cs.Width
p.Y \= cs.Height
'下一个白子
If e.Button = Windows.Forms.MouseButtons.Left Then
ucpcSquares.Set(p.Y * 15 + p.X, 0)
'更新显示
pnlBoard_Paint(sdr, New PaintEventArgs(sdr.CreateGraphics, sdr.DisplayRectangle))
End If
End Sub
End Class
--------------------------------------------------------------------------------
剛剛寫完了第4個程序，實現了迭代加深、空步剪裁、衝棋延伸。（棋盤剪裁已經在第3個程序裡面實現了）。本來準備寫第5個程序，不過有點累了，就沒有繼續寫。後面幾篇更新的速度會慢一些，主要是寫完之後我還需要仔細檢查一下，這樣一個程序尤其是偌大一個遞歸函數里面搞來搞去的，難免出現一些問題，尤其是手誤，邏輯怎麼看都沒問題，又處於遞歸當中很難調試查找。為了示例程序盡可能少的出現問題，我會進行一定量的測試，當然測試量不可能很大，我還沒有寫和其他程序下棋的接口，所以無法從大量對局中查找問題和評價程序的真實棋力。
引擎下棋的最基礎的東西，就是評價局面。這往往需要大量的對局和校正參數，而我沒有做這些工作，原因前面已經說過了。但是不代表我們無法粗略的設置一些分值，尤其是像五子棋這樣的程序，評分不是子力，而應該是從“形”“勢”角度出發，所以沒有固定的子力分值評價和位置分值評價。在我的程序中，是使用模板來進行棋型評價（這和我最初發布的文章當中有所不同，因為經過測試，發現那種方法不僅難於編碼和調試，而且速度並不比模板匹配快多少，所以綜合起來還是採用了模板評價）的，然後綜合這72個評價結果並與對方棋72個結果進行比較來得到分值。原文地址http://www.cnblogs.com/zcsor/例如，對方有一個衝4，而我們雙活3，我們理所應當的去封堵，但是我們能認為雙活3的棋力小於衝4嗎？當然不。所以我採用了上述的評價方式。具體實現是這樣的：
1、為什麼是72個？
72這個數，是五子棋上的“成棋向量”，只有72個方向能成5，而其他方向不夠長度……這麼說吧，橫向15，縱向15，左下右上21，左上右下21，一共72。
2、如何得到這72個向量？如何記錄它們？
得到這些向量很容易，可以硬編碼，也可以循環遍歷。我才用了循環遍歷的方式，因為為了速度更快，我需要記錄向量上的每個點，而不是計算它們。——當然，這裡我沒有進行測試，我感覺，一個14個元素的byte數組尋址速度不會很慢。
代碼就像這樣：
'求所有的向量
Dim x, y As Integer
'横向
For y = 0 To 14
all.Add(GetVector(0, y, 14, y, 1, 0))
Next
'纵向
For x = 0 To 14
all.Add(GetVector(x, 0, x, 14, 0, 1))
Next
'右上
For y = 4 To 14
all.Add(GetVector(0, y, y, 0, 1, -1))
Next
For x = 1 To 10
all.Add(GetVector(x, 14, 14, x, 1, -1))
Next
'左上
For x = 4 To 14
all.Add(GetVector(x, 14, 0, 14 - x, -1, -1))
Next
For y = 13 To 4 Step -1
all.Add(GetVector(14, y, 14 - y, 0, -1, -1))
Next
'分配到点记录表
Dim i As Integer
For x = 0 To 14
For y = 0 To 14
Dim ls As New List(Of mVector)
'遍历全部向量，将点所在的向量保存到ls。
For i = 0 To 71
If InLine(i, y * 15 + x) <> -1 Then ls.Add(all(i))
Next
'以点坐标为键，加入表中。
hs.Add(y * 15 + x, ls)
Next
Next
其中的hs是一個哈希表，為什麼需要這個表呢？因為我們需要知道一個點所在的全部向量，這樣我們放一個棋子或刪除一個棋子之後，就可以知道哪些向量需要更新評價值，而不是更新全部的向量評價，要知道模板匹配即使使用了內存比較API也非常慢，何況我們是從一個長度可能達到14的信息中遍歷若干個模板的位置。當然，現在的做法完全可以進一步優化，但是我準備在發完這些連載之後，再抽時間進行細緻的優化或許到時候能夠找到更有效更快速的方式。
3、得到向量之後，如何評價？
我們使用一個數組，來記錄當前向量上的全部子和空位，而後和模板數組進行比較，從而得到棋型信息。我們不會得到棋型的具體分值，最終綜合棋型才得到得分。
實際的評價函數，是一個非常長的函數：
'评价向量的当前情况
Sub Evaluate(ucpc As mBitBoard)
'向量点数组最大下标
Dim infend As Integer = ps.Length - 1
'循环变量
Dim i As Integer
'本方、对方在向量上的子分布信息
Dim inf1(infend) As Byte
Dim inf2(infend) As Byte
'循环访问向量上指向的棋盘点
For i = 0 To infend
If ucpc.Get(ps(i)) = 1 Then '黑子
inf1(i) = 1
inf2(i) = 2
ElseIf ucpc.Get(ps(i)) = 0 Then '白子
inf1(i) = 2
inf2(i) = 1
Else '无子
inf1(i) = 0
inf2(i) = 0
End If
Next
'白子棋型
linkInfs(1) = EvaluateShape(inf1, 0, infend)
'更新冲棋点坐标为棋盘坐标
For i = 0 To linkInfs(1).cqpend
linkInfs(1).cqp(i) = ps(linkInfs(1).cqp(i))
Next
'黑子棋型
linkInfs(0) = EvaluateShape(inf2, 0, infend)
For i = 0 To linkInfs(0).cqpend
linkInfs(0).cqp(i) = ps(linkInfs(0).cqp(i))
Next
End Sub
--------------------------------------------------------------------------------
'根据模板进行棋型获取（匹配最高连即返回）。
Private Shared Function EvaluateShape(inf As Byte(), infstart As Integer, infend As Integer) As LinkInfo
Dim count As Integer
Dim lnkinf As New LinkInfo
'长连
If CompareArray(inf, infstart, infend, mll1, count) Then
lnkinf.lnk = 60
Return lnkinf
End If
If CompareArray(inf, infstart, infend, mll2, count) Then
lnkinf.lnk = 60
Return lnkinf
End If
If CompareArray(inf, infstart, infend, mll3, count) Then
lnkinf.lnk = 60
Return lnkinf
End If
If CompareArray(inf, infstart, infend, mll4, count) Then
lnkinf.lnk = 60
Return lnkinf
End If
'成5
If CompareArray(inf, infstart, infend, ml5, count) Then
lnkinf.lnk = 50
Return lnkinf
End If
'活4
If CompareArray(inf, infstart, infend, ml42, count) Then
lnkinf.lnk = 42
'在这里记录的冲棋坐标是inf的下标，也是ps的下标，而不是实际棋盘坐标。
'虽然可以用循环来找到模板当中的0，但是比硬编码要慢很多。
lnkinf.cqp(0) = count
lnkinf.cqp(1) = count + 5
lnkinf.cqpend = 1
Return lnkinf
End If
4、得到向量的棋型評價和衝棋信息之後，是如何評價局面的？實際上，局面評價函數也是面目猙獰的……不過幸好線條很清晰：
首先，我們要遍歷每個向量，如果需要更新，那麼就運行向量的評價函數。
For j = 0 To 71
If all(j).update Then '若需要，则更新棋型评价。
all(j).Evaluate(ucpc) '更新函数同时更新黑白两色。
all(j).update = False
End If
然後，我們分別統計己方、對方的72向量上的長連、成5、活4、衝4、活3、衝3、活2，，，，停停停，後面的就沒有了！
'统计本方、对方的72向量上各种棋型的信息。
'本方
Select Case all(j).linkInfs(player).lnk
Case 60 '长连
l60_1.Add(all(j).linkInfs(player))
Case 50 '成5
l50_1.Add(all(j).linkInfs(player))
Case 42 '活4
l42_1.Add(all(j).linkInfs(player))
Case 41 '冲4
l41_1.Add(all(j).linkInfs(player))
Case 32 '活3
l32_1.Add(all(j).linkInfs(player))
Case 31 '冲3
l31_1.Add(all(j).linkInfs(player))
Case 22 '活2
l22_1.Add(all(j).linkInfs(player))
End Select
--------------------------------------------------------------------------------
最後，我們根據不同的情況，給出不同的得分，例如死棋——對方死棋，那麼判斷對方是否禁手，如果禁手並且走了禁手那我們勝利了（好像是撿的）……如果我們稱5，那我們理所當然的勝利了（當然如果是對方沒看見我們偷偷的下上的，也撿到了……但是這種情況是幻覺…………）。當然還有很多情況，我們需要一一評價。總體來說，衝棋部分處理起來代碼最多，但是卻得到了額外的好處——可以直接生成衝棋點，也就是說不用生成全部招法，而得到非常準確的招法點。
'====================================死棋棋型（长连、禁手、成5）======================================
'1、被杀死
'1.1、对方成5
If l50_2.Count > 0 Then Return -10000
'1.2、对方不禁手
If RestrictedMove <> 1 - player Then
If l60_2.Count > 0 Then Return -10000
End If
'1.3、被禁手
If RestrictedMove = player Then
If l60_1.Count > 0 AndAlso l50_1.Count = 0 Then Return -10000 '长连，但是同时成5不为禁手。
If l32_1.Count > 1 Then Return -10000 '双活三禁手
If l42_1.Count > 1 Then Return -10000 '双活四禁手
If l41_1.Count > 1 Then Return -10000 '双冲四禁手
End If
--------------------------------------------------------------------------------
注：今天更新了評價方法，主要是增加了一組變量來記錄每個向量上有多少個黑子或白子，從而選擇性的使用相應模板來進行匹配，這導致pos類也有更改。另外，向量評價代碼中發現一處錯誤，導致黑白混淆；界面代碼中忘記使用addpipe來添子，已經修正，但是哎pcgo函數那裡忘記改了，不重新上傳了。源碼已經重新上傳。現在基本可以穩定在迭代加深4、5，不會出現假死的情況了。因為修正評價的問題而置換錶代碼還存在一些問題（主要是測試使用數組快還是哈希表快的問題），所以沒有完成。估計明天或後天會完成這部分代碼。然後進行評價函數的優化，準備採取“查表”的方法來進行向量評分而不是匹配。當然，現在優化過的評價函數使用性能評價工具進行評價時已經不會突出佔用處理時間了（佔用處理時間最突出的應該是pcgo函數——alpha-beta剪裁函數，測試結果也是如此）。
首先說明一下，源碼很多都是藉鑑於開源象棋軟件的源碼，主要參考了象棋小巫師網站上提供的一些下載地址上的開源軟件源碼。框架基本相同，所以沒有什麼新意。在此首先感謝各位前輩無私的貢獻！後面的一些技術實現代碼中會有一些不同甚至很大差別，但是基本框架都是完全一樣的。
剛剛完善了置換錶也就是第六個程序，但是程序被我刪了，因為有些東西寫得還是很亂，看起來不清晰，後面再重寫。從置換錶的測試結果來看，我們的評價函數確實存在很大的問題，需要一個更快，而且是快非常多的局面評價函數！一般來說，迭代加深達到7就能比較令人滿意，當然6也勉強可以。但是我最後的測試結果還是4，甚至是3,2。雖然程序中進行了衝棋延伸，但是這可以讓置換錶更豐富，雖然也用了靜態評價，但不使用靜態評價時，速度也不怎麼樣，雖然用了空步剪裁，但棋力的提升相對於它的耗時要重要得多，所以，速度慢全部要“歸功於”我們的評價函數了。不過我還是決定用現在的評價函數把整個連載寫完。也許在第六集之後，解決這個令人惱怒的問題。那麼，我們還是繼續討論如何讓程序會走棋吧，這將是非常令人興奮的時刻！
1、怎麼讓程序動起來？
程序是基於得分高低，來判斷走哪步棋的。換句話說，我們評價走哪步時，總是考慮假如走這裡會怎麼樣，假如走那裡會怎麼樣，程序也是如此。只是實現起來沒有那麼簡單。
2、alpha-beta剪裁是如何達到目的的？
這基於一個思想，如果局面評價是基於得分的，那麼輪到誰走誰都要把這個得分弄得更高，程序如此，程序猜想對手走棋也是如此。所以，局面評價函數如果是：己方得分-對方得分，那麼，這個分值越正，說明我們越接近勝利了，而這個分值越負，說明我們越接近輸棋了。於是，我們總是尋找得分更高的走法，而得分低於一定程度（如對方成5）的走法，被剪裁（所謂剪裁掉，在程序中體現出來就是不繼續掃描——exit for） 。
3、如何實現這個遞歸函數？
設計遞歸的方式不止一種，但無疑都是要實現自己的目的。我們的目的是找到得分更高的走法，這裡有這樣幾個關鍵點：
A、評價得分並比較
B、最高得分點需要記錄
C、要交替查找可以走的點走棋
很明顯，遞歸語句就在遍歷點的循環中；最高得分的點可以用全局變量記錄。接下來討論一下評價函數放在哪裡的問題：
無非是遞歸前或遞歸後，我們要的不是無限遞歸——那是一個可不完成的工作（玩家會等的花兒也謝了，或許花兒謝了之前他氣憤的關閉了程序甚至計算機），所以遞歸要有深度。當遞歸達我們要求的深度遞歸深度之後，評價結果這是很好的做法。實際上，alpha-beta剪裁把每下一個子都評價這件事情交給了”迭代加深“，換句話說，我們把每一步都評價這件事情，分離出去，形成了”迭代加深“。這樣做的好處是明顯的，回想一下，alpha-beta剪裁是怎樣一個循環？它遍歷樹的過程是前序遍歷，所以在他完成之前，我們無法對每一層的走法進行排序來獲取這層中的最佳走法，而迭代加深解決了一個很重要的問題：它讓alpha-beta剪裁先運行1層，然後1、2層，讓後1、2、3層……當然你可能認為這多浪費時間啊，實際上，相對遍歷第N層前面N-1層的耗時都是毛線，更何況我們還有”置換錶“。這意味著，我們可以更好的對上一次的搜索進行排序從而更容易發生截斷，並且當我們達到規定時間時，完全可以不搜索完當前層而返回現在得到的最好結果，因為這個結果不會比上一層的最好結果壞——也許是一樣好、更好，但不會更壞。當然，迭代加深和置換錶是後話了。好了，那麼我們的結論是，alpha-beta剪裁長得就是這麼蹩腳：
'傳入alpha值、beta值、深度。
function alpha-beta (vlAlpha As Integer, vlBeta As Integer, nDepth As Integer) As Integer
'達到深度返回評價
if nDepth<=0 then return Evaluate
'獲取全部合理招法
GenerateMoves
'遍歷招法
For i = 1 To 招法個數
pos.AddPiece(mvs(i)) '添子
vl = -SearchFull(-vlBeta, -vlAlpha, nDepth - 1) '遞歸。這一句後面都是出棧了，開始統計吧。
pos.DelPiece(mvs(i)) '刪子
記錄更大的alpha並記錄相應的走法，進行beta截斷。
next
返回得分
end function
這就是整個alpha-beta遞歸函數的框架了。
那麼，我們整個的alpha-beta函數，看起來會非常眼熟：
'超出边界(Fail-Soft)的Alpha-Beta搜索过程。这个过程返回值是一个分值，而最佳走法被记录到一个全局变量（pos.mvResult）。
Public Function SearchFull(vlAlpha As Integer, vlBeta As Integer, nDepth As Integer) As Integer
'循环变量，走法数组最大下标（走法个数-1）
Dim i, nGenMoves As Integer
'分值，最高分值，最佳走法
Dim vl, vlBest, mvBest As Integer
'生成的全部走法（定长，具体有多少个走法由nGenMoves决定）
Dim mvs(MAX_GEN_MOVES) As Byte
'一个Alpha-Beta完全搜索分为以下几个阶段
'1. 到达水平线，则返回局面评价值
If nDepth = 0 Then
Return pos.Evaluate()
End If
'2. 初始化最佳值和最佳走法
vlBest = -MATE_VALUE '这样可以知道，是否一个走法都没走过(杀棋)
mvBest = 0 '这样可以知道，是否搜索到了Beta走法或PV走法，以便保存到历史表
'3. 生成全部走法，并根据历史表排序
nGenMoves = pos.GenerateMoves(mvs)
Array.Sort(mvs, 0, nGenMoves, mCompare)
'4. 逐一走这些走法，并进行递归
For i = 0 To nGenMoves
pos.AddPiece(mvs(i))
vl = -SearchFull(-vlBeta, -vlAlpha, nDepth - 1)
pos.DelPiece(mvs(i))
' 5. 进行Alpha-Beta大小判断和截断
If (vl > vlBest) Then '找到最佳值(但不能确定是Alpha、PV还是Beta走法)
vlBest = vl '"vlBest"就是目前要返回的最佳值，可能超出Alpha-Beta边界
If (vl >= vlBeta) Then '找到一个Beta走法
mvBest = mvs(i) 'Beta走法要保存到历史表
Exit For 'Beta截断
End If
If (vl > vlAlpha) Then '找到一个PV走法
mvBest = mvs(i) 'PV走法要保存到历史表
vlAlpha = vl '缩小Alpha-Beta边界
End If
End If
Next
'5. 所有走法都搜索完了，把最佳走法(不能是Alpha走法)保存到历史表，返回最佳值
If vlBest = -MATE_VALUE Then
'如果是杀棋，就根据杀棋步数给出评价
Return pos.nDistance - MATE_VALUE
End If
If mvBest <> 0 Then
'如果不是Alpha走法，就将最佳走法保存到历史表
pos.nHistoryTable(mvBest) += nDepth ^ 2
If pos.nDistance = 0 Then
'搜索根节点时，总是有一个最佳走法(因为全窗口搜索不会超出边界)，将这个走法保存下来
pos.mvResult = mvBest
End If
End If
'返回最高分
Return vlBest
End Function
這裡面有一個非常有必要解釋的問題，就是歷史表。都知道它是用來排序的，經過歷史表排序能更快地截斷，事實也是這樣，如果註釋掉這句：
pos.nHistoryTable(mvBest) += nDepth ^ 2
那麼示例代碼中的深度3，也會非常耗時，慘不忍睹……所以來解釋一下歷史表是如何發揮作用的：
看看歷史表的結構：
public nHistoryTable(224) as integer
那也就是說，nvBest是最佳走法坐標，那麼每個元素的值就是這個坐標過去搜索時，如果是一個最佳走法，那麼他的分值就比較高。這個分值怎麼對排序起到作用的呢？讓我們看看排序器：
'根据历史走法对合理招法进行排序的排序器。
Class mvsCompare
Implements IComparer
'这个数组是给走法排序的依据，是历史表的引用。
Public Shared ms() As Integer
Public Function Compare(x As Object, y As Object) As Integer Implements System.Collections.IComparer.Compare
Return ms(y) - ms(x)
End Function
End Class
其中的ms數組就是歷史表的引用。我把它直接傳過去了。這樣，結論就非常明顯了：
歷史表中第最佳走法個元素的分值越高，那麼以後生成的走法進行排序後越靠前。也就是說，以後搜索時，這個走這個位置的招法被更先搜索。先到什麼程度呢，那就與深度有關（確切的說是深度平方的累計），越深層得到的最佳招法，越被先搜索。
其中涉及到的pos類，無非就是一些輔助的函數：
Public Class mPosition
'72成棋向量
Public Vectors As New mVectors
'轮到谁走，0=红方，1=黑方
Public sdPlayer As Integer
'棋盘上的棋子，0=红方，1=黑方，2=无子
Public ucpcSquares As mBitBoard
'距离根节点的步数
Public nDistance As Integer
'禁手玩家
Public RtPlayer As Integer = 2
'电脑走的棋
Public mvResult As Integer
'历史表
Public nHistoryTable(224) As Integer
'初始化棋盘类
Sub New()
ucpcSquares = New mBitBoard()
End Sub
'清空历史表
Public Sub ClearnHistoryTable()
mvResult = 0
Array.Clear(nHistoryTable, 0, 225)
End Sub
'交换走棋者
Sub ChangeSide()
sdPlayer = 1 - sdPlayer
End Sub
'在棋盘上放一枚棋子
Sub AddPiece(sq As Integer)
'更新棋盘
ucpcSquares.Set(sq, sdPlayer)
'更新更新标志和向量上棋子个数
For Each v As mVector In Vectors.hs(sq)
v.pipecount(ucpcSquares.Get(sq)) += 1
v.update = True
Next
'交换走棋方
ChangeSide()
'更新步数
nDistance += 1
End Sub
'从棋盘上拿走一枚棋子
Sub DelPiece(sq As Integer)
For Each v As mVector In Vectors.hs(sq)
v.pipecount(ucpcSquares.Get(sq)) -= 1
v.update = True
Next
ucpcSquares.Set(sq, 2)
ChangeSide()
nDistance -= 1
End Sub
'局面评价函数
Function Evaluate() As Integer
Return Vectors.Evaluate(ucpcSquares, sdPlayer, RtPlayer)
End Function
Sub Startup() '初始化棋盘
sdPlayer = 1
nDistance = 0
For i As Integer = 0 To 224 '没有使用bitarray的setall函数。
ucpcSquares.Set(i, 2)
Next
End Sub
'mvs为全部合理招法
Function GenerateMoves(mvs() As Byte) As Integer '生成所有走法
Dim GenBoard = ucpcSquares.GetGeneratePoints
Dim i As Integer = 0, nGenMoves As Integer = 0
For i = 0 To 224
If GenBoard(i) Then
mvs(nGenMoves) = i
nGenMoves += 1
End If
Next
Return nGenMoves - 1
End Function
End Class
--------------------------------------------------------------------------------
注：PCGO函數扔未修正添子方法。請自行修改。
一、迭代加深
1、什麼是迭代加深
所謂迭代加深，就是讓alpha-beta剪裁運行深度1，然後運行深度1,2，然後運行深度1,2,3。
2、為什麼進行迭代加深
這樣做的好處就是可以在搜索完一次之後，得到排序的依據——歷史表，然後下次搜索時，歷史表會給出一個大約的方向——下哪一步更好，也就是更容易產生截斷了。
3、這樣做增加了多少開銷
實際上，單純考慮迭代加深，它可能會多運行一點時間，但是考慮到歷史表，也差不多抵消這些時間了。更何況，還有置換錶（我一直不太喜歡這個名字）。
4、如何實現迭代加深
想法很簡單，實際上代碼也很簡單，只需要實現一個循環，for i = 1 to n，i是要掃描的深度，在這個循環中調用alpha-beta剪裁即可。代碼就這麼幾行：
'===============================迭代加深===============================
'迭代加深搜索过程
Function SearchMain() As Integer
Dim i, t, vl As Integer
'初始化
pos.ClearnHistoryTable() ' 清空历史表
mvsCompare.ms = pos.nHistoryTable
t = My.Computer.Clock.TickCount ' 初始化定时器
pos.nDistance = 0 '初始步数
winplayr = 2 '胜利者
'迭代加深过程
For i = 1 To LIMIT_DEPTH_SearchFull - 1
Debug.Print("正在迭代：" & i)
vl = SearchFull(-MATE_VALUE, MATE_VALUE, i)
'搜索到杀棋，就终止搜索
If vl > WIN_VALUE Then '计算机胜利
winplayr = 1
Exit For
End If
If vl < -WIN_VALUE Then '玩家胜利
winplayr = 0
Exit For
End If
'超过一秒，就终止搜索
If My.Computer.Clock.TickCount - t > 1000 Then
Exit For
End If
Next
Debug.Print("迭代加深:" & i)
Return pos.mvResult
End Function
'==============================================================================
整個循環中，先清空歷史表（但是我感覺不應該同時置換錶，當然這是後話）；然後調用alpha-beta的遞歸函數就可以了。其他的判斷都很容易理解。
二、棋盤剪裁
1、為什麼剪裁棋盤
這可以大量剪裁掉不合理招法，在五子棋中，我們很容易遇見，如果下的子遠每個離黑子和白子，那一定是臭棋。那麼遠離程度是多少呢，可能是4，因為要成5，所以最遠只能離當前子4格，但是真的是這樣嗎？讓我們大膽的猜測：其實第四格也是臭棋！為什麼呢，中間有3個格的話，遠離程度也太大了，需要在該方向上再連續下3子才能連起來。而我們，有多大機會能這樣做呢？即使我們想，可我們成功的機會有多大呢？我想微乎其微——五子棋雙方的纏繞（指互相衝堵，當然好棋是衝並且堵著……）是非常嚴重的，所以，我們的結論是3而不是4。
2、如何實現
我的代碼中是先遍歷棋盤，找到黑子或白子，然後把他們周圍的非子點記錄下來。當然這存在一個重複記錄的問題，所以我是記錄在一個bitarray裡面，它的操作速度非常快，然後再次遍歷它取出合理點。當然，另一種想法也許更好——遍歷所有點，並記錄每個三格以內有子的空點。但遺憾的是我最初意識到的是第一種做法。
這個代碼在上一個示例裡面已經在使用了。這裡不再羅列。
三、空步剪裁
1、什麼是空步剪裁
就是輪到自己不下子卻不下，讓對方接著下。
2、為什麼進行空步剪裁
它基於這樣一種想法：如果己方不下，那對方會下哪？這對於五子棋來講，好處不僅僅是預測性的剪裁，更重要的是對方衝棋時，可以把衝棋點直接作為合理招法點：因為如果不去封堵，自己就要被殺死了！當然，在我的代碼中，由於評價函數還不完善（這裡主要指分數設置方面的不准確性），所以程序會去封堵對方的單個衝3或活2，這完全可以通過重新規劃分值解決。
3、如何限制的空步剪裁
首先，什麼時候進行空步剪裁。如果對方已經衝棋了（衝4，活3等）那麼再讓他走，無疑是不明智的。所以，只有對方不衝棋的時候，我們才進行空步剪裁。
其次，無限制的空步剪裁當然不是一個好辦法。從預測的角度來看，一步貌似有點少，兩步還可以，如果3步對方的衝2都成5了！所以，結論是2步。
4、如何實現
其實代碼很簡單，但是要建立在對alpha-beta剪裁已經充分理解的前提下。首先分析是否被沖棋，如果沒有，那麼空步剪裁；如果有，用衝棋點作為接下來迭代的”合理招法“。這就是思路。代碼也就不復雜了，當然需要注意的是，空步剪裁對”深度“的影響：
'====================================空步剪裁=====================================
If pos.nDistance > 0 Then
'1. 到达水平线
If nDepth <= 0 Then Return pos.Evaluate '
'1-1. 到达极限深度就返回局面评价
If pos.nDistance = LIMIT_DEPTH_SearchFull Then Return pos.Evaluate()
'1-2. 尝试空步裁剪(根节点的Beta值是"MATE_VALUE"，所以不可能发生空步裁剪)
If pos.Evaluate() = -3000 Then '被冲棋时，根据冲棋点返回值生成走法，而不是生成全部走法。
'遍历棋型信息，提取全部冲棋点。
For i = 0 To pos.Vectors.lnkinf.Count - 1
For j = 0 To pos.Vectors.lnkinf(i).cqpend
nGenMoves += 1
mvs(nGenMoves) = pos.Vectors.lnkinf(i).cqp(j)
Next
Next
Else '未被冲棋时进行空步剪裁
pos.NullMove()
vl = -SearchFull(-vlBeta, 1 - vlBeta, nDepth - NULL_DEPTH - 1)
pos.UnNullMove()
If (vl >= vlBeta) Then
Return vl
End If
End If
End If
'==================================空步剪裁结束===================================
接下來我們討論衝棋延伸
四、衝棋延伸
1、什麼是衝棋延伸
在對方衝棋時，我們無限制的進行迭代，直至分析出最終解。
2、為什麼進行沖棋延伸
當對沖棋時，往往會形成比較險的連沖棋，一步失誤全盤皆輸，所以我們需要分析到最終局面——確切知道到底走哪步棋才是明智的。當然，這非常耗時，但同時也為置換錶提供了非常多寶貴的局面。
3、如何實現衝棋延伸
基於我們的想法，我們無限延長迭代，使之達到最終解。但實際上，還是做了一些限制，我們沒有真正分析全部局面的時間。具體的限制就在上面的代碼中，”達到極限深度就返回局面評價“。而真正的衝棋延伸，實現起來很簡單：當被沖棋時，我們的迭代過程傳入的參數不是n-1，而是n，這樣深度不會減少到0，也就會繼續分析下去：
'=================================冲棋延伸================================
'vl = -SearchFull(-vlBeta, -vlAlpha, nDepth - 1)
'=========以上为被替换代码==========
vl = -SearchFull(-vlBeta, -vlAlpha, IIf(pos.Evaluate = -3000, nDepth, nDepth - 1))
'===============================冲棋延伸结束==============================
--------------------------------------------------------------------------------
仍然在寫置換錶，但是還存在一些問題，所以還會後延一段時間。不過已經可以明確的是，使用哈希表確實沒有數組速度快（較為理想的情況是用純粹的alpha-beta剪裁和空招剪裁——這也是我最初設計的想法，並沒有其他技術，迭代加深至少可以處理7次，多是8次，甚至可以達到10——但是，如果加入其他代碼，速度會降下來一些，也就是說，我們的評價函數還是太慢太慢，不過即使我們進行各種剪裁，五子棋的複雜度也還是很高，這也是一方面原因吧。），所以大部分代碼還是在藉鑑開源的象棋引擎。畢竟我的目標不是要寫一個多麼出色的五子棋引擎，而是把這些技術介紹給大家，並且用VB.NET代碼展示出來。好了，言歸正傳。
1、什麼是靜態搜索
它是一個在達到指定深度（迭代加深）之後，用來評價局面的函數，是局面評價的進一步延伸。它是一個不帶深度參數的、非常“武斷”的alpha-beta剪裁，它只評價對方衝棋或己方衝棋的情況。
2、為什麼要進行靜態搜索
防止我們搜索到若干步之後，找到的最佳招法是“昏招”，也就是進一步檢查一下招法的可靠度。
3、如何實現靜態搜索
仿照alpha-beta剪裁函數去寫就可以了，只是把條件稍加修改，使之只分析對方衝棋、己方衝棋：
'==================================静态搜索==================================
'静态(Quiescence)搜索过程，实际上和alpha-beta搜索非常相似，但是目标是不同的，ab搜索达到深度就退出了，不管下面发生什么，哪怕下一步可以形成杀棋。
'而静态搜索是ab搜索的延伸，它将处理这些的情况。
Private Function SearchQuiesc(vlAlpha As Integer, vlBeta As Integer) As Integer
Dim i, nGenMoves As Integer
nGenMoves = -1
Dim vl, vlBest As Integer
Dim mvs(MAX_GEN_MOVES) As Byte
' 一个静态搜索分为以下几个阶段
'1. 到达极限深度就返回局面评价
If pos.nDistance = LIMIT_DEPTH Then Return pos.Evaluate()
'2. 初始化最佳值
vlBest = -MATE_VALUE '这样可以知道，是否一个走法都没走过(杀棋)
'评价局面
vl = pos.Evaluate()
If vl = -3000 Then
'3. 如果被冲棋，则取全部冲棋点作为走法。
For i = 0 To pos.Vectors.lnkinf.Count - 1
For j = 0 To pos.Vectors.lnkinf(i).cqpend
nGenMoves += 1
mvs(nGenMoves) = pos.Vectors.lnkinf(i).cqp(j)
Next
Next
Else
'4.如果不被冲棋, 先做局面评价
If vl > vlBest Then
vlBest = vl
If vl >= vlBeta Then
Return vl
End If
If vl > vlAlpha Then
vlAlpha = vl
End If
End If
'5. 如果局面评价没有截断，生成冲棋走法，冲棋走法本身就是排序的无需再次排序。
If vl = 3000 Then '杀棋时无需进行评价，根本就没有走法，6的循环会被略过直接进入最后评价。
'实际上这几行和3中完全一样，可以提取出来，但是为了结构更清晰，还是单独列出了。
For i = 0 To pos.Vectors.lnkinf.Count - 1
For j = 0 To pos.Vectors.lnkinf(i).cqpend
nGenMoves += 1
mvs(nGenMoves) = pos.Vectors.lnkinf(i).cqp(j)
Next
Next
End If
End If
'6. 逐一走这些走法，并进行递归
For i = 0 To nGenMoves
pos.AddPiece(mvs(i))
vl = -SearchQuiesc(-vlBeta, -vlAlpha)
pos.DelPiece(mvs(i))
'7. 进行Alpha-Beta大小判断和截断
If vl > vlBest Then '找到最佳值(但不能确定是Alpha、PV还是Beta走法)
vlBest = vl '"vlBest"就是目前要返回的最佳值，可能超出Alpha-Beta边界
If vl >= vlBeta Then '找到一个Beta走法
Return vl 'Beta截断
End If
If vl > vlAlpha Then '找到一个PV走法
vlAlpha = vl '缩小Alpha-Beta边界
End If
End If
Next
'8. 所有走法都搜索完了，返回最佳值
Return IIf(vlBest = -MATE_VALUE, pos.nDistance - MATE_VALUE, vlBest)
End Function
'==================================静态搜索结束==================================
在像棋中，被“將軍”的情況和我們被“衝棋”非常類似。但是像棋被將軍往往要生成全部走法，因為吃掉對方將軍子，墊子，走將等都可以解決問題，但是，五子棋不是如此，五子棋考慮的是對方的衝棋點即可，或許也該考慮自己是不是比對方衝的更遠了。
好了，這一集就到這裡，關於置換錶這裡先提一下。置換錶這個名字確實不討人喜歡，因為它是一種“歷史表”，只是歷史表這個名詞早早被佔據了——它是記錄搜索過程中哪個點產生的招法可能更好以對後續搜索進行排序的。所以，置換錶也是一種歷史表，它記錄著搜索一定深度之後，得到的棋型的評分。這裡的深度指迭代加深深度，而棋型本身，就記錄著“步數”，因為形成相同局面所需的棋子個數是一樣的，但是無論先後。我們要考慮的是，什麼時候記錄局面的變換，當然這包括下子還包括提子，是不是要考慮空步剪裁呢？如何記錄，怎麼提取等一系列問題。好了就預告到這裡。
--------------------------------------------------------------------------------
這幾天更新了一些內容，在現在發布的程序當中存在若干處錯誤，都被修復了。其中包括模型評價、局面評價、置換錶提取等關鍵部分的錯誤。程序的基本框架沒有太大變化，增加了PV路徑記錄，從而可以得到除了最佳招法之外的走棋路線，修改了模板當中的衝棋點部分，準備實現VCn搜索、回溯搜索，但是由於思路上還有一點問題所以還沒有真正付諸實施。在修復錯誤並增加了幾條知識之後進行了一定的測試，現在和連珠妙手（fiver6、豬八戒級別）進行對戰測試，勝率大概在30%-40%，但是棋局下的比較少，數據可能不很準確。不過我不想和這些知名軟件做比較，只是為了給程序排查錯誤和增加一些知識，畢竟我本人的五子棋水平非常低。當實現VCn搜索和回溯搜索之後，會把根節點的搜索單獨列出，之後會發布一個版本，這個版本將會作為這一階段的最終版本，也可能以後就不更新了；當然，如果時間太少，可能暫時放棄VCn和回溯的開發，那麼會發布現在的這個版本。2012年8月1日。
今天更新這一版本的程序，主要做了以下修改：
1、將常量放在一個單獨類
2、用向量類代替棋盤類並更改記錄方式
3、新的評價方法
4、根據棋型生成key
5、下子時只更新被改變的向量
6、實現雙置換錶
7、使用：歷史表、alpha-beta剪裁、空步剪裁、衝棋延伸、主要變例搜索、迭代加深技術。不使用靜態搜索等技術。
8、統計相關信息，以便計算置換錶命中率、每秒搜索節點數、等等信息。
遺留問題：
1、棋型提取和評價函數。雖然找到了更優的棋型提取方法和評價函數，並且理論上速度可以達到與象棋引擎接近甚至更快的速度，但是代碼還沒寫。
2、更好的剪裁方式。雖然現有的剪裁方式已經不錯了，但是只要挖掘就還能找到更好的方法。就像代碼中的棋盤剪裁更新一樣。
接下來解釋一下置換錶和更新的這些部分的代碼，以便下載源程序後更快的看完它。
'============================以下更新前內容保留================ ==================
1、什麼是置換錶
它記錄了一個局面、局面評分等相關信息，用來在搜索過程中用來將評價得分這一系列的運算”置換“為查表得到結果。它的目標是減少運算量，提高速度。
2、置換錶都記錄什麼，如何處理
因為搜索時，很多情況下能遇到相同的局面已經搜索過的現象。所以，如果我們能記錄下一個局面、評分、類型、深度，那麼，當我們再遇到這個棋型時，只需要知道，若當前深度小於等於記錄深度，那麼就返回評價，當然還要看記錄的局面的節點類型，稍微處理一下。
3、如何實現置換錶
我們最好用一個數(key)來記錄一個局面，然後，根據這個數，就能找到評分、類型、深度等信息。怎麼看都是使用key-value的東西，但是我測試了一下，哈希表速度要比前輩們的方法慢很多。他們把這個key處理了一下：變成下標（key mod len)，那麼好吧，這樣做的速度被證實非常快。而這同時也涉及到一些問題，其中最嚴重的就是，如果我把長度設置的較小例如10，那麼它就無法起到記錄局面的作用了（因為它的內容不斷的被更新，而我們查找的時候根本找不到過去的局面），可多大行呢，這不好說，除非你設置的置換錶和你能夠經歷的局面相等，呵呵，整個硬盤作為虛擬內存都未必夠用，估計初始化置換錶就要很久很久……所以這個”適當“的值，很難說，我的做法是：設置一個盡量大的值，這可以減少重複提高效率，而前提是，初始化過程，不超過1秒。我的計算機可以初始化1<<24這麼多，而不會超過一秒。所以我就設置了這麼大一個置換錶。
那麼，思路已經很清晰了，你可以先去閱讀象棋小巫師的源代碼，看看他是如何實現置換錶的，當然，如果你感覺它的RC2改成VB.NET讓你頭疼，那麼建議你使用RC4，因為VB.NET已經提供了這種算法，你只需要稍微修改一下原來的代碼，因為RC4是一個64位的結果。但是需要注意的是，我們得到局面的dwkey沒有那麼麻煩，你只需要去修改mbitboard類，在set函數中對dwkey進行更新就可以了。因為局面的變化在這裡最容易記錄。
'==============================以上更新前內容保留============== ===================
好了，現在我們介紹一下新程序，當然，它還會被更新幾次。幸好今天我測試的時候感覺棋力還可以了，雖然還會出現明顯的失誤，但可以肯定的是，這些失誤是由於分值設置引起的，而沒有大量對局參考的情況下，這些數據很難做到較為準確。
1、更新的常量類
我把常量都放在一個類裡面，這樣修改時可以避免很多麻煩。這沒有什麼好介紹的，並且源碼中註釋非常明確。
2、模板類
這個類負責評價一個向量上是否存在這個模板。它有一些成員變量需要解釋一下：
' 模板長度
Public len As Integer
' 模板含有棋子數
Private pipecount As Integer
' 模板
Private infow As Integer
Private infob As Integer
' 模板返回值
Public value As Integer
' 適用於本模板的信息截斷
Private make As Integer
例如，在模板New mMod({0, 1, 1, 1, 1, 0}, 42)中，
模板長度：6，也就是說，這個模板將檢測向量中連續6位。
模板含有棋子數：4
infow和infob這是白棋和黑棋模板，它們被new函數根據傳入數組初始化。
value是模闆對應的棋型，也就是上面new函數中的42。
make是掩碼信息，它用於把向量的棋型當中無用的（前面）部分去掉。
new函數是這樣的：
Sub New(bs() As Byte, val As Integer)
len = bs.Length
pipecount = val \ 10
value = val
For i = 0 To bs.Length - 1
infow = infow << 2
infob = infob << 2
If bs(i) = 1 Then
infow = infow Or CInt(1)
infob = infob Or CInt(2)
End If
make = make Or (CInt(1) << (i * 2)) '遮蔽，把模板中用到的位都置1。所以只需要对信息进行AND操作，就可以去掉信息中无用部分。
make = make Or (CInt(1) << (i * 2 + 1))
Next
End Sub
其中pipecount的初始化時根據val這可能要解釋一下，因為在程序中定義：長連為60，連5為50，活4為42，衝4為41……所以，分值整除10就是含有的棋子個數。
在循環中，分別記錄黑棋和白棋的模板，因為如果記錄到同一模板，那麼判斷黑棋時非常麻煩！並不是>>1就能解決的問題（會遺漏白棋，使得判斷結果不准確）。
New mMod({0, 1, 1, 1, 1, 0}, 42) 這個模板的二進製表示看起來是這樣的：
infow=00 01 01 01 01 00
infob=00 10 10 10 10 00
make=11 11 11 11 11 11
可以看出，白棋和黑棋他們分別佔據每2位中的後一位和前一位，而在向量中記錄棋型時，也是這樣：
info = info Or (CInt(1) << ((table(point) * 2 + player) Mod &H20))
好了，這些代碼我們不做更多的解釋，在vector類中再詳細說明。現在我們只需要知道，在向量和模板中，我們從最右面開始用連續2位記錄棋盤上的一個位置，其中後一位為白棋，前一位為黑棋，若沒有棋子則這兩位均為0，但絕不可能出現兩位都為1的情況。
於是，我們的比較函數簡單了一些——我們進行了“塊”比較，但這不是完整的塊，只是integer的比較速度要快於byte()的比較速度，所以比較函數速度比原來快。後來我想到了不用遍歷整個向量信息的方法，而且不是比較整個30位（可以想像，比較全部30位將有多少模板……那是難以完成的工作），當然這是以後我們要討論的。所以，現在的比較函數還存在for循環：
inf0 = vector.info >> (i * 2) '逐两位进行比较
inf0 = inf0 And make '将无用信息去掉
If inf0 = infow Then '符合模板
vector.value(0) = value '记录模板值
vector.update(0) = False '已符合，无需继续扫描
End If
首先，使用位移運算從向量信息取出一部分，然後用and運算把信息中前面的多餘部分去掉，直接和模板比較數值是否相等就可以了。當然，如果相同，我們還需要更新一下向量的相關值和更新標誌。
3、模板管理類
這個類負責初始化全部模板，並且，負責比較一個向量符合哪一個模板，它的初始化函數非常簡單，我們只介紹一下評價函數：
Public Shared Sub Evaluate(ByRef vector As mVector)
If vector.info <> 0 Then
Dim i, ilen As Integer
For i = 0 To AllMod.Length - 1
ilen = AllMod(i).len
If vector.len >= ilen Then '若向量长度不小于模板长度
AllMod(i).CompareMod(vector)
If vector.update(0) = False AndAlso vector.update(1) = False Then
Return
End If
End If
Next
End If
If vector.update(0) Then
vector.value(0) = 0
vector.update(0) = False
End If
If vector.update(1) Then
vector.value(1) = 0
vector.update(1) = False
End If
End Sub
在這段代碼中我們統一評價白棋和黑棋：
首先我們檢查向量是否為空，若為空，則設置值為0並且更新標誌為空；
而後，比較向量長度和模板長度，得出相應的評價；
應該注意的是，vector.update(0) = False AndAlso vector.update(1)這一條件，僅有這個條件是不夠的，因為我們的模板不是全部情況都概括了，所以，當評價混合棋型時、棋型變為空時，可能不會更新某些向量的棋型標誌和更新標誌，這是非常嚴重的。
4、向量類
'是否需要更新
Public update(1) As Boolean
'转换表
Private table(224) As Byte
'向量上的棋型
Public info As Integer
'向量长度
Public len As Integer
'向量上白棋、黑棋的个数
Public pipecount(1) As Byte
'向量上白棋、黑棋的棋型
Public value(1) As Byte
'向量方向
Private Direction As Integer
'坐标表
Public points() As Byte
Sub New(ps As Byte(), dir As Integer)
points = ps
Direction = dir
len = ps.Length
For i = 0 To ps.Length - 1
table(ps(i)) = i '转换表的下标对应着在points的值，而值对应下标在points中的位置。
Next
End Sub
轉換錶：這個表在new函數中被初始化，可以看出，它的值記錄了i，這個i實際上就是它的下標對應的ps當中的位置，簡單地說，通過它，我們可以快速的得到一個坐標在ps數組當中的下標。
向量方向：這個值就是用來記錄向量是4個方向中的那個方向，只用於更新相應方向上的key。所以，一個局面有4個key。簡單的來說，這4個key就是棋型在該方向垂直方向上的投影。
get函數非常簡單，我們不做介紹了，解釋一下set函數當中的關鍵代碼（以刪除一個子為例，下一個子和刪除的情況基本一致）：
mVectorManeger.keys(Direction) = mVectorManeger.keys(Direction) Xor info '去掉原来的记录
info = info And Not (CInt(1) << table(point) * 2) '删除白棋
info = info And Not (CInt(1) << table(point) * 2 + 1) '删除黑棋
mVectorManeger.keys(Direction) = mVectorManeger.keys(Direction) Xor info '记录新的记录
pipecount(bp) -= 1 '记录白棋或黑棋个数
update(0) = True '记录需要更新，无论白棋变了还是黑棋变了，棋型都变化，所以同时需要更新。
update(1) = True
mVectorManeger.shapes(0)(value(0)) -= 1
mVectorManeger.shapes(1)(value(1)) -= 1
mModManager.Evaluate(Me)
mVectorManeger.shapes(0)(value(0)) += 1
mVectorManeger.shapes(1)(value(1)) += 1
key的更新：
首先，在key中去掉當前棋型
然後，刪除白棋和黑棋（當然，bp值=0就是白棋，=1就是黑棋）。刪除的方法很簡單，就是把1移動到指定位置，然後not，這樣其他位都是1，而指定位置為0，接下來and。
最後，在key中記錄更新後的棋型
中間的代碼更新了棋子個數、更新標誌。最後：
評價前：從棋型記錄中減去原來的棋型（注意，雖然棋型確實更新了，但是沒有經過評價，向量的value是不變的）
評價：按照update來更新棋型信息
評價後：在棋型記錄中加上現在的棋型
5、向量管理
這個類的代碼非常少。也很容易看懂。其中set函數中Dim a = mVectorManeger.shapes沒有什麼實際意義，只是用來在這裡檢查棋型匯總是否正確，這是我在調試過程中遺留的。
6、局麵類
局麵類進行了較多更新，例如分離了禁手判斷等函數，但基本上還是很容易看懂的。需要介紹的是原來在bitboard類中的GenerateMoves函數：
'mvs为全部合理招法
Function GenerateMoves(ByRef mvs() As Byte, mv As Integer) As Integer '生成所有走法
'临时变量，存储当前局面下每个子周围三格以内的空位
Dim tmp As BitArray = GetGeneratePoints()
Dim offset As Integer = 0
If mv > -1 Then
tmp.Set(mv, False)
offset = 1
End If
'统计全部空位
Dim i As Integer = 0, nGenMoves As Integer = offset
For i = 0 To 224
If tmp(i) Then
mvs(offset + nGenMoves) = i
nGenMoves += 1
End If
Next
Return nGenMoves - 1
End Function
函數中的mv是置換錶招法，所以函數所做的改動是為了把置換錶招法放在mvs(0)這個位置，並且，tmp.set(mv,false）保證了後面的搜索中不會再次找到這個招法。
然後是置換錶的覆蓋和提取，因為我們使用了2個置換錶（橫向和縱向，兩個斜向沒有使用），所以查找和保存邏輯稍微複雜一些。尤其是保存邏輯：
' 保存置换表项
Sub RecordHash(nFlag As Integer, vl As Integer, nDepth As Integer, mv As Integer)
'被替换的置换表
Dim hshtindex As Integer = -1
Dim hsh, hsh0, hsh1 As mHashItem
'===============================置换表覆盖策略=================================
'0、查找空的，直接覆盖。若没有空的：
'分别找到置换表0、1当中对应的元素，
'1、若元素完全符合某一个，则
'1.1、若深度更深，则直接覆盖
'1.2、否则，退出
'2、若不完全符合任何一个，则
'2.1、若深度比置换表中深度更浅的深，则覆盖这个
'2.2、否则，退出
hsh0 = hstb0(mVectorManeger.keys(0) And mConstValue.HASH_SIZE_S1) '提取
If hsh0.dwLock_a = 0 Then '若为空，直接覆盖
hshtindex = 0
Else '不为空
'若一致
If (hsh0.dwLock_a = mVectorManeger.keys(1)) AndAlso (hsh0.dwLock_b = mVectorManeger.keys(2)) AndAlso (hsh0.dwLock_c = mVectorManeger.keys(3)) Then
If hsh0.ucDepth < nDepth Then '若深度更大则更新
hshtindex = 0
Else '若深度更小则返回
Return
End If
End If
'若不一致，查找下一个
End If
If hshtindex = -1 Then
hsh1 = hstb1(mVectorManeger.keys(1) And mConstValue.HASH_SIZE_S1)
If hsh1.dwLock_a = 0 Then
hshtindex = 1
Else
If (hsh1.dwLock_a = mVectorManeger.keys(0)) AndAlso (hsh1.dwLock_b = mVectorManeger.keys(2)) AndAlso (hsh1.dwLock_c = mVectorManeger.keys(3)) Then
If hsh1.ucDepth < nDepth Then
hshtindex = 1
Else
Return
End If
End If
End If
End If
'若没有找到空的、完全符合的，则覆盖深度更小的。
If hshtindex = -1 Then
If hsh0.ucDepth < hsh1.ucDepth Then
If hsh0.ucDepth < nDepth Then hshtindex = 0
Else
If hsh1.ucDepth < nDepth Then hshtindex = 1
End If
End If
'若没有深度更小的，那么不记录。
If hshtindex = -1 Then
Return
End If
If hshtindex = 0 Then hsh = hsh0 Else hsh = hsh1
hsh.ucFlag = nFlag
hsh.ucDepth = nDepth
If vl > mConstValue.WIN_VALUE Then
hsh.svl = vl + nDistance
ElseIf vl < -mConstValue.WIN_VALUE Then
hsh.svl = vl - nDistance
Else
hsh.svl = vl
End If
hsh.wmv = mv
'保存到置换表
hsh.dwLock_b = mVectorManeger.keys(2)
hsh.dwLock_c = mVectorManeger.keys(3)
If hshtindex = 0 Then
hsh.dwLock_a = mVectorManeger.keys(1)
hstb0(mVectorManeger.keys(0) And mConstValue.HASH_SIZE_S1) = hsh
Else
hsh.dwLock_a = mVectorManeger.keys(0)
hstb0(mVectorManeger.keys(1) And mConstValue.HASH_SIZE_S1) = hsh
End If
c += 1
End Sub
不用關心c這個變量，它是用來記錄置換錶中一共存儲了多少局面的。
這個邏輯是這樣的：
A、找到兩個置換錶中與當前局面一致的局面，能覆蓋則覆蓋，不能就不記錄了
B、如果沒有一致局面，則找到空的，記錄當前局面
C、如果沒有一致局面，也沒空的，那就覆蓋深度更淺的。
D、如果還沒記錄下來，那算了吧……
7、掃描類
這個類就是核心了，其中包括各種剪裁技術。但是前面我們已經做過非常多的介紹了，至少，原理是沒有什麼問題（之所以這麼說，是因為我懷疑前面的代碼中有一處甚至若干處難以查找的“手誤”），所以應該很容易能夠看懂這些代碼。
下集預告：
下次更新的時候，我希望迭代加深能夠超過現在的6——通過優化棋型評價和局面評價（雖然現在是按需更新，但也許我們可以不更新整個局面）。當然，你如果使用更嚴格的棋盤剪裁，現在就可以達到8。所以，歷史表和階梯式棋盤剪裁結合起來也許效果更好，但是這還沒有進入日程。
--------------------------------------------------------------------------------
我們都知道α—β剪裁的準確程度、局評價函數的快慢、招法排序的好壞這些因素是我們的引擎棋力高低的決定性因素。剪裁的準確度與局面信息息息相關但這不在我們這次討論的範圍之內。這次我們要討論的是一種提高局面評價速度和招法排序程度的五子棋棋型表示方法：
一、局面評價函數
最基本形式就是子力得分的差值，當然還有很多因素影響著評價結果。我們這裡採用的是棋型得分差值（因為代碼我還沒有完全完成，所以沒有測試先行權問題，這也是我的程序一直沒有使用的一個因子，現在的想法是這個因子應該在子數一樣時為0，而多子一方應該做適當的減法），也就是我們計算黑棋成5、衝四、活四、衝3……全部棋型的個數並根據我們設定的每種棋型的分值得到一個和，白棋也是如此：
VLB=LB5*K5+LB41*K41+LB42*K42+LB31*K31……
VLW也進行類似計算
若走棋方為白棋，則局面評價返回VLW-VLB，若為黑棋則VLB-VLW。這是我們所熟悉的算法，這裡最耗時的是LB5，WB5，LB41，WB41，LB42，WB42……的獲取，也就是黑棋、白棋雙方各種棋型的個數。前面我採用的是模板匹配的方式，那非常慢。這次我們討論的新方法將避免識別。
二、招法排序
在很多程序中，採用歷史表技術來得知走一步棋可能好或壞，這種技術在歷史表排序算法足夠好的情況下，使用α—β剪裁算法將產生非常多的截斷，從而產生令人振奮的效果。前面我們的程序也使用了這種方法。但是，我們仔細研究就會發現，五子棋走棋的位置選擇，往往可以從當前局面出發（我是指不嘗試下子而是直接觀察——從衝點看，我們以前的程序也是這樣做的），直接得到更好的排序方法，至少，我們知道，當走幾步之後，再去下一步只能得到一個衝2的棋不會好到哪去。所以，我們的新方法除了快速得到棋型也必須能夠快速的得出棋型上的衝棋點。
三、新的局面表示方法
基於前面的原因，還有說得麻一點就是對五子棋內在機理的初步的深入研究基礎上，我們可以發現：五子棋最終的目的就是成5，哇咔咔……成5的過程呢？就是不斷的不斷的增加連接的個數，哇咔咔咔……別拍磚，其實道理都知道……於是我們可以發現，在五個位置上，每個位置只能是0,1,2這幾種種情況，也就是說，如果我們以5個位置為基本單元來考察五子棋，那麼五子棋的棋型演變只有3*3*3*3*3種情況。我們枚舉這些情況成為一個表，這個表的元素用以下結構來表示：
sooxx mod
public vl as integer
public smods(14) as mod
end sooxx
就可以了。vl是當前的棋型的得分，只有各位均為0或2，或者均為1或2（我們用0表示白棋，1表示黑棋，2表示空，原因可以參考前面的代碼中數組的組織和走棋者表示）時才有分，其他都是0分。smods就是這個意思：
smods(0) 為第一位為變為0時的結構的引用，smods(1)為第一位變為1時的結構引用，smods(2)為第一位變為2時的結構引用，
smods(3) 為第二位為變為0時的結構的引用，smods(4)為第二位變為1時的結構引用，smods(5)為第二位變為2時的結構引用，
以此類推。這樣導致我們更新棋型時，只需要更新棋型的引用就可以了。算法就像這樣：
mm=mm.smods(point*3+player)
就可以得到新的棋型了，當然，在一個位置上下子時，最多時要更新20個這樣的棋型。也就是說，我們需要在15長的一維數組中進行尋址20次。這也許可以忍受吧。至少省略掉了模板匹配，而且可以更詳細的設置每種棋型的分值。
當然，我們還需要解決這樣一個問題：從這個5長度的向量到棋盤坐標和從棋盤坐標到向量之間的位置轉換，這只需要查一個長度5的表就可以了。嗯，最終的棋型表示形式肯定要增加一些其他元素，例如前面說的坐標，例如當前棋型屬於黑棋還是白棋。
好了，這次的更新沒有代碼，只是把想法寫在這裡。因為我還有幾個邏輯問題不是很清楚，所以代碼還沒有寫完。過些天我會發布這個版本的新的代碼，當然時間可能要長一些，因為最近忙嘛！這個藉口不錯……希望新的代碼能使棋力有一定的提升，因為打算按照我們開始時說的方法來更新招法排序和生成函數。感覺這種方法比較靠近另一種方式的引擎。
今天完成了新的棋盤表示方法和一些算法，默認debug設置在E5200上（單線程）可以達到每秒運行剪裁函數90000次左右，一般都在80000-100000之間。速度還算可以。如果使用置換錶的話，速度還會快很多，應該說速度還能令人滿意。但是在局面評價上或者剪裁上還有一些問題，可能要剪裁到上一步去才能解決（還沒有時間仔細查找代碼當中的問題，但是按照設想改了幾次局面評價函數和棋型分值都沒能解決比對方晚一步勝利卻以為自己勝利了，這程序真愚，比我還愚。而且從下面的輸出結果來看，某些層上存在一些意外情況，應該是和分值設置有關，也可以從綜合分值來解決這些問題，暫時還沒有改的打算）。也就是說程序到現在還有一些問題。至於搜索深度，一般達到6-7也就是說樹上一般有5個節點左右。以下是輸出的一個結果（AI執黑，下7,7，白下8,6時的搜索）
正在迭代：1
已經迭代：1共搜索31最佳招法96最佳分值133耗時0
正在迭代：2
已經迭代：2共搜索182最佳招法128最佳分值-3耗時0
正在迭代：3
已經迭代：3共搜索3582最佳招法142最佳分值135耗時31
正在迭代：4
已經迭代：4共搜索13145最佳招法113最佳分值-10耗時110
正在迭代：5
已經迭代：5共搜索58703最佳招法82最佳分值235耗時500
正在迭代：6
已經迭代：6共搜索257445最佳招法114最佳分值80耗時2204
耗時(毫秒): 2875
迭代加深: 6
置換錶命中: 0
共搜索局面: 257445
本次搜索局面: 257445
最多步數: 12
走法路徑： bestmove 9,7 ponder 6,7 moveline 9,7 6,6 2, 2 1,1 8,7 7,9 6,6
最終分值: 80
最佳走法： 114
搜索速度： 89081.3148788927
下面公開一下源碼：呃……怎麼code那裡光出錯。。。。
Public Class mShapes
Private list As New List(Of mShape)
Sub New()
list.Add(New mShape(New Byte() {0, 0, 0, 0, 0}, mConstValue.LinkType.l50))
list.Add(New mShape(New Byte() {0, 0, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 0, 0, 2}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte( ) {0, 0, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 0, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {0, 0, 0, 2, 0}, mConstValue.LinkType.l41))
list. Add(New mShape(New Byte() {0, 0, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 0, 2, 2}, mConstValue.LinkType .l31))
list.Add(New mShape(New Byte() {0, 0, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 1, 2}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 2, 0}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 1, 2, 2}, 0))
list.Add(New mShape(New Byte() { 0, 0, 2, 0, 0}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {0, 0, 2, 0, 1}, 0))
list.Add(New mShape (New Byte() {0, 0, 2, 0, 2}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {0, 0, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 0, 2, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 2, 1, 2}, 0 ))
list.Add(New mShape(New Byte() {0, 0, 2, 2, 0}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {0, 0, 2, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 0, 2, 2, 2}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() { 0, 1, 0, 0, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 0, 0, 1}, 0))
list.Add(New mShape(New Byte( ) {0, 1, 0, 0, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 0, 1, 2}, 0))
list.Add(New mShape (New Byte() {0, 1, 0, 2, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 0, 2, 1}, 0))
list.Add( New mShape(New Byte() {0, 1, 0, 2, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 0, 0}, 0))
list. Add(New mShape(New Byte() {0, 1, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 1, 1}, 0 ))
list.Add(New mShape(New Byte() {0, 1, 1, 1, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 2, 0} , 0))
list.Add(New mShape(New Byte() {0, 1, 1, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 1, 2, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 0, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 0, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 1, 2}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 2, 0}, 0))
list.Add(New mShape(New Byte() { 0, 1, 2, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 1, 2, 2, 2}, 0))
list.Add(New mShape(New Byte( ) {0, 2, 0, 0, 0}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {0, 2, 0, 0, 1}, 0))
list.Add( New mShape(New Byte() {0, 2, 0, 0, 2}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {0, 2, 0, 1, 0}, 0 ))
list.Add(New mShape(New Byte() {0, 2, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 0, 1, 2} , 0))
list.Add(New mShape(New Byte() {0, 2, 0, 2, 0}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {0, 2, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 0, 2, 2}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte( ) {0, 2, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {0, 2, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {0, 2, 1, 1, 0}, 0))
list.Add(New mShape (New Byte() {0, 2, 1, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 1, 1, 2}, 0))
list.Add( New mShape(New Byte() {0, 2, 1, 2, 0}, 0))
list.Add(New mShape(New Byte() {0, 2, 1, 2, 1}, 0))
list. Add(New mShape(New Byte() {0, 2, 1, 2, 2}, 0))
list.Add(New mShape(New Byte() {0, 2, 2, 0, 0}, mConstValue.LinkType .l31))
list.Add(New mShape(New Byte() {0, 2, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 2, 0, 2}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {0, 2, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {0, 2, 2, 1, 1}, 0))
list.Add(New mShape(New Byte() {0, 2, 2, 1, 2}, 0))
list.Add(New mShape(New Byte() { 0, 2, 2, 2, 0}, mConstValue.LinkType.l20))
list.Add(New mShape(New Byte() {0, 2, 2, 2, 1}, 0))
list.Add(New mShape (New Byte() {0, 2, 2, 2, 2}, mConstValue.LinkType.l11))
list.Add(New mShape(New Byte() {1, 0, 0, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 0, 2}, 0 ))
list.Add(New mShape(New Byte() {1, 0, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 1, 1} , 0))
list.Add(New mShape(New Byte() {1, 0, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 0, 2, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 1, 1}, 0))
list.Add(New mShape(New Byte() { 1, 0, 1, 1, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 2, 0}, 0))
list.Add(New mShape(New Byte( ) {1, 0, 1, 2, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 1, 2, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 0, 1}, 0))
list.Add(New mShape (New Byte() {1, 0, 2, 0, 2}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 1, 0}, 0))
list.Add( New mShape(New Byte() {1, 0, 2, 1, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 1, 2}, 0))
list. Add(New mShape(New Byte() {1, 0, 2, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 2, 1}, 0))
list.Add(New mShape(New Byte() {1, 0, 2, 2, 2}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 0, 0}, 0 ))
list.Add(New mShape(New Byte() {1, 1, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 0, 2} , 0))
list.Add(New mShape(New Byte() {1, 1, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {1, 1, 0, 2, 2}, 0))
list.Add(New mShape(New Byte() {1, 1, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 1, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() { 1, 1, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 1, 1, 1}, mConstValue.LinkType.l50))
list.Add(New mShape (New Byte() {1, 1, 1, 1, 2}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {1, 1, 1, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 1, 2, 1}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {1, 1, 1, 2, 2}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 1, 2, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 1, 2, 0, 2}, 0))
list.Add(New mShape(New Byte() { 1, 1, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 2, 1, 1}, mConstValue.LinkType.l41))
list.Add(New mShape (New Byte() {1, 1, 2, 1, 2}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 1, 2, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 1, 2, 2, 1}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 1, 2, 2, 2}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {1, 2, 0, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 0, 2}, 0))
list.Add(New mShape(New Byte() { 1, 2, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 1, 1}, 0))
list.Add(New mShape(New Byte( ) {1, 2, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {1, 2, 0, 2, 2}, 0))
list.Add(New mShape (New Byte() {1, 2, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 1, 0, 1}, 0))
list.Add( New mShape(New Byte() {1, 2, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {1, 2, 1, 1, 0}, 0))
list. Add(New mShape(New Byte() {1, 2, 1, 1, 1}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {1, 2, 1, 1, 2} , mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 2, 1, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 1, 2, 1}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 2, 1, 2, 2}, mConstValue.LinkType.l21))
list.Add(New mShape (New Byte() {1, 2, 2, 0, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 2, 0, 1}, 0))
list.Add( New mShape(New Byte() {1, 2, 2, 0, 2}, 0))
list.Add(New mShape(New Byte() {1, 2, 2, 1, 0}, 0))
list. Add(New mShape(New Byte() {1, 2, 2, 1, 1}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {1, 2, 2, 1, 2} , mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {1, 2, 2, 2, 0}, 0))
list.Add(New mShape(New Byte() {1, 2, 2, 2, 1}, mConstValue.LinkType.l20))
list.Add(New mShape(New Byte() {1, 2, 2, 2, 2}, mConstValue.LinkType.l11))
list.Add(New mShape (New Byte() {2, 0, 0, 0, 0}, mConstValue.LinkType.l41))
list.Add(New mShape(New Byte() {2, 0, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 0, 0, 2}, mConstValue.LinkType.l32))
list.Add(New mShape(New Byte() {2, 0, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 0, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {2, 0, 0, 2, 0}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() { 2, 0, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 0, 2, 2}, mConstValue.LinkType.l22))
list.Add(New mShape (New Byte() {2, 0, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() {2, 0, 1, 0, 1}, 0))
list.Add( New mShape(New Byte() {2, 0, 1, 0, 2}, 0))
list.Add(New mShape(New Byte() {2, 0, 1, 1, 0}, 0))
list. Add(New mShape(New Byte() {2, 0, 1, 1, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 1, 1, 2}, 0))
list.Add(New mShape(New Byte() {2, 0, 1, 2, 0}, 0))
list.Add(New mShape(New Byte() {2, 0, 1, 2, 1}, 0 ))
list.Add(New mShape(New Byte() {2, 0, 1, 2, 2}, 0))
list.Add(New mShape(New Byte() {2, 0, 2, 0, 0} , mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {2, 0, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 2, 0, 2}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {2, 0, 2, 1, 0}, 0))
list.Add(New mShape(New Byte( ) {2, 0, 2, 1, 1}, 0))
list.Add(New mShape(New Byte() {2, 0, 2, 1, 2}, 0))
list.Add(New mShape(New Byte() {2, 0, 2, 2, 0}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {2, 0, 2, 2, 1}, 0))
list. Add(New mShape(New Byte() {2, 0, 2, 2, 2}, mConstValue.LinkType.l12))
list.Add(New mShape(New Byte() {2, 1, 0, 0, 0} , 0))
list.Add(New mShape(New Byte() {2, 1, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 0, 2}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 2, 0}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {2, 1, 0, 2, 2}, 0))
list.Add(New mShape(New Byte() {2, 1, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() { 2, 1, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 1, 1, 0, 2}, 0))
list.Add(New mShape(New Byte( ) {2, 1, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 1, 1, 1, 1}, mConstValue.LinkType.l41))
list.Add( New mShape(New Byte() {2, 1, 1, 1, 2}, mConstValue.LinkType.l32))
list.Add(New mShape(New Byte() {2, 1, 1, 2, 0}, 0 ))
list.Add(New mShape(New Byte() {2, 1, 1, 2, 1}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {2, 1, 1, 2, 2}, mConstValue.LinkType.l22))
list.Add(New mShape(New Byte() {2, 1, 2, 0, 0}, 0))
list.Add(New mShape(New Byte() { 2, 1, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 1, 2, 0, 2}, 0))
list.Add(New mShape(New Byte( ) {2, 1, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 1, 2, 1, 1}, mConstValue.LinkType.l31))
list.Add( New mShape(New Byte() {2, 1, 2, 1, 2}, mConstValue.LinkType.l22))
list.Add(New mShape(New Byte() {2, 1, 2, 2, 0}, 0 ))
list.Add(New mShape(New Byte() {2, 1, 2, 2, 1}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {2, 1, 2, 2, 2}, mConstValue.LinkType.l12))
list.Add(New mShape(New Byte() {2, 2, 0, 0, 0}, mConstValue.LinkType.l31))
list.Add(New mShape(New Byte() {2, 2, 0, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 2, 0, 0, 2}, mConstValue.LinkType.l22))
list. Add(New mShape(New Byte() {2, 2, 0, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 2, 0, 1, 1}, 0))
list.Add(New mShape(New Byte() {2, 2, 0, 1, 2}, 0))
list.Add(New mShape(New Byte() {2, 2, 0, 2, 0}, mConstValue .LinkType.l21))
list.Add(New mShape(New Byte() {2, 2, 0, 2, 1}, 0))
list.Add(New mShape(New Byte() {2, 2, 0, 2, 2}, mConstValue.LinkType.l12))
list.Add(New mShape(New Byte() {2, 2, 1, 0, 0}, 0))
list.Add(New mShape(New Byte() { 2, 2, 1, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 2, 1, 0, 2}, 0))
list.Add(New mShape(New Byte( ) {2, 2, 1, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 2, 1, 1, 1}, mConstValue.LinkType.l31))
list.Add( New mShape(New Byte() {2, 2, 1, 1, 2}, mConstValue.LinkType.l22))
list.Add(New mShape(New Byte() {2, 2, 1, 2, 0}, 0 ))
list.Add(New mShape(New Byte() {2, 2, 1, 2, 1}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {2, 2, 1, 2, 2}, mConstValue.LinkType.l12))
list.Add(New mShape(New Byte() {2, 2, 2, 0, 0}, mConstValue.LinkType.l21))
list.Add(New mShape(New Byte() {2, 2, 2, 0, 1}, 0))
list.Add(New mShape(New Byte() {2, 2, 2, 0, 2}, mConstValue.LinkType.l12))
list. Add(New mShape(New Byte() {2, 2, 2, 1, 0}, 0))
list.Add(New mShape(New Byte() {2, 2, 2, 1, 1}, mConstValue.LinkType .l31))
list.Add(New mShape(New Byte() {2, 2, 2, 1, 2}, mConstValue.LinkType.l12))
list.Add(New mShape(New Byte() {2, 2, 2, 2, 0}, mConstValue.LinkType.l11))
list.Add(New mShape(New Byte() {2, 2, 2, 2, 1}, mConstValue.LinkType.l11))
list.Add(New mShape (New Byte() {2, 2, 2, 2, 2}, 0))
'下面初始化轉換結果
For i As Integer = 0 To list.Count - 1 '遍歷list，對每個模型進行查找
Dim lm As mShape = list(i)
Dim bk As Byte '原始值備份
For j As Integer = 0 To 4 '5個點
For k As Integer = 0 To 2 '3種值
If lm.PointValues(j) = k Then '若轉換後是自身
lm.sMod(j * 3 + k) = Nothing
Else
bk = lm.PointValues(j) '取原始值
lm.PointValues(j) = k '替換
For l As Integer = 0 To list. Count - 1 '遍歷list，查找與之一致的模型
If i <> l Then '不能是自身
Dim tk As mShape = list(l)
If lm.Equals(tk) Then
lm.sMod(j * 3 + k) = tk '將一致模型記錄下來
Exit For
End If
End If
Next
lm.PointValues(j) = bk '恢復原始值
End If
Next
Next
Next
End Sub
'獲取設置指定點上的棋子後轉化成的形態
Public Function NextShape(mlmd As mShape, point As Integer, player As Integer) As mShape
Return mlmd.sMod(point * 3 + player)
End Function
'默認形態
Public Function defShape() As mShape
Return list(242)
End Function
End Class
Public Class mShape
Public PointValues(4) As Integer '各點棋子（0=無子，1=己方，2=對方）。
Public sMod(14) As mShape '轉換結果
Public Player As Integer '所屬玩家
Public type As mConstValue.LinkType '棋型類型
Sub New(pvs() As Byte, tp As mConstValue.LinkType)
Dim i, w, b As Integer
For i = 0 To 4
PointValues(i) = pvs(i)
If pvs(i) = 0 Then
w += 1
ElseIf pvs(i) = 1 Then
b += 1
End If
Next
Player = 2
If w = 0 AndAlso b > 0 Then Player = 1
If w > 0 AndAlso b = 0 Then Player = 0
type = tp
End Sub
Public Overrides Function Equals(obj As Object) As Boolean
Dim tmp As mShape = obj
Return tmp.PointValues(0) = Me.PointValues(0) AndAlso tmp.PointValues(1) = Me.PointValues(1) AndAlso tmp.PointValues( 2) = Me.PointValues(2) AndAlso tmp.PointValues(3) = Me.PointValues(3) AndAlso tmp.PointValues(4) = Me.PointValues(4)
End Function
End Class
這樣貼出來不太整齊。這就是核心的代碼了，前面已經說過，五子棋是棋型轉換，無論是下子還是提子，一次一個，所以變化之後的結果是完全可以預知的，無需去識別。存儲棋型的lsit的代碼是寫了一段程序自動生成的，當然了，分值是改上去的好像是七十幾個。代碼沒有什麼難的地方。接下來就是把以前代碼中的14長度的向量，拆分成5長度的向量，記錄每個點對應的向量。這樣一來，我們完全可以在addpipe函數和delpipe函數運行時提高極大：用一個數組來記錄5，衝4，活3，衝3，活2，衝2包含的向量，變化時直接從上面的類取結果，評價時直接取那些向量的分值即可，而走法生成無需排序，從衝4開始向下生成就可以了（之所以我輸出的結果中只有5個節點左右，是因為只取了2層衝棋情況，實際上最近打算使用完全搜索結合棋型剪裁來嘗試一下，不過有些地方還比較懵懂）。當然，由於我們的向量長度只有5，所以沒有活4，而且一個點對應的向量有若干個，生成時需要用一個表來記錄哪些點已經添加（不要去讀返回值數組，用一個bitarray記錄速度更快）。 |
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
