ITI0011RUS:minimax
Вернуться на страницу предмета
MinimaxGomoku.java: <source lang="java"> import java.util.ArrayList;
public class MinimaxGomoku {
public static final int MAX_PAYOFF = 100;
/** * Empty cell on the board. */ public static final int E = 0;
/** * Player "X" piece in the board * is marked by this value. */ public static final int X = 1; /** * Player "O" piece on the board. */ public static final int O = 2;
/** * Number of rows. */ public static final int ROWS = 10; /** * Number of columns. */ public static final int COLS = 10;
/** * Symbols to be printed out for each cell. * 0, 1, 2 = {., X, O} */ public static final char[] SYM = {'.', 'X', 'O'};
/** * Number of pieces "in a row" to win. */ private static final int WINCOUNT = 5;
public static class Location { public int row; public int col; public Location(int row, int col) { this.row = row; this.col = col; } }
public static void main(String[] args) { { // initial state, // X has (atleast) 5 in a row int[][] board = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, X, X, X, X, X, X, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, }; print(board); System.out.println("score=" + getScore(board));
// fill in the minimax method // after you have finished with minimax, you should get a score indication System.out.println("minimax:" + minimax(board, X, 1)); } { // X has 4 in a row, X can win with 1 move int[][] board = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, X, X, X, X, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, }; print(board); System.out.println("score=" + getScore(board));
// this should output the winning score System.out.println("minimax:" + minimax(board, X, 1)); } // 12) we want to get location instead. // now modify minimax call to something like that: // moves = getPossibleMoves() // for (move : moves) { // "make a move" // call minimax // "undo the move" // if minimax returns a better score than previous best, // then store the value as the new best. // also, store the location as the best.
// the stored best location is the place to make your move.
}
public static boolean isTerminalState(int[][] board) { int score = getScore(board); return( score == MAX_PAYOFF || // WIN score == -MAX_PAYOFF || // LOSS ( // DRAW Math.abs(score) != MAX_PAYOFF && getPossibleMoves(board).size() == 0 ) ); } public static int minimax(int[][] board, int player, int depth) { if(depth == 0 || isTerminalState(board)) { return getScore(board); }
int best_score; Location best_move = null;
ArrayList<Location> moves = getPossibleMoves(board);
if(player == X) { best_score = -Integer.MAX_VALUE; for(Location move : moves) { board[move.row][move.col] = player; int score = minimax(board, X+O-player, depth-1); if(score > best_score) { best_score = score; best_move = move; } board[move.row][move.col] = E; } } else { // player == O best_score = Integer.MAX_VALUE; for(Location move : moves) { board[move.row][move.col] = player; int score = minimax(board, X+O-player, depth-1); if(score < best_score) { best_score = score; best_move = move; } board[move.row][move.col] = E; } }
return best_score; }
/** * Returns all possible moves. * It is used by the minimax algorithm. * It might be wise to only return * certain empty cells (as cells in the corner * and border are not so valuable as in the center etc). * @param board The board. * @return A list of location objects */ public static ArrayList<Location> getPossibleMoves(int[][] board) { ArrayList<Location> availableMoves = new ArrayList<Location>();
// TODO:
// loop over the board
// and return only cells which are available
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[row].length; col++) {
if (board[row][col] == E) {
availableMoves.add(new Location(row, col));
}
}
}
return availableMoves;
}
/** * Given a game state (board with pieces) * returns a score for the state. * * @param board Game state (e.g. board) * @return score A heuristic score for the given state. */ public static int getScore(int[][] board) { for (int row = 0; row < board.length; row++) { for (int col = 0; col < board[row].length; col++) { if (board[row][col] == X) { if (row <= WINCOUNT) { if (getCount(board, row, col, 1, 0, X) >= WINCOUNT) return MAX_PAYOFF; // | if (col <= WINCOUNT && getCount(board, row, col, 1, 1, X) >= WINCOUNT) return MAX_PAYOFF; // \ if (col >= WINCOUNT && getCount(board, row, col, 1, -1, X) >= WINCOUNT) return MAX_PAYOFF; // / } if (col <= WINCOUNT && getCount(board, row, col, 0, 1, X) >= WINCOUNT) return MAX_PAYOFF; // - } } } return 0; }
/** * Counts pieces on the board starting from (row, col) and * moving in direction (rowd, cold). * @param board The board * @param row Starting row * @param col Starting col * @param rowd Row step (-1, 0, 1) * @param cold Col step (-1, 0, 1) * @param player Player (whose piece is expected) * @return The number of connected player pieces "in a row" */ public static int getCount(int[][] board, int row, int col, int rowd, int cold, int player) { int count = 0; for (int i = 0; i < WINCOUNT; i++) { if (board[row + i * rowd][col + i * cold] == player) count++; else break; } return count; }
/** * Prints out the board. * @param board The board to be printed. */ public static void print(int[][] board) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { System.out.print(SYM[board[i][j]]); } System.out.println(); } } } </source>