我正在尝试为点和框游戏（http://en.wikipedia.org/wiki/Dots_and_Boxes）实现一个使用Minimax算法的人工智能。
这是我目前的代码：
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()返回一个整数，表示得分。
回答：
我建议你完全重构你的代码。查看你的代码的问题（也是为什么这里没有很多回应的原因）是它难以理解和调试。例如，gs.getRemainingLines是什么，它具体做什么？（为什么是剩余的线而不是所有合法的线？）
但是，通过一些简化，将更容易弄清楚发生了什么并修复它。
在抽象层面上，Minimax算法只是这样一个过程：
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和你的其他代码。
-
你可以通过验证所有合法移动都被生成，并且在应用一个移动后，你有一个合法的状态，并且下一个移动的玩家正确，来测试你的点和框代码。（你可以通过播放和撤销一长串随机移动来帮助验证你总是回到开始状态。）
-
你可以轻松地在单个状态上测试你的评估函数，以确保它正常工作。（在实践中，你通常无法搜索到游戏结束来确定赢家。）
-
你可以通过使用一个简单的评估函数并测试是否做出了正确的移动来测试Minimax。（例如，如果你更喜欢边缘上的移动，一个1层搜索应该返回一个边缘上的移动）
-
其他人可以更容易地阅读你的代码。我们可以查看每段代码并单独检查它是否正确，而不是将游戏特定的实现细节混入Minimax特定的细节中。
-
如果你能正确地应用和撤销移动，你不需要制作游戏状态的副本。这将使代码更加高效。
虽然你可以尝试在不重构的情况下修复你的代码（例如，只需找到它返回null的第一个地方，这将指出你的错误所在），但从长远来看，如果没有这些更改，你的代码将难以调试和改进。
