我堅持alpha-beta修剪算法實現

Question

我試圖實現遊戲AI爲9Men的莫里斯遊戲。

到目前爲止，我有板這樣表示：

public class board 
    { 
      public  node []gNode  = null; 
      ... // so the table has 24 nodes, for 9 men morris game: 
      gNode = new node[24]; 
      ... 
      int evaluateBoard(); // evaluates the current board (tokens) 
    } 

好了，現在每節點表示，像這樣：

public class node 
    { 
    node() // constructor 
    {  ...  } 

    // setting current node's neighbours (maximum 4 neighbours) 
    void setNeighbours(int left, int right, int top, int bottom) 
    {  ...  } 

    short  gOccupiedByTeam = renderer.TEAM_NOTEAM; // info if this node is occupied by a token (and a wich team this token belongs to) 
    short []gNeighbourId = null; // info about this node neighbours (can be max. 4 in a 9Men's morris game) 
    short  gInternalID  = -1; // board's IDs (from 0..23) 
    short  gTokenID  = -1; // this node can be occupied by a token. (from 0 .. 8) -see below the token class. 
    short  gNodeScore  = -1; // a dummy node score. 
    vector3 gLocation  = null; // 3d coordinates for this node. 


    } 

和令牌外觀像這樣：

public class token 
{ 
    token(vector3 startpos, short nodeId) // Constructor. 
    {  ...  } 


    public physx  gPhysX  = null; // 3d coordinates , velocity , accel. for this Token. 
    public boolean  bIsAlive = false; // is this token alive ? (or eliminated?) 
    public boolean  bFormsMill = false; // does it form a Mill? 

    public short   gNodeID  = -1; // "link" this token with a gNodeID (when placing a token on current board). See above the node class. This represents a link ID to that node. 
    public short   gTokenMill1 = -1; // used when this token forms a mill (with gTokenMill1 token!) 
    public short   gTokenMill2 = -1; // same. 

} 

，這裏是我的α-β剪枝算法的實現，其中我堅持：

public int getBestMove(board board, int depth, int alpha, int beta, boolean bIsPlayer) 
{ 
    // if depth reached, return current's board's Evaluation (a score). 
    if (depth == 0) return board.evaluateBoard(bIsPlayer); 

    // is it Player's turn ? (max?) 
    if (bIsPlayer) 
    { 
     // QUESTIONS: 
     // retrevie all possible "boards" below ! (all new possible token moves) 
     // 1. here i should generate a new board with 1st possible move (for player token1) ?? ... then a second new board with 2nd possible move still for token1 ? .. and so on until no possible moves for token1? 
     // (remembering that a token can move in 4 available spots - wich are a neighbour?) 
     // 
     // 2. the problem is that if i generate 4 new boards as per token 1 above let's say, then it will "eat" lot of memory for all 18 tokens and a function recursion depth of 5 for example, right ? 
     // 3. how do i fix point 2? 


     ArrayList<board> possible_boards = board.getAllPossibleBoards(); 

     // 4. ok, some possible boards were generated, loop thru them starting with the first one and calling recursively this function, is it right ? 
     for(board iterator: possible_boards) 
     { 
      alpha = Math.max(alpha, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer)); 

      if (beta < alpha) 
      { 

       break; 
      } 
     } 

     // 5. how do i return best move to main calling function ? (wich token is it best move from all of these board's moves ? 
     return alpha; 
    } 
    else 
    { 
     ArrayList<board> possible_boards = board.getAllPossibleBoards(); 

     for(board iterator: possible_boards) 
     { 

      beta = Math.min(beta, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer)); 


      if (beta < alpha) 
      { 
       break; 
      } 


     } 

     return beta; 
    } 


} 

OK，這是我的功能至今。 我不知道即使我在正確的軌道上 ??！

什麼是錯誤的，我的功能？
請回答我上面的問題（getBestMove（）函數中的1到5）。

謝謝你提前請escuse我的語言錯誤（我的英語就不是那麼好）

---

謝謝你這麼多saeedn您的回覆！

我想沒有人會回答我:)。我真的幫助我瞭解我的想法。

所以，CheckWinner（布爾）將檢查當前的播放器有着很好的優勢（如贏得或非常好動形阻擋對手等），至今在這個深度，如果是，則返回當前玩家的BIG得分。所有這一切都是因爲球員或對手都不會嘗試贏（大比分），對吧？

否則，如果深度 = 0，則返回當前選定委員會的評價（評分）（INT evaluateBoard（）），好吧。

在此之後，然後我必須生成一個單一的板（與單個令牌更多鈔票移動）：

while(board.generateNextPossibleBoard(nextBoard)) // board generated and stored in "nextBoard". Also check if it is a valid board or no more boards to generate further. 

好，具有現在一個新生成的板，遞歸和如果有更好的板（板具有更好的SCORE），然後將當前的電路板保存到chosenBoard。如果不是，則切斷並返回（不要再檢查樹的下方）。

再次感謝saeedn！

Answer 1

通常你的代碼是可以的，但是你應該牢記一些觀點。

首先，你應該檢查節點（這裏是一個棋盤）是否最終（某人贏了比賽），然後檢查深度等於零。如果某人在該狀態下獲勝，則可能需要返回一個很大的值（用於贏得最大玩家）和一個小值（用於贏得最小玩家），例如分別爲MAXINT和MININT。

爲避免高內存消耗，請不要生成所有可能的主板。生成一個電路板併爲其進行遞歸調用，然後生成另一個電路板並搜索該電路板等。這樣你就可以在每個堆棧幀中爲一個狀態使用內存。這對於高分支因素的搜索至關重要！

最後你應該記錄最大玩家的棋盤更新分數（你在哪裏更新阿爾法）。

看到我的僞代碼更多的澄清：

if (board.checkWinner(bIsPlayer)) return board.evaluateBoard(bIsPlayer); 

// if depth reached, return current's board's Evaluation (a score). 
if (depth == 0) return board.evaluateBoard(bIsPlayer); 

board chosenBoard;  
if (bIsPlayer) 
{ 
    // You should implement this method, or write your board generation code here 
    // returns false if no more boards could be generated 
    board nextBoard; 
    while(board.generateNextPossibleBoard(nextBoard)) 
    { 
     int v = getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer)); 

     if (v > alpha) 
     { 
      alpha = v; 
      chosenBoard = nextBoard; // return this chosenBoard by reference ;) 
     } 

     if (beta < alpha) 
     { 
      break; 
     } 
    } 

    return alpha; 
} 
else 
{ 
    // The same for beta except you don't need to update chosenBoard :) 
}