1 /*
2 XBubble - opponent.c
3
4 Copyright (C) 2002 Ivan Djelic <ivan@savannah.gnu.org>
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #include "utils.h"
26 #include "cell.h"
27 #include "bubble.h"
28 #include "board.h"
29 #include "setting.h"
30 #include "opponent.h"
31 #include <assert.h> /* XXX */
32
33 #ifdef DEBUG_OPPONENT
34 #define DEBUG 1
35 #else
36 #define DEBUG 0
37 #endif
38
39 #define MAX_DEPTH 3
40
41 struct _Opponent {
42 int launch_count;
43 int period;
44 int angle;
45 int max_depth;
46 int line[MAX_DEPTH];
47 int color[MAX_DEPTH];
48 int target[NB_ANGLES];
49 int perimeter_cache[NB_CELLS];
50 int eval_cache[NB_CELLS][NB_COLORS];
51 int best_target;
52 int angle_bias_period;
53 double *vx;
54 double *vy;
55 Set explosive_bubbles;
56 Set removed_bubbles[MAX_DEPTH];
57 Vector floating_cells;
58 Vector path[NB_ANGLES];
59 Vector targets[MAX_DEPTH];
60 Vector perimeters[NB_CELLS];
61 struct _Bubble bubble[MAX_DEPTH];
62 CellArray array;
63 Board board;
64 };
65
new_opponent(Board board,int level)66 Opponent new_opponent( Board board, int level ) {
67 int i;
68
69 CellArray ca;
70 Opponent op;
71 op = (Opponent) xmalloc( sizeof( struct _Opponent ));
72 op->board = board;
73 get_board_info( op->board,
74 &op->vx,
75 &op->vy,
76 &op->color[0],
77 &op->color[1],
78 &op->launch_count,
79 &op->period);
80
81 ca = get_board_array(board);
82 op->array = cell_array_new( ca->moving_ceiling );
83 op->explosive_bubbles = set_new( NB_CELLS );
84 op->floating_cells = vector_new( NB_CELLS );
85 for ( i = 0; i < MAX_DEPTH; i++ ) {
86 op->removed_bubbles[i] = set_new( NB_CELLS );
87 op->targets[i] = vector_new( NB_CELLS );
88 }
89 for ( i = 0; i < NB_CELLS; i++ )
90 op->perimeters[i] = vector_new(16);
91 for ( i = 0; i < NB_ANGLES; i++ ) {
92 op->path[i] = vector_new( NB_CELLS );
93 }
94 op->max_depth = 2;
95
96 switch( level ) {
97 case VERY_EASY:
98 op->angle_bias_period = 2;
99 break;
100 case EASY:
101 op->angle_bias_period = 4;
102 break;
103 case NORMAL:
104 op->angle_bias_period = 8;
105 break;
106 case HARD:
107 op->angle_bias_period = 0;
108 break;
109 case VERY_HARD:
110 op->max_depth = 3;
111 op->angle_bias_period = 0;
112 break;
113 }
114 return op;
115 }
116
delete_opponent(Opponent op)117 void delete_opponent( Opponent op ) {
118 int i;
119 cell_array_free( op->array );
120 set_free( op->explosive_bubbles );
121 vector_free( op->floating_cells );
122 for ( i = 0; i < NB_CELLS; i++ )
123 vector_free( op->perimeters[i] );
124 for ( i = 0; i < NB_ANGLES; i++ )
125 vector_free( op->path[i] );
126 for ( i = 0; i < MAX_DEPTH; i++ ) {
127 set_free( op->removed_bubbles[i] );
128 vector_free( op->targets[i] );
129 }
130 free( op );
131 }
132
133 /*
134 array_overflow() returns 1 if the last played move is losing.
135 We don't use cell_array_overflow() because we may simulate board
136 lowering by moving the canon up.
137 */
138
array_overflow(Opponent op,int depth)139 static int array_overflow( Opponent op, int depth ) {
140 int i, first, last_row;
141 last_row = ROWS - 1;
142 if ( op->launch_count + depth > op->period )
143 last_row--;
144 first = COLS*last_row;
145 for ( i = first; i < NB_CELLS; i++ )
146 if ( op->array->cell[i] != EMPTY_CELL )
147 return 1;
148 return 0;
149 }
150
play_move(Opponent op,int depth,int target)151 static void play_move( Opponent op, int depth, int target ) {
152 int count, i, cell;
153 Bubble bubble, bubble2;
154
155 set_empty( op->removed_bubbles[depth] );
156
157 /* stick bubble in target cell */
158 bubble = &op->bubble[depth];
159 bubble->state = STUCK;
160 bubble->cell = target;
161 bubble->color = op->color[depth];
162 op->array->cell[target] = bubble;
163 count = count_explosive_bubbles( op->array, target,
164 op->explosive_bubbles, NULL );
165 if ( count >= 3 ) {
166 /* remove explosive bubbles */
167 for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
168 bubble2 = op->explosive_bubbles->element[i];
169 op->array->cell[bubble2->cell] = EMPTY_CELL;
170 set_add( op->removed_bubbles[depth], bubble2 );
171 }
172 /* remove dropped bubbles */
173 count_floating_bubbles( op->array, op->floating_cells );
174 for ( i = 0; i < op->floating_cells->size; i++ ) {
175 cell = op->floating_cells->element[i];
176 bubble2 = op->array->cell[cell];
177 op->array->cell[cell] = EMPTY_CELL;
178 set_add( op->removed_bubbles[depth], bubble2 );
179 }
180 }
181 set_empty( op->explosive_bubbles );
182 op->line[depth] = target;
183
184 if ( DEBUG ) {
185 fprintf( stderr, "\n" );
186 for ( i = 0; i < depth; i++ )
187 fprintf( stderr, " " );
188 switch( bubble->color ) {
189 case 0: fprintf( stderr, " red" ); break;
190 case 1: fprintf( stderr, " blue" ); break;
191 case 2: fprintf( stderr, " green" ); break;
192 case 3: fprintf( stderr, " yellow" ); break;
193 case 4: fprintf( stderr, " black" ); break;
194 case 5: fprintf( stderr, " brown" ); break;
195 case 6: fprintf( stderr, " white" ); break;
196 case 7: fprintf( stderr, "magenta" ); break;
197 }
198 fprintf( stderr, "@%2d%c", target, ( count >= 3 )? 'E' : ' ' );
199 }
200 }
201
unplay_move(Opponent op,int depth)202 static void unplay_move( Opponent op, int depth ) {
203 int i;
204 Bubble bubble;
205 /* restore removed bubbles */
206 for ( i = 0; i < op->removed_bubbles[depth]->size; i++ ) {
207 bubble = op->removed_bubbles[depth]->element[i];
208 op->array->cell[bubble->cell] = bubble;
209 }
210 /* empty cell */
211 op->array->cell[op->line[depth]] = EMPTY_CELL;
212 }
213
214 /*
215 compute_targets() computes the target cells associated with each
216 firing angle and builds op->targets[depth].
217 */
218
compute_targets(Opponent op,int depth)219 static void compute_targets( Opponent op, int depth ) {
220 // double y, canon_y;
221 int i, angle, target, cell, move, target_invalid;
222 int cell_cache[NB_CELLS];
223
224 /* flush cache (used to avoid studying two angles with the same target) */
225 memset( cell_cache, 0, NB_CELLS*sizeof(int));
226 vector_empty( op->targets[depth] );
227
228 if ( depth == 0 )
229 /* full target cell computation for each angle */
230 for ( i = 0; i < NB_ANGLES; i++ ) {
231 angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
232 target = target_cell( op->array, angle, NULL, op->path[angle] );
233 /* store target cell */
234 op->target[angle] = target;
235 /* make targets vector for searching */
236 if ( ! cell_cache[target] ) {
237 cell_cache[target] = 1;
238 vector_push( op->targets[0], target );
239 }
240 }
241
242 else /* depth >= 1 */
243 /*
244 Instead of calling target_cell() for every angle (expensive), we try
245 to reuse the targets computed at depth 0. In order to do so, we must
246 ensure that such a target is still valid at the current searching depth;
247 we use the following test:
248
249 Let t be the target computed at depth 0;
250
251 for each previous played move ( = cell c ), starting from depth 0:
252
253 if one of the following conditions is true:
254 * board has been lowered
255 * cell c is now empty (i.e. some explosion occurred)
256 * c == t or c is on the path reaching t
257 then we consider t invalid and call target_cell() for recomputation.
258
259 */
260 for ( i = 0; i < NB_ANGLES; i++ ) {
261 angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
262
263 /* depth >= 1 : try to use op->target[] */
264 // canon_y = op->canon_y;
265 target = op->target[angle];
266 target_invalid = 0;
267
268 /* move canon up to fake board going down */
269 if ( op->launch_count + depth >= op->period + 1 ) {
270 // canon_y -= ROW_HEIGHT;
271 target_invalid = 1;
272 }
273 if ( ! target_invalid )
274 /* check if target recomputation is really needed */
275 for ( move = 0; move < depth; move++ ) {
276 cell = op->line[move];
277 if (( op->array->cell[cell] == EMPTY_CELL )||
278 ( target == cell )||
279 ( vector_membership( op->path[angle], cell ))) {
280 target_invalid = 1;
281 break;
282 }
283 }
284 if ( target_invalid )
285 target = target_cell( op->array, angle, NULL, NULL );
286 /* make targets vector for searching */
287 if ( ! cell_cache[target] ) {
288 cell_cache[target] = 1;
289 vector_push( op->targets[depth], target );
290 }
291 }
292 /*
293 if ( DEBUG ) {
294 fprintf(stderr,"\n");
295 for( i = 1; i <= depth; i++ )
296 fprintf( stderr, "\t");
297 fprintf( stderr, "targets[%d]={ ", depth);
298 for( i = 0; i < op->targets[depth]->size; i++ )
299 fprintf( stderr, "%d,", op->targets[depth]->element[i]);
300 fprintf( stderr, "} ");
301 }
302 */
303 }
304
305 /*
306 add_to_perimeter() is used to add cell neighbors to a perimeter
307 ( a list of cells used in evaluate_target_potential() ).
308 */
309
add_to_perimeter(Opponent op,Vector perimeter,int cell)310 static void add_to_perimeter( Opponent op, Vector perimeter, int cell ) {
311 int neighbor;
312 Quadrant q;
313 for ( q = 0; q < 6; q++ ) {
314 neighbor = neighbor_cell( op->array, cell, q );
315 if (( neighbor != OUT_OF_BOUNDS )&&
316 ( op->array->cell[neighbor] == EMPTY_CELL )&&
317 ( ! op->perimeter_cache[neighbor] )) {
318 vector_push( perimeter, neighbor );
319 op->perimeter_cache[neighbor] = 1;
320 }
321 }
322 }
323
324 /*
325 evaluate_target_potential() is used to evaluate the potential benefit
326 of putting a bubble of any color in a given target.
327 The following algorithm is used:
328
329 FOR each color c:
330 eval[c] = eval_min;
331 put a bubble of color c in target;
332 IF this bubble triggers an explosion:
333 FOR each exploding bubble in cell C:
334 eval[c] += row(C);
335 FOR each dropped bubble in cell C:
336 eval[c] += row(C) + 1;
337 ELSE
338 IF this bubble has a neighbor of the same color:
339 eval[c] += 2;
340
341 IF board overflow
342 eval[c] = 1;
343
344 Additionally, the function can build of list of cells called "perimeter":
345 this is actually a list of the empty neighbors of all cells that would be
346 "touched" (i.e. exploded/dropped/neighbor) if a bubble was put in target.
347 This is later used in eval_tree() to avoid redundant calls to
348 evaluate_target_potential().
349 */
350
evaluate_target_potential(Opponent op,int target,int * eval,int search_depth,Vector perimeter)351 static void evaluate_target_potential( Opponent op,
352 int target,
353 int *eval,
354 int search_depth,
355 Vector perimeter ) {
356 int cell, count, color, i;
357 struct _Bubble temp_bubble;
358 Bubble bubble;
359 if ( perimeter != NULL )
360 vector_empty(perimeter);
361
362 /* stick temporary bubble in target cell */
363 temp_bubble.state = STUCK;
364 temp_bubble.cell = target;
365 op->array->cell[target] = &temp_bubble;
366 for ( color = 0; color < NB_COLORS; color++ ) {
367 eval[color] = 1000;
368 temp_bubble.color = color;
369 count = count_explosive_bubbles( op->array, target,
370 op->explosive_bubbles, NULL );
371 if ( count >= 3 ) { /* explosion */
372 count_floating_bubbles( op->array, op->floating_cells );
373 /* sum explosive bubbles */
374 for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
375 bubble = op->explosive_bubbles->element[i];
376 eval[color] += bubble->cell/COLS;
377 if ( perimeter != NULL )
378 add_to_perimeter( op, perimeter, bubble->cell );
379 }
380 /* sum dropped bubbles */
381 for ( i = 0; i < op->floating_cells->size; i++ ) {
382 cell = op->floating_cells->element[i];
383 eval[color] += cell/COLS + 1; /* dropping bonus */
384 if ( perimeter != NULL )
385 add_to_perimeter( op, perimeter, cell);
386 }
387 }
388 else { /* no explosion */
389 if ( perimeter != NULL )
390 for ( i = 0; i < op->explosive_bubbles->size; i++ ) {
391 bubble = op->explosive_bubbles->element[i];
392 add_to_perimeter( op, perimeter, bubble->cell );
393 }
394 if ( count == 2 )
395 eval[color] += 2;
396 }
397 set_empty( op->explosive_bubbles );
398 /* check if move is losing */
399 if ( array_overflow( op, search_depth ))
400 eval[color] = 1;
401 }
402 /* flush cache only if we used it */
403 if (( perimeter != NULL )&&( perimeter->size ))
404 memset( op->perimeter_cache, 0, NB_CELLS*sizeof(int));
405 /* remove temporary bubble */
406 op->array->cell[target] = EMPTY_CELL;
407 }
408
eval_tree(Opponent op,int depth)409 static int eval_tree( Opponent op, int depth ) {
410 int i, j;
411 int target;
412 int cell;
413 int eval;
414 int first;
415 int sum;
416 int compute_sum;
417 int best_eval = 0;
418 int need_target_evaluation;
419 int target_eval[NB_COLORS];
420 int leaf_best_eval[NB_COLORS];
421 Bubble bubble;
422
423 if ( array_overflow( op, depth ) ) {
424 /* losing later is better than losing now */
425 if ( DEBUG )
426 fprintf( stderr, "* [%d]", depth+1 );
427 return depth + 1;
428 }
429 if ( depth < op->max_depth-1 ) {
430 /* compute list of available targets */
431 compute_targets( op, depth );
432
433 if ( depth == 0 ) {
434 if ( DEBUG )
435 fprintf( stderr, "\nfilling eval_cache[] and perimeters[]");
436 /* fill eval_cache[] and perimeters[] */
437 for ( i = 0; i < op->targets[0]->size; i++ ) {
438 target = op->targets[0]->element[i];
439 evaluate_target_potential( op,
440 target,
441 op->eval_cache[target],
442 0,
443 op->perimeters[target] );
444 }
445 }
446
447 /* scan targets */
448 for ( i = 0; i < op->targets[depth]->size; i++ ) {
449 target = op->targets[depth]->element[i];
450 play_move( op, depth, target );
451 eval = eval_tree( op, depth+1 );
452 /* XXX */
453 assert( eval >= 1 );
454 unplay_move( op, depth );
455 if ( best_eval < eval ) {
456 best_eval = eval;
457 if ( depth == 0 )
458 op->best_target = target;
459 }
460 }
461 return best_eval;
462 }
463 else {
464 /*
465 leaf node evaluation: the idea is to compute all available targets
466 and evaluate each of them for all possible colors.
467 */
468 if ( DEBUG )
469 fprintf( stderr, " (" );
470 memset( leaf_best_eval, 0, sizeof(int)*NB_COLORS );
471 /* compute list of available targets */
472 compute_targets( op, depth );
473 for ( i = 0; i < op->targets[depth]->size; i++ ) {
474 target = op->targets[depth]->element[i];
475 /*
476 we don't really want to call evaluate_target_potential() because
477 it's expensive, so let's try to use cached info:
478 */
479 need_target_evaluation = 0;
480 /* of course if this is a new target we need to evaluate it */
481 if ( ! vector_membership( op->targets[0], target ))
482 need_target_evaluation = 1;
483 else
484 /*
485 We use perimeters to ensure evaluation is still valid:
486 for a given target t, we use its cached evaluation if none of
487 the followings conditions holds:
488 - an explosion occured since depth 0.
489 - a bubble has been played in target's perimeter since depth 0.
490
491 */
492 for ( j = 0; j < depth; j++ ) {
493 cell = op->line[j];
494 if (( op->array->cell[cell] != &op->bubble[j] )||
495 ( vector_membership( op->perimeters[target], cell ))) {
496 need_target_evaluation = 1;
497 break;
498 }
499 }
500
501 if ( need_target_evaluation ) {
502 /* miss :-( */
503 if ( DEBUG )
504 fprintf( stderr, "." );
505 evaluate_target_potential( op, target, target_eval, depth, NULL);
506 }
507 else {
508 /* hit !! */
509 if ( DEBUG )
510 fprintf( stderr, "!" );
511 for ( j = 0; j < NB_COLORS; j++ )
512 target_eval[j] = op->eval_cache[target][j];
513 }
514 /* compute max evaluations */
515 for ( j = 0; j < NB_COLORS; j++ )
516 if ( leaf_best_eval[j] < target_eval[j] )
517 leaf_best_eval[j] = target_eval[j];
518 }
519 if ( DEBUG ) {
520 fprintf( stderr, ")" );
521 for ( j = 0; j < 16 - op->targets[depth]->size; j++ )
522 fprintf( stderr, " " );
523 }
524
525 /* last step of our evaluation: take into account bubble positions. */
526 compute_sum = 0;
527 for ( j = 0; j < NB_COLORS; j++ )
528 if ( leaf_best_eval[j] > 1 ) {
529 compute_sum = 1;
530 break;
531 }
532 else
533 leaf_best_eval[j] = 1 + depth;
534 if ( compute_sum ) {
535 sum = NB_CELLS*ROWS;
536 /* compute global sum on bubbles */
537 first = first_cell(op->array);
538 for ( i = first; i < NB_CELLS - COLS; i++ ) {
539 bubble = op->array->cell[i];
540 if ( bubble != EMPTY_CELL )
541 /* higher cell is better */
542 sum -= bubble->cell/COLS;
543 }
544 for ( j = 0; j < NB_COLORS; j++ )
545 if ( leaf_best_eval[j] > 1 + depth )
546 leaf_best_eval[j] += sum;
547 }
548 /*
549 OK, now we have an evaluation of our position for every color;
550 We compute an average:
551 */
552 for ( i = 0; i < NB_COLORS; i++ )
553 best_eval += leaf_best_eval[i];
554 best_eval = best_eval/NB_COLORS;
555
556 if ( DEBUG )
557 fprintf( stderr, "[%04d]", best_eval );
558 return best_eval;
559 }
560 }
561
find_best_angle(Opponent op,int * best_eval)562 int find_best_angle( Opponent op , int *best_eval ) {
563 int i, angle;
564 static int counter = 0;
565 CellArray ca;
566 /* make a clean copy of board array */
567 ca = get_board_array(op->board);
568 memcpy( op->array->cell, ca->cell, sizeof(void *)*NB_CELLS);
569 memset( op->array->tagged, 0, sizeof(int)*NB_CELLS );
570 memset( op->perimeter_cache, 0, NB_CELLS*sizeof(int));
571 op->array->first_row = ca->first_row;
572 op->array->parity = ca->parity;
573 get_board_info( op->board,
574 &op->vx,
575 &op->vy,
576 &op->color[0],
577 &op->color[1],
578 &op->launch_count,
579 &op->period);
580 /* depth first search */
581 *best_eval = eval_tree( op, 0 );
582 /* retrieve best angle */
583 for ( i = 0; i < NB_ANGLES; i++ ) {
584 angle = (i/2)*(1-2*(i%2)) + CANON_ANGLE_MAX;
585 if ( op->target[angle] == op->best_target ) {
586 angle -= CANON_ANGLE_MAX;
587 if ( op->angle_bias_period ) {
588 counter++;
589 /* add a random factor sometimes to simulate bad aiming */
590 if ( counter % op->angle_bias_period == 0 )
591 angle += rnd(8) - 4;
592 }
593 if ( DEBUG )
594 fprintf( stderr, "\n*** best = %d (%d) ***", op->best_target,
595 *best_eval);
596 return angle;
597 }
598 }
599 /* should not be reached */
600 fprintf( stderr, "\nOUCH : best_eval=%d best_target=%d\n", *best_eval,
601 op->best_target );
602 return 0;
603 }
604
605