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 = 1L; |
12 static final long serialVersionUID = 1L; |
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: simu: print all valid, simulated moves undo: |
27 * Set the current DEBUG-Level: simu: print all valid, simulated moves undo: |
28 * print all undos |
28 * print all undos |
29 */ |
29 */ |
30 public void setDebug(boolean simu, boolean undo) { |
30 public void setDebug(boolean simu, boolean undo) { |
31 SIMU_DEBUG = simu; |
31 SIMU_DEBUG = simu; |
32 UNDO_DEBUG = undo; |
32 UNDO_DEBUG = undo; |
33 } |
33 } |
34 |
34 |
35 public boolean simu_debug() { |
35 public boolean simu_debug() { |
36 return SIMU_DEBUG; |
36 return SIMU_DEBUG; |
37 } |
37 } |
38 |
38 |
39 public boolean undo_debug() { |
39 public boolean undo_debug() { |
40 return UNDO_DEBUG; |
40 return UNDO_DEBUG; |
41 } |
41 } |
42 |
42 |
43 /** |
43 /** |
44 * This function flips the sides: Player A maximizes and Player B minimizes |
44 * This function flips the sides: Player A maximizes and Player B minimizes |
45 */ |
45 */ |
46 public void negateEstimation(boolean b) { |
46 public void negateEstimation(boolean b) { |
47 negate_estimation = b; |
47 negate_estimation = b; |
48 } |
48 } |
49 |
49 |
50 /** |
50 /** |
51 * The Minimax-Algorithm works for TWO-PLAYER Games Player A minimizes, |
51 * The Minimax-Algorithm works for TWO-PLAYER Games Player A minimizes, |
52 * Player B maximizes |
52 * Player B maximizes |
53 */ |
53 */ |
54 public int estimateFunction() { |
54 public int estimateFunction() { |
55 int i; |
55 int i; |
56 int white = 0; |
56 int white = 0; |
57 int black = 0; |
57 int black = 0; |
58 |
58 |
59 for (i = 0; i < 64; i++) { |
59 for (i = 0; i < 64; i++) { |
60 if (isWhite(i)) |
60 if (isWhite(i)) |
61 white += getValue(i); |
61 white += getValue(i); |
62 else if (isBlack(i)) |
62 else if (isBlack(i)) |
63 black += getValue(i); |
63 black += getValue(i); |
64 } |
64 } |
65 |
65 |
66 // Bewerte Entwicklung, Anzahl der Steine |
66 // Bewerte Entwicklung, Anzahl der Steine |
67 // Das hier ist alles zu lahm... |
67 // Das hier ist alles zu lahm... |
68 white += controls("white"); |
68 white += controls("white"); |
69 black += controls("black"); |
69 black += controls("black"); |
70 |
70 |
71 /** |
71 /** |
72 * solves ticket #3 |
72 * solves ticket #3 |
73 */ |
73 */ |
74 if (negate_estimation) |
74 if (negate_estimation) |
75 return white - black; |
75 return white - black; |
76 |
76 |
77 return black - white; |
77 return black - white; |
78 } |
78 } |
79 |
79 |
80 /** |
80 /** |
81 * simulates and returns the next possible move for a Player or null, when |
81 * simulates and returns the next possible move for a Player or null, when |
82 * no more moves are possible. The Turn will flip automatically if |
82 * no more moves are possible. The Turn will flip automatically if |
83 * "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 |
129 else |
130 /* best next move */ |
130 /* best next move */ |
131 moveValue = min_alpha_beta(depth - 1, alpha, beta); |
131 moveValue = min_alpha_beta(depth - 1, alpha, beta); |
132 |
132 |
133 undo(); |
133 undo(); |
134 t++; |
134 t++; |
135 |
135 |
136 if (moveValue >= beta) |
136 if (moveValue >= beta) |
137 return beta; |
137 return beta; |
138 |
138 |
139 if (moveValue > alpha) { |
139 if (moveValue > alpha) { |
140 alpha = moveValue; |
140 alpha = moveValue; |
141 if (depth == desired_depth) |
141 if (depth == desired_depth) |
142 bestMove = move; |
142 bestMove = move; |
143 } |
143 } |
144 } |
144 } |
145 } |
145 } |
146 |
146 |
147 return alpha; |
147 return alpha; |
148 } |
148 } |
149 |
149 |
150 /** |
150 /** |
151 * AlphaBeta-Algorithm: the Minimizer |
151 * AlphaBeta-Algorithm: the Minimizer |
152 */ |
152 */ |
153 int min_alpha_beta(int depth, int alpha, int beta) { |
153 int min_alpha_beta(int depth, int alpha, int beta) { |
154 int moveValue; |
154 int moveValue; |
155 int o, t; |
155 int o, t; |
156 Move move; |
156 Move move; |
157 |
157 |
158 for (o = 0; o < 64; o++) { |
158 for (o = 0; o < 64; o++) { |
159 t = 0; |
159 t = 0; |
160 while ((move = simulate(t, o)) != null) { |
160 while ((move = simulate(t, o)) != null) { |
161 /* particular move from white */ |
161 /* particular move from white */ |
162 t = move.target; |
162 t = move.target; |
163 |
163 |
164 if (depth == 0 || Math.abs(move.value) > game_const) |
164 if (depth == 0 || Math.abs(move.value) > game_const) |
165 moveValue = move.value; |
165 moveValue = move.value; |
166 else |
166 else |
167 /* best next move */ |
167 /* best next move */ |
168 moveValue = max_alpha_beta(depth - 1, alpha, beta); |
168 moveValue = max_alpha_beta(depth - 1, alpha, beta); |
169 |
169 |
170 undo(); |
170 undo(); |
171 t++; |
171 t++; |
172 |
172 |
173 if (moveValue <= alpha) |
173 if (moveValue <= alpha) |
174 return alpha; |
174 return alpha; |
175 |
175 |
176 if (moveValue < beta) |
176 if (moveValue < beta) |
177 beta = moveValue; |
177 beta = moveValue; |
178 } |
178 } |
179 } |
179 } |
180 |
180 |
181 return beta; |
181 return beta; |
182 } |
182 } |
183 |
183 |
184 /** |
184 /** |
185 * Evaluates the next, best Move after search_depth half-moves. When the |
185 * Evaluates the next, best Move after search_depth half-moves. When the |
186 * Machine has Black, set negateEstimation(false); When the Machine has |
186 * Machine has Black, set negateEstimation(false); When the Machine has |
187 * White, set negateEstimation(true); |
187 * White, set negateEstimation(true); |
188 */ |
188 */ |
189 public boolean doBestMove(int search_depth) { |
189 public boolean doBestMove(int search_depth) { |
190 int value; |
190 int value; |
191 desired_depth = -1; |
191 desired_depth = -1; |
192 bestMove = null; |
192 bestMove = null; |
193 |
193 |
194 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
194 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
195 |
195 |
196 if (bestMove == null) { |
196 if (bestMove == null) { |
197 System.err.println("Computing once more..."); |
197 System.err.println("Computing once more..."); |
198 value = max_alpha_beta(--search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
198 value = max_alpha_beta(--search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
199 if (bestMove == null) { |
199 if (bestMove == null) { |
200 System.out.println("Check Mate " + value); |
200 System.out.println("Check Mate " + value); |
201 return false; |
201 return false; |
202 } |
202 } |
203 } |
203 } |
204 |
204 |
205 if (doMove(bestMove.target, bestMove.origin)) { |
205 if (doMove(bestMove.target, bestMove.origin)) { |
206 print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value); |
206 print(getColor(bestMove.target), bestMove.target, bestMove.origin, bestMove.value); |
207 return true; |
207 return true; |
208 } |
208 } |
209 |
209 |
210 print("Check Mate", bestMove.target, bestMove.origin, bestMove.value); |
210 print("Check Mate", bestMove.target, bestMove.origin, bestMove.value); |
211 return false; |
211 return false; |
212 } |
212 } |
213 } |
213 } |