org/homelinux/largo/checkers/KIBoard.java
author Markus Bröker<broeker.markus@googlemail.com>
Fri, 27 Jan 2017 21:25:15 +0100
changeset 16 55b0d5006e7b
parent 14 f12f77aa13b2
permissions -rw-r--r--
Sourcecode neu formatiert und ins Jahr 2017 migriert Eine 9 Jahre alte Software konnte mit einigen Korrekturen wieder belebt werden.

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