12 	static final long serialVersionUID = 250408;

    12     static final long serialVersionUID = 250408;

    13 	static final int game_const = 500;

    13     static final int game_const = 500;

    14 

    14 

    15 	protected boolean SIMU_DEBUG  = false;

    15     protected boolean SIMU_DEBUG = false;

    16 	private boolean negate_estimation = false;

    16     private boolean negate_estimation = false;

    17 

    17 

    18 	private Move bestMove;

    18     private Move bestMove;

    19 	private int desired_depth;

    19     private int desired_depth;

    20 

    20 

    21 	public KIBoard(int w, int h) {

    21     public KIBoard(int w, int h) {

    22 		super(w, h);

    22         super(w, h);

    23 		desired_depth = -1;

    23         desired_depth = -1;

    24 	}

    24     }

    25 

    25 

    26 	/**

    26     /**

    27 	 * Set the current DEBUG-Level:

    27      * Set the current DEBUG-Level: simu: print all valid, simulated moves undo:

    28 	 * simu: print all valid, simulated moves

    28      * print all undos

    29 	 * undo: print all undos

    29      */

    30 	 */

    30     public void setDebug(boolean simu, boolean undo) {

    31 	public void setDebug(boolean simu, boolean undo) {

    31         SIMU_DEBUG = simu;

    32 		SIMU_DEBUG = simu;

    32         UNDO_DEBUG = undo;

    33 		UNDO_DEBUG = undo;

    33     }

    34 	}

    34 

    35 

    35     public boolean simu_debug() {

    36 	public boolean simu_debug() {

    36         return SIMU_DEBUG;

    37 		return SIMU_DEBUG;

    37     }

    38 	}

    38 

    39 

    39     public boolean undo_debug() {

    40 	public boolean undo_debug() {

    40         return UNDO_DEBUG;

    41 		return UNDO_DEBUG;

    41     }

    42 	}

    42 

    43 

    43     /**

    44 	/**

    44      * This function flips the sides: Player A maximizes and Player B minimizes

    45 	 * This function flips the sides: Player A maximizes and Player B minimizes

    45      */

    46 	 */

    46     public void negateEstimation(boolean b) {

    47 	public void negateEstimation(boolean b) {

    47         negate_estimation = b;

    48 		negate_estimation = b;

    48     }

    49 	}

    49 

    50 

    50     /**

    51 	/**

    51      * The Minimax-Algorithm works for TWO-PLAYER Games Player A minimizes,

    52 	 * The Minimax-Algorithm works for TWO-PLAYER Games

    52      * Player B maximizes

    53 	 * Player A minimizes, Player B maximizes

    53      */

    54 	 */

    54     public int estimateFunction() {

    55 	public int estimateFunction() {

    55         int i;

    56 		int i;

    56         int white = 0;

    57 		int white = 0;

    57         int black = 0;

    58 		int black = 0;

    58 

    59 

    59         for (i = 0; i < 64; i++) {

    60 		for(i=0;i<64;i++) {

    60             if (isWhite(i))

    61 			if (isWhite(i))

    61                 white += getValue(i);

    62 				white+=getValue(i);

    62             if (isBlack(i))

    63 			if (isBlack(i))

    63                 black += getValue(i);

    64 				black+=getValue(i);

    64         }

    65 		}

    65 

    66 

    66         /**

    67 		/**

    67          * solves ticket #3

    68 		 * solves ticket #3

    68          */

    69 		 */

    69         if (negate_estimation)

    70 		if ( negate_estimation )

    70             return white - black;

    71 			return white-black;

    71 

    72 

    72         return black - white;

    73 		return black-white;

    73     }

    74 	}

    74 

    75 

    75     /**

    76 	/**

    76      * simulates and returns the next possible move for a Player or null, when

    77 	 * simulates and returns the next possible move for a Player or null, when no more moves are possible.

    77      * no more moves are possible. The Turn will flip automatically if

    78 	 * The Turn will flip automatically if "simulate(...)" finds a valid move.

    78      * "simulate(...)" finds a valid move.

    79 	 */

    79      */

    80 	Move simulate(int t, int o) {

    80     Move simulate(int t, int o) {

    81 		Move move = null;

    81         Move move = null;

    82 		int value;

    82         int value;

    83 

    83 

    84 		if ( validTurn(o) ) {

    84         if (validTurn(o)) {

    85 			while ( t < 64 ) {

    85             while (t < 64) {

    86 				if (!simulateMove(t, o) ) {

    86                 if (!simulateMove(t, o)) {

    87 					t++;

    87                     t++;

    88 					continue;

    88                     continue;

    89 				}

    89                 }

    90 

    90 

    91 				value = estimateFunction();

    91                 value = estimateFunction();

    92 				move = new Move(value, t, o);

    92                 move = new Move(value, t, o);

    93 

    93 

    94 				/* Flip Sides */

    94                 /* Flip Sides */

    95 				setBlacksTurn(!isBlacksTurn());

    95                 setBlacksTurn(!isBlacksTurn());

    96 				return move;

    96                 return move;

    97 			}

    97             }

    98 		}

    98         }

    99 		return null;

    99         return null;

   100 	}

   100     }

   101 

   101 

   102 	/**

   102     /**

   103 	 * AlphaBeta-Algorithm: the Maximizer

   103      * AlphaBeta-Algorithm: the Maximizer

   104 	 */

   104      */

   105 	int max_alpha_beta (int depth, int alpha, int beta) {

   105     int max_alpha_beta(int depth, int alpha, int beta) {

   106 		int moveValue;

   106         int moveValue;

   107 		int o, t;

   107         int o, t;

   108 		Move move = null;

   108         Move move = null;

   109 

   109 

   110 		if ( desired_depth == -1 )

   110         if (desired_depth == -1)

   111 			desired_depth = depth;

   111             desired_depth = depth;

   112 

   112 

   113 		for (o = 0; o < 64; o++) {

   113         for (o = 0; o < 64; o++) {

   114 			t=0;

   114             t = 0;

   115 			while ( (move=simulate(t, o)) != null ) {

   115             while ((move = simulate(t, o)) != null) {

   116 				/* particular move from black */

   116                 /* particular move from black */

   117 				t = move.target;

   117                 t = move.target;

   118 

   118 

   119 				if ( depth == 0 || Math.abs(move.value) > game_const )

   119                 if (depth == 0 || Math.abs(move.value) > game_const)

   120 					moveValue = move.value;

   120                     moveValue = move.value;

   121 				else /* best next move */

   121                 else

   122 					moveValue = min_alpha_beta(depth-1, alpha, beta);

   122                     /* best next move */

   123 

   123                     moveValue = min_alpha_beta(depth - 1, alpha, beta);

   124 				undo();

   124 

   125 				t++;

   125                 undo();

   126 

   126                 t++;

   127 				if ( moveValue >= beta )

   127 

   128 					return beta;

   128                 if (moveValue >= beta)

   129 

   129                     return beta;

   130 				if ( moveValue > alpha ) {

   130 

   131 					alpha = moveValue;

   131                 if (moveValue > alpha) {

   132 					if ( depth == desired_depth )

   132                     alpha = moveValue;

   133 						bestMove = move;

   133                     if (depth == desired_depth)

   134 				}

   134                         bestMove = move;

   135 			}

   135                 }

   136 		}

   136             }

   137 

   137         }

   138 		return alpha;

   138 

   139 	}

   139         return alpha;

   140 

   140     }

   141 	/**

   141 

   142 	 * AlphaBeta-Algorithm: the Minimizer

   142     /**

   143 	 */

   143      * AlphaBeta-Algorithm: the Minimizer

   144 	int min_alpha_beta(int depth, int alpha, int beta) {

   144      */

   145 		int moveValue;

   145     int min_alpha_beta(int depth, int alpha, int beta) {

   146 		int o, t;

   146         int moveValue;

   147 		Move move = null;

   147         int o, t;

   148 

   148         Move move = null;

   149 		for (o = 0; o < 64; o++) {

   149 

   150 			t=0;

   150         for (o = 0; o < 64; o++) {

   151 			while ( (move=simulate(t, o)) != null ) {

   151             t = 0;

   152 				/* particular move from white */

   152             while ((move = simulate(t, o)) != null) {

   153 				t = move.target;

   153                 /* particular move from white */

   154 

   154                 t = move.target;

   155 				if ( depth == 0 || Math.abs(move.value) > game_const )

   155 

   156 					moveValue = move.value;

   156                 if (depth == 0 || Math.abs(move.value) > game_const)

   157 				else /* best next move */

   157                     moveValue = move.value;

   158 					moveValue = max_alpha_beta(depth-1, alpha, beta);

   158                 else

   159 

   159                     /* best next move */

   160 				undo();

   160                     moveValue = max_alpha_beta(depth - 1, alpha, beta);

   161 				t++;

   161 

   162 

   162                 undo();

   163 				if ( moveValue <= alpha )

   163                 t++;

   164 					return alpha;

   164 

   165 

   165                 if (moveValue <= alpha)

   166 				if ( moveValue < beta )

   166                     return alpha;

   167 					beta = moveValue;

   167 

   168 			}

   168                 if (moveValue < beta)

   169 		}

   169                     beta = moveValue;

   170 

   170             }

   171 		return beta;

   171         }

   172 	}

   172 

   173 

   173         return beta;

   174 	/**

   174     }

   175 	 * Evaluates the next, best Move after search_depth half-moves.

   175 

   176 	 * When the Machine has Black, set negateEstimation(false);

   176     /**

   177 	 * When the Machine has White, set negateEstimation(true);

   177      * Evaluates the next, best Move after search_depth half-moves. When the

   178 	 */

   178      * Machine has Black, set negateEstimation(false); When the Machine has

   179 	public boolean doBestMove(int search_depth) {

   179      * White, set negateEstimation(true);

   180 		int value;

   180      */

   181 

   181     public boolean doBestMove(int search_depth) {

   182 		desired_depth = -1;

   182         int value;

   183 		bestMove = null;

   183 

   184 		value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);

   184         desired_depth = -1;

   185 

   185         bestMove = null;

   186 		if ( bestMove == null ) {

   186         value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);

   187 			System.err.println("Computing once more...");

   187 

   188 			value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE);

   188         if (bestMove == null) {

   189 			if (bestMove == null) {

   189             System.err.println("Computing once more...");

   190 				System.out.println("Finito " + value);

   190             value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE);

   191 				return false;

   191             if (bestMove == null) {

   192 			}

   192                 System.out.println("Finito " + value);

   193 		}

   193                 return false;

   194 

   194             }

   195 		if (doMove(bestMove.target, bestMove.origin)) {

   195         }

   196 			System.out.println("Next Move");

   196 

   197 			return true;

   197         if (doMove(bestMove.target, bestMove.origin)) {

   198 		}

   198             System.out.println("Next Move");

   199 

   199             return true;

   200 		return false;

   200         }

   201 	}

   201 

   202         return false;

   203     }