+
−/**
+
− *   $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 = 250408;
+
−	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;
+
−	}
+
−}