ITI0011:harjutus 19

Kirjeldus

Realiseerida minimax algoritm.

Mall

<source lang="java">

import java.util.ArrayList;

public class MinimaxGomoku {

/** * 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 int minimax(int[][] board, int player, int depth) { // 1) check for win, you can use getScore method // if one player is winning, return a winning score depending on the player // for X, we want to return high score, for O, small score. // for example for X, infinity, for O, -infinity.

// 2) if we are in the deepest level, let's calc score using getScore() // and return the score

// 3) initialize best score to be -infinity for X and infinity for O // (as we want to max X score, -inf is a good place to start)

// 4) get possible moves

// 5) loop over possible moves

// 6) "make the move" by setting the value of according board // cell value to "X" or "O", depending on the player // basically, you should do: board[location.row][location.col] = player;

// 7) let's call out minimax again (recursive call) // but this time let's change the player and change the depth: // if player == 1 then newplayer = 2 // if player == 2 then newplayer = 1 // newdepth = depth - 1 // int value = minimax(board, newplayer, newdepth)

// (you don't have to declare new variables newplayer and newdepth, // rather put the expression in the call.)

// 8) now let's "undo" move, something like // board[location.row][location.col] = EMPTY // as this position was empty before we "made our move", // so we have restored the state we had.

// 9) in case it's our (X's) turn, we want to find the max: // if value > best score then best score = value // and in case it's O's turn, we want to find the min: // if value < best score then best score = value

// 10) in the end, let's return best value as the best score

// 11) if everything is done, the minimax returns the best score // which is almost what we want // actually we want to get the location where to make our move // to get this score // this is best achieved to modify the place where we call minimax initially

return 0; }

/** * 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 100; // | if (col <= WINCOUNT && getCount(board, row, col, 1, 1, X) >= WINCOUNT) return 100; // \ if (col >= WINCOUNT && getCount(board, row, col, 1, -1, X) >= WINCOUNT) return 100; // / } if (col <= WINCOUNT && getCount(board, row, col, 0, 1, X) >= WINCOUNT) return 100; // - } } } 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>