org/homelinux/largo/schach/KIBoard.java
author Markus Bröker <mbroeker@largo.homelinux.org>
Sun, 10 May 2009 16:04:42 +0200
changeset 7 93fe1f21e0d8
parent 3 673c7ef3411e
child 11 1afe167876fb
permissions -rw-r--r--
Class Variables have default values via default A class variable is initialized via default, it doesn't need explicit initialization
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     1
/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     2
 *   $Id: KIBoard.java 139 2008-04-25 05:02:55Z mbroeker $
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     3
 *  $URL: http://localhost/svn/eclipse/Schachspiel/trunk/org/homelinux/largo/schach/KIBoard.java $
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     4
 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     5
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     6
package org.homelinux.largo.schach;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     7
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     8
import org.homelinux.largo.games.board.Move;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
     9
import org.homelinux.largo.games.board.chessboard.ChessBoard;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    10
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    11
public class KIBoard extends ChessBoard {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    12
	static final long serialVersionUID = 200208;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    13
	static final int game_const = 500;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    14
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    15
	protected boolean SIMU_DEBUG  = false;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    16
	private boolean negate_estimation = false;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    17
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    18
	private Move bestMove;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    19
	private int desired_depth;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    20
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    21
	public KIBoard(int w, int h) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    22
		super(w, h);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    23
		desired_depth = -1;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    24
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    25
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    26
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    27
	 * Set the current DEBUG-Level:
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    28
	 * simu: print all valid, simulated moves
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    29
	 * undo: print all undos
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    30
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    31
	public void setDebug(boolean simu, boolean undo) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    32
		SIMU_DEBUG = simu;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    33
		UNDO_DEBUG = undo;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    34
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    35
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    36
	public boolean simu_debug() {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    37
		return SIMU_DEBUG;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    38
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    39
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    40
	public boolean undo_debug() {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    41
		return UNDO_DEBUG;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    42
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    43
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    44
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    45
	 * This function flips the sides: Player A maximizes and Player B minimizes
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    46
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    47
	public void negateEstimation(boolean b) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    48
		negate_estimation = b;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    49
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    50
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    51
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    52
	 * The Minimax-Algorithm works for TWO-PLAYER Games
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    53
	 * Player A minimizes, Player B maximizes
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    54
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    55
	public int estimateFunction() {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    56
		int i;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    57
		int white = 0;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    58
		int black = 0;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    59
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    60
		for(i=0;i<64;i++) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    61
			if (isWhite(i))
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    62
				white+=getValue(i);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    63
			if (isBlack(i))
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    64
				black+=getValue(i);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    65
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    66
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    67
		white+=controls("white");
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    68
		black+=controls("black");
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    69
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    70
		/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    71
		 * solves ticket #3
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    72
		 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    73
		if ( negate_estimation )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    74
			return white-black;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    75
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    76
		return black-white;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    77
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    78
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    79
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    80
	 * simulates and returns the next possible move for a Player or null, when no more moves are possible.
3
673c7ef3411e If clauses and passive are horrible.
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 0
diff changeset
    81
	 * The Turn will flip automatically if "simulate(...)" finds a valid move.
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    82
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    83
	Move simulate(int t, int o) {
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
    84
		Move move;
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    85
		int value;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    86
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    87
		if ( validTurn(o) ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    88
			while ( t < 64 ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    89
				if (!simulateMove(t, o) ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    90
					t++;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    91
					continue;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    92
				}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    93
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    94
				value = estimateFunction();
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    95
				if(SIMU_DEBUG)
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    96
					print("SIMU", t, o, value);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    97
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    98
				move = new Move(value, t, o);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
    99
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   100
				/* Flip Sides */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   101
				setBlacksTurn(!isBlacksTurn());
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   102
				return move;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   103
			}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   104
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   105
		return null;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   106
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   107
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   108
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   109
	 * AlphaBeta-Algorithm: the Maximizer
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   110
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   111
	int max_alpha_beta (int depth, int alpha, int beta) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   112
		int moveValue;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   113
		int o, t;
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
   114
		Move move;
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   115
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   116
		if ( desired_depth == -1 )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   117
			desired_depth = depth;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   118
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   119
		for (o = 0; o < 64; o++) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   120
			t=0;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   121
			while ( (move=simulate(t, o)) != null ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   122
				/* particular move from black */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   123
				t = move.target;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   124
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   125
				if ( depth == 0 || Math.abs(move.value) > game_const )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   126
					moveValue = move.value;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   127
				else /* best next move */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   128
					moveValue = min_alpha_beta(depth-1, alpha, beta);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   129
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   130
				undo();
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   131
				t++;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   132
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   133
				if ( moveValue >= beta )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   134
					return beta;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   135
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   136
				if ( moveValue > alpha ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   137
					alpha = moveValue;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   138
					if ( depth == desired_depth )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   139
						bestMove = move;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   140
				}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   141
			}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   142
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   143
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   144
		return alpha;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   145
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   146
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   147
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   148
	 * AlphaBeta-Algorithm: the Minimizer
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   149
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   150
	int min_alpha_beta(int depth, int alpha, int beta) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   151
		int moveValue;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   152
		int o, t;
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
   153
		Move move;
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   154
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   155
		for (o = 0; o < 64; o++) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   156
			t=0;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   157
			while ( (move=simulate(t, o)) != null ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   158
				/* particular move from white */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   159
				t = move.target;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   160
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   161
				if ( depth == 0 || Math.abs(move.value) > game_const )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   162
					moveValue = move.value;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   163
				else /* best next move */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   164
					moveValue = max_alpha_beta(depth-1, alpha, beta);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   165
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   166
				undo();
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   167
				t++;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   168
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   169
				if ( moveValue <= alpha )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   170
					return alpha;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   171
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   172
				if ( moveValue < beta )
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   173
					beta = moveValue;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   174
			}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   175
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   176
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   177
		return beta;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   178
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   179
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   180
	/**
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   181
	 * Evaluates the next, best Move after search_depth half-moves.
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   182
	 * When the Machine has Black, set negateEstimation(false);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   183
	 * When the Machine has White, set negateEstimation(true);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   184
	 */
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   185
	public boolean doBestMove(int search_depth) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   186
		int value;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   187
		desired_depth = -1;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   188
		bestMove = null;
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
   189
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   190
		value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   191
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   192
		if ( bestMove == null ) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   193
			System.err.println("Computing once more...");
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
   194
			value = max_alpha_beta(--search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   195
			if (bestMove == null) {
7
93fe1f21e0d8 Class Variables have default values via default
Markus Bröker <mbroeker@largo.homelinux.org>
parents: 3
diff changeset
   196
				System.out.println("Check Mate " + value);
0
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   197
				return false;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   198
			}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   199
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   200
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   201
		if (doMove(bestMove.target, bestMove.origin)) {
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   202
			print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   203
			return true;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   204
		}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   205
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   206
		print("Check Mate", bestMove.target, bestMove.origin, bestMove.value);
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   207
		return false;
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   208
	}
e0dbaef72362 svn copy of the chess engine
Markus Bröker <mbroeker@largo.homelinux.org>
parents:
diff changeset
   209
}