1 /*
2 * Biloba
3 * Copyright (C) 2004-2008 Guillaume Demougeot, Colin Leroy
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
18 */
19
20 /**
21 * Biloba - Q1 2005
22 * Game by Guillaume Demougeot <dmgt@wanadoo.fr>
23 * Code by Colin Leroy <colin@colino.net>
24 *
25 * This file contains all the AI-related code.
26 */
27
28 #include <SDL.h>
29 #include <SDL_thread.h>
30 #include <stdlib.h>
31 #include <time.h>
32
33 #include "utils.h"
34 #include "local_input.h"
35 #include "tile.h"
36 #include "net.h"
37 #include "computer.h"
38 #include "board.h"
39 #include "player.h"
40 #include "llist.h"
41 #include "logic.h"
42
43 #undef IA_DEBUG
44
45 static Pawn *selected_pawn = NULL;
46 static Tile *best_destination = NULL;
47 static Tile *best_destination_after_middle = NULL;
48
49 static int first = FALSE;
50
computer_defend(Player * player,LList * allowed,int immediate_defense)51 static Tile *computer_defend(Player *player, LList *allowed, int immediate_defense)
52 {
53 /* get the best pawn to move so that it won't be eaten */
54 LList *pawns;
55 LList *cur;
56 Tile *best = NULL;
57 LList *max_eaten_pawns = NULL;
58 int max_eaten = 0;
59 int search_now = (immediate_defense > 0);
60 int center_ok = can_move_on_center();
61
62 if (allowed)
63 pawns = llist_copy(allowed);
64 else
65 pawns = pawn_get_all(player->color);
66
67 search_again:
68 max_eaten_pawns = player_can_be_eaten(player, search_now, allowed);
69 max_eaten = llist_length(max_eaten_pawns);
70 llist_free(max_eaten_pawns);
71 #ifdef IA_DEBUG
72 printf("DEFENCE: maximum possible to be eaten at %s move: %d\n",
73 search_now?"next":"afternext", max_eaten);
74 #endif
75 assert(best_destination == NULL);
76
77 for (cur = pawns; cur; cur = cur->next) {
78 Pawn *pawn = (Pawn *)cur->data;
79 Tile *origtile = pawn_get_tile(pawn);
80 LList *positions = tile_get_accessible_surroundings(pawn_get_tile(pawn));
81 LList *curpos = positions;
82
83 for (; curpos; curpos = curpos->next) {
84 Tile *desttile = (Tile *)curpos->data;
85 LList *can_be_eaten = NULL;
86 LList *allowed_for_this = NULL;
87
88 if (desttile->pawn != NULL)
89 continue; /* work around repaint hack */
90
91 if (tile_is_near_center(origtile) &&
92 tile_is_near_center(desttile) &&
93 !center_ok)
94 continue;
95
96 allowed_for_this = llist_append(NULL, pawn);
97 pawn_move_to(pawn, desttile);
98
99 can_be_eaten = player_can_be_eaten(player, search_now, allowed);
100
101 llist_free(allowed_for_this);
102 allowed_for_this = NULL;
103
104 if (llist_length(can_be_eaten) < max_eaten) {
105 #ifdef IA_DEBUG
106 printf("MIN!found %d to be eaten by moving %d,%d to %d,%d\n",
107 llist_length(can_be_eaten),
108 origtile->pos_x, origtile->pos_y,
109 desttile->pos_x, desttile->pos_y);
110 #endif
111 max_eaten = llist_length(can_be_eaten);
112 best = origtile;
113 best_destination = desttile;
114 }
115 llist_free(can_be_eaten);
116 pawn_move_to(pawn, origtile);
117 }
118 llist_free(positions);
119 }
120 if (best == NULL && search_now == TRUE && immediate_defense > 1) {
121 search_now = FALSE;
122 goto search_again;
123 }
124
125 llist_free(pawns);
126
127 return best;
128 }
129
finish_move(Player * player,LList * allowed)130 static Tile *finish_move(Player *player, LList *allowed)
131 {
132 Tile *orig = NULL;
133 Tile *dest = NULL;
134 LList *eater_dest = NULL;
135
136 if (allowed) {
137 Pawn *allowed_pawn = (Pawn *)allowed->data;
138 eater_dest = allowed_pawn->just_ate_on;
139 }
140
141 assert(selected_pawn != NULL);
142
143 orig = pawn_get_tile(selected_pawn);
144 if (best_destination) {
145 dest = best_destination;
146 } else if (best_destination_after_middle) {
147 if (orig->pos_x == 4 && orig->pos_y == 4) {
148 dest = best_destination_after_middle;
149 }
150 best_destination_after_middle = NULL;
151 }
152
153 selected_pawn = NULL;
154 best_destination = NULL;
155
156 if (first) {
157 first = FALSE;
158 return tile_get(4,4);
159 }
160
161 if (orig && dest && !eater_dest)
162 return dest;
163 else {
164 /* have to figure out dest, idiotic for now */
165 LList *destinations = eater_dest ? eater_dest : tile_get_accessible_surroundings(orig);
166 LList *cur = destinations;
167 float r = (float)rand()/RAND_MAX;
168 int num = r * llist_length(destinations);
169 int i = 0;
170
171 /* if replacement and best found position is acceptable, then great */
172 if (dest && eater_dest && llist_find(eater_dest, dest))
173 return dest;
174
175 for (i = 0; i < num; i++)
176 cur = cur->next;
177
178 dest = (Tile *)cur->data;
179 if (eater_dest == NULL)
180 llist_free(destinations);
181
182 /* we should check we're not committing suicide */
183 return dest;
184 }
185 }
186
prepare_move(Player * player,LList * allowed)187 static Tile *prepare_move(Player *player, LList *allowed)
188 {
189 /* get the best pawn to move so that I'll be able to eat later */
190 LList *pawns, *cur;
191 Pawn *best = NULL;
192 int max_eatables_soon = 0;
193 int pawn_count;
194 int search_now = TRUE;
195
196 if (allowed)
197 pawns = llist_copy(allowed);
198 else
199 pawns = pawn_get_all(player->color);
200
201 pawn_count = llist_length(pawns);
202
203 if (pawn_count == 1) {
204 Pawn *pawn = (Pawn *)pawns->data;
205 if (pawn_get_tile(pawn)->type == TILE_CENTER) {
206 /* move again */
207 assert(selected_pawn == NULL);
208 selected_pawn = pawn;
209 }
210 }
211
212 if (selected_pawn != NULL) {
213 llist_free(pawns);
214 return finish_move(player, allowed);
215 }
216 if (first) {
217 llist_free(pawns);
218 selected_pawn = tile_get(4,3)->pawn;
219 return tile_get(4,3);
220 }
221
222 search_again:
223 #ifdef IA_DEBUG
224 printf("ATTACK: choosing for %s turn\n", search_now?"current":"next");
225 #endif
226 for (cur = pawns; cur; cur = cur->next) {
227 Pawn *pawn = (Pawn *)cur->data;
228 Tile *origtile = pawn_get_tile(pawn);
229 LList *positions = tile_get_accessible_surroundings(pawn_get_tile(pawn));
230 LList *curpos = positions;
231
232 for (; curpos; curpos = curpos->next) {
233 Tile *desttile = (Tile *)curpos->data;
234 LList *eatables = NULL;
235 LList *can_be_eaten = NULL;
236 LList *allowed_for_this = NULL;
237 int score = 0, can_be_eaten_before_move = 0;
238
239 if (desttile->pawn != NULL)
240 continue; /* work around repaint hack */
241
242 if (desttile->pos_x == 4 && desttile->pos_y == 4) {
243 /*middle tile*/
244 LList *mid_surr = tile_get_accessible_surroundings(desttile);
245 LList *cur_mid = mid_surr;
246 for (; cur_mid; cur_mid = cur_mid->next) {
247 if (!llist_find(positions, cur_mid->data))
248 llist_append(positions, cur_mid->data);
249 }
250 llist_free(mid_surr);
251 continue;
252 }
253 can_be_eaten = player_can_be_eaten(player, search_now, allowed_for_this);
254 can_be_eaten_before_move = llist_length(can_be_eaten);
255 llist_free(can_be_eaten);
256 can_be_eaten = NULL;
257
258 allowed_for_this = llist_append(NULL, pawn);
259
260 pawn_move_to(pawn, desttile);
261
262 eatables = player_can_eat_soon(player, search_now, allowed_for_this);
263
264 can_be_eaten = player_can_be_eaten(player, search_now, allowed_for_this);
265
266 llist_free(allowed_for_this);
267 allowed_for_this = NULL;
268
269 if (!search_now && llist_length(can_be_eaten) > can_be_eaten_before_move) {
270 #ifdef IA_DEBUG
271 printf("won't move to %d %d, would be suicide\n",
272 desttile->pos_x, desttile->pos_y);
273 #endif
274 goto no_suicide;
275 }
276
277 score = llist_length(eatables) - llist_length(can_be_eaten);
278
279 if ((search_now || llist_length(can_be_eaten) == 0) && llist_length(eatables) > max_eatables_soon) {
280 #ifdef IA_DEBUG
281 printf("MAX!found %d eatables and %d to be eaten by moving %d,%d to %d,%d\n",
282 llist_length(eatables), llist_length(can_be_eaten),
283 origtile->pos_x, origtile->pos_y,
284 desttile->pos_x, desttile->pos_y);
285 #endif
286 max_eatables_soon = llist_length(eatables);
287 best = pawn;
288 if ((abs(origtile->pos_x - desttile->pos_x) == 2 ||
289 abs(origtile->pos_y - desttile->pos_y) == 2) &&
290 tile_is_near_center(origtile) &&
291 tile_is_near_center(desttile) &&
292 search_now) {
293 best_destination_after_middle = desttile;
294 best_destination = tile_get(4, 4);
295 } else if ((abs(origtile->pos_x - desttile->pos_x) == 2 ||
296 abs(origtile->pos_y - desttile->pos_y) == 2) &&
297 tile_is_near_center(origtile) &&
298 tile_is_near_center(desttile) &&
299 !search_now) {
300 best_destination_after_middle = desttile;
301 best_destination = tile_get(4, 4);
302 } else {
303 best_destination = desttile;
304 }
305 }
306 no_suicide:
307 llist_free(eatables);
308 llist_free(can_be_eaten);
309 pawn_move_to(pawn, origtile);
310 }
311 llist_free(positions);
312 }
313 if (best == NULL && search_now == TRUE) {
314 Tile *best_defense = computer_defend(player, allowed, TRUE); /* now only */
315 if (best_defense) {
316 best = best_defense->pawn;
317 goto no_random;
318 }
319 search_now = FALSE;
320 goto search_again;
321 }
322
323 if (best == NULL) {
324 Tile *best_defense = NULL;
325 int pawn_num = 0;
326 int i = 0;
327 int center_ok = can_move_on_center();
328 #ifdef IA_DEBUG
329 printf("no best move found, trying to protect myself\n");
330 #endif
331
332 best_defense = computer_defend(player, allowed, 2); /* both now and later */
333 if (best_defense) {
334 best = best_defense->pawn;
335 goto no_random;
336 }
337 #ifdef IA_DEBUG
338 printf("no best move found, randomly playing\n");
339 #endif
340 random_again:
341 pawn_num = (rand()%pawn_count);
342
343 cur = pawns;
344 for (i = 0; i < pawn_num; i++) {
345 cur = cur->next;
346 }
347
348 best = (Pawn *)cur->data;
349 if (tile_is_near_center(pawn_get_tile(best)) &&
350 !center_ok)
351 goto random_again;
352
353 }
354 no_random:
355 llist_free(pawns);
356
357 selected_pawn = best;
358
359 return pawn_get_tile(best);
360 }
361
computer_select_tile(Player * player,LList * allowed)362 Tile *computer_select_tile(Player *player, LList *allowed)
363 {
364 Tile *res = NULL;
365
366 if (delay_with_event_poll(1000) < 0)
367 goto out;
368
369 while (game_suspended()) {
370 if (delay_with_event_poll(20) < 0)
371 goto out;
372 }
373 if (game_ended())
374 goto out;
375
376 board_freeze();
377 res = prepare_move(player, allowed);
378 board_thaw();
379
380 out:
381 while (game_suspended()) {
382 delay_with_event_poll(20);
383 }
384 if (game_ended())
385 goto no_push;
386
387 no_push:
388 return res;
389 }
390