org/homelinux/largo/schach/KIBoard.java
author Markus Bröker <mbroeker@largo.homelinux.org>
Sun, 08 Feb 2009 07:47:39 +0100
changeset 5 42da09368d71
parent 3 673c7ef3411e
child 7 93fe1f21e0d8
permissions -rw-r--r--
Platform Independend Newlines Java uses %n for platform independend newlines \r\n on windows, \n on linux and so on...

/**
 *   $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 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();
				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;
	}
}