+
−/**
+
− *   $Id: KIBoard.java 144 2008-04-25 13:09:35Z mbroeker $
+
− *  $URL: http://localhost/svn/eclipse/Schachspiel/trunk/org/homelinux/largo/checkers/KIBoard.java $
+
− */
+
−
+
−package org.homelinux.largo.checkers;
+
−
+
−import org.homelinux.largo.games.board.Move;
+
−import org.homelinux.largo.games.board.checkersboard.CheckersBoard;
+
−
+
−public class KIBoard extends CheckersBoard {
+
−	static final long serialVersionUID = 1L;
+
−	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);
+
−		}
+
−
+
−		/**
+
−		 * 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 will flip automatically if
+
−	 * "simulate(...)" finds 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();
+
−				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("Finito " + value);
+
−				return false;
+
−			}
+
−		}
+
−
+
−		if (doMove(bestMove.target, bestMove.origin)) {
+
−			System.out.println("Next Move");
+
−			return true;
+
−		}
+
−
+
−		return false;
+
−	}
+
−}