【導讀】本論文主要闡述以iOS開發(fā)平臺為基礎(chǔ)，通過使用Xcode開發(fā)工具以及objective-c和c++語言開發(fā)。五子棋是一種兩人對弈的純策略型棋類游戲，棋具與圍棋。通用，是起源于中國古代的傳統(tǒng)黑白棋種之一。近年來，隨著智能手機的流行，出現(xiàn)了許多在移動操作。所以，開發(fā)一款可以在iOS系統(tǒng)上運行的五子棋游戲是非常有意義的。在開發(fā)的過程中，我首先學習了objective-c語言的相關(guān)語法，objective-c語言是在C語言上進行一。些面向?qū)ο蟮臄U充，學習它大概用了一周的時間。接下來，開始學習iOS應(yīng)用的構(gòu)建原理（學習視圖控。這時候的界面是用xib文件來搭建的，通過直接拖拉控件來產(chǎn)生界面。在做好這些基礎(chǔ)的準備后，我開始動手搭建五子棋的界面，五子棋界面。家點擊棋盤觸發(fā)的事件，判斷游戲輸贏，悔棋和認輸功能的實現(xiàn)等等。之后，就開始設(shè)計與實現(xiàn)五子棋。經(jīng)過多年的發(fā)展，五子棋的算法已經(jīng)較為完善，我做的工作是在理解這些算法原理的基礎(chǔ)上，五子棋算法一般包括估值算法以及搜索算法，估值算法的實

　　

【正文】 ) || ( (rightEdge == line_size 1 || ( rightEdge line_size 1 amp。amp。 line[ rightEdge + 1 ] == enemy )) amp。amp。 ( leftEdge 0 amp。amp。 line[ leftEdge 1 ] == EMPTY) )) { numOfState[ current_player ][ SLEEP_FOUR ] ++ 。 } } 這個函數(shù)的功能主要就是分析每一行中對于某一方的子力 的個數(shù)并且放入存放子力個數(shù)的數(shù)組中，函數(shù)傳入兩個參數(shù)，一個代表需要分析的代表棋子的字符串，另一個代表是計算哪一方的子力情況。整個方法的實現(xiàn)思路大概如下：將同一行棋子分為已經(jīng)分析過的和未被分析過的兩種，做一個循環(huán)，在這個循環(huán)中，從左到右找出連續(xù)的同一類的棋子一個區(qū)域，且這塊區(qū)域的棋子都是之前未被分析過的，得到這塊區(qū)域的左右邊界，通過左右邊界值的差來得到這塊區(qū)域有這種類型棋子的個數(shù)，首先通過連續(xù)的同一類型的個數(shù)來區(qū)分不同子力的情況，比如左右邊界的距離是四的話那一定是五子相連了，所以代表該玩家的代表五子相連的狀態(tài) 數(shù)需要加一。有一些不能僅僅通過左右邊界就確定它的子力情況，這樣就需要通過分析這個區(qū)域之外的棋子情況得到確認。已經(jīng)分析過的區(qū)域需要將它的棋子狀態(tài)設(shè)為已經(jīng)分析過以防止這塊區(qū)域進行重新分析。 除了前兩個部分之外，還有另外一個部分那就是己方的棋子和對方的棋子若相鄰也需要加上一定的分值，這個分值只是加在己方的分值上而不需要加在對方的分值中。己方的棋子和對方相鄰雖然不一定是固定的子力，在計算子力分值時不會將它考慮進去，但是這樣的局面確是有利于防守的，對于這個的作用不能簡單的忽視。計算的方法是確定一個己方棋子與對方相鄰為 某一個分值，然后計算出有多少 第 13 頁 共 38 頁 個這樣的相鄰，再乘以原來的基數(shù)就是這一部分的分值，加到原來己方的分值中。最后將己方的分值與對方的分值相減就構(gòu)成了最后這個棋局相對于那時刻下子那一方的估值了。 搜索算法的分析與實現(xiàn) 前面介紹了計算每一個棋面估值的算法以及實現(xiàn)。下面要介紹在估值算法上找出最佳落子點的搜索算法。 搜索算法是怎么起作用的？假設(shè)當我們進行下子時，我們可以計算出在每個可以下子的地方下子后棋面的估值，然后找出下子后棋面對于己方估值最高的下子點，并把該點作為最佳下子點。但是這存在一個很大的問題，那就是這個 點在此時看似是最佳下子點。但是，走完若干步棋子后，此時估值最大的點未必就是最適合的點了。而搜索算法的目的就是通過分析走幾步棋后的局面來找到最佳落子點。 首先介紹在搜索過程中的數(shù)據(jù)結(jié)構(gòu)，這是一個樹的結(jié)構(gòu)，如下圖 3： 第一層不代表可以實際下子的點，從第二層開始每一層的節(jié)點都是代表一個下子點，第二層是己方下子，第三層就是對方下子。我們要找最佳下子點是存在于第二層中的點。這里假設(shè)每個父節(jié)點下面有兩個子節(jié)點，即每次可以找出兩個點拿來考慮?？梢哉业狞c有那么多，這兩個點是怎么確定的。我們不可能找出所有的點拿來搜索 ，所以就通過函數(shù)找出兩個估值比較大的點，在這個函數(shù)里面使用到了估值的算法。我們來模擬一下搜索的過程：首先輪到機器人下子，那么就通過方法找到兩個估值最高的點，這兩個點是機器人可能會走的。然后接下去到了第三層輪到玩家下子。我們假設(shè)玩家的考慮也是這樣的，所以在第二層兩個節(jié)點的每個節(jié)點下面各自尋找兩個估值最高的點。同樣的道理，第四層也是這樣。在這里，我們假設(shè)只搜索到了第四層，那么第二層左邊的點 ，第三層的兩個點 。下面模擬一下搜索過程：首先，我們在 第 14 頁 共 38 頁 值較大的那點，并把該估值轉(zhuǎn)化為對于第三層下子一方的估值（若使用負極大值算法就需要轉(zhuǎn)化），這個估值就是 ， 。而 的估值就從 和 中得來。同樣可以得到 節(jié)點的估值。最后，再用 落子點，搜索的過程就類似于上面。 在這里有一個關(guān)鍵的點事如何表示每一層節(jié)點的估值，傳統(tǒng)的方法時使用極大極小值算法。由于我們通過估值算法得到的是相對于某一方的分值，假設(shè)某一個局面對于機器人的分值是 100分，那么它相對于玩家的分值就是 100 分。極大極小算法就是把所有的節(jié)點的估值都轉(zhuǎn)化為相對于機器人的分值，假如是機器人下子就無需轉(zhuǎn)化。但是假如該點是玩家下子，該點使用估值算法得到的估值是相對于玩家的，在這里我們就需要將對于玩家的估值轉(zhuǎn)化為對于機器人的估值，方法就是在原來的估值上面取負。所以，當機器人下子的時候，他就會找值最大的一點，就是極大值點，而當輪到是玩家下子時，他就會尋找值最小的一點，就是極小值點。在上圖中，第二層和第四層都是極大值點，第三層是極小值點。第一層是尋找第二層中值最大的那點，所以也可以算是極大值點。 在上面的基礎(chǔ)上，我們就可以搜索整棵樹找到最佳下子點了。但是，在這樣的算法下面，我們需要把整棵樹都搜索一遍，耗費的時間很多，特別是當搜索的深度加深時，搜索的數(shù)量級是成倍增長的。在這樣的基礎(chǔ)上我們引進了 alphabeta 減枝搜索算法。 如下圖 4: 上圖中 A 和 C所在的都是極大值點， B所在的點是極小值點。 的值是 10， 9。從左到由搜索，當搜索完 時， A 點的值就是 的值。由于 A 點的值是極大值點，所以 須要大于 10?，F(xiàn)在來看 ， 是一個極小值點，由于 須要大于 10才能作為 A 點的值，所以 B下面的 C點都必須要大于 10。當我們搜索到 的時候，由于它的值是 9，而 是極小值點。所以 的值必然是小于等于 9，所以 。那么搜索完 后就沒有必要搜索 ，這就是 alpha 減枝。 而 beta 減枝的示例圖如下圖 5： 第 15 頁 共 38 頁 上圖中 的值是 10， 的值是 11。搜索完 之后， A 的值是 10，由于 A 點是極小值點，所以 10才有用。 ，當 搜索到 ，由于 的值是 11，所以 的值是必然大于等于 11，由于它需要小于 10 才有用，所以當搜索完 的值之后就沒有必要再搜索 和 了，這就是 beta 搜索。 可以看出， alpha 和 beta 搜索可以減少搜索時很多沒有必要搜索的節(jié)點。但是這個是和節(jié)點的排列順序有關(guān)。例如在上圖 beta 減枝示例圖中， 9，而且是先搜索 ，結(jié)果就是當搜索了 后由于 ，所以他還會繼續(xù)往下搜索，這就照成了不必要的時間損耗。假如搜索節(jié)點排列順序不恰當，可能即 使使用了 alphabeta 減枝搜索算法也沒有任何的時間優(yōu)化。 在上面的介紹的方法中，是用了極大極小值和 alphabeta 減枝搜索算法。但是假如使用極大極小值的話，就必須判斷極大值點和極小值點。下面可以對極大極小值算法進行改進，改進后 alphabeta 算法就不需要進行 alpha 減枝，而只需要進行 beta 減枝。 將極大極小值算法改為負極大值算法就可以實現(xiàn)這一點。在原來的極大極小算法中，需要區(qū)分極大值點和極小值點。而負極大值算法的每個節(jié)點都是極大值點。它的原理是這樣子的：在原來的極小值點中，我們需要找到相對 于機器人的值最小的一點，而相對于機器人估值較小的一點就是相對于玩家估值較大的一點，所以就可以轉(zhuǎn)換為求相對于玩家估值較大的一點，這就是極大值點。那么當節(jié)點是玩家走棋時，它的節(jié)點估值都是相對于玩家的而不是像極大極小算法中都是相對于機器人的。在每個節(jié)點中，它的估值都是相對于該節(jié)點要下子的一方的，所以我們在不同層的節(jié)點之間傳遞值得時候就需要進行轉(zhuǎn)換，方法就是取負數(shù)。極大極小值算法與負極大值算法其實非常類似。只不過是負極大值算法是將極大極小值算法中極小值點的變?yōu)闃O大值點，因為它的上下層值傳遞時進行了轉(zhuǎn)換。 用了負極大 值算法之后， alphabeta 剪枝算法只需要使用 beta 剪枝這一塊了。因為 alpha 剪枝是極小值點剪去它下面的節(jié)點的搜索，而現(xiàn)在已經(jīng)沒有極小值點了，所以只需要用到極大值點。 搜索關(guān)鍵代碼如下： //alphabeta 減枝搜索算法 int Search::alphaBetaSearch( int search_depth , int alpha , int beta , char player ) { int score 。//估值結(jié)果 Node *goodNodes = new Node[ numOfGoodNodes ] 。 第 16 頁 共 38 頁 Node *badNodes = new Node[ 1 ] 。 badNodes[ 0 ].x = badNodes[ 0 ].y = badNodes[ 0 ].win = TIE 。 search_several_good_nodes( player , chessBoard , goodNodes , numOfGoodNodes ) 。 search_several_good_nodes( ( player == MYSELF ) ? RIVAL : MYSELF , chessBoard , badNodes , 1 ) 。 //如果贏了，不可能再在此基礎(chǔ)上下下去 if ( goodNodes[ 0 ].win == WIN ) { if ( search_depth == 1) { = goodNodes[ 0 ].x 。 = goodNodes[ 0 ].y 。 } return ( search_depth % 2 ) ? goodNodes[ 0 ].value : ( goodNodes[ 0 ].value ) 。 } //自己不贏，敵方贏了，這下一步得走在敵方的一步上 if ( badNodes[ 0 ].win == WIN ) { if ( search_depth == 1 ) { = badNodes[ 0 ].x 。 = badNodes[ 0 ].y 。 } return ( search_depth % 2 ) ? badNodes[ 0 ].value : ( badNodes[ 0 ].value ) 。 } //搜索到了最后一層，則返回 if ( search_depth == thisdepth ) { return ( search_depth % 2 ) ? goodNodes[ 0 ].value : ( goodNodes[ 0 ].value ) 。 } 第 17 頁 共 38 頁 for ( int i = 0 。 i numOfGoodNodes 。 ++ i ) { chessBoard[ goodNodes[ i ].x ][ goodNodes[ i ].y ] = player 。 if (search_depth == 1) { score = alphaBetaSearch( search_depth + 1 , alpha , beta , (player == MYSELF) ? MYSELF : RIVAL ) 。 } else{ score = alphaBetaSearch( search_depth + 1 , beta , alpha , (player == MYSELF) ? RIVAL : MYSELF ) 。 } chessBoard[ goodNodes[ i ].x ][ goodNodes[ i ].y ] = EMPTY 。 if ( score = beta ) { return beta