幫助我的MinMax實現

我一直在試圖實現一個minMax算法（稍後將嘗試alphabeta修剪）爲一個簡單的遊戲....我見過很多僞代碼和教程，但我無法得到它工作...幫助我的MinMax實現

一點點幫助將不勝感激:)

下面是相關的類...（爲清楚起見移除實現）

class Board { //Stores board state, Immutable 

    Board playMove(Move m); //generates new Board after playing "Move m" 

    List<Move> nextMoves(Move m); // generates all possible moves, previous move is required to decide the validity of the next moves 

    boolean isTerminal(); //board at terminal state? 
} 


class Move { //stores positions played and score gained from that move 

}

，這裏是我的最小 - 最大的實現...有人可以指出我做錯了什麼嗎？謝謝。

private Move bestMove = null; // field variable 

private int maxMove(Board board, Move prevMove, int myScore, int oppnScore) { 
    out("maxMove " + board); 
    if(board.isTerminal()) { 
     return myScore - oppnScore; 
    } 
    int mx = Integer.MIN_VALUE; 
    for(Move nxtMove: board.nextMoves(prevMove)) { 
     int k = minMove(board.playMove(nxtMove), 
         nxtMove, 
         myScore + nxtMove.score, 
         oppnScore); 
     if(k > mx) { 
      mx = k; 
      bestMove = nxtMove; 
     } 
    } 
    return mx; 
} 

private int minMove(Board board, Move prevMove, int myScore, int oppnScore) { 
    if(board.isTerminal()) { 
     return myScore - oppnScore; 
    } 
    out("minMove " + board); 
    int mn = Integer.MAX_VALUE; 
    for(Move nxtMove: board.nextMoves(prevMove)) { 
     int k = maxMove(board.playMove(nxtMove), 
         nxtMove, 
         myScore, 
         oppnScore + nxtMove.score); 
     if(k < mn) { 
      mn = k; 
      bestMove = nxtMove; 
     } 
    } 
    return mn; 
}

編輯：遊戲簡要說明如下，你有一定數量的硬幣的不同教派面前的硬幣。你和另一位玩家輪流從消費者一側（左側或右側）取出一枚硬幣。硬幣的面額表示你爲這一舉動得分。某些硬幣有特殊的含義，比如說Picking X意味着你會跳過一個轉彎，或者Y意味着你會再轉一圈。你的目標是比對手得分更多。

來源

2011-03-15 st0le

也許告訴我們一些關於遊戲規則的信息會有所幫助。 – MAK 2011-03-15 08:51:37

@MAK，done ..... – st0le 2011-03-15 08:59:35

遊戲的目標是什麼？儘可能多地得分？比對手得分更多？ – MAK 2011-03-15 09:06:34

我只看到一個錯誤：你不記得你給定板子狀態的哪個回合，所以你多次計算它，算法變慢。或者速度不是你的問題？

來源

2011-03-15 08:56:05

速度不是問題。這是不正確的，它會選擇錯誤的（如非優化）移動（有時候是無效移動）。 – st0le 2011-03-15 09:00:18

我不認爲我明白遊戲規則，但它看起來像你的終端條件不太正確。

您正在返回玩家之間的分數差異。這意味着一個玩家想要最大化這個數值（與對手最大的差距），而另一個想要最小化這個數值（他試圖將最接近的分數作爲對手）。這看起來並不像真正的遊戲會有什麼樣的目標。

我想你想要的是得分最高的玩家獲勝。因此，您可以檢查myScore> oppScore是否相應地返回1,0和-1。這意味着第一個玩家想要最大限度地獲得回報（即他試圖讓它成爲1--他贏了），而對手試圖最小化回報（即如果它是-1，他就贏了）。如果沒有取得勝利，他們寧可選擇0（平局）。

另外，您爲什麼需要prevMove來產生下一步？ board沒有關於遊戲當前狀態的所有信息（即剩下的硬幣）？

來源

2011-03-15 09:15:49 MAK

我需要'prevMove'，因爲如果之前的移動移除了一個'X'硬幣，這意味着我需要選擇2個硬幣而不僅僅是一個。否則我只挑一枚硬幣。 – st0le 2011-03-15 09:19:22

@ st0le：我明白了。我會將它作爲「board」中的一個標記，但我想保留'prevMove'也可以。 – MAK 2011-03-15 09:24:00

@MAK，你的觀察似乎是正確的，我會試試看，並報告。 – st0le 2011-03-15 09:27:19

幫助我的MinMax實現

回答

相關問題