1 /*
2 * Alizarin Tetris
3 * Functions relating to AI players.
4 *
5 * Copyright 2000, Westley Weimer & Kiri Wagstaff
6 */
7
8 #include <config.h>
9
10 #include "atris.h"
11 #include "display.h"
12 #include "identity.h"
13 #include "grid.h"
14 #include "piece.h"
15 #include "sound.h"
16 #include "ai.h"
17 #include "menu.h"
18
19 #include "event.pro"
20 #include "identity.pro"
21 #include "display.pro"
22
23 /*********** Wes's globals ***************/
24
25
26 typedef struct wessy_struct {
27 int know_what_to_do;
28 int desired_column;
29 int desired_rot;
30 int cc;
31 int current_rot;
32 int best_weight;
33 Grid tg;
34 } Wessy_State;
35
36 typedef struct double_struct {
37 int know_what_to_do;
38
39 int desired_col;
40 int desired_rot;
41 int best_weight;
42
43 int stage_alpha;
44 int cur_alpha_col;
45 int cur_alpha_rot;
46 Grid ag;
47 int cur_beta_col;
48 int cur_beta_rot;
49 Grid tg;
50 } Double_State;
51
52 #define WES_MIN_COL -4
53 static int weight_board(Grid *g);
54
55 /***************************************************************************
56 * The code here determines what the board would look like after all the
57 * color-sliding and tetris-clearing that would happen if you pasted the
58 * given piece (pp) onto the given scratch grid (tg) at location (x,y) and
59 * rotation (current_rot). You are welcome to copy it.
60 *
61 * Returns -1 on failure or the number of lines cleared.
62 ***************************************************************************/
63 int
drop_piece_on_grid(Grid * g,play_piece * pp,int col,int row,int rot)64 drop_piece_on_grid(Grid *g, play_piece *pp, int col, int row, int rot)
65 {
66 int should_we_loop = 0;
67 int lines_cleared = 0;
68
69 if (!valid_position(pp, col, row, rot, g))
70 return -1;
71
72 while (valid_position(pp, col, row, rot, g))
73 row++;
74 row--; /* back to last valid position */
75
76 /* *-*-*-*
77 */
78 if (!valid_position(pp, col, row, rot, g))
79 return -1;
80
81 if (pp->special != No_Special) {
82 handle_special(pp, row, col, rot, g, NULL);
83 cleanup_grid(g);
84 } else
85 paste_on_board(pp, col, row, rot, g);
86 do {
87 int x,y,l;
88 should_we_loop = 0;
89 if ((l = check_tetris(g))) {
90 cleanup_grid(g);
91 }
92 lines_cleared += l;
93 for (y=g->h-1;y>=0;y--)
94 for (x=g->w-1;x>=0;x--)
95 FALL_SET(*g,x,y,UNKNOWN);
96 run_gravity(g);
97
98 if (determine_falling(g)) {
99 do {
100 fall_down(g);
101 cleanup_grid(g);
102 run_gravity(g);
103 } while (determine_falling(g));
104 should_we_loop = 1;
105 }
106 } while (should_we_loop);
107 /*
108 * Simulation code ends here.
109 * *-*-*-*
110 */
111 return lines_cleared;
112 }
113
114 /***************************************************************************
115 * double_ai_reset()
116 **************************************************************************/
117 static void *
double_ai_reset(void * state,Grid * g)118 double_ai_reset(void *state, Grid *g)
119 {
120 Double_State *retval;
121 /* something has changed (e.g., a new piece) */
122
123 if (state == NULL) {
124 /* first time we've been called ... */
125 Calloc(retval, Double_State *, sizeof(Double_State));
126 } else
127 retval = state;
128 Assert(retval);
129 retval->know_what_to_do=0;
130 retval->desired_col = g->w / 2;
131 retval->desired_rot = 0;
132 retval->best_weight = 1<<30;
133 retval->stage_alpha = 1;
134 retval->cur_alpha_col = WES_MIN_COL;
135 retval->cur_alpha_rot = 0;
136 retval->cur_beta_col = WES_MIN_COL;
137 retval->cur_beta_rot = 0;
138
139 if (retval->tg.contents == NULL)
140 retval->tg = generate_board(g->w, g->h, 0);
141 if (retval->ag.contents == NULL)
142 retval->ag = generate_board(g->w, g->h, 0);
143
144 return retval;
145 }
146
147 /***************************************************************************
148 *
149 ***************************************************************************/
150 static void
double_ai_think(void * data,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)151 double_ai_think(void *data, Grid *g, play_piece *pp, play_piece *np,
152 int col, int row, int rot)
153 {
154 Double_State *ds = (Double_State *)data;
155 Uint32 incoming_time = SDL_GetTicks();
156
157 Assert(ds);
158
159 for (;SDL_GetTicks() == incoming_time;) {
160 if (ds->know_what_to_do)
161 return;
162
163 if (ds->stage_alpha) {
164 memcpy(ds->ag.contents, g->contents, (g->w * g->h * sizeof(ds->ag.contents[0])));
165 memcpy(ds->ag.fall, g->fall, (g->w * g->h * sizeof(ds->ag.fall[0])));
166
167 if ( drop_piece_on_grid(&ds->ag, pp, ds->cur_alpha_col, row,
168 ds->cur_alpha_rot) != -1) {
169 int weight;
170 /* success */
171 ds->cur_beta_col = WES_MIN_COL;
172 ds->cur_beta_rot = 0;
173
174 ds->stage_alpha = 0;
175
176 weight = weight_board(&ds->ag);
177 if (weight <= 0) {
178 ds->best_weight = weight;
179 ds->desired_col = ds->cur_alpha_col;
180 ds->desired_rot = ds->cur_alpha_rot;
181 ds->know_what_to_do = 1;
182 }
183 } else {
184 /* advance alpha */
185 if (++ds->cur_alpha_col == g->w) {
186 ds->cur_alpha_col = WES_MIN_COL;
187 if (++ds->cur_alpha_rot == 4) {
188 ds->cur_alpha_rot = 0;
189 ds->know_what_to_do = 1;
190 }
191 }
192 }
193 } else {
194 /* stage beta */
195 int weight;
196
197 memcpy(ds->tg.contents, ds->ag.contents, (ds->ag.w * ds->ag.h * sizeof(ds->ag.contents[0])));
198 memcpy(ds->tg.fall, ds->ag.fall, (ds->ag.w * ds->ag.h * sizeof(ds->ag.fall[0])));
199
200 if (drop_piece_on_grid(&ds->tg, np, ds->cur_beta_col, row,
201 ds->cur_beta_rot) != -1) {
202 /* success */
203 weight = 1+weight_board(&ds->tg);
204 if (weight < ds->best_weight) {
205 ds->best_weight = weight;
206 ds->desired_col = ds->cur_alpha_col;
207 ds->desired_rot = ds->cur_alpha_rot;
208 }
209 }
210
211 if (++ds->cur_beta_col == g->w) {
212 ds->cur_beta_col = WES_MIN_COL;
213 if (++ds->cur_beta_rot == 2) {
214 ds->cur_beta_rot = 0;
215
216 ds->stage_alpha = 1;
217 if (++ds->cur_alpha_col == g->w) {
218 ds->cur_alpha_col = WES_MIN_COL;
219 if (++ds->cur_alpha_rot == 4) {
220 ds->cur_alpha_rot = 0;
221 ds->know_what_to_do = 1;
222 }
223 }
224 }
225 }
226 } /* endof: stage beta */
227 } /* for: iterations */
228 }
229
230 /***************************************************************************
231 * double_ai_move()
232 ***************************************************************************/
233 static Command
double_ai_move(void * state,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)234 double_ai_move(void *state, Grid *g, play_piece *pp, play_piece *np,
235 int col, int row, int rot)
236 {
237 /* naively, there are ((g->w - pp->base->dim) * 4) choices */
238 /* determine how to get there ... */
239 Double_State *ws = (Double_State *) state;
240
241 if (rot != ws->desired_rot)
242 return MOVE_ROTATE;
243 else if (col > ws->desired_col)
244 return MOVE_LEFT;
245 else if (col < ws->desired_col)
246 return MOVE_RIGHT;
247 else if (ws->know_what_to_do) {
248 return MOVE_DOWN;
249 } else
250 return MOVE_NONE;
251 }
252
253 /***************************************************************************
254 * weight_board()
255 * Determines the value the AI places on the given board configuration.
256 * This is a Wes-specific function that is used to evaluate the result of
257 * a possible AI choice. In the end, the choice with the best weight is
258 * selected.
259 ***************************************************************************/
260 static int
weight_board(Grid * g)261 weight_board(Grid *g)
262 {
263 int x,y;
264 int w = 0;
265 int holes = 0;
266 int same_color = 0;
267 int garbage = 0;
268
269 /* favor the vast extremes ... */
270 int badness[10] = { 7, 9, 9, 9, 9, 9, 9, 9, 9, 7};
271
272 /*
273 * Simple Heuristic: highly placed blocks are bad, as are "holes":
274 * blank areas with blocks above them.
275 */
276 for (x=0; x<g->w; x++) {
277 int possible_holes = 0;
278 for (y=g->h-1; y>=0; y--) {
279 int what;
280 if ((what = GRID_CONTENT(*g,x,y))) {
281 w += 2 * (g->h - y) * badness[x] / 3;
282 if (possible_holes) {
283 if (what != 1)
284 holes += 3 * ((g->h - y)) * g->w * possible_holes;
285 possible_holes = 0;
286 }
287
288 if (x > 1 && what)
289 if (GRID_CONTENT(*g,x-1,y) == what)
290 same_color++;
291 if (what == 1)
292 garbage++;
293 } else {
294 possible_holes++;
295 }
296 }
297 }
298 w += holes * 2;
299 w += same_color * 4;
300 if (garbage == 0) w = 0; /* you'll win! */
301
302 return w;
303 }
304
305 /***************************************************************************
306 * wes_ai_think()
307 * Ruminates for the Wessy AI.
308 *
309 * This function is called every so (about every fall_event_interval) by
310 * event_loop(). The AI is expected to think for < 1 "tick" (as in,
311 * SDL_GetTicks()).
312 *
313 * Input:
314 * Grid *g Your side of the board. The currently piece (the
315 * you are trying to place) is not "stamped" on the
316 * board yet. You may not modify this board, but you
317 * may make copies of it in order to reason about it.
318 * play_piece *pp This describes the piece you are currently trying
319 * to place. You can use it in conjunction with
320 * functions like "valid_position()" to see where
321 * possible placements are.
322 * play_piece *np This is the next piece you will be given.
323 * int col,row The current grid coordinates of your (falling)
324 * piece.
325 * int rot The current rotation (0-3) of your (falling) piece.
326 *
327 * Output:
328 * Nothing Later, "ai_move()" will be called. Return your
329 * value (== your action) there.
330 ***************************************************************************/
331 static void
wes_ai_think(void * data,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)332 wes_ai_think(void *data, Grid *g, play_piece *pp, play_piece *np,
333 int col, int row, int rot)
334 {
335 int weight;
336 Wessy_State *ws = (Wessy_State *)data;
337 Uint32 incoming_time = SDL_GetTicks();
338
339 Assert(ws);
340
341 for (;SDL_GetTicks() == incoming_time;) {
342
343 if (ws->know_what_to_do)
344 return;
345
346 memcpy(ws->tg.contents, g->contents, (g->w * g->h * sizeof(ws->tg.contents[0])));
347 memcpy(ws->tg.fall, g->fall, (g->w * g->h * sizeof(ws->tg.fall[0])));
348 /* what would happen if we dropped ourselves on cc, current_rot now? */
349 if (drop_piece_on_grid(&ws->tg, pp, ws->cc, row, ws->current_rot) != -1) {
350 weight = weight_board(&ws->tg);
351
352 if (weight < ws->best_weight) {
353 ws->best_weight = weight;
354 ws->desired_column = ws->cc;
355 ws->desired_rot = ws->current_rot;
356 if (weight == 0)
357 ws->know_what_to_do = 1;
358 }
359 }
360 if (++(ws->cc) == g->w) {
361 ws->cc = 0;
362 if (++(ws->current_rot) == 4)
363 ws->know_what_to_do = 1;
364 }
365 }
366 }
367
368 /***************************************************************************
369 ***************************************************************************/
370 static void
beginner_ai_think(void * data,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)371 beginner_ai_think(void *data, Grid *g, play_piece *pp, play_piece *np,
372 int col, int row, int rot)
373 {
374 int weight;
375 Wessy_State *ws = (Wessy_State *)data;
376
377 Assert(ws);
378
379 if (ws->know_what_to_do || (SDL_GetTicks() & 3))
380 return;
381
382 memcpy(ws->tg.contents, g->contents, (g->w * g->h * sizeof(ws->tg.contents[0])));
383 memcpy(ws->tg.fall, g->fall, (g->w * g->h * sizeof(ws->tg.fall[0])));
384 /* what would happen if we dropped ourselves on cc, current_rot now? */
385
386 if (drop_piece_on_grid(&ws->tg, pp, ws->cc, row, ws->current_rot) != -1) {
387
388 weight = weight_board(&ws->tg);
389
390 if (weight < ws->best_weight) {
391 ws->best_weight = weight;
392 ws->desired_column = ws->cc;
393 ws->desired_rot = ws->current_rot;
394 if (weight == 0)
395 ws->know_what_to_do = 1;
396 }
397 }
398 if (++(ws->cc) == g->w) {
399 ws->cc = 0;
400 if (++(ws->current_rot) == 4)
401 ws->know_what_to_do = 1;
402 }
403 }
404
405
406 /***************************************************************************
407 * wes_ai_reset()
408 * This is a special function instructing you to that the something has
409 * changed (for example, you dropped your piece and you will have a new one
410 * soon) and that you should clear any state you have lying around.
411 **************************************************************************/
412 static void *
wes_ai_reset(void * state,Grid * g)413 wes_ai_reset(void *state, Grid *g)
414 {
415 Wessy_State *retval;
416 /* something has changed (e.g., a new piece) */
417
418 if (state == NULL) {
419 /* first time we've been called ... */
420 Calloc(retval, Wessy_State *, sizeof(Wessy_State));
421 } else
422 retval = state;
423 Assert(retval);
424
425 retval->know_what_to_do = 0;
426 retval->cc = WES_MIN_COL;
427 retval->current_rot = 0;
428 retval->best_weight = 1<<30;
429 retval->desired_column = g->w / 2;
430 retval->desired_rot = 0;
431
432 if (retval->tg.contents == NULL)
433 retval->tg = generate_board(g->w, g->h, 0);
434
435 return retval;
436 }
437
438 /***************************************************************************
439 * wes_ai_move()
440 * Determines the AI's next move. All of the inputs are as for ai_think().
441 * This function should be virtually instantaneous (do long calculations in
442 * ai_think()). Possible return values are:
443 * MOVE_NONE Do nothing, fall normally.
444 * MOVE_LEFT [Try to] Move one column to the left.
445 * MOVE_RIGHT [Try to] Move one column to the right.
446 * MOVE_ROTATE [Try to] Rotate the piece.
447 * MOVE_DOWN Fall down really quickly.
448 *
449 * This is a special form instructing you to that the something has changed
450 * (for example, you dropped your piece and you will have a new one soon)
451 * and that you should clear any state you have lying around.
452 **************************************************************************/
453 static Command
wes_ai_move(void * state,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)454 wes_ai_move(void *state, Grid *g, play_piece *pp, play_piece *np,
455 int col, int row, int rot)
456 {
457 /* naively, there are ((g->w - pp->base->dim) * 4) choices */
458 /* determine how to get there ... */
459 Wessy_State *ws = (Wessy_State *) state;
460
461 if (rot != ws->desired_rot)
462 return MOVE_ROTATE;
463 else if (col > ws->desired_column)
464 return MOVE_LEFT;
465 else if (col < ws->desired_column)
466 return MOVE_RIGHT;
467 else if (ws->know_what_to_do) {
468 return MOVE_DOWN;
469 } else
470 return MOVE_NONE;
471 }
472
473 /*****************************************************************/
474 /*************** Impermeable AI barrier **************************/
475 /*****************************************************************/
476
477 /*********** Kiri's globals ***************/
478 /*#define DEBUG */
479
480 typedef struct Aliz_State_struct {
481 double bestEval;
482 int foundBest;
483 int goalColumn, goalRotation;
484 int checkColumn, checkRotation;
485 int goalSides;
486 int checkSides; /* 0, 1, 2 = middle, left, right */
487 Grid kg;
488 } Aliz_State;
489
490
491 /*******************************************************************
492 * evalBoard()
493 * Evaluates the 'value' of a given board configuration.
494 * Return values range from 0 (in theory) to g->h + <something>.
495 * The lowest value is the best.
496 * Check separately for garbage?
497 *******************************************************************/
evalBoard(Grid * g,int nLines,int row)498 static double evalBoard(Grid* g, int nLines, int row)
499 {
500 /* Return the max height plus the number of holes under blocks */
501 /* Should encourage smaller heights */
502 int x, y, z;
503 int maxHeight = 0, minHeight = g->h;
504 int nHoles = 0, nGarbage = 0, nCanyons = 0;
505 double avgHeight = 0;
506 int nColumns = g->w;
507
508 /* Find the minimum, maximum, and average height */
509 for (x=0; x<g->w; x++) {
510 int height = g->h;
511 char gc;
512 for (y=0; y<g->h; y++) {
513 gc = GRID_CONTENT(*g, x, y);
514 if (gc == 0) height--;
515 else {
516 /* garbage */
517 if (gc == 1) nGarbage++;
518 /* Penalize for holes under blocks */
519 for (z=y+1; z<g->h; z++) {
520 char gc2 = GRID_CONTENT(*g, x, z);
521 /* count the holes under here */
522 if (gc2 == 0) {
523 nHoles += 2; /* these count for double! */
524 }
525 else if (gc2 == 1) nGarbage++;
526 }
527 break;
528 }
529 }
530 avgHeight += height;
531 if (height > maxHeight) maxHeight = height;
532 if (height < minHeight) minHeight = height;
533 }
534 avgHeight /= nColumns;
535
536 nHoles *= g->h;
537
538 /* Find the number of holes lower than the maxHeight */
539 for (x=0; x<g->w; x++) {
540 for (y=g->h-maxHeight; y<g->h; y++) {
541 /* count the canyons under here */
542 if (GRID_CONTENT(*g, x, y) == 0&&
543 ((x == 0 || GRID_CONTENT(*g, x-1, y)) &&
544 (x == g->w-1 || GRID_CONTENT(*g, x+1, y))))
545 nCanyons += y;
546 }
547 }
548
549 #ifdef DEBUG
550 printf("*** %d holes ", nHoles);
551 #endif
552
553 return (double)(maxHeight*(g->h) + avgHeight + (maxHeight - minHeight) +
554 nHoles + nCanyons + nGarbage + (g->h - row)
555 - nLines*nLines);
556 }
557
558 /*******************************************************************
559 * cogitate()
560 * Kiri's AI 'thinking' function. Again, called once 'every so'
561 * by event_loop().
562 *******************************************************************/
563 static void
alizCogitate(void * state,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)564 alizCogitate(void *state, Grid* g, play_piece* pp, play_piece* np,
565 int col, int row, int rot)
566 {
567 Aliz_State *as = (Aliz_State *)state;
568 double eval, evalLeft = -1, evalRight = -1;
569 int nLines;
570
571 Assert(as);
572
573 if (as->foundBest) return;
574
575 memcpy(as->kg.contents, g->contents, (g->w * g->h * sizeof(as->kg.contents[0])));
576 memcpy(as->kg.fall, g->fall, (g->w * g->h * sizeof(*as->kg.fall)));
577
578 if (as->bestEval == -1) {
579 /* It's our first think! */
580 as->checkColumn = col; /* check this column first */
581 as->checkRotation = 0; /* check no rotation (it's easy!) */
582 as->checkSides = 0; /* middle */
583 }
584 else {
585 /* Try the next thing */
586 as->checkRotation = (as->checkRotation+1)%4;
587 if (as->checkRotation == 0) {
588 /* Try a new column */
589 /* Go all the way left first */
590 if (as->checkColumn == col || as->checkColumn < col) {
591 as->checkColumn--;
592 if (!valid_position(pp, as->checkColumn, row,
593 as->checkRotation, &as->kg)) {
594 as->checkColumn = col + 1;
595 if (!valid_position(pp, as->checkColumn, row,
596 as->checkRotation, &as->kg)) {
597 /* skip this one */
598 return;
599 }
600 }
601 }
602 else {
603 /* Now go all the way to the right */
604 as->checkColumn++;
605 if (!valid_position(pp, as->checkColumn, row,
606 as->checkRotation, &as->kg)) {
607 /* skip this one */
608 return;
609 }
610 }
611 } else if (!valid_position(pp, as->checkColumn, row,
612 as->checkRotation, &as->kg)) {
613 /* as->checkRotation != 0 */
614 if (as->checkColumn >= g->w && as->checkRotation == 3) {
615 /* final one */
616 as->foundBest = TRUE;
617 #ifdef DEBUG
618 printf("Aliz: Found best! (last checked %d, %d)\n",
619 as->checkColumn, as->checkRotation);
620 #endif
621 return;
622 }
623 /* Trying a specific rotation; skip this one */
624 else return;
625 }
626 }
627 #ifdef DEBUG
628 printf("Aliz: trying (col %d, rot %d) ", as->checkColumn, as->checkRotation);
629 #endif
630
631 /* Check for impending doom */
632 if (GRID_CONTENT(*g, col, row+1)) {
633 #ifdef DEBUG
634 printf("Aliz: panic! about to crash, ");
635 #endif
636
637 /* something right below us, so move the direction with more space */
638 if (col > g->w - col) {
639 /* go left, leave rotation as is */
640 as->goalColumn = col/2;
641 /* wessy commentary: you might want to set goalRotation to the
642 * current rotation so that your next move (the panic flight) will
643 * be a motion, not a rotation) ...
644 */
645 as->goalRotation = as->checkRotation;
646 #ifdef DEBUG
647 printf("moving left.\n");
648 #endif
649 }
650 else {
651 /* go right, leave rotation as is */
652 as->goalColumn = col + (g->w - col)/2;
653 as->goalRotation = as->checkRotation;
654 #ifdef DEBUG
655 printf("moving right.\n");
656 #endif
657 }
658 #ifdef DEBUG
659 printf(" NEW goal: col %d, rot %d\n", as->goalColumn, as->goalRotation);
660 #endif
661 return;
662 }
663
664 /************** Test the current choice ****************/
665 nLines = drop_piece_on_grid(&as->kg, pp, as->checkColumn, row,
666 as->checkRotation);
667 if (nLines != -1) { /* invalid place to drop something */
668 eval = evalBoard(&as->kg, nLines, row);
669 #ifdef DEBUG
670 printf(": eval = %.3f", eval);
671 #endif
672 if (as->bestEval == -1 || eval < as->bestEval) {
673 as->bestEval = eval;
674 as->goalColumn = as->checkColumn;
675 as->goalRotation = as->checkRotation;
676 #ifdef DEBUG
677 printf(" **");
678 #endif
679
680 /* See if we should try to slide left */
681 if (as->checkColumn > 0 && !GRID_CONTENT(*g, as->checkColumn-1, row)) {
682 int y;
683 for (y=row; y>=0; y--)
684 /* worth trying if there's something above it */
685 if (GRID_CONTENT(*g, as->checkColumn-1, y)) break;
686 if (y >= 0 && valid_position(pp, as->checkColumn-1, row,
687 as->checkRotation, &as->kg)) {
688 printf("Aliz: Trying to slip left.\n");
689 /* get a fresh copy */
690 memcpy(as->kg.contents, g->contents, (g->w * g->h * sizeof(as->kg.contents[0])));
691 memcpy(as->kg.fall, g->fall, (g->w * g->h * sizeof(*as->kg.fall)));
692 paste_on_board(pp, as->checkColumn-1, row,
693 as->checkRotation, &as->kg);
694 /* nLines is the same */
695 evalLeft = evalBoard(&as->kg, nLines, row);
696 }
697 }
698
699 /* See if we should try to slide left */
700 if (as->checkColumn < g->w-1 && !GRID_CONTENT(*g, as->checkColumn+1, row)) {
701 int y;
702 for (y=row; y>=0; y--)
703 /* worth trying if there's something above it */
704 if (GRID_CONTENT(*g, as->checkColumn+1, y)) break;
705 if (y >= 0 && valid_position(pp, as->checkColumn+1, row,
706 as->checkRotation, &as->kg)) {
707 printf("Aliz: Trying to slip right.\n");
708 /* get a fresh copy */
709 memcpy(as->kg.contents, g->contents, (g->w * g->h * sizeof(as->kg.contents[0])));
710 memcpy(as->kg.fall, g->fall, (g->w * g->h * sizeof(*as->kg.fall)));
711 paste_on_board(pp, as->checkColumn+1, row,
712 as->checkRotation, &as->kg);
713 /* nLines is the same */
714 evalRight = evalBoard(&as->kg, nLines, row);
715 }
716 }
717
718 if (evalLeft >= 0 && evalLeft < as->bestEval && evalLeft <= evalRight) {
719 as->goalColumn = as->checkColumn;
720 as->goalSides = -1;
721 printf(": eval = %.3f left **", eval);
722 } else if (evalRight >= 0 && evalRight < as->bestEval && evalRight < evalLeft) {
723 as->goalColumn = as->checkColumn;
724 as->goalSides = 1;
725 printf(": eval = %.3f right **", eval);
726 }
727 else {
728 #ifdef DEBUG
729 printf(": eval = %.3f", eval);
730 #endif
731 if (as->bestEval == -1 || eval < as->bestEval) {
732 as->bestEval = eval;
733 as->goalColumn = as->checkColumn;
734 as->goalRotation = as->checkRotation;
735 as->goalSides = as->checkSides;
736 }
737 }
738 }
739 #ifdef DEBUG
740 printf("\n");
741 #endif
742 }
743
744 }
745
746 /*******************************************************************
747 * alizReset()
748 * Clear all of Kiri's globals.
749 *********************************************************************/
750 static void *
alizReset(void * state,Grid * g)751 alizReset(void *state, Grid *g)
752 {
753 Aliz_State *as;
754
755 if (state == NULL) {
756 /* first time we have been called (this game) */
757 Calloc(as, Aliz_State *,sizeof(Aliz_State));
758 } else
759 as = (Aliz_State *)state;
760 Assert(as);
761
762 #ifdef DEBUG
763 printf("Aliz: Clearing state.\n");
764 #endif
765 as->bestEval = -1;
766 as->foundBest = FALSE;
767 if (as->kg.contents == NULL) as->kg = generate_board(g->w, g->h, 0);
768 return as;
769 }
770
771 /*******************************************************************
772 * alizMove()
773 * Kiri's AI 'move' function. Possible retvals:
774 * MOVE_NONE Do nothing, fall normally.
775 * MOVE_LEFT [Try to] Move one column to the left.
776 * MOVE_RIGHT [Try to] Move one column to the right.
777 * MOVE_ROTATE [Try to] Rotate the piece.
778 * MOVE_DOWN Fall down really quickly.
779 *********************************************************************/
780 static Command
alizMove(void * state,Grid * g,play_piece * pp,play_piece * np,int col,int row,int rot)781 alizMove(void *state, Grid* g, play_piece* pp, play_piece* np, int col, int row, int rot)
782 {
783 Aliz_State *as = (Aliz_State *)state;
784 Assert(as);
785 if (rot == as->goalRotation) {
786 if (col == as->goalColumn) {
787 if (as->foundBest) {
788 if (GRID_CONTENT(*g, col, row+1)) {
789 if (as->goalSides == -1) return MOVE_LEFT;
790 else if (as->goalSides == 1) return MOVE_RIGHT;
791 }
792 return MOVE_DOWN;
793 }
794 else return MOVE_NONE;
795 } else if (col < as->goalColumn) return MOVE_RIGHT;
796 else return MOVE_LEFT;
797 } else return MOVE_ROTATE;
798
799
800 }
801
802 /*************************************************************************
803 * AI_Players_Setup()
804 * This function creates a structure describing all of the available AI
805 * players.
806 *******************************************************************PROTO*/
807 AI_Players *
AI_Players_Setup(void)808 AI_Players_Setup(void)
809 {
810 int i;
811 AI_Players *retval;
812
813 Calloc(retval, AI_Players *, sizeof(AI_Players));
814
815 retval->n = 4; /* change this to add another */
816 Calloc(retval->player, AI_Player *, sizeof(AI_Player) * retval->n);
817 i = 0;
818
819 retval->player[i].name = "Simple Robot";
820 retval->player[i].msg = "An introductory opponent.";
821 retval->player[i].move = wes_ai_move;
822 retval->player[i].think = beginner_ai_think;
823 retval->player[i].reset = wes_ai_reset;
824 i++;
825
826 retval->player[i].name = "Lightning";
827 retval->player[i].msg = "Warp-speed heuristics.";
828 retval->player[i].move = wes_ai_move;
829 retval->player[i].think = wes_ai_think;
830 retval->player[i].reset = wes_ai_reset;
831 i++;
832
833 retval->player[i].name = "Aliz";
834 retval->player[i].msg = "Kiri's codified wit and wisdom.";
835 retval->player[i].move = alizMove;
836 retval->player[i].think = alizCogitate;
837 retval->player[i].reset = alizReset;
838 i++;
839
840 retval->player[i].name = "Double-Think";
841 retval->player[i].msg = "Brilliant but slow.";
842 retval->player[i].move = double_ai_move;
843 retval->player[i].think = double_ai_think;
844 retval->player[i].reset = double_ai_reset;
845 i++;
846
847 Debug("AI Players Initialized (%d AIs).\n",retval->n);
848
849 return retval;
850 }
851
852 /***************************************************************************
853 * pick_key_repeat()
854 * Ask the player to select a keyboard repeat rate.
855 *********************************************************************PROTO*/
856 int
pick_key_repeat(SDL_Surface * screen)857 pick_key_repeat(SDL_Surface * screen)
858 {
859 char *factor;
860 int retval;
861
862 clear_screen_to_flame();
863 draw_string("(1 = Slow Repeat, 16 = Default, 32 = Fastest)",
864 color_purple, screen->w/2,
865 screen->h/2, DRAW_UPDATE | DRAW_CENTER | DRAW_ABOVE);
866 draw_string("Keyboard repeat delay factor:", color_purple,
867 screen->w/2, screen->h/2, DRAW_UPDATE | DRAW_LEFT);
868 factor = input_string(screen, screen->w/2, screen->h/2, 0);
869 retval = 0;
870 sscanf(factor,"%d",&retval);
871 free(factor);
872 if (retval < 1) retval = 1;
873 if (retval > 32) retval = 32;
874 clear_screen_to_flame();
875 return retval;
876 }
877
878 /***************************************************************************
879 * pick_ai_factor()
880 * Asks the player to choose an AI delay factor.
881 *********************************************************************PROTO*/
882 int
pick_ai_factor(SDL_Surface * screen)883 pick_ai_factor(SDL_Surface * screen)
884 {
885 char *factor;
886 int retval;
887
888 clear_screen_to_flame();
889 draw_string("(1 = Impossible, 100 = Easy, 0 = Set Automatically)",
890 color_purple, screen->w/2,
891 screen->h/2, DRAW_UPDATE | DRAW_CENTER | DRAW_ABOVE);
892 draw_string("Pick an AI delay factor:", color_purple,
893 screen->w/2, screen->h/2, DRAW_UPDATE | DRAW_LEFT);
894 factor = input_string(screen, screen->w/2, screen->h/2, 0);
895 retval = 0;
896 sscanf(factor,"%d",&retval);
897 free(factor);
898 if (retval < 0) retval = 0;
899 if (retval > 100) retval = 100;
900 return retval;
901 }
902
903
904 /***************************************************************************
905 * pick_an_ai()
906 * Asks the player to choose an AI.
907 *
908 * Returns -1 on "cancel".
909 *********************************************************************PROTO*/
910 int
pick_an_ai(SDL_Surface * screen,char * msg,AI_Players * AI)911 pick_an_ai(SDL_Surface *screen, char *msg, AI_Players *AI)
912 {
913 WalkRadioGroup *wrg;
914 int i, text_h;
915 int retval;
916 SDL_Event event;
917
918 wrg = create_single_wrg( AI->n + 1 );
919 for (i=0; i<AI->n ; i++) {
920 char buf[1024];
921 SPRINTF(buf,"\"%s\" : %s", AI->player[i].name, AI->player[i].msg);
922 wrg->wr[0].label[i] = strdup(buf);
923 }
924
925 wrg->wr[0].label[AI->n] = "-- Cancel --";
926
927 wrg->wr[0].defaultchoice = retval = 0;
928
929 if (wrg->wr[0].defaultchoice > AI->n)
930 PANIC("not enough choices!");
931
932 setup_radio(&wrg->wr[0]);
933
934 wrg->wr[0].x = (screen->w - wrg->wr[0].area.w) / 2;
935 wrg->wr[0].y = (screen->h - wrg->wr[0].area.h) / 2;
936
937 clear_screen_to_flame();
938
939 text_h = draw_string(msg, color_ai_menu, ( screen->w ) / 2,
940 wrg->wr[0].y - 30, DRAW_UPDATE | DRAW_CENTER);
941
942 draw_string("Choose a Computer Player", color_ai_menu, (screen->w ) /
943 2, (wrg->wr[0].y - 30) - text_h, DRAW_UPDATE | DRAW_CENTER);
944
945 draw_radio(&wrg->wr[0], 1);
946
947 while (1) {
948 int retval;
949 poll_and_flame(&event);
950
951 retval = handle_radio_event(wrg,&event);
952 if (retval == -1)
953 continue;
954 if (retval == AI->n)
955 return -1;
956 return retval;
957 }
958 }
959
960
961 /*
962 * $Log: ai.c,v $
963 * Revision 1.27 2001/01/05 21:12:31 weimer
964 * advance to atris 1.0.5, add support for ".atrisrc" and changing the
965 * keyboard repeat rate
966 *
967 * Revision 1.26 2000/11/06 04:06:44 weimer
968 * option menu
969 *
970 * Revision 1.25 2000/11/06 01:22:40 wkiri
971 * Updated menu system.
972 *
973 * Revision 1.24 2000/11/06 00:24:01 weimer
974 * add WalkRadioGroup modifications (inactive field for Kiri) and some support
975 * for special pieces
976 *
977 * Revision 1.23 2000/11/02 03:06:20 weimer
978 * better interface for walk-radio menus: we are now ready for Kiri to change
979 * them to add run-time options ...
980 *
981 * Revision 1.22 2000/11/01 04:39:41 weimer
982 * clear the little scoring spot correctly, updates for making a no-sound
983 * distribution
984 *
985 * Revision 1.21 2000/11/01 03:53:06 weimer
986 * modifications for version 1.0.1: you can pick your starting level, you can
987 * pick the AI difficulty factor, the game is better about placing new pieces
988 * when there is garbage, when things fall out of your control they now fall
989 * at a uniform rate ...
990 *
991 * Revision 1.20 2000/10/29 21:23:28 weimer
992 * One last round of header-file changes to reflect my newest and greatest
993 * knowledge of autoconf/automake. Now if you fail to have some bizarro
994 * function, we try to go on anyway unless it is vastly needed.
995 *
996 * Revision 1.19 2000/10/29 19:04:32 weimer
997 * minor highscore handling changes: new filename, use the draw_string() and
998 * draw_bordered_rect() and input_string() interfaces, handle the widget layer
999 * and the flame layer, etc. Also fix a minor bug where you would be prevented
1000 * from settling if you pressed a key even if it didn't really move you. :-)
1001 *
1002 * Revision 1.18 2000/10/29 17:23:13 weimer
1003 * incorporate "xflame" flaming background for added spiffiness ...
1004 *
1005 * Revision 1.17 2000/10/28 21:30:34 wkiri
1006 * Kiri AI rules!
1007 *
1008 * Revision 1.16 2000/10/21 01:14:42 weimer
1009 * massic autoconf/automake restructure ...
1010 *
1011 * Revision 1.15 2000/10/20 01:32:09 weimer
1012 * Minor play issue problems -- time is now truly a hard limit!
1013 *
1014 * Revision 1.14 2000/10/18 23:57:49 weimer
1015 * general fixup, color changes, display changes.
1016 * Notable: "Safe" Blits and Updates now perform "clipping". No more X errors,
1017 * we hope!
1018 *
1019 * Revision 1.13 2000/10/18 02:04:02 weimer
1020 * playability changes ...
1021 *
1022 * Revision 1.12 2000/10/14 16:17:41 weimer
1023 * level adjustment changes, added some new AIs, etc.
1024 *
1025 * Revision 1.11 2000/10/14 03:36:22 weimer
1026 * wessy AI changes: resource management
1027 *
1028 * Revision 1.10 2000/10/14 02:56:37 wkiri
1029 * Kiri AI gets another leg up.
1030 *
1031 * Revision 1.9 2000/10/14 01:56:35 weimer
1032 * remove dates from identity files
1033 *
1034 * Revision 1.8 2000/10/14 01:56:10 wkiri
1035 * Kiri AI comes of age!
1036 *
1037 * Revision 1.7 2000/10/14 01:24:34 weimer
1038 * fixed error with not advancing levels when fighting AI
1039 *
1040 * Revision 1.6 2000/10/13 22:34:26 weimer
1041 * minor wessy AI changes
1042 *
1043 * Revision 1.5 2000/10/13 21:16:43 wkiri
1044 * Aliz AI evolves!
1045 *
1046 * Revision 1.4 2000/10/13 16:37:39 weimer
1047 * Changed the AI so that it now passes state around via void pointers, rather
1048 * than using global variables. This allows the same AI to play itself. Also
1049 * changed the "AI vs. AI" display so that you can keep track of total wins
1050 * and losses.
1051 *
1052 * Revision 1.3 2000/10/13 15:41:53 weimer
1053 * revamped AI support, now you can pick your AI and have AI duels (such fun!)
1054 * the mighty Aliz AI still crashes a bit, though ... :-)
1055 *
1056 * Revision 1.2 2000/10/13 03:02:05 wkiri
1057 * Added Aliz (Kiri AI) to ai.c.
1058 * Note event.c currently calls Aliz, not Wessy AI.
1059 *
1060 * Revision 1.1 2000/10/12 19:19:43 weimer
1061 * Sigh!
1062 *
1063 */
1064