From 94340e17d55ace3776b6111f303beb2c57957a20 Mon Sep 17 00:00:00 2001 From: gumartinm Date: Wed, 5 Sep 2012 20:11:52 +0200 Subject: [PATCH] Fixed alpha beta pruning. alpha init value always: the smallest possible heuristic value beta init value alway: the biggest possible heuristic value --- src/de/android/reversi/AI.java | 70 +++++++++++++++++---------------- src/de/android/reversi/ReversiView.java | 17 +++++++- 2 files changed, 51 insertions(+), 36 deletions(-) diff --git a/src/de/android/reversi/AI.java b/src/de/android/reversi/AI.java index 66dd1de..2c570f0 100644 --- a/src/de/android/reversi/AI.java +++ b/src/de/android/reversi/AI.java @@ -2,11 +2,11 @@ package de.android.reversi; import java.util.List; +import de.android.reversi.logic.ReversiLogic; public class AI { - private Player max; - private Player min; + private final Player maxPlayer; /** * Disk-square table. @@ -22,20 +22,11 @@ public class AI { { 50, -1, 5, 2, 2, 5, -1, 50 } }; - private static final int depth = 2; + private static final int depth = 3; 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; - } + maxPlayer = currentPlayer; } /** @@ -47,26 +38,21 @@ public class AI { * @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; - } + final Player player) { - List allowedPositions; - if (depth == 0 || (allowedPositions = board.allowedPositions(player)).isEmpty()) { + final List allowedPositions = board.allowedPositions(player); + if (depth == 0 || allowedPositions.isEmpty()) { return this.heuristic(board, player); //the heuristic value of node } - if (max) { + if (player == maxPlayer) { for (final Position child : allowedPositions) { //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + //What I need is an undo movement function. In that way I do not need to clone/copy the whole board :( + //see: http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html 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); + final int val = minimaxAB (newBoard, child, depth -1, alpha, beta, ReversiLogic.opponent(player)); if (val > alpha) { alpha = val; } @@ -80,10 +66,12 @@ public class AI { else { for (final Position child : allowedPositions) { //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + //What I need is an undo movement function. In that way I do not need to clone/copy the whole board :( + //see: http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html 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); + final int val = minimaxAB (newBoard, child, depth -1, alpha, beta, ReversiLogic.opponent(player)); if (val < beta) { beta = val; } @@ -97,16 +85,18 @@ public class AI { } public Position getBestMove(final Board board) { - final List allowedPositions = board.allowedPositions(this.max); - int alpha = -10; + final List allowedPositions = board.allowedPositions(this.maxPlayer); + int alpha = 0 ; Position bestMove = null; for (final Position child : allowedPositions) { //TODO: This clone sucks. I must re design this program. :( I should just need the array :( + //What I need is an undo movement function. In that way I do not need to clone/copy the whole board :( + //see: http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html 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, 0, 0, true); + newBoard.makeMove(this.maxPlayer, child.getColumn(), child.getRow()); + newBoard.flipOpponentDiscs(child, this.maxPlayer); + final int val = this.minimaxAB(newBoard, child, depth -1, alpha, Integer.MAX_VALUE, ReversiLogic.opponent(this.maxPlayer)); if (val > alpha) { alpha = val; bestMove = child; @@ -117,10 +107,22 @@ public class AI { } + /** + * http://www.site-constructor.com/othello/Present/MobilityEval.html + * 1. Minimize your opponents move options. + * 2. Less importantly, maximize your own move options. + * + * @param board + * @param player + * @return + */ private int getMobilityForPlayer(final Board board, final Player player) { - - return board.allowedPositions(player).size(); - + final int mobility = board.allowedPositions(player).size(); + if (mobility == 0) { + return Integer.MAX_VALUE - 1; + } else { + return 64 / mobility; + } } private int heuristic (final Board board, final Player player) { diff --git a/src/de/android/reversi/ReversiView.java b/src/de/android/reversi/ReversiView.java index c36f04c..4359b7d 100644 --- a/src/de/android/reversi/ReversiView.java +++ b/src/de/android/reversi/ReversiView.java @@ -128,8 +128,21 @@ public class ReversiView extends SurfaceView { public void run() { final AI ai = new AI(currentPlayer); - mainLoop(ai.getBestMove(board)); + final Position move = ai.getBestMove(board); + if (move != null) { + mainLoop(move); + } + else { + int idString; + if (player1Score > player2Score) { + idString = R.string.player1WON; + } else { + idString = R.string.player2WON; + } + final DialogFragment newFragment = ErrorDialogFragment.newInstance(idString); + newFragment.show(((Activity)context).getFragmentManager(), "errorDialog"); + } } @@ -313,7 +326,7 @@ public class ReversiView extends SurfaceView { final Position move = ai.getBestMove(board); if (move != null) { - mainLoop(ai.getBestMove(board)); + mainLoop(move); } else { int idString; -- 2.1.4