【正文】 這個 Min 節(jié)點最終的倒推值就確定為β值。這個就是β剪枝。這個就是α剪枝。A： 40B：40C：=30D：204050E：30？?F：20H：=25I：25??圖11 Alpha—Beta剪枝從上圖可以看出，由于C節(jié)點的值肯定不大于30而B節(jié)點的值為40大于C節(jié)點，那么目前為止可以很肯定的說A節(jié)點值一定不小于40。那么是否有很好的改進技術(shù)，去除那些不必要的節(jié)點，并且在剪去了這些點后不影響結(jié)果呢？答案是肯定的，這種方法就是AlphaBeta剪枝。D。C224。B224。F。D224。所以整個過程的遍歷結(jié)果為：AB224。ABCFDE圖10 圖的遍歷 DFS遍歷過程如下：首先從A點出發(fā)訪問它的領(lǐng)接點B，因為B的領(lǐng)接點C，F(xiàn)均未被訪問過，所以B點選擇C（當(dāng)然也可以選擇F點）作為下一個要訪問的點，C點的領(lǐng)接點是D，F(xiàn)選擇下個節(jié)點D，而D的鄰接點只有一個E且未被訪問過，就將E作為了它下個節(jié)點。而BFS則是逐個的遍歷它的聯(lián)接接點，將已經(jīng)訪問過的點放入隊列中。則向上返回到上一個節(jié)點，在遍其他的未被訪問過的點。601056010402051560圖9 極大極小樹 深度優(yōu)先搜索在圖論中有兩個很重要的遍歷的方法，一個是深度優(yōu)先搜索（DFS），另外一個是廣度優(yōu)先搜索(BFS).這兩個方法的主要區(qū)別在于下一個節(jié)點的選擇。在計算這個點時可以很明顯的看出這是一個不斷遞歸的過程，到達葉子節(jié)點時根據(jù)相關(guān)的計算規(guī)則算出該值然后向上一層不斷的返回。通俗的說就是當(dāng)輪到我方時，我們就應(yīng)該選擇一個最有利于我們的點，預(yù)測對方可能下的最有利他方的點（相對我方來說就是最壞的點）。當(dāng)在MAX層時，該層的值就應(yīng)該為下一個MIN層中的最大一個的值。假設(shè)己方為MAX點，對方則為MIN點。 } return false。 count 5) { count++。 () 15 amp。 () 15 amp。 while (((() + 1).setY( () + 1)) amp。 } if (count = 5) { return true。amp。amp。 (x).setY(y)。 } if (count = 5) { return true。amp。amp。amp。 } (x).setY(y)。 () 15) { count++。 () = 0 amp。 while (((() 1).setY( () + 1)) amp。 } // 正斜向 ，判斷方法同上 count = 1。 count 5) { count++。 () 15 amp。 while (((() + 1)) amp。 } if (count = 5) { return true。amp。 (x).setY(y)。 } if (count = 5) { return true。amp。amp。 } (x).setY(y)。 count 5) { count++。 () = 0 amp。 //從當(dāng)前位置著手判斷，如果橫向緊鄰當(dāng)前位置也是我方棋子，且該位置還在棋盤內(nèi)， //截止到此位置我方的相鄰的棋子數(shù)還小于5，則count加1，temp指向與當(dāng)前位置相鄰的我方棋子 while (((() 1)) amp。 int x = ()， y = ()。 } Point point = (() 1)。 } private final Point temp = new Point(0， 0)。 allFreePoints = ()。 // 所有空白棋子 //獲取己方棋子 public final ListPoint getMyPoints() { return myPoints。// 我已下的棋子 protected ChessBoard chessboard。如果在其中的某一個方向上一連有5個都是玩家的棋子則判玩家贏了。如何才能判斷玩家是否贏了呢？本次設(shè)計所采取的方法是：如果每個玩家所下的棋子還不足5個，則不予判斷。下面將主要介紹一下BasePlayer類。 }} 玩家類本次設(shè)計中共有三個玩家類，BasePlayer類，HumanPlayer類，PhonePlayer類。 refressCanvas()。 (point2)。 Point point2 =().get(().size() 1)。 ().remove(point1)。 } public void setTextView(TextView textView) { // TODO Autogenerated method stub =textView。 j++) { (new Point(i， j))。 i++) { for (int j = 0。 for (int i = 0。 } } } private static void drawImage(Canvas canvas， Bitmap bitmap， int x， int y) { // TODO Autogenerated method stub (bitmap， x， y， null)。 } else { ()。 // 畫玩家2所下的棋子 if (hasStart()) { if (isPlayer2Run()) { ()。 // 畫棋盤上面的線條 drawPlayer1Point(canvas)。 // 加載白色棋缽圖片 (canvas， whitechess， 320， 2)。 (canvas， board， 0， 80)。 pointArray[color] = bitmap。 (0， 0， pointSize， pointSize)。 } public void fillPointArrays(int color， Drawable drawable) { Bitmap bitmap = (pointSize， pointSize， )。 i++) { drawPoint(canvas， ().get(i)， WHITE)。 } for (int i = 0。 } int size = ().size() 1。 } drawPoint(canvas， ().get(size)， NEW_BLACK)。 i size。 if (size 0) { return。 } private void refressCanvas() { // 觸發(fā)onDraw函數(shù) ()。 } // 是否輪到人類玩家下子 public boolean isPlayer2Run() { return whoRun == 2。 } private void setOnProcessing() { whoRun = 1。 private boolean onProcessing() { // TODO Autogenerated method stub return whoRun == 1。 } else {// 第二個玩家贏了 setMode(PLAYER_ONE_LOST)。 // 刷新一下 refressCanvas()。 // 發(fā)消息觸發(fā)handleMessage函數(shù) sendMessageDelayed(obtainMessage(0)， delayMillis)。 } } } private RefreshHandler refreshHandler = new RefreshHandler()。 // 判斷我是否贏了 if (!()) {// 我還沒有贏 setPlayer1Run()。 // (point)。 if ((point)) {// 此棋是否可下 setOnProcessing()。 } } else { // 否則，提示游戲結(jié)束 setMode(PLAYER_TWO_LOST)。 // 判斷第一個玩家是否已經(jīng)下了 if (!()) {// 我還沒有贏 if (player2 == phonePlayer) {// 如果第二玩家是電腦 // 10豪秒后才給玩家2下棋 (10)。 // (point)。 if ((point)) {// 此棋是否可下 setOnProcessing()。 } else if (isPlayer2Run()) {// 第二玩家下棋 player2Run(event)。 return true。 } // 是否正在處理一步棋的過程中 if (onProcessing()) { return true。 } public boolean hasStart() { return currentMode == RUNNING。 // 刷新一下 refressCanvas()。 (this)。 case 2： player2 = humanPlayer。 switch (i) { case 1： player2=phonePlayer。 int i。 } } return p。amp。 i maxY。 x (i* pointSize + xOffset + pointSize / 2)) { (i)。 i++) { if ((i * pointSize + xOffset pointSize / 2) = x amp。 for (int i = 0。 currentMode = READY。 } else if (currentMode == READY) { ()。 currentMode = READY。 } public void setMode(int newMode) { currentMode = newMode。 } } // 畫棋盤上的線條 private void drawChssboardLines(Canvas canvas) { for (Lines line ： lines) { (， ， ， ， paint)。 i maxY。 i++) {// 豎線 (new Lines(xOffset + i * pointSize， yoffset， xOffset + i * pointSize， yoffset + (maxX 1) * pointSize))。 } // 產(chǎn)生棋盤上所有的線 private void createLines() { for (int i = 0。 // 設(shè)置畫線時用的顏色 createLines()。 hide2 = ((BitmapDrawable) getResources().getDrawable()) .getBitmap()。 blackchess = ((BitmapDrawable) getResources().getDrawable( )).getBitmap()。 // 從資源文件中裝載圖片 board = ((BitmapDrawable) getResources().getDrawable( )).getBitmap()。 fillPointArrays(WHITE， ())。 // 把棋子按顏色對應(yīng)放入數(shù)組 fillPointArrays(BLACK， ())。 setFocusable(true)。 //用于提示輸贏的文本控件 public TextView textView = null。 private static Player humanPlayer = new HumanPlayer()。 // 玩家1，在本游戲中默認(rèn)有人類游戲玩家 public Player player2。 // 線條集合 public final ListPoint allFreePoints = new ArrayListPoint()。// 棋盤上橫線的左邊起點 public static int yoffset = 110。// 棋盤上橫線的條數(shù) public static int maxY = 15。// 四種棋子的Bigmap數(shù)組 public static int pointSize = 30。// 白色棋子 private static final int NEW_WHITE = 3。// 黑色棋子 private static final int NEW_BLACK = 1。 private Bitmap hide2 = null。 // 黑色棋缽圖片 private Bitmap blackchess = null。// 畫筆對象 private Bitmap board = null。 private int currentMode = READY。 // 以玩家2失敗結(jié)束 private