我最近一直在研究 Java 中 Android 上标准 8x8 黑白棋（黑白棋）游戏的 MiniMax 算法。每个日志似乎都显示了每个节点的正确值，但不知何故，算法只是没有选择最佳移动（我将行为与其他人的应用程序进行了比较，在某些时候它们有所不同）。
恐怕有相当多的代码要吞下，但我相信你可以做到这一点！
首先，我的算法类（从那个类我继承了 MiniMax 算法）：
public abstract class Algorithm
{
/** game instance to which the strategy is applied */
Game game;
public Algorithm (Game game)
{
this.game = game;
}
/**Finds player's all possible moves for the current state *
* @param gb - a game board for which the moves are found
* @param player - current player
* @return - an array list of possible fields to move
*/
public ArrayList<Field> findAllPossibleMoves(GameBoard gb, boolean player)
{
ArrayList <Field> moves = new ArrayList <Field> ();
for (int y= 0; y<gb.getHeight();y++) for (int x= 0; x<gb.getWidth();x++)
{
Field f = new Field (x,y);
if (game.isAvailable(gb, f, player)) moves.add(f);
}
return moves;
}
/** Searches for the right move
* @param gb - game board to do the search on
* @param depth maximum depth of search tree
* @param player - current player
* @return - optimum move (Field)
*/
public abstract Field findBestMove(GameBoard gb, int depth, boolean player);
/**Evaluates the player's current state *
* @param gb - game board to be evaluated
* @param player - player for which we evaluate
* @return - the current rating (int)
*/
public int evaluate(GameBoard gb)
{
int rating = 0;
int[][] eval_table = {
{99, -8, 8, 6, 6, 8, -8, 99},
{-8, -24, -4, -3, -3, -4, -24, -8},
{ 8, -4, 7, 4, 4, 7, -4, 8},
{ 6, -3, 4, 0, 0, 4, -3, 6},
{ 6, -3, 4, 0, 0, 4, -3, 6},
{ 8, -4, 7, 4, 4, 7, -4, 8},
{-8, -24, -4, -3, -3, -4, -24, -8},
{99, -8, 8, 6, 6, 8, -8, 99}
};
for (int x=0; x<8; x++) for (int y=0;y<8;y++)
{
if(gb.board[x][y] == GameBoard.WHITE)
{
//rating+=eval_table[x][y];
rating++;
}
}
return rating;
}
}
findBestMove 函数当然在 MiniMax 子类中被覆盖：
@Override
public Field findBestMove(GameBoard gb, int depth, boolean player)
{
/** maximum depth of search reached, we stop */
if(depth >= max_depth) return null;
//player = (depth+1)%2 + 1;
/** getting a list of moves to chose from */
ArrayList <Field> moves = findAllPossibleMoves(gb, player);
Field best_move = null;
/** iterating over all possible moves, to find the best one */
for (int i=0; i<moves.size(); i++)
{
/** board to simulate moves */
GameBoard temp_board = new GameBoard(gb);
/** getting the current move */
Field move = moves.get(i);
/** simulating the move for the current node */
game.move(move, temp_board, player);
Log.i("board", "Depth:"+depth+" Player:"+player+" Move:"+i+" Rating:"+evaluate(temp_board));
Log.i("board", ""+moves.get(i).getX()+","+moves.get(i).getY());
temp_board.printBoard();
/** getting to the next inferior node */
Field best_deep_move = findBestMove (temp_board, depth + 1, !player);
/** if the maximum depth is reached, we have a null, so we evaluate */
if (best_deep_move == null)
{
move.setRating(evaluate (temp_board));
}
/** if we are not the deepest possible, we get the rating from the lower node */
else
{
move.setRating(best_deep_move.getRating());
Log.i("eval", ""+best_deep_move.getRating());
}
if(best_move == null)
{
best_move = move;
}
else
{
Log.i("update", "Current move rating:"+move.getRating());
Log.i("update", "New move rating:"+best_move.getRating());
if (depth%2==0)
{
Log.i("update", "MAX player");
/** for us, we look for the maximum */
if (best_move.getRating() < move.getRating())
{
best_move = move;
}
}
else
{
Log.i("update", "MIN player");
/** for the opponent, we look for the minimum */
if (best_move.getRating() > move.getRating())
{
best_move = move;
}
}
Log.i("update", "Updated move rating"+best_move.getRating());
}
}
return best_move;
}
该算法在我当前的 Game 实例中实例化：
public class Game {
public GameBoard game_board;
public Algorithm alg;
boolean active_player;
//int other_player;
int white_count;
int black_count;
int depth;
public Game()
{
game_board = new GameBoard(8, 8);
active_player = true;
//other_player = GameBoard.WHITE;
white_count = 0;
black_count = 0;
// AI strategy
alg = new MiniMaxAlgorithm(this);
}
public boolean getActive_player() {
return active_player;
}
public void setActive_player(boolean active_player) {
this.active_player = active_player;
}
//public boolean getOther_player() {
//return other_player;
//}
//public void setOther_player(boolean other_player) {
//this.other_player = other_player;
// }
public int getWhite_count() {
return white_count;
}
public void setWhite_count(int white_count) {
this.white_count = white_count;
}
public int getBlack_count() {
return black_count;
}
public void setBlack_count(int black_count) {
this.black_count = black_count;
}
// array of 8 possible directions
public final int[][] directions = new int [][]{
{-1, 0},
{-1, 1},
{0, 1},
{1, 1},
{1, 0},
{1, -1},
{0, -1},
{-1, -1}
};
public int playerToPiece (boolean player)
{
return player == true? GameBoard.BLACK : GameBoard.WHITE;
}
/** Function checking if a given field is available to move
*
* @param f - field to be checked
* @return - whether or not the field is available (boolean)
*/
public boolean isAvailable (GameBoard gb, Field f, boolean player)
{
if(gb.board[f.x][f.y] != GameBoard.EMPTY) return false;
/** iterating over all 8 possible directions */
for (int k=0; k<directions.length; k++)
{
int dx = directions[k][0];
int dy = directions[k][1];
/** scanning through all fields in line with the current direction */
for (int i = f.x + dx, j = f.y + dy;
i>=0 && i<gb.getWidth() && j>=0 && j<gb.getHeight() ; i+=dx, j+=dy)
{
if(i == f.x + dx && j == f.y + dy && gb.board[i][j] == playerToPiece(player)) break;
if(gb.board[i][j] == GameBoard.EMPTY) break;
else if(gb.board[i][j] == playerToPiece(player)) return true;
}
}
return false;
}
/** Function performing a move
*
* @param f - destination field of the move
* @param board - board to do the move on
* @param player - player that performs the move
*/
public void move (Field f, GameBoard board, boolean player)
{
if (f == null) return;
if (isAvailable(board, f, player))
{
board.board[f.x][f.y] = playerToPiece(player);
/** iterating over all 8 possible directions */
for (int k=0;k < directions.length; k++)
{
int dx = directions[k][0];
int dy = directions[k][1];
/** scanning through all fields in line with the current direction */
for (int i = f.x + dx, j = f.y + dy;
i>=0 && j>=0 && i<board.getWidth() && j<board.getHeight() ; i+=dx, j+=dy)
{
/** if there is an empty field, there can be no line, so we move on to the next dir */
if(board.board[i][j] == GameBoard.EMPTY) break;
/** if the field is the same as active, we fill all the fields up to that one with
* that color */
else if(board.board[i][j] == playerToPiece(player))
{
for (int a = f.x, b = f.y; a*dx<=i*dx && b*dy<=j*dy; a+=dx, b+=dy)
{
board.board[a][b] = playerToPiece(player);
}
break;
}
}
}
white_count = black_count = 0;
for (int i = 0; i < board.getWidth(); i++)
{
for (int j=0; j < board.getHeight(); j++)
{
if (board.board[i][j] == GameBoard.WHITE) white_count++;
else if (board.board[i][j] == GameBoard.BLACK) black_count++;
}
}
}
}
/** Function changing the active player
*
*/
public void changePlayer ()
{
active_player = !active_player;
//active_player = active_player == GameBoard.BLACK ? GameBoard.WHITE : GameBoard.BLACK;
//other_player = other_player == GameBoard.BLACK ? GameBoard.WHITE : GameBoard.BLACK;
}
}
我确实做了研究，但我必须承认，仅仅通过谷歌搜索问题并不容易追踪和错误的循环函数。这让我非常坚持进一步的优化（alpha-beta 等），我现在真的真的需要加快速度。