diff --git a/org/homelinux/largo/checkers/KIBoard.java b/org/homelinux/largo/checkers/KIBoard.java new file mode 100644 --- /dev/null +++ b/org/homelinux/largo/checkers/KIBoard.java @@ -0,0 +1,202 @@ +/** + * $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 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(); + 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"); + return false; + } + } + + if (doMove(bestMove.target, bestMove.origin)) { + System.out.println("Next Move"); + return true; + } + + return false; + } +}