1 /**

     2  *   $Id: KIBoard.java 144 2008-04-25 13:09:35Z mbroeker $

     3  *  $URL: http://localhost/svn/eclipse/Schachspiel/trunk/org/homelinux/largo/checkers/KIBoard.java $

     4  */

     5 

     6 package org.homelinux.largo.checkers;

     7 

     8 import org.homelinux.largo.games.board.Move;

     9 import org.homelinux.largo.games.board.checkersboard.CheckersBoard;

    10 

    11 public class KIBoard extends CheckersBoard {

    12 	static final long serialVersionUID = 250408;

    13 	static final int game_const = 500;

    14 

    15 	protected boolean SIMU_DEBUG  = false;

    16 	private boolean negate_estimation = false;

    17 

    18 	private Move bestMove;

    19 	private int desired_depth;

    20 

    21 	public KIBoard(int w, int h) {

    22 		super(w, h);

    23 		desired_depth = -1;

    24 	}

    25 

    26 	/**

    27 	 * Set the current DEBUG-Level:

    28 	 * simu: print all valid, simulated moves

    29 	 * undo: print all undos

    30 	 */

    31 	public void setDebug(boolean simu, boolean undo) {

    32 		SIMU_DEBUG = simu;

    33 		UNDO_DEBUG = undo;

    34 	}

    35 

    36 	public boolean simu_debug() {

    37 		return SIMU_DEBUG;

    38 	}

    39 

    40 	public boolean undo_debug() {

    41 		return UNDO_DEBUG;

    42 	}

    43 

    44 	/**

    45 	 * This function flips the sides: Player A maximizes and Player B minimizes

    46 	 */

    47 	public void negateEstimation(boolean b) {

    48 		negate_estimation = b;

    49 	}

    50 

    51 	/**

    52 	 * The Minimax-Algorithm works for TWO-PLAYER Games

    53 	 * Player A minimizes, Player B maximizes

    54 	 */

    55 	public int estimateFunction() {

    56 		int i;

    57 		int white = 0;

    58 		int black = 0;

    59 

    60 		for(i=0;i<64;i++) {

    61 			if (isWhite(i))

    62 				white+=getValue(i);

    63 			if (isBlack(i))

    64 				black+=getValue(i);

    65 		}

    66 

    67 		/**

    68 		 * solves ticket #3

    69 		 */

    70 		if ( negate_estimation )

    71 			return white-black;

    72 

    73 		return black-white;

    74 	}

    75 

    76 	/**

    77 	 * simulates and returns the next possible move for a Player or null, when no more moves are possible.

    78 	 * The Turn is flipped automatically if "simulate(...)" will find a valid move.

    79 	 */

    80 	Move simulate(int t, int o) {

    81 		Move move = null;

    82 		int value;

    83 

    84 		if ( validTurn(o) ) {

    85 			while ( t < 64 ) {

    86 				if (!simulateMove(t, o) ) {

    87 					t++;

    88 					continue;

    89 				}

    90 

    91 				value = estimateFunction();

    92 				move = new Move(value, t, o);

    93 

    94 				/* Flip Sides */

    95 				setBlacksTurn(!isBlacksTurn());

    96 				return move;

    97 			}

    98 		}

    99 		return null;

   100 	}

   101 

   102 	/**

   103 	 * AlphaBeta-Algorithm: the Maximizer

   104 	 */

   105 	int max_alpha_beta (int depth, int alpha, int beta) {

   106 		int moveValue;

   107 		int o, t;

   108 		Move move = null;

   109 

   110 		if ( desired_depth == -1 )

   111 			desired_depth = depth;

   112 

   113 		for (o = 0; o < 64; o++) {

   114 			t=0;

   115 			while ( (move=simulate(t, o)) != null ) {

   116 				/* particular move from black */

   117 				t = move.target;

   118 

   119 				if ( depth == 0 || Math.abs(move.value) > game_const )

   120 					moveValue = move.value;

   121 				else /* best next move */

   122 					moveValue = min_alpha_beta(depth-1, alpha, beta);

   123 

   124 				undo();

   125 				t++;

   126 

   127 				if ( moveValue >= beta )

   128 					return beta;

   129 

   130 				if ( moveValue > alpha ) {

   131 					alpha = moveValue;

   132 					if ( depth == desired_depth )

   133 						bestMove = move;

   134 				}

   135 			}

   136 		}

   137 

   138 		return alpha;

   139 	}

   140 

   141 	/**

   142 	 * AlphaBeta-Algorithm: the Minimizer

   143 	 */

   144 	int min_alpha_beta(int depth, int alpha, int beta) {

   145 		int moveValue;

   146 		int o, t;

   147 		Move move = null;

   148 

   149 		for (o = 0; o < 64; o++) {

   150 			t=0;

   151 			while ( (move=simulate(t, o)) != null ) {

   152 				/* particular move from white */

   153 				t = move.target;

   154 

   155 				if ( depth == 0 || Math.abs(move.value) > game_const )

   156 					moveValue = move.value;

   157 				else /* best next move */

   158 					moveValue = max_alpha_beta(depth-1, alpha, beta);

   159 

   160 				undo();

   161 				t++;

   162 

   163 				if ( moveValue <= alpha )

   164 					return alpha;

   165 

   166 				if ( moveValue < beta )

   167 					beta = moveValue;

   168 			}

   169 		}

   170 

   171 		return beta;

   172 	}

   173 

   174 	/**

   175 	 * Evaluates the next, best Move after search_depth half-moves.

   176 	 * When the Machine has Black, set negateEstimation(false);

   177 	 * When the Machine has White, set negateEstimation(true);

   178 	 */

   179 	public boolean doBestMove(int search_depth) {

   180 		int value;

   181 

   182 		desired_depth = -1;

   183 		bestMove = null;

   184 		value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);

   185 

   186 		if ( bestMove == null ) {

   187 			System.err.println("Computing once more...");

   188 			value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE);

   189 			if (bestMove == null) {

   190 				System.out.println("Finito");

   191 				return false;

   192 			}

   193 		}

   194 

   195 		if (doMove(bestMove.target, bestMove.origin)) {

   196 			System.out.println("Next Move");

   197 			return true;

   198 		}

   199 

   200 		return false;

   201 	}

   202 }