1 /**

     2  *   $Id: KIBoard.java 139 2008-04-25 05:02:55Z mbroeker $

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

     4  */

     5 

     6 package org.homelinux.largo.schach;

     7 

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

     9 import org.homelinux.largo.games.board.chessboard.ChessBoard;

    10 

    11 public class KIBoard extends ChessBoard {

    12 	static final long serialVersionUID = 200208;

    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 		white+=controls("white");

    68 		black+=controls("black");

    69 

    70 		/**

    71 		 * solves ticket #3

    72 		 */

    73 		if ( negate_estimation )

    74 			return white-black;

    75 

    76 		return black-white;

    77 	}

    78 

    79 	/**

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

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

    82 	 */

    83 	Move simulate(int t, int o) {

    84 		Move move = null;

    85 		int value;

    86 

    87 		if ( validTurn(o) ) {

    88 			while ( t < 64 ) {

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

    90 					t++;

    91 					continue;

    92 				}

    93 

    94 				value = estimateFunction();

    95 				if(SIMU_DEBUG)

    96 					print("SIMU", t, o, value);

    97 

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

    99 

   100 				/* Flip Sides */

   101 				setBlacksTurn(!isBlacksTurn());

   102 				return move;

   103 			}

   104 		}

   105 		return null;

   106 	}

   107 

   108 	/**

   109 	 * AlphaBeta-Algorithm: the Maximizer

   110 	 */

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

   112 		int moveValue;

   113 		int o, t;

   114 		Move move = null;

   115 

   116 		if ( desired_depth == -1 )

   117 			desired_depth = depth;

   118 

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

   120 			t=0;

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

   122 				/* particular move from black */

   123 				t = move.target;

   124 

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

   126 					moveValue = move.value;

   127 				else /* best next move */

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

   129 

   130 				undo();

   131 				t++;

   132 

   133 				if ( moveValue >= beta )

   134 					return beta;

   135 

   136 				if ( moveValue > alpha ) {

   137 					alpha = moveValue;

   138 					if ( depth == desired_depth )

   139 						bestMove = move;

   140 				}

   141 			}

   142 		}

   143 

   144 		return alpha;

   145 	}

   146 

   147 	/**

   148 	 * AlphaBeta-Algorithm: the Minimizer

   149 	 */

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

   151 		int moveValue;

   152 		int o, t;

   153 		Move move = null;

   154 

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

   156 			t=0;

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

   158 				/* particular move from white */

   159 				t = move.target;

   160 

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

   162 					moveValue = move.value;

   163 				else /* best next move */

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

   165 

   166 				undo();

   167 				t++;

   168 

   169 				if ( moveValue <= alpha )

   170 					return alpha;

   171 

   172 				if ( moveValue < beta )

   173 					beta = moveValue;

   174 			}

   175 		}

   176 

   177 		return beta;

   178 	}

   179 

   180 	/**

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

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

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

   184 	 */

   185 	public boolean doBestMove(int search_depth) {

   186 		int value;

   187 

   188 		desired_depth = -1;

   189 		bestMove = null;

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

   191 

   192 		if ( bestMove == null ) {

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

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

   195 			if (bestMove == null) {

   196 				System.out.println("Check Mate");

   197 				return false;

   198 			}

   199 		}

   200 

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

   202 			print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value);

   203 			return true;

   204 		}

   205 

   206 		print("Check Mate", bestMove.target, bestMove.origin, bestMove.value);

   207 		return false;

   208 	}

   209 }