7 |
7 |
8 import org.homelinux.largo.games.board.Move; |
8 import org.homelinux.largo.games.board.Move; |
9 import org.homelinux.largo.games.board.chessboard.ChessBoard; |
9 import org.homelinux.largo.games.board.chessboard.ChessBoard; |
10 |
10 |
11 public class KIBoard extends ChessBoard { |
11 public class KIBoard extends ChessBoard { |
12 static final long serialVersionUID = 200208; |
12 static final long serialVersionUID = 200208; |
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 else if (isBlack(i)) |
63 else if (isBlack(i)) |
63 black += getValue(i); |
64 black+=getValue(i); |
64 } |
65 } |
65 |
66 |
66 // Bewerte Entwicklung, Anzahl der Steine |
67 // Bewerte Entwicklung, Anzahl der Steine |
67 // Das hier ist alles zu lahm... |
68 // Das hier ist alles zu lahm... |
68 white += controls("white"); |
69 white+=controls("white"); |
69 black += controls("black"); |
70 black+=controls("black"); |
70 |
71 |
71 /** |
72 /** |
72 * solves ticket #3 |
73 * solves ticket #3 |
73 */ |
74 */ |
74 if (negate_estimation) |
75 if ( negate_estimation ) |
75 return white - black; |
76 return white-black; |
76 |
77 |
77 return black - white; |
78 return black-white; |
78 } |
79 } |
79 |
80 |
80 /** |
81 /** |
81 * simulates and returns the next possible move for a Player or null, when |
82 * simulates and returns the next possible move for a Player or null, when no more moves are possible. |
82 * no more moves are possible. The Turn will flip automatically if |
83 * The Turn will flip automatically if "simulate(...)" finds a valid move. |
83 * "simulate(...)" finds a valid move. |
84 */ |
84 */ |
85 Move simulate(int t, int o) { |
85 Move simulate(int t, int o) { |
86 Move move; |
86 Move move; |
87 int value; |
87 int value; |
88 |
88 |
89 if ( validTurn(o) ) { |
89 if (validTurn(o)) { |
90 while ( t < 64 ) { |
90 while (t < 64) { |
91 if (!simulateMove(t, o) ) { |
91 if (!simulateMove(t, o)) { |
92 t++; |
92 t++; |
93 continue; |
93 continue; |
94 } |
94 } |
95 |
95 |
96 value = estimateFunction(); |
96 value = estimateFunction(); |
97 if(SIMU_DEBUG) |
97 if (SIMU_DEBUG) |
98 print("SIMU", t, o, value); |
98 print("SIMU", t, o, value); |
99 |
99 |
100 move = new Move(value, t, o); |
100 move = new Move(value, t, o); |
101 |
101 |
102 /* Flip Sides */ |
102 /* Flip Sides */ |
103 setBlacksTurn(!isBlacksTurn()); |
103 setBlacksTurn(!isBlacksTurn()); |
104 return move; |
104 return move; |
105 } |
105 } |
106 } |
106 } |
107 return null; |
107 return null; |
108 } |
108 } |
109 |
109 |
110 /** |
110 /** |
111 * AlphaBeta-Algorithm: the Maximizer |
111 * AlphaBeta-Algorithm: the Maximizer |
112 */ |
112 */ |
113 int max_alpha_beta (int depth, int alpha, int beta) { |
113 int max_alpha_beta(int depth, int alpha, int beta) { |
114 int moveValue; |
114 int moveValue; |
115 int o, t; |
115 int o, t; |
116 Move move; |
116 Move move; |
117 |
117 |
118 if ( desired_depth == -1 ) |
118 if (desired_depth == -1) |
119 desired_depth = depth; |
119 desired_depth = depth; |
120 |
120 |
121 for (o = 0; o < 64; o++) { |
121 for (o = 0; o < 64; o++) { |
122 t=0; |
122 t = 0; |
123 while ( (move=simulate(t, o)) != null ) { |
123 while ((move = simulate(t, o)) != null) { |
124 /* particular move from black */ |
124 /* particular move from black */ |
125 t = move.target; |
125 t = move.target; |
126 |
126 |
127 if ( depth == 0 || Math.abs(move.value) > game_const ) |
127 if (depth == 0 || Math.abs(move.value) > game_const) |
128 moveValue = move.value; |
128 moveValue = move.value; |
129 else /* best next move */ |
129 else |
130 moveValue = min_alpha_beta(depth-1, alpha, beta); |
130 /* best next move */ |
131 |
131 moveValue = min_alpha_beta(depth - 1, alpha, beta); |
132 undo(); |
132 |
133 t++; |
133 undo(); |
134 |
134 t++; |
135 if ( moveValue >= beta ) |
135 |
136 return beta; |
136 if (moveValue >= beta) |
137 |
137 return beta; |
138 if ( moveValue > alpha ) { |
138 |
139 alpha = moveValue; |
139 if (moveValue > alpha) { |
140 if ( depth == desired_depth ) |
140 alpha = moveValue; |
141 bestMove = move; |
141 if (depth == desired_depth) |
142 } |
142 bestMove = move; |
143 } |
143 } |
144 } |
144 } |
145 |
145 } |
146 return alpha; |
146 |
147 } |
147 return alpha; |
148 |
148 } |
149 /** |
149 |
150 * AlphaBeta-Algorithm: the Minimizer |
150 /** |
151 */ |
151 * AlphaBeta-Algorithm: the Minimizer |
152 int min_alpha_beta(int depth, int alpha, int beta) { |
152 */ |
153 int moveValue; |
153 int min_alpha_beta(int depth, int alpha, int beta) { |
154 int o, t; |
154 int moveValue; |
155 Move move; |
155 int o, t; |
156 |
156 Move move; |
157 for (o = 0; o < 64; o++) { |
157 |
158 t=0; |
158 for (o = 0; o < 64; o++) { |
159 while ( (move=simulate(t, o)) != null ) { |
159 t = 0; |
160 /* particular move from white */ |
160 while ((move = simulate(t, o)) != null) { |
161 t = move.target; |
161 /* particular move from white */ |
162 |
162 t = move.target; |
163 if ( depth == 0 || Math.abs(move.value) > game_const ) |
163 |
164 moveValue = move.value; |
164 if (depth == 0 || Math.abs(move.value) > game_const) |
165 else /* best next move */ |
165 moveValue = move.value; |
166 moveValue = max_alpha_beta(depth-1, alpha, beta); |
166 else |
167 |
167 /* best next move */ |
168 undo(); |
168 moveValue = max_alpha_beta(depth - 1, alpha, beta); |
169 t++; |
169 |
170 |
170 undo(); |
171 if ( moveValue <= alpha ) |
171 t++; |
172 return alpha; |
172 |
173 |
173 if (moveValue <= alpha) |
174 if ( moveValue < beta ) |
174 return alpha; |
175 beta = moveValue; |
175 |
176 } |
176 if (moveValue < beta) |
177 } |
177 beta = moveValue; |
178 |
178 } |
179 return beta; |
179 } |
180 } |
180 |
181 |
181 return beta; |
182 /** |
182 } |
183 * Evaluates the next, best Move after search_depth half-moves. |
183 |
184 * When the Machine has Black, set negateEstimation(false); |
184 /** |
185 * When the Machine has White, set negateEstimation(true); |
185 * Evaluates the next, best Move after search_depth half-moves. When the |
186 */ |
186 * Machine has Black, set negateEstimation(false); When the Machine has |
187 public boolean doBestMove(int search_depth) { |
187 * White, set negateEstimation(true); |
188 int value; |
188 */ |
189 desired_depth = -1; |
189 public boolean doBestMove(int search_depth) { |
190 bestMove = null; |
190 int value; |
191 |
191 desired_depth = -1; |
192 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
192 bestMove = null; |
193 |
193 |
194 if ( bestMove == null ) { |
194 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
195 System.err.println("Computing once more..."); |
195 |
196 value = max_alpha_beta(--search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
196 if (bestMove == null) { |
197 if (bestMove == null) { |
197 System.err.println("Computing once more..."); |
198 System.out.println("Check Mate " + value); |
198 value = max_alpha_beta(--search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
199 return false; |
199 if (bestMove == null) { |
200 } |
200 System.out.println("Check Mate " + value); |
201 } |
201 return false; |
202 |
202 } |
203 if (doMove(bestMove.target, bestMove.origin)) { |
203 } |
204 print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value); |
204 |
205 return true; |
205 if (doMove(bestMove.target, bestMove.origin)) { |
206 } |
206 print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value); |
207 |
207 return true; |
208 print("Check Mate", bestMove.target, bestMove.origin, bestMove.value); |
208 } |
209 return false; |
209 |
210 } |
210 print("Check Mate", bestMove.target, bestMove.origin, bestMove.value); |
|
211 return false; |
|
212 } |
211 } |
213 } |