org/homelinux/largo/schach/KIBoard.java
changeset 0 e0dbaef72362
child 3 673c7ef3411e
new file mode 100644
--- /dev/null
+++ b/org/homelinux/largo/schach/KIBoard.java
@@ -0,0 +1,209 @@
+/**
+ *   $Id: KIBoard.java 139 2008-04-25 05:02:55Z mbroeker $
+ *  $URL: http://localhost/svn/eclipse/Schachspiel/trunk/org/homelinux/largo/schach/KIBoard.java $
+ */
+
+package org.homelinux.largo.schach;
+
+import org.homelinux.largo.games.board.Move;
+import org.homelinux.largo.games.board.chessboard.ChessBoard;
+
+public class KIBoard extends ChessBoard {
+	static final long serialVersionUID = 200208;
+	static final int game_const = 500;
+
+	protected boolean SIMU_DEBUG  = false;
+	private boolean negate_estimation = false;
+
+	private Move bestMove;
+	private int desired_depth;
+
+	public KIBoard(int w, int h) {
+		super(w, h);
+		desired_depth = -1;
+	}
+
+	/**
+	 * Set the current DEBUG-Level:
+	 * simu: print all valid, simulated moves
+	 * undo: print all undos
+	 */
+	public void setDebug(boolean simu, boolean undo) {
+		SIMU_DEBUG = simu;
+		UNDO_DEBUG = undo;
+	}
+
+	public boolean simu_debug() {
+		return SIMU_DEBUG;
+	}
+
+	public boolean undo_debug() {
+		return UNDO_DEBUG;
+	}
+
+	/**
+	 * This function flips the sides: Player A maximizes and Player B minimizes
+	 */
+	public void negateEstimation(boolean b) {
+		negate_estimation = b;
+	}
+
+	/**
+	 * The Minimax-Algorithm works for TWO-PLAYER Games
+	 * Player A minimizes, Player B maximizes
+	 */
+	public int estimateFunction() {
+		int i;
+		int white = 0;
+		int black = 0;
+
+		for(i=0;i<64;i++) {
+			if (isWhite(i))
+				white+=getValue(i);
+			if (isBlack(i))
+				black+=getValue(i);
+		}
+
+		white+=controls("white");
+		black+=controls("black");
+
+		/**
+		 * solves ticket #3
+		 */
+		if ( negate_estimation )
+			return white-black;
+
+		return black-white;
+	}
+
+	/**
+	 * simulates and returns the next possible move for a Player or null, when no more moves are possible.
+	 * The Turn is flipped automatically if "simulate(...)" will find a valid move.
+	 */
+	Move simulate(int t, int o) {
+		Move move = null;
+		int value;
+
+		if ( validTurn(o) ) {
+			while ( t < 64 ) {
+				if (!simulateMove(t, o) ) {
+					t++;
+					continue;
+				}
+
+				value = estimateFunction();
+				if(SIMU_DEBUG)
+					print("SIMU", t, o, value);
+
+				move = new Move(value, t, o);
+
+				/* Flip Sides */
+				setBlacksTurn(!isBlacksTurn());
+				return move;
+			}
+		}
+		return null;
+	}
+
+	/**
+	 * AlphaBeta-Algorithm: the Maximizer
+	 */
+	int max_alpha_beta (int depth, int alpha, int beta) {
+		int moveValue;
+		int o, t;
+		Move move = null;
+
+		if ( desired_depth == -1 )
+			desired_depth = depth;
+
+		for (o = 0; o < 64; o++) {
+			t=0;
+			while ( (move=simulate(t, o)) != null ) {
+				/* particular move from black */
+				t = move.target;
+
+				if ( depth == 0 || Math.abs(move.value) > game_const )
+					moveValue = move.value;
+				else /* best next move */
+					moveValue = min_alpha_beta(depth-1, alpha, beta);
+
+				undo();
+				t++;
+
+				if ( moveValue >= beta )
+					return beta;
+
+				if ( moveValue > alpha ) {
+					alpha = moveValue;
+					if ( depth == desired_depth )
+						bestMove = move;
+				}
+			}
+		}
+
+		return alpha;
+	}
+
+	/**
+	 * AlphaBeta-Algorithm: the Minimizer
+	 */
+	int min_alpha_beta(int depth, int alpha, int beta) {
+		int moveValue;
+		int o, t;
+		Move move = null;
+
+		for (o = 0; o < 64; o++) {
+			t=0;
+			while ( (move=simulate(t, o)) != null ) {
+				/* particular move from white */
+				t = move.target;
+
+				if ( depth == 0 || Math.abs(move.value) > game_const )
+					moveValue = move.value;
+				else /* best next move */
+					moveValue = max_alpha_beta(depth-1, alpha, beta);
+
+				undo();
+				t++;
+
+				if ( moveValue <= alpha )
+					return alpha;
+
+				if ( moveValue < beta )
+					beta = moveValue;
+			}
+		}
+
+		return beta;
+	}
+
+	/**
+	 * Evaluates the next, best Move after search_depth half-moves.
+	 * When the Machine has Black, set negateEstimation(false);
+	 * When the Machine has White, set negateEstimation(true);
+	 */
+	public boolean doBestMove(int search_depth) {
+		int value;
+
+		desired_depth = -1;
+		bestMove = null;
+		value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
+
+		if ( bestMove == null ) {
+			System.err.println("Computing once more...");
+			value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE);
+			if (bestMove == null) {
+				System.out.println("Check Mate");
+				return false;
+			}
+		}
+
+		if (doMove(bestMove.target, bestMove.origin)) {
+			print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value);
+			return true;
+		}
+
+		print("Check Mate", bestMove.target, bestMove.origin, bestMove.value);
+		return false;
+	}
+}