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.checkersboard.CheckersBoard; |
9 import org.homelinux.largo.games.board.checkersboard.CheckersBoard; |
10 |
10 |
11 public class KIBoard extends CheckersBoard { |
11 public class KIBoard extends CheckersBoard { |
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 if (isBlack(i)) |
62 if (isBlack(i)) |
63 black += getValue(i); |
63 black += getValue(i); |
64 } |
64 } |
65 |
65 |
66 /** |
66 /** |
67 * solves ticket #3 |
67 * solves ticket #3 |
68 */ |
68 */ |
69 if (negate_estimation) |
69 if (negate_estimation) |
70 return white - black; |
70 return white - black; |
71 |
71 |
72 return black - white; |
72 return black - white; |
73 } |
73 } |
74 |
74 |
75 /** |
75 /** |
76 * simulates and returns the next possible move for a Player or null, when |
76 * simulates and returns the next possible move for a Player or null, when |
77 * no more moves are possible. The Turn will flip automatically if |
77 * no more moves are possible. The Turn will flip automatically if |
78 * "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 |
121 else |
122 /* best next move */ |
122 /* best next move */ |
123 moveValue = min_alpha_beta(depth - 1, alpha, beta); |
123 moveValue = min_alpha_beta(depth - 1, alpha, beta); |
124 |
124 |
125 undo(); |
125 undo(); |
126 t++; |
126 t++; |
127 |
127 |
128 if (moveValue >= beta) |
128 if (moveValue >= beta) |
129 return beta; |
129 return beta; |
130 |
130 |
131 if (moveValue > alpha) { |
131 if (moveValue > alpha) { |
132 alpha = moveValue; |
132 alpha = moveValue; |
133 if (depth == desired_depth) |
133 if (depth == desired_depth) |
134 bestMove = move; |
134 bestMove = move; |
135 } |
135 } |
136 } |
136 } |
137 } |
137 } |
138 |
138 |
139 return alpha; |
139 return alpha; |
140 } |
140 } |
141 |
141 |
142 /** |
142 /** |
143 * AlphaBeta-Algorithm: the Minimizer |
143 * AlphaBeta-Algorithm: the Minimizer |
144 */ |
144 */ |
145 int min_alpha_beta(int depth, int alpha, int beta) { |
145 int min_alpha_beta(int depth, int alpha, int beta) { |
146 int moveValue; |
146 int moveValue; |
147 int o, t; |
147 int o, t; |
148 Move move = null; |
148 Move move = null; |
149 |
149 |
150 for (o = 0; o < 64; o++) { |
150 for (o = 0; o < 64; o++) { |
151 t = 0; |
151 t = 0; |
152 while ((move = simulate(t, o)) != null) { |
152 while ((move = simulate(t, o)) != null) { |
153 /* particular move from white */ |
153 /* particular move from white */ |
154 t = move.target; |
154 t = move.target; |
155 |
155 |
156 if (depth == 0 || Math.abs(move.value) > game_const) |
156 if (depth == 0 || Math.abs(move.value) > game_const) |
157 moveValue = move.value; |
157 moveValue = move.value; |
158 else |
158 else |
159 /* best next move */ |
159 /* best next move */ |
160 moveValue = max_alpha_beta(depth - 1, alpha, beta); |
160 moveValue = max_alpha_beta(depth - 1, alpha, beta); |
161 |
161 |
162 undo(); |
162 undo(); |
163 t++; |
163 t++; |
164 |
164 |
165 if (moveValue <= alpha) |
165 if (moveValue <= alpha) |
166 return alpha; |
166 return alpha; |
167 |
167 |
168 if (moveValue < beta) |
168 if (moveValue < beta) |
169 beta = moveValue; |
169 beta = moveValue; |
170 } |
170 } |
171 } |
171 } |
172 |
172 |
173 return beta; |
173 return beta; |
174 } |
174 } |
175 |
175 |
176 /** |
176 /** |
177 * Evaluates the next, best Move after search_depth half-moves. When the |
177 * Evaluates the next, best Move after search_depth half-moves. When the |
178 * Machine has Black, set negateEstimation(false); When the Machine has |
178 * Machine has Black, set negateEstimation(false); When the Machine has |
179 * White, set negateEstimation(true); |
179 * White, set negateEstimation(true); |
180 */ |
180 */ |
181 public boolean doBestMove(int search_depth) { |
181 public boolean doBestMove(int search_depth) { |
182 int value; |
182 int value; |
183 |
183 |
184 desired_depth = -1; |
184 desired_depth = -1; |
185 bestMove = null; |
185 bestMove = null; |
186 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
186 value = max_alpha_beta(search_depth, Integer.MIN_VALUE, Integer.MAX_VALUE); |
187 |
187 |
188 if (bestMove == null) { |
188 if (bestMove == null) { |
189 System.err.println("Computing once more..."); |
189 System.err.println("Computing once more..."); |
190 value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE); |
190 value = max_alpha_beta(1, Integer.MIN_VALUE, Integer.MAX_VALUE); |
191 if (bestMove == null) { |
191 if (bestMove == null) { |
192 System.out.println("Finito " + value); |
192 System.out.println("Finito " + value); |
193 return false; |
193 return false; |
194 } |
194 } |
195 } |
195 } |
196 |
196 |
197 if (doMove(bestMove.target, bestMove.origin)) { |
197 if (doMove(bestMove.target, bestMove.origin)) { |
198 System.out.println("Next Move"); |
198 System.out.println("Next Move"); |
199 return true; |
199 return true; |
200 } |
200 } |
201 |
201 |
202 return false; |
202 return false; |
203 } |
203 } |
204 } |
204 } |