Ago – 6. mai 2015, kell 12:45

2015-05-06T12:45:42Z

Ago: Uus lehekülg: '== Kirjeldus == Realiseerida minimax algoritm. == Mall == import java.util.ArrayList; public class Minimax { /** * Empty cell on the board. */ p...'

2015-05-06T01:19:36Z

Uus lehekülg: '== Kirjeldus == Realiseerida minimax algoritm. == Mall == <source lang="java"> import java.util.ArrayList; public class Minimax { * * Empty cell on the board.: p...'

Uus lehekülg

== Kirjeldus ==

Realiseerida minimax algoritm.

== Mall ==

<source lang="java">

import java.util.ArrayList;

public class Minimax {

/**
* 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 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));

// 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 (whos 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>

@@ 6. rida: / 6. rida: @@
 <source lang="java">
 import java.util.ArrayList;
-public class Minimax {
+public class MinimaxGomoku {
 	/**
@@ 57. rida: / 58. rida: @@
 	public static void main(String[] args) {
 		// initial state,
-		// X has 5 in a row
+			// initial state,
-		int[][] board = {
+			// X has (atleast) 5 in a row
-				{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+			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, 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, 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},
-				{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+					{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
-				{0, 0, 0, 0, 0, 0, 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));
+			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
+			// fill in the minimax method
-		System.out.println("minimax:" + minimax(board, X, 1));
+			// after you have finished with minimax, you should get a score indication
+			System.out.println("minimax:" + minimax(board, X, 1));
 		// 12) we want to get location instead.
 		// now modify minimax call to something like that:
@@ 205. rida: / 227. rida: @@
 	 * @param rowd Row step (-1, 0, 1)
 	 * @param cold Col step (-1, 0, 1)
-	 * @param player Player (whos piece is expected)
+	 * @param player Player (whose piece is expected)
 	 * @return The number of connected player pieces "in a row"
 	 */
@@ 230. rida: / 252. rida: @@
+	}
+}
 </source>

ITI0011:harjutus 19 - Redigeerimiste ajalugu

Ago – 6. mai 2015, kell 12:45

Ago: Uus lehekülg: '== Kirjeldus == Realiseerida minimax algoritm. == Mall == import java.util.ArrayList; public class Minimax { /** * Empty cell on the board. */ p...'