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 = 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 } |
202 } |
204 } |