Fixed alpha beta pruning.

alpha init value always: the smallest possible heuristic value
beta init value alway: the biggest possible heuristic value

diff --git a/src/de/android/reversi/AI.java b/src/de/android/reversi/AI.java
index 66dd1de..2c570f0 100644 (file)
--- 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<Position> allowedPositions;
-        if (depth == 0 || (allowedPositions = board.allowedPositions(player)).isEmpty()) {
+        final List<Position> 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<Position> allowedPositions = board.allowedPositions(this.max);
-        int alpha = -10;
+        final List<Position> 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 (file)
--- 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;