的Java極小

Question

我想要實現使用極小的點和噴砂遊戲的AI（http://en.wikipedia.org/wiki/Dots_and_Boxes）

這是我到目前爲止有：

public Line makeMove(GameState gs) { 
    if (gs.getRemainingLines().size() == 1) { 
     return gs.getRemainingLines().get(0); 
    } 

    if (gs.getPlayer() == 1) { 
     int minscore = -1; 
     GameState g = gs.clone(); 
     Line lnew = null; 
     List<Line> l = gs.getRemainingLines(); 
     for (Line l2 : l) { 
      g.addLine(l2); 
      if (evaluate(g) > minscore) { 
       minscore = (evaluate(g)); 
       lnew = l2; 
      } 
     } 
     return lnew; 
    } else { 
     int maxscore = 999; 
     GameState g = gs.clone(); 
     Line lnew = null; 
     List<Line> l = gs.getRemainingLines(); 
     for (Line l2 : l) { 
      g.addLine(l2); 
      if (evaluate(g) < maxscore) { 
       maxscore = (evaluate(g)); 
       lnew = l2; 
      } 
     } 
     return lnew; 
    } 

} 

然而，它不斷返回null，我不認爲我正確地阻止minimax。任何人都可以給我一些指點。

getRemainingLines()返回仍然可能的移動列表。

evaluate()返回分數的整數。

Answer 1

我想建議你完全重新考慮你的代碼。查看代碼的問題（以及爲什麼在這裏沒有太多的迴應）是很難遵循並且很難調試。例如，什麼是gs.getRemainingLines，它究竟做了什麼？ （爲什麼剩餘的線路和不是所有的法定線路？）

但是，通過一些簡化，將更容易找出正在發生的事情並解決它。

在抽象的層面極小只是這個過程：

float minimax_max(GameState g) 
{ 
    if (g is terminal or max depth reached) 
     return eval(g); 

    float bestVal = -inf; 
    bestMove = null; 

    moves = g->getLegalMoves(); 
    for (m : moves) 
    { 
     ApplyMove(m); 
     if (g->nextPlayer == maxPlayer) 
      nextVal = minimax_max(g); 
     else 
      nextVal = minimax_min(g); 
     if (nextVal > bestVal) 
     { 
      bestVal = nextVal; 
      bestMove = m; 
     } 
     UndoMove(m); 
    } 

    return bestVal; 
} 

我還沒有表現出究竟是如何獲得/使用在最後的最後一步，但它並不難。您還需要另一個程序minimax_min，或者您可以將if語句放入代碼中。

如果你看看你的代碼，你已經寫得很接近這個，但是你已經在代碼中留下了很多遊戲特定的細節。但是，你不應該考慮這些事情才能讓minimax正常工作。

特別是，大多數遊戲都可以用抽象如果你GetMoves()，ApplyMove()，UndoMove()和eval()，後者評估狀態提供功能合理。 （進一步搜索增強將需要更多的功能，但是這將讓你長的路。）

一些原因，你可能要重新因素是這樣的：

• 現在您可以測試極小和你的其他代碼分開。

• 您可以通過驗證所有的法律動作是產生和應用的舉動後，你有正確的玩家下一個移動的法律狀態測試點格棋代碼。 （您可以播放和撤消的隨機移動長序列，以幫助驗證你最後總是回到起始狀態之後。）

• 您可以很方便地測試評價函數對個別國家以確保其正常工作。 （在實踐中，通常不能搜索到遊戲結束以確定勝利者。）

• 您可以使用簡單的評估函數測試minimax並測試是否正確移動。 （例如，如果你喜歡上邊緣移動時，1層搜索應該返回上邊緣移動）

• 其他人可以更容易地閱讀你的代碼。我們可以查看每段代碼，看看它是否正確，而不必將遊戲特定的實現細節混合到最小特定細節中。

• 如果你可以申請並正確悔棋，你不需要做遊戲狀態的副本。這將使代碼更高效。

雖然你可以嘗試修復您的代碼，而重構（例如，只要找到它返回null首位，並會指出其中的錯誤），從長遠來看，你的代碼將難以調試並沒有這些改變而改進。

Answer 2

首先要檢查的是gs.getRemainingLines（）實際上有剩餘的行。

一個單獨的問題是，您將每行添加到GameState g進行檢查。您可能需要調用評估或將克隆環內的頂部，如

int minscore = -1; 
Line lnew = null; 
List<Line> l = gs.getRemainingLines(); 
for (Line l2 : l) { 
    GameState g = gs.clone(); 
    g.addLine(l2); 
    if (evaluate(g) > minscore) { 
     minscore = (evaluate(g)); 
     lnew = l2; 
    } 
} 

或

int minscore = -1; 
GameState g = gs.clone(); 
Line lnew = null; 
List<Line> l = gs.getRemainingLines(); 
for (Line l2 : l) { 
    g.addLine(l2); 
    if (evaluate(g) > minscore) { 
     minscore = (evaluate(g)); 
     lnew = l2; 
    } 
    g.removeLine(l2); 
} 

然而，如果你試圖用極小（http://en.wikipedia.org/wiki/Minimax），然後後刪除每個添加的行您將需要更改代碼以遞歸調用makeMove（除非您修改算法以確定使用最小最大循環結構）。

public GameState makeMove(GameState gs) { 
    if (gs.getRemainingLines().size() == 1) { 
     GameState g = gs.clone(); 
     g.addLine(gs.getRemainingLines().get(0)); 
     return g; 
    } 

    if (gs.getPlayer() == 1) { 
     GameState g = gs.clone(); 
     g.setPlayer(2); 
     int bestValue = -1; 
     Line lbest = null; 
     List<Line> lines = gs.getRemainingLines(); 
     for (Line line : lines) { 
      g.addLine(line); 
      GameState val = makeMove(g); 
      g.removeLine(line); 
      if (evaluate(val) > bestValue) { 
       bestValue = evaluate(g); 
       lbest = line; 
      } 
     } 
     g.addLine(lbest); 
     return g; 
    } else { 
     GameState g = gs.clone(); 
     g.setPlayer(1); 
     int bestValue = 999; 
     Line lbest = null; 
     List<Line> lines = gs.getRemainingLines(); 
     for (Line line : lines) { 
      g.addLine(line); 
      GameState val = makeMove(g); 
      g.removeLine(line); 
      if (evaluate(val) < bestValue) { 
       bestValue = evaluate(g); 
       lbest = line; 
      } 
     } 
     g.addLine(lbest); 
     return g; 
    } 

}