我正在为游戏开发 AI,我想使用MinMax算法与Alpha-Beta 修剪.
我对它的工作原理有一个粗略的了解,但我仍然无法从头开始编写代码,所以我花了两天的时间在网上寻找某种伪代码。
我的问题是,我在网上找到的每个伪代码似乎都是基于寻找最佳动作的值,而我需要返回最佳动作本身而不是数字。
我当前的代码基于这个伪代码(source https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html)
minimax(level, player, alpha, beta){ // player may be "computer" or "opponent"
if (gameover || level == 0)
return score
children = all valid moves for this "player"
if (player is computer, i.e., max's turn){
// Find max and store in alpha
for each child {
score = minimax(level - 1, opponent, alpha, beta)
if (score > alpha) alpha = score
if (alpha >= beta) break; // beta cut-off
}
return alpha
} else (player is opponent, i.e., min's turn)
// Find min and store in beta
for each child {
score = minimax(level - 1, computer, alpha, beta)
if (score < beta) beta = score
if (alpha >= beta) break; // alpha cut-off
}
return beta
}
}
// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)
正如您所看到的,此代码返回一个数字,我猜想这是使一切正常工作所必需的(因为返回的数字在递归期间使用)。
所以我想我可以使用外部变量来存储最佳移动,这就是我更改之前代码的方式:
minimax(level, player, alpha, beta){ // player may be "computer" or "opponent"
if (gameover || level == 0)
return score
children = all valid moves for this "player"
if (player is computer, i.e., max's turn){
// Find max and store in alpha
for each child {
score = minimax(level - 1, opponent, alpha, beta)
if (score > alpha) {
alpha = score
bestMove = current child // ROW THAT I ADDED TO UPDATE THE BEST MOVE
}
if (alpha >= beta) break; // beta cut-off
}
return alpha
} else (player is opponent, i.e., min's turn)
// Find min and store in beta
for each child {
score = minimax(level - 1, computer, alpha, beta)
if (score < beta) beta = score
if (alpha >= beta) break; // alpha cut-off
}
return beta
}
}
// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)
现在,这对我来说是有意义的,因为只有轮到玩家并且该动作比前一个更好时,我们才需要更新最佳动作。
所以,虽然我认为这是正确的(即使我不是 100% 确定),source https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html还有一个java更新的实现bestMove
即使在score < beta
案例,我不明白为什么。
尝试使用该实现导致我的代码选择对方玩家的移动作为最佳移动,这似乎不正确(假设我是黑人玩家,我正在寻找我可以做出的最佳移动,所以我期待的是“黑”棋,而不是“白”棋)。
我不知道我的伪代码(第二个)是否是使用以下命令找到最佳动作的正确方法MinMax with α-β剪枝或者如果我需要更新最好的动作,即使是在分数 case.
如果您愿意,请随意建议任何新的和更好的伪代码,我不受任何约束,并且如果比我的更好,我不介意重写一些代码。
EDIT:
由于我无法理解这些回复,我想也许这个问题没有问我想知道的问题,所以我试图在这里写得更好。
假设我只想为一名球员获得最佳走法,并且该球员,这是最大化者,被传递给MinMax每当我需要新的动作时都会起作用(这样minmax(2, black, a, b)
返回黑色玩家的最佳走法,同时minmax(2, white, a ,b)
返回白人玩家最好的一个),您将如何更改第一个伪代码(或java源中的实现)将给定的最佳移动存储在某处?
EDIT 2:
让我们看看是否可以让它以这种方式工作。
这是我的实现,你能告诉我它是否正确吗?
//PlayerType is an enum with just White and Black values, opponent() returns the opposite player type
protected int minMax(int alpha, int beta, int maxDepth, PlayerType player) {
if (!canContinue()) {
return 0;
}
ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
Iterator<Move> movesIterator = moves.iterator();
int value = 0;
boolean isMaximizer = (player.equals(playerType)); // playerType is the player used by the AI
if (maxDepth == 0 || board.isGameOver()) {
value = evaluateBoard();
return value;
}
while (movesIterator.hasNext()) {
Move currentMove = movesIterator.next();
board.applyMove(currentMove);
value = minMax(alpha, beta, maxDepth - 1, player.opponent());
board.undoLastMove();
if (isMaximizer) {
if (value > alpha) {
selectedMove = currentMove;
alpha = value;
}
} else {
if (value < beta) {
beta = value;
}
}
if (alpha >= beta) {
break;
}
}
return (isMaximizer) ? alpha : beta;
}
EDIT 3:
基于@Codor 的回答/评论的新实现
private class MoveValue {
public Move move;
public int value;
public MoveValue() {
move = null;
value = 0;
}
public MoveValue(Move move, int value) {
this.move = move;
this.value = value;
}
@Override
public String toString() {
return "MoveValue{" + "move=" + move + ", value=" + value + '}';
}
}
protected MoveValue minMax(int alpha, int beta, int maxDepth, PlayerType player) {
if (!canContinue()) {
return new MoveValue();
}
ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
Iterator<Move> movesIterator = moves.iterator();
MoveValue moveValue = new MoveValue();
boolean isMaximizer = (player.equals(playerType));
if (maxDepth == 0 || board.isGameOver()) {
moveValue.value = evaluateBoard();
return moveValue;
}
while (movesIterator.hasNext()) {
Move currentMove = movesIterator.next();
board.applyMove(currentMove);
moveValue = minMax(alpha, beta, maxDepth - 1, player.opponent());
board.undoLastMove();
if (isMaximizer) {
if (moveValue.value > alpha) {
selectedMove = currentMove;
alpha = moveValue.value;
}
} else {
if (moveValue.value < beta) {
beta = moveValue.value;
selectedMove = currentMove;
}
}
if (alpha >= beta) {
break;
}
}
return (isMaximizer) ? new MoveValue(selectedMove, alpha) : new MoveValue(selectedMove, beta);
}
我不知道我是否做对了或者做错了什么,但我又回到了我发布问题时遇到的问题:
calling minMax(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, PlayerType.Black)
返回一个只能由白人玩家完成的动作,这不是我需要的。
我需要给定玩家的最佳走法,而不是整个棋盘的最佳走法。