Aleksandr: Uus lehekülg: 'Вернуться на страницу предмета MinimaxGomoku.java: import java.util.ArrayList; public class MinimaxGomoku { pu...'

2015-05-14T10:57:18Z

Uus lehekülg: 'Вернуться на страницу предмета MinimaxGomoku.java: <source lang="java"> import java.util.ArrayList; public class MinimaxGomoku { pu...'

Uus lehekülg

Вернуться [[ITI0011RUS|на страницу предмета]]

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>

ITI0011RUS:minimax - Redigeerimiste ajalugu

Aleksandr: Uus lehekülg: 'Вернуться на страницу предмета MinimaxGomoku.java: import java.util.ArrayList; public class MinimaxGomoku { pu...'