From 3c6df57077a084ed54d5cf5bd070d145d114cfb2 Mon Sep 17 00:00:00 2001 From: gumartinm Date: Tue, 4 Sep 2012 23:05:38 +0200 Subject: [PATCH] Alpha-Beta pruning. --- src/de/android/reversi/AI.java | 118 +++++++++++++++++++++++++ src/de/android/reversi/Board.java | 67 +++++++++----- src/de/android/reversi/Player.java | 1 + src/de/android/reversi/ReversiView.java | 6 ++ src/de/android/reversi/Square.java | 21 +++-- src/de/android/reversi/logic/ReversiLogic.java | 1 + 6 files changed, 184 insertions(+), 30 deletions(-) create mode 100644 src/de/android/reversi/AI.java diff --git a/src/de/android/reversi/AI.java b/src/de/android/reversi/AI.java new file mode 100644 index 0000000..d9f201e --- /dev/null +++ b/src/de/android/reversi/AI.java @@ -0,0 +1,118 @@ +package de.android.reversi; + +import java.util.List; + + + +public class AI { + private Player max; + private Player min; + + /** + * Disk-square table. + */ + private final int[][] values = new int[][] { + { 50, -1, 5, 2, 2, 5, -1, 50 }, + { -1, -10, 1, 1, 1, 1, -10, -1 }, + { 5, 1, 1, 1, 1, 1, 1, 5 }, + { 2, 1, 1, 0, 0, 1, 1, 2 }, + { 2, 1, 1, 0, 0, 1, 1, 2 }, + { 5, 1, 1, 1, 1, 1, 1, 5 }, + { -1, -10, 1, 1, 1, 1, -10, -1 }, + { 50, -1, 5, 2, 2, 5, -1, 50 } }; + + + private static final int depth = 2; + + + public AI(final Player currentPlayer) { + + //TODO: This sucks. Re implementation without Enum and with MVC pattern :( + if (currentPlayer == Player.PLAYER1) { + max = Player.PLAYER1; + min = Player.PLAYER2; + } + else { + max = Player.PLAYER2; + min = Player.PLAYER1; + } + } + + /** + * Alpha-beta pruning + * @param node + * @param depth + * @param alpha + * @param beta + * @param player + */ + private int minimaxAB (final Board board, final Position node, final int depth, int alpha, int beta, + final boolean max) { + Player player; + //TODO: This sucks. I must re design this program. :( + if (max) { + player = this.max; + } else { + player = this.min; + } + + List allowedPositions; + if (depth == 0 || (allowedPositions = board.allowedPositions(player)).isEmpty()) { + return 10; //the heuristic value of node + } + if (max) { + for (final Position child : allowedPositions) { + //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + final Board newBoard = board.clone(); + newBoard.makeMove(player, child.getColumn(), child.getRow()); + newBoard.flipOpponentDiscs(child, player); + final int val = minimaxAB (newBoard, child, depth -1, alpha, beta, false); + if (val > alpha) { + alpha = val; + } + if (beta <= alpha) { + break; + } + } + + return alpha; + } + else { + for (final Position child : allowedPositions) { + //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + final Board newBoard = board.clone(); + newBoard.makeMove(player, child.getColumn(), child.getRow()); + newBoard.flipOpponentDiscs(child, player); + final int val = minimaxAB (newBoard, child, depth -1, alpha, beta, false); + if (val < beta) { + beta = val; + } + if (beta <= alpha) { + break; + } + } + + return beta; + } + } + + public Position getBestMove(final Board board) { + final List allowedPositions = board.allowedPositions(this.max); + int alpha = -10; + Position bestMove = null; + + for (final Position child : allowedPositions) { + //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + final Board newBoard = board.clone(); + newBoard.makeMove(this.max, child.getColumn(), child.getRow()); + newBoard.flipOpponentDiscs(child, this.max); + final int val = this.minimaxAB(newBoard, child, depth, -10, 10, true); + if (val > alpha) { + alpha = val; + bestMove = child; + } + } + + return bestMove; + } +} diff --git a/src/de/android/reversi/Board.java b/src/de/android/reversi/Board.java index b84c358..d802dde 100644 --- a/src/de/android/reversi/Board.java +++ b/src/de/android/reversi/Board.java @@ -3,7 +3,7 @@ package de.android.reversi; import java.util.ArrayList; import java.util.List; -public class Board { +public class Board implements Cloneable { private final static short [][] directions = { { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, -1 } }; @@ -12,7 +12,8 @@ public class Board { public static final short TOP_MARGIN = 0; public static final short LEFT_MARGIN = 0; - private final Square gameBoard[][] = new Square[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]; + //TODO: I am using clone but it could be interesting to use a copy factory. + private Square gameBoard[][] = new Square[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]; //Just one dimension because it is a square. private int squareWidth; @@ -45,9 +46,9 @@ public class Board { } - public void flipOpponentDiscs(final Position movement, final Player currentPlayer) { - final List flippedDiscs = flippedDiscs(currentPlayer, movement.getRow(), - movement.getColumn()); + public void flipOpponentDiscs(final Position position, final Player currentPlayer) { + final List flippedDiscs = flippedDiscs(currentPlayer, position.getRow(), + position.getColumn()); for (final Position flippedDisc : flippedDiscs) { this.makeMove(currentPlayer, flippedDisc.getColumn(), flippedDisc.getRow()); } @@ -118,14 +119,31 @@ public class Board { squareWidth = (width - Board.LEFT_MARGIN * 2) / Board.NUMBER_OF_COLUMNS; } - public final boolean empty(final short column, final short row) { + + public final List allowedPositions(final Player player) { + final List list = new ArrayList(); + + for (short column = 0; column < Board.NUMBER_OF_COLUMNS; column++) { + for (short row = 0; row < Board.NUMBER_OF_ROWS; row++) { + if (empty(column, row)) { + if (isValidMove(player, row, column)) { + list.add(new Position(row, column)); + } + } + } + } + + return list; + } + + private final boolean empty(final short column, final short row) { if (gameBoard[column][row].getPlayer() == Player.NOPLAYER) { return true; } return false; } - public final boolean isValidMove (final Player player, final short row, final short column) { + private final boolean isValidMove (final Player player, final short row, final short column) { for (int i = 0; i < directions.length; i++) { if (isValidMove (directions[i][0], directions[i][1], player, (short)(row + directions[i][1]), (short)(column + directions[i][0])) > 0) { @@ -136,7 +154,7 @@ public class Board { return false; } - public final List flippedDiscs (final Player player, final short row, final short column) { + private final List flippedDiscs (final Player player, final short row, final short column) { final List flippedDiscs = new ArrayList(); List aux; @@ -151,22 +169,6 @@ public class Board { return flippedDiscs; } - public final List allowedPositions(final Player player) { - final List list = new ArrayList(); - - for (short column = 0; column < Board.NUMBER_OF_COLUMNS; column++) { - for (short row = 0; row < Board.NUMBER_OF_ROWS; row++) { - if (empty(column, row)) { - if (isValidMove(player, row, column)) { - list.add(new Position(row, column)); - } - } - } - } - - return list; - } - private final int isValidMove (final short moveX, final short moveY, final Player player, short row, short column) { int flippedDiscs = 0; @@ -233,4 +235,21 @@ public class Board { public Square[][] getGameBoard() { return gameBoard; } + + @Override + public Board clone() { + try { + final Board result = (Board) super.clone(); + //If this was not a matrix (a simple array) I could use gameBoard.clone(); + result.gameBoard = new Square[NUMBER_OF_ROWS][NUMBER_OF_COLUMNS]; + for (short column = 0; column < NUMBER_OF_COLUMNS; column++) { + for (short row = 0; row < NUMBER_OF_ROWS; row++) { + result.gameBoard[column][row] = gameBoard[column][row].clone(); + } + } + return result; + } catch (final CloneNotSupportedException e) { + throw new AssertionError(e); + } + } } diff --git a/src/de/android/reversi/Player.java b/src/de/android/reversi/Player.java index 10d2c8a..17bd528 100644 --- a/src/de/android/reversi/Player.java +++ b/src/de/android/reversi/Player.java @@ -2,6 +2,7 @@ package de.android.reversi; import android.graphics.Color; +//TODO: better a linked list public enum Player { NOPLAYER { @Override diff --git a/src/de/android/reversi/ReversiView.java b/src/de/android/reversi/ReversiView.java index a998e2b..31dd62c 100644 --- a/src/de/android/reversi/ReversiView.java +++ b/src/de/android/reversi/ReversiView.java @@ -225,6 +225,10 @@ public class ReversiView extends SurfaceView { //AllowedPositions for player. listAllowedPositions = board.allowedPositions(currentPlayer); + final AI prueba = new AI(this.currentPlayer); + + prueba.getBestMove(board); + //UpdateBoard with suggestions for (final Position suggestedPosition : listAllowedPositions) { board.makeMove(currentPlayer, suggestedPosition.getColumn(), suggestedPosition.getRow(), true); @@ -238,6 +242,8 @@ public class ReversiView extends SurfaceView { this.isEnableUserTouch = true; + + //Going to wait for touch event from human player. } else { diff --git a/src/de/android/reversi/Square.java b/src/de/android/reversi/Square.java index f981bce..49d6d58 100644 --- a/src/de/android/reversi/Square.java +++ b/src/de/android/reversi/Square.java @@ -1,6 +1,6 @@ package de.android.reversi; -public class Square { +public class Square implements Cloneable { private Player player; private boolean suggestion; private int squareMediumX; @@ -16,7 +16,7 @@ public class Square { return suggestion; } - public void setSuggestion(boolean suggestion) { + public void setSuggestion(final boolean suggestion) { this.suggestion = suggestion; } @@ -24,7 +24,7 @@ public class Square { return squareMediumX; } - public void setSquareMediumX(int squareMediumX) { + public void setSquareMediumX(final int squareMediumX) { this.squareMediumX = squareMediumX; } @@ -32,11 +32,11 @@ public class Square { return squareMediumY; } - public void setSquareMediumY(int squareMediumY) { + public void setSquareMediumY(final int squareMediumY) { this.squareMediumY = squareMediumY; } - public void setPlayer (Player player) { + public void setPlayer (final Player player) { this.player = player; } @@ -44,11 +44,20 @@ public class Square { return player; } - public void setRadius (int radius) { + public void setRadius (final int radius) { this.radius = radius; } public int getRadius() { return radius; } + @Override + public Square clone() { + try { + final Square result = (Square) super.clone(); + return result; + } catch (final CloneNotSupportedException e) { + throw new AssertionError(e); + } + } } diff --git a/src/de/android/reversi/logic/ReversiLogic.java b/src/de/android/reversi/logic/ReversiLogic.java index c8d4081..aed6b9e 100644 --- a/src/de/android/reversi/logic/ReversiLogic.java +++ b/src/de/android/reversi/logic/ReversiLogic.java @@ -18,6 +18,7 @@ public final class ReversiLogic { return null; } + //TODO: With a linked list this is not needed public static Player opponent(final Player currentPlayer) { switch (currentPlayer){ case PLAYER1: -- 2.1.4