ai_minimax.c

   1 /*
   2 ** $Id$
   3 */
   4 /*
   5 **    Copyright (C) 1998 Kurt Van den Branden
   6 **
   7 ** This program is free software; you can redistribute it and/or modify
   8 ** it under the terms of the GNU General Public License as published by
   9 ** the Free Software Foundation; either version 2 of the License, or
  10 ** (at your option) any later version.
  11 **
  12 ** This program is distributed in the hope that it will be useful,
  13 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 ** GNU General Public License for more details.
  16 **
  17 ** You should have received a copy of the GNU General Public License
  18 ** along with this program; if not, write to the Free Software
  19 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20 */
  21
  22 #include "ai_minimax.h"
  23
  24 #ifdef WINGIPF
  25 extern void checkwindowevents (void);
  26 extern int interrupt_computer;
  27 #endif
  28
  29 #define RANDOMCHOOSE
  30 /*#define PRINTMOVES*/
  31
  32 /* structures for keeping my own info in */
  33 typedef struct {
  34     char colour;
  35     int game;
  36     struct {
  37         int searchdepth;
  38         int remoppgipf;
  39         int maxgipf;
  40 #ifdef RANDOMCHOOSE
  41         int randomchoose;
  42 #endif
  43     } config;
  44     listheader * movelist;  /* list of items of type nextmove */
  45 } minimax_info;
  46
  47 typedef struct {
  48     int remtype;   /* REM_GIPF or REM_ROW */
  49     listheader * gipflist; /* list of items of type gipfdata */
  50     struct {
  51         char * start;
  52         char * end;
  53     } rowdata;
  54 } nextmove;
  55
  56 #define REM_GIPF 1
  57 #define REM_ROW  2
  58
  59 typedef struct {
  60     char from[3];
  61     char to[3];
  62     char type;
  63     listheader * movelist; /* list of items of type nextmove */
  64     int value;
  65 } movestruct;
  66
  67 typedef struct {
  68     board * sboard;
  69     char to[3];
  70 } saveboard;
  71
  72 typedef struct {
  73     char pos[3];
  74     char flag;
  75 } gipfdata;
  76
  77 typedef struct {
  78     rem_gipf * gipf;
  79     int flag;
  80 } gipfitem;
  81
  82
  83 #define MINNODE 1
  84 #define MAXNODE 2
  85
  86 movestruct * alfabeta_move (board * oboard, int alfa, int beta, int minmax,
  87                             int depth, minimax_info * me);
  88 movestruct * move (board * oboard, int alfa, int beta, int minmax, int depth,
  89                    minimax_info * me, fromto * todo, saveboard * lmove);
  90 movestruct * alfabeta_gipf (board * oboard, int alfa, int beta, int minmax,
  91                             int depth, minimax_info * me);
  92 movestruct * remove_gipflist (board * oboard, int alfa, int beta, int minmax,
  93                               int depth, minimax_info * me, listheader * myg,
  94                               listheader * otherg);
  95 movestruct * alfabeta_row (board * oboard, int alfa, int beta, int minmax,
  96                            int depth, minimax_info * me);
  97 movestruct * remove_row (board * oboard, int alfa, int beta, int minmax,
  98                          int depth, minimax_info * me, int rem);
  99 int evaluate (board * oboard, minimax_info * me);
 100 void del_move (movestruct * todel);
 101
 102 #ifdef RANDOMCHOOSE
 103 int equ_l (int nr1, int nr2, int * chance, minimax_info * me, int depth);
 104 int equ_h (int nr1, int nr2, int * chance, minimax_info * me, int depth);
 105 #endif
 106
 107 void * minimax_new (char colour, int game)
 108 {
 109     minimax_info * me;
 110     listheader * configlist;
 111
 112     me = (minimax_info *) malloc (sizeof (minimax_info));
 113     me->colour = colour;
 114     me->game = game;
 115     me->movelist = NULL;
 116
 117     /* check for config-values from the config-file */
 118     configlist = readconfigfile ("gf1.cfg");
 119
 120     me->config.searchdepth = findconfigvalue (configlist, "searchdepth",
 121                                               colour, 2);
 122     me->config.remoppgipf = findconfigvalue (configlist, "remoppgipf",
 123                                              colour, 1);
 124     me->config.maxgipf = findconfigvalue (configlist, "maxgipf",
 125                                           colour, 3);
 126 #ifdef RANDOMCHOOSE
 127     me->config.randomchoose = findconfigvalue (configlist, "randomchoose",
 128                                                colour, 1);
 129 #endif
 130
 131     clearconfiglist (configlist);
 132
 133     return ((void *) me);
 134 }
 135
 136
 137 void minimax_move (board * oboard, void * self,
 138                    char * type, char * from, char * to)
 139 {
 140     minimax_info * me = self;
 141     int depth = 1;
 142     movestruct * move;
 143
 144     b_nolog (oboard);
 145
 146     move = alfabeta_move (oboard, -1001, 1001, MAXNODE, depth, me);
 147
 148     from[0] = move->from[0];
 149     from[1] = move->from[1];
 150     to[0] = move->to[0];
 151     to[1] = move->to[1];
 152     *type = move->type;
 153
 154     me->movelist = move->movelist;
 155
 156 #ifdef PRINTMOVES
 157     printf ("ai_minimax %c (%d): move %2s-%2s\n",
 158             me->colour, move->value, from, to);
 159 #endif
 160
 161     move->movelist = NULL;
 162     del_move (move);
 163
 164     return;
 165 }
 166
 167
 168 char minimax_gipf (board * oboard, void * self, char * pos)
 169 {
 170     minimax_info * me = self;
 171     nextmove * movedata;
 172     gipfdata * gipfd;
 173     int counter;
 174     char val;
 175
 176     b_nolog (oboard);
 177
 178     /* check if movelist contains info about removing gipf-pieces */
 179     if (me->movelist == NULL)
 180     {
 181         /*
 182         ** no info in movelist, my opponent made 4 in a row
 183         ** with my pieces (only possible explanation)
 184         */
 185         int depth = 1;
 186         movestruct * nmove;
 187
 188         /* remark: I have to start this as a min-node,
 189         ** because this is really my opponents move */
 190         nmove = alfabeta_gipf (oboard, -1001, 1001, MINNODE, depth, me);
 191         me->movelist = nmove->movelist;
 192         nmove->movelist = NULL;
 193         del_move (nmove);
 194     }
 195
 196     /* now check the movelist for the move we have to make */
 197     if (((movedata = (nextmove *) llitembynr (me->movelist, 1)) == NULL) ||
 198         (movedata->remtype != REM_GIPF))
 199     {
 200         /* very wrong */
 201 #ifdef PRINTMOVES
 202         printf ("action removegipf, but nextmove contains something else\n\n");
 203 #endif
 204         exit (0);
 205     }
 206
 207     /* look for the gipf to remove */
 208     counter = 1;
 209     while ((gipfd = (gipfdata *) llitembynr (movedata->gipflist, counter))
 210            != NULL)
 211     {
 212         if ((gipfd->pos[0] == pos[0]) && (gipfd->pos[1] == pos[1]))
 213         {
 214             break;
 215         }
 216         counter++;
 217     }
 218     if (gipfd == NULL)
 219     {
 220         /* very wrong */
 221 #ifdef PRINTMOVES
 222         printf ("action removegipf, but the gipf isn't in nextmove\n\n");
 223 #endif
 224         exit (0);
 225     }
 226     /* remove gipf from list */
 227     gipfd = (gipfdata *) llrembynr (movedata->gipflist, counter);
 228
 229     /* remove nextmove from movelist if gipflist is empty */
 230     if (llitembynr (movedata->gipflist, 1) == NULL)
 231     {
 232         movedata = (nextmove *) llrembynr (me->movelist, 1);
 233         free (movedata->gipflist);
 234         free (movedata);
 235
 236         /* remove movelist if empty */
 237         if (llitembynr (me->movelist, 1) == NULL)
 238         {
 239             free (me->movelist);
 240             me->movelist = NULL;
 241         }
 242     }
 243
 244     val = gipfd->flag;
 245     free (gipfd);
 246
 247 #ifdef PRINTMOVES
 248     printf ("ai_minimax %c: remove gipf %2s (%c)\n", me->colour, pos, val);
 249 #endif
 250     return (val);
 251 }
 252
 253
 254 char minimax_row (board * oboard, void * self, char * start, char * end)
 255 {
 256     minimax_info * me = self;
 257     nextmove * movedata;
 258     int correct;
 259
 260     b_nolog (oboard);
 261
 262     /* check if movelist contains info about removing rows */
 263     if (me->movelist == NULL)
 264     {
 265         /*
 266         ** no info in movelist, my opponent made several "4 in a row"s
 267         ** with my pieces (only possible explanation)
 268         */
 269         int depth = 1;
 270         movestruct * nmove;
 271
 272         /* remark: I have to start this as a min-node,
 273         ** because this is really my opponents move */
 274         nmove = alfabeta_row (oboard, -1001, 1001, MINNODE, depth, me);
 275         me->movelist = nmove->movelist;
 276         nmove->movelist = NULL;
 277         del_move (nmove);
 278     }
 279
 280     /* now check the movelist for the move we have to make */
 281     if (((movedata = (nextmove *) llitembynr (me->movelist, 1)) == NULL) ||
 282         (movedata->remtype != REM_ROW))
 283     {
 284         /* very wrong */
 285 #ifdef PRINTMOVES
 286         printf ("action removerow, but nextmove contains something else\n\n");
 287 #endif
 288         exit (0);
 289     }
 290
 291     correct = 0;
 292     /* check if this is the correct row to be removed */
 293     if ((start[0] == movedata->rowdata.start[0]) &&
 294         (start[1] == movedata->rowdata.start[1]))
 295     {
 296         if ((end[0] == movedata->rowdata.end[0]) &&
 297             (end[1] == movedata->rowdata.end[1]))
 298         {
 299             correct = 1;
 300         }
 301     }
 302     else if ((start[0] == movedata->rowdata.end[0]) &&
 303              (start[1] == movedata->rowdata.end[1]))
 304     {
 305         if ((end[0] == movedata->rowdata.start[0]) &&
 306             (end[1] == movedata->rowdata.start[1]))
 307         {
 308             correct = 1;
 309         }
 310     }
 311
 312     if (correct)
 313     {
 314         /* remove nextmove from movelist */
 315         movedata = (nextmove *) llrembynr (me->movelist, 1);
 316         free (movedata->rowdata.start);
 317         free (movedata->rowdata.end);
 318         free (movedata);
 319
 320         /* remove movelist if empty */
 321         if (llitembynr (me->movelist, 1) == NULL)
 322         {
 323             free (me->movelist);
 324             me->movelist = NULL;
 325         }
 326
 327 #ifdef PRINTMOVES
 328         printf ("ai_minimax %c: remove row %2s-%2s\n", me->colour, start, end);
 329 #endif
 330         return ('y');
 331     }
 332
 333     /* don't remove the row */
 334 #ifdef PRINTMOVES
 335     printf ("ai_minimax %c: don't remove row %2s-%2s\n",
 336             me->colour, start, end);
 337 #endif
 338
 339     return ('n');
 340 }
 341
 342
 343 void minimax_end (void * self)
 344 {
 345     minimax_info * me = self;
 346
 347     /* do I have to clean up the movelist first */
 348
 349     free (me);
 350     return;
 351 }
 352
 353
 354 movestruct * alfabeta_move (board * oboard, int alfa, int beta, int minmax,
 355                             int depth, minimax_info * me)
 356 {
 357     movestruct * nmove,
 358         * bestmove = NULL;
 359     fromto * allmoves;
 360     int maxmoves,
 361         chance=1,
 362         value,
 363         i;
 364     saveboard lastmove;
 365
 366     /* maximum search depth or end of game */
 367     if ((b_game_finished (oboard)) ||
 368         (depth > me->config.searchdepth))
 369     {
 370         nmove = (movestruct *) malloc (sizeof (movestruct));
 371         nmove->from[0] = '\0';
 372         nmove->to[0] = '\0';
 373         nmove->type = 0;
 374         nmove->movelist = NULL;
 375         nmove->value = evaluate (oboard, me);
 376         return (nmove);
 377     }
 378
 379 #ifdef WINGIPF
 380     if ((depth == 1) || (depth < me->config.searchdepth))
 381     {
 382         checkwindowevents ();
 383     }
 384 #endif
 385
 386     /* list of moves to try depends on the question if we can
 387     ** place a gipf or not.
 388     ** cutoff after a predetermined number of gipf-pieces */
 389     if ((b_colour_type (oboard, b_next_piece (oboard)) == 'g') &&
 390         (b_colour_gipf (oboard, b_next_piece (oboard)) < me->config.maxgipf))
 391     {
 392         allmoves = allmovesg;
 393         maxmoves = 84;
 394     }
 395     else
 396     {
 397         allmoves = allmovesn;
 398         maxmoves = 42;
 399     }
 400
 401     lastmove.sboard = NULL;
 402
 403     if (minmax == MAXNODE)
 404     {
 405         value = -1001;
 406
 407         for (i = 0; i < maxmoves; i++)
 408         {
 409             nmove = move (oboard, alfa, beta, minmax, depth, me,
 410                           &(allmoves[i]), &lastmove);
 411             if (nmove == NULL)
 412             {
 413                 continue;
 414             }
 415 #ifdef RANDOMCHOOSE
 416             if (equ_h (nmove->value, value, &chance, me, depth))
 417 #else
 418             if (nmove->value > value)
 419 #endif
 420             {
 421                 value = nmove->value;
 422                 if (bestmove != NULL)
 423                 {
 424                     del_move (bestmove);
 425                 }
 426                 bestmove = nmove;
 427             }
 428             else
 429             {
 430                 del_move (nmove);
 431             }
 432             alfa = max (alfa, value);
 433
 434 #ifdef RANDOMCHOOSE
 435             if (value > beta)
 436 #else
 437             if (value >= beta)
 438 #endif
 439             {
 440                 /*
 441                 ** problems if value is the same as beta, this means that
 442                 ** when randomly selecting a move from the moves with the
 443                 ** same value, this one could be chosen.
 444                 ** solution: change value to (-1001 or 1001)
 445                 **           or the current value (+1 or -1)
 446                 **
 447                 ** is this correct? or does it depend on the fact if
 448                 ** this was called from a min- or a max-node?
 449                 */
 450                 break;
 451             }
 452         }
 453     }
 454     else
 455     {
 456         value = 1001;
 457
 458         for (i = 0; i < maxmoves; i++)
 459         {
 460             nmove = move (oboard, alfa, beta, minmax, depth, me,
 461                           &(allmoves[i]), &lastmove);
 462             if (nmove == NULL)
 463             {
 464                 continue;
 465             }
 466 #ifdef RANDOMCHOOSE
 467             if (equ_l (nmove->value, value, &chance, me, depth))
 468 #else
 469             if (nmove->value < value)
 470 #endif
 471             {
 472                 value = nmove->value;
 473                 if (bestmove != NULL)
 474                 {
 475                     del_move (bestmove);
 476                 }
 477                 bestmove = nmove;
 478             }
 479             else
 480             {
 481                 del_move (nmove);
 482             }
 483             /* how and when did I throw this out ?????? */
 484             beta = min (beta, value);
 485
 486 #ifdef RANDOMCHOOSE
 487             if (value < alfa)
 488 #else
 489             if (value <= alfa)
 490 #endif
 491             {
 492                 break;
 493             }
 494         }
 495     }
 496
 497     if (lastmove.sboard != NULL)
 498     {
 499         b_del (lastmove.sboard);
 500     }
 501
 502     return (bestmove);
 503 }
 504
 505
 506 movestruct * move (board * oboard, int alfa, int beta, int minmax, int depth,
 507                    minimax_info * me, fromto * todo, saveboard * lmove)
 508 {
 509     char piece;
 510     int newminmax;
 511     board * newboard;
 512     movestruct * mymove,
 513         * nmove;
 514
 515     if (todo->type == 'g')
 516     {
 517         piece = b_otherpiece (b_next_piece (oboard));
 518     }
 519     else
 520     {
 521         piece = b_next_piece (oboard);
 522     }
 523
 524     newboard = b_move (oboard, todo->from, todo->to, piece);
 525
 526     if (newboard == NULL)
 527     {
 528         return (NULL);
 529     }
 530
 531     /* check if the result is the same as the last move */
 532     if ((lmove->sboard != NULL) &&
 533         ((lmove->to[0] == todo->to[0]) && (lmove->to[1] == todo->to[1])) &&
 534         (b_compare (newboard, lmove->sboard) == 0))
 535     {
 536         b_del (newboard);
 537         return (NULL);
 538     }
 539     if (lmove->sboard != NULL)
 540     {
 541         b_del (lmove->sboard);
 542     }
 543     lmove->sboard = newboard; /* don't delete the board at the end */
 544     lmove->to[0] = todo->to[0];
 545     lmove->to[1] = todo->to[1];
 546
 547     /* create new movestruct */
 548     mymove = (movestruct *) malloc (sizeof (movestruct));
 549     mymove->from[0] = todo->from[0];
 550     mymove->from[1] = todo->from[1];
 551     mymove->to[0] = todo->to[0];
 552     mymove->to[1] = todo->to[1];
 553     mymove->type = todo->type;
 554     mymove->movelist = NULL;
 555
 556     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 557     if ((b_status (newboard) == S_NORMAL) ||
 558         (b_status (newboard) == S_FINISHED))
 559     {
 560         nmove = alfabeta_move (newboard, alfa, beta, newminmax, depth+1, me);
 561         mymove->value = nmove->value;
 562         del_move (nmove);
 563     }
 564     else if (b_status (newboard) == S_REMOVEROW)
 565     {
 566         nmove = alfabeta_row (newboard, alfa, beta, minmax, depth, me);
 567         mymove->movelist = nmove->movelist;
 568         mymove->value = nmove->value;
 569         nmove->movelist = NULL;
 570         del_move (nmove);
 571     }
 572     else if (b_status (newboard) == S_REMOVEGIPF)
 573     {
 574         nmove = alfabeta_gipf (newboard, alfa, beta, minmax, depth, me);
 575         mymove->movelist = nmove->movelist;
 576         mymove->value = nmove->value;
 577         nmove->movelist = NULL;
 578         del_move (nmove);
 579     }
 580     else
 581     {   /* impossible */
 582 #ifdef PRINTMOVES
 583         printf ("ERROR: impossible in ai_minimax::move\n\n");
 584 #endif
 585         exit (0);
 586     }
 587
 588     /* don't cleanup newboard here */
 589     return (mymove);
 590 }
 591
 592
 593 movestruct * alfabeta_gipf (board * oboard, int alfa, int beta, int minmax,
 594                             int depth, minimax_info * me)
 595 {
 596     movestruct * nmove,
 597         * bestmove = NULL;
 598     int value,
 599         realminmax,
 600         counter,
 601         mynr,
 602         i,
 603         maxnr;
 604     unsigned char bits1,
 605         bits2;
 606     rem_gipf * gipfi;
 607     listheader * myg,
 608         * otherg;
 609     char * gipfpos;
 610     gipfitem * gipfflag;
 611
 612     gipfi = (rem_gipf *) llitembynr (b_gipf_extra (oboard), 1);
 613
 614     /*
 615     ** I may have to change if I am a min or a max-node here
 616     ** it's possible that my opponent won a row, so he has to
 617     ** decide if gipf-pieces must be removed
 618     */
 619     if (b_gipf_owner(gipfi) == b_next_piece (oboard))
 620     {
 621         realminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 622     }
 623     else
 624     {
 625         realminmax = minmax;
 626     }
 627
 628     /* always remove gipf-pieces from my opponent if the flag is set */
 629     myg = (listheader *) malloc (sizeof (listheader));
 630     newlist (myg);
 631     otherg = (listheader *) malloc (sizeof (listheader));
 632     newlist (otherg);
 633     counter = 1;
 634     mynr = 0;
 635     while ((gipfi = (rem_gipf *) llitembynr (b_gipf_extra (oboard), counter))
 636            != NULL)
 637     {
 638         counter++;
 639         gipfflag = (gipfitem *) malloc (sizeof (gipfitem));
 640         gipfflag->gipf = gipfi;
 641         gipfflag->flag = 1;
 642
 643         gipfpos = b_gipf_position (gipfi);
 644         if ((me->config.remoppgipf == 1) &&
 645             (b_otherpiece (b_gipf_owner (gipfi)) !=
 646              b_piece (oboard, gipfpos)))
 647         {
 648             pushll (otherg, (void *) gipfflag);
 649         }
 650         else
 651         {
 652             mynr++;
 653             pushll (myg, (void *) gipfflag);
 654         }
 655         free (gipfpos);
 656     }
 657
 658     maxnr = 1 << mynr; /* 2 ^ mynr */
 659
 660     if (realminmax == MAXNODE)
 661     {
 662         value = -1001;
 663
 664         for (bits1 = 0; bits1 < maxnr ; bits1++)
 665         {
 666             bits2 = bits1;
 667             for (i = 0; i < mynr; i++)
 668             {
 669                 gipfflag = (gipfitem *) llitembynr (myg, i+1);
 670                 gipfflag->flag = bits2 & 1;
 671                 bits2 = bits2 >> 1;
 672             }
 673             nmove = remove_gipflist (oboard, alfa, beta, minmax, depth, me,
 674                                      myg, otherg);
 675
 676             if (nmove->value > value)
 677             {
 678                 value = nmove->value;
 679                 if (bestmove != NULL)
 680                 {
 681                     del_move (bestmove);
 682                 }
 683                 bestmove = nmove;
 684             }
 685             else
 686             {
 687                 del_move (nmove);
 688             }
 689             alfa = max (alfa, value);
 690
 691 #ifdef RANDOMCHOOSE
 692             if (value > beta)
 693 #else
 694             if (value >= beta)
 695 #endif
 696             {
 697                 break;
 698             }
 699         }
 700     }
 701     else
 702     {
 703         value = 1001;
 704
 705         for (bits1 = 0; bits1 < maxnr ; bits1++)
 706         {
 707             bits2 = bits1;
 708             for (i = 0; i < mynr; i++)
 709             {
 710                 gipfflag = (gipfitem *) llitembynr (myg, i+1);
 711                 gipfflag->flag = bits2 & 1;
 712                 bits2 = bits2 >> 1;
 713             }
 714             nmove = remove_gipflist (oboard, alfa, beta, minmax, depth, me,
 715                                      myg, otherg);
 716
 717             if (nmove->value < value)
 718             {
 719                 value = nmove->value;
 720                 if (bestmove != NULL)
 721                 {
 722                     del_move (bestmove);
 723                 }
 724                 bestmove = nmove;
 725             }
 726             else
 727             {
 728                 del_move (nmove);
 729             }
 730             beta = min (beta, value);
 731
 732 #ifdef RANDOMCHOOSE
 733             if (value < alfa)
 734 #else
 735             if (value <= alfa)
 736 #endif
 737             {
 738                 break;
 739             }
 740         }
 741     }
 742
 743     /* cleanup temporary lists */
 744     while ((gipfflag = (gipfitem *) llrembynr (myg, 1)) != NULL)
 745     {
 746         free (gipfflag);
 747     }
 748     free (myg);
 749     while ((gipfflag = (gipfitem *) llrembynr (otherg, 1)) != NULL)
 750     {
 751         free (gipfflag);
 752     }
 753     free (otherg);
 754
 755     return (bestmove);
 756 }
 757
 758
 759 movestruct * remove_gipflist (board * oboard, int alfa, int beta, int minmax,
 760                               int depth, minimax_info * me, listheader * myg,
 761                               listheader * otherg)
 762 {
 763     board * nboard,
 764         * newboard;
 765     movestruct * mymove,
 766         * nmove;
 767     int counter;
 768     gipfitem * gipfflag;
 769     listheader * remlist;
 770     gipfdata * gipfd;
 771     char * strpos,
 772         owner;
 773     nextmove * movedata;
 774     int newminmax;
 775
 776     newboard = oboard;
 777     remlist = (listheader *) malloc (sizeof (listheader));;
 778     newlist (remlist);
 779     /* list of gipf-pieces that may or may not have to be removed */
 780     counter = 1;
 781     while ((gipfflag = (gipfitem *) llitembynr (myg, counter)) != NULL)
 782     {
 783         counter++;
 784         gipfd = (gipfdata *) malloc (sizeof (gipfdata));
 785         strpos = b_gipf_position (gipfflag->gipf);
 786         owner = b_gipf_owner (gipfflag->gipf);
 787         gipfd->pos[0] = strpos[0];
 788         gipfd->pos[1] = strpos[1];
 789         gipfd->pos[2] = '\0';
 790         free (strpos);
 791
 792         if (gipfflag->flag == 1)
 793         {
 794             gipfd->flag = 'y';
 795             nboard = b_remove_gipf (newboard, gipfflag->gipf);
 796             if (newboard != oboard)
 797             {
 798                 b_del (newboard);
 799             }
 800             newboard = nboard;
 801         }
 802         else
 803         {
 804             gipfd->flag = 'n';
 805         }
 806         pushll (remlist, (void *) gipfd);
 807     }
 808
 809     /* list of gipf-pieces that always have to be removed */
 810     counter = 1;
 811     while ((gipfflag = (gipfitem *) llitembynr (otherg, counter)) != NULL)
 812     {
 813         counter++;
 814         gipfd = (gipfdata *) malloc (sizeof (gipfdata));
 815         strpos = b_gipf_position (gipfflag->gipf);
 816         owner = b_gipf_owner (gipfflag->gipf);
 817         gipfd->pos[0] = strpos[0];
 818         gipfd->pos[1] = strpos[1];
 819         gipfd->pos[2] = '\0';
 820         free (strpos);
 821
 822         gipfd->flag = 'y';
 823         nboard = b_remove_gipf (newboard, gipfflag->gipf);
 824         if (newboard != oboard)
 825         {
 826             b_del (newboard);
 827         }
 828         newboard = nboard;
 829         pushll (remlist, (void *) gipfd);
 830     }
 831
 832     /* check again for 4 in a row */
 833     nboard = b_checkfour (newboard);
 834     if (newboard != oboard)
 835     {
 836         b_del (newboard);
 837     }
 838     newboard = nboard;
 839
 840     mymove = (movestruct *) malloc (sizeof (movestruct));
 841     mymove->from[0] = '\0';
 842     mymove->to[0] = '\0';
 843     mymove->type = 0;
 844     mymove->movelist = (listheader *) malloc (sizeof (listheader));
 845     newlist (mymove->movelist);
 846
 847     /*
 848     ** only add actions to the movelist if they have to be executed
 849     ** by the max-player
 850     ** this means moves for the min-player will not be executable,
 851     ** but that really isn't necessary
 852     */
 853     if (me->colour == owner)
 854     {
 855         movedata = (nextmove *) malloc (sizeof (nextmove));
 856         movedata->remtype = REM_GIPF;
 857         movedata->gipflist = remlist;
 858         pushll (mymove->movelist, (void *) movedata);
 859     }
 860     else
 861     {   /* remove remlist, we don't need it here */
 862         while ((gipfd = (gipfdata *) llrembynr (remlist, 1)) != NULL)
 863         {
 864             free (gipfd);
 865         }
 866         free (remlist);
 867     }
 868
 869     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 870
 871     if ((b_status (newboard) == S_NORMAL) ||
 872         (b_status (newboard) == S_FINISHED))
 873     {
 874         nmove = alfabeta_move (newboard, alfa, beta, newminmax, depth+1, me);
 875         mymove->value = nmove->value;
 876         del_move (nmove);
 877     }
 878     else if (b_status (newboard) == S_REMOVEROW)
 879     {
 880         nmove = alfabeta_row (newboard, alfa, beta, minmax, depth, me);
 881
 882         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
 883                != NULL)
 884         {
 885             pushll (mymove->movelist, (void *) movedata);
 886         }
 887
 888         mymove->value = nmove->value;
 889         del_move (nmove);
 890     }
 891     else if (b_status (newboard) == S_REMOVEGIPF)
 892     {
 893         nmove = alfabeta_gipf (newboard, alfa, beta, minmax, depth, me);
 894
 895         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
 896                != NULL)
 897         {
 898             pushll (mymove->movelist, (void *) movedata);
 899         }
 900
 901         mymove->value = nmove->value;
 902         del_move (nmove);
 903     }
 904     else
 905     {   /* impossible */
 906 #ifdef PRINTMOVES
 907         printf ("ERROR: impossible in ai_minimax::remove_gipf\n\n");
 908 #endif
 909         exit (0);
 910     }
 911
 912     b_del (newboard);
 913
 914     /* check if the movelist of mymove contains something */
 915     if (llitembynr (mymove->movelist, 1) == NULL)
 916     {
 917         free (mymove->movelist);
 918         mymove->movelist = NULL;
 919     }
 920
 921     return (mymove);
 922 }
 923
 924
 925 movestruct * alfabeta_row (board * oboard, int alfa, int beta, int minmax,
 926                            int depth, minimax_info * me)
 927 {
 928     int counter,
 929         value,
 930         realminmax;
 931     movestruct * nmove,
 932         * bestmove = NULL;
 933     rem_row * rowi;
 934     listheader * rowlist;
 935
 936     rowlist = b_row_extra (oboard);
 937     rowi = (rem_row *) llitembynr (rowlist, 1);
 938
 939     /*
 940     ** I may have to change if I am a min or a max-node here
 941     ** it's possible that my opponent won several rows, so he has to
 942     ** decide what row to remove
 943     */
 944     if (row_owner(rowi) == b_next_piece (oboard))
 945     {
 946         realminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 947     }
 948     else
 949     {
 950         realminmax = minmax;
 951     }
 952
 953     if (realminmax == MAXNODE)
 954     {
 955         value = -1001;
 956
 957         counter = 1;
 958         while ((rowi = (rem_row *) llitembynr (rowlist, counter))
 959                != NULL)
 960         {
 961             nmove = remove_row (oboard, alfa, beta, minmax, depth, me,
 962                                 counter);
 963             counter++;
 964
 965             if (nmove->value > value)
 966             {
 967                 value = nmove->value;
 968                 if (bestmove != NULL)
 969                 {
 970                     del_move (bestmove);
 971                 }
 972                 bestmove = nmove;
 973             }
 974             else
 975             {
 976                 del_move (nmove);
 977             }
 978             alfa = max (alfa, value);
 979
 980 #ifdef RANDOMCHOOSE
 981             if (value > beta)
 982 #else
 983             if (value >= beta)
 984 #endif
 985             {
 986                 break;
 987             }
 988         }
 989     }
 990     else
 991     {
 992         value = 1001;
 993
 994         counter = 1;
 995         while ((rowi = (rem_row *) llitembynr (rowlist, counter))
 996                != NULL)
 997         {
 998             nmove = remove_row (oboard, alfa, beta, minmax, depth, me,
 999                                 counter);
1000             counter++;
1001
1002             if (nmove->value < value)
1003             {
1004                 value = nmove->value;
1005                 if (bestmove != NULL)
1006                 {
1007                     del_move (bestmove);
1008                 }
1009                 bestmove = nmove;
1010             }
1011             else
1012             {
1013                 del_move (nmove);
1014             }
1015             beta = min (beta, value);
1016
1017 #ifdef RANDOMCHOOSE
1018             if (value < alfa)
1019 #else
1020             if (value <= alfa)
1021 #endif
1022             {
1023                 break;
1024             }
1025         }
1026     }
1027
1028     return (bestmove);
1029 }
1030
1031
1032 movestruct * remove_row (board * oboard, int alfa, int beta, int minmax,
1033                          int depth, minimax_info * me, int rem)
1034 {
1035     board * newboard;
1036     movestruct * nmove,
1037         * mymove;
1038     rem_row * remi;
1039     nextmove * movedata;
1040     int newminmax;
1041
1042     newboard = b_remove_row (oboard, rem);
1043
1044     mymove = (movestruct *) malloc (sizeof (movestruct));
1045     mymove->from[0] = '\0';
1046     mymove->to[0] = '\0';
1047     mymove->type = 0;
1048     mymove->movelist = (listheader *) malloc (sizeof (listheader));
1049     newlist (mymove->movelist);
1050
1051     /*
1052     ** only add actions to the movelist if they have to be executed
1053     ** by the max-player
1054     ** this means moves for the min-player will not be executable,
1055     ** but that really isn't necessary
1056     */
1057     remi = (rem_row *) llitembynr (b_row_extra (oboard), rem);
1058     if (me->colour == row_owner (remi))
1059     {
1060         movedata = (nextmove *) malloc (sizeof (nextmove));
1061         movedata->remtype = REM_ROW;
1062         movedata->gipflist = NULL;
1063         movedata->rowdata.start = postostr (remi->startpos);
1064         movedata->rowdata.end = postostr (remi->endpos);
1065         pushll (mymove->movelist, (void *) movedata);
1066     }
1067
1068     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
1069
1070     if ((b_status (newboard) == S_NORMAL) ||
1071         (b_status (newboard) == S_FINISHED))
1072     {
1073         nmove = alfabeta_move (newboard, alfa, beta, newminmax, depth+1, me);
1074         mymove->value = nmove->value;
1075         del_move (nmove);
1076     }
1077     else if (b_status (newboard) == S_REMOVEROW)
1078     {
1079         nmove = alfabeta_row (newboard, alfa, beta, minmax, depth, me);
1080
1081         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1082                != NULL)
1083         {
1084             pushll (mymove->movelist, (void *) movedata);
1085         }
1086
1087         mymove->value = nmove->value;
1088         del_move (nmove);
1089     }
1090     else if (b_status (newboard) == S_REMOVEGIPF)
1091     {
1092         nmove = alfabeta_gipf (newboard, alfa, beta, minmax, depth, me);
1093
1094         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1095                != NULL)
1096         {
1097             pushll (mymove->movelist, (void *) movedata);
1098         }
1099
1100         mymove->value = nmove->value;
1101         del_move (nmove);
1102     }
1103     else
1104     {   /* impossible */
1105 #ifdef PRINTMOVES
1106         printf ("ERROR: impossible in ai_minimax::remove_row\n\n");
1107 #endif
1108         exit (0);
1109     }
1110
1111     b_del (newboard);
1112
1113     /* check if the movelist of mymove contains something */
1114     if (llitembynr (mymove->movelist, 1) == NULL)
1115     {
1116         free (mymove->movelist);
1117         mymove->movelist = NULL;
1118     }
1119
1120     return (mymove);
1121 }
1122
1123 static struct {
1124     position coor;
1125     int value;
1126 } pos_val[] = {
1127     {{4, 5}, 5},
1128     {{3, 4}, 2},{{3, 5}, 2},{{4, 6}, 2},{{5, 5}, 2},{{5, 4}, 2},{{4, 4}, 2},
1129     {{2, 3}, 1},{{2, 4}, 1},{{2, 5}, 1},{{3, 6}, 1},{{4, 7}, 1},{{5, 6}, 1},
1130     {{6, 5}, 1},{{6, 4}, 1},{{6, 3}, 1},{{5, 3}, 1},{{4, 3}, 1},{{3, 3}, 1}
1131 };
1132
1133 /*
1134 ** calculate the value of a certain board position
1135 **
1136 ** returns a value between 1000 and -1000 (inclusive)
1137 **   1000 : I win
1138 **  -1000 : my opponent wins
1139 */
1140 int evaluate (board * oboard, minimax_info * me)
1141 {
1142     int total,
1143         i,
1144         value;
1145     double wvalue,
1146         bvalue;
1147     char myc,
1148         otherc,
1149         piece;
1150     position * pos;
1151
1152     myc = me->colour;
1153     otherc = b_opponent (myc);
1154
1155     if (b_game_finished (oboard))
1156     {
1157         if (b_winner (oboard) == myc)
1158         {
1159             return (1000);
1160         }
1161         else
1162         {
1163             return (-1000);
1164         }
1165     }
1166
1167     /* maybe I can return 1000 or -1000, but I'm not completely sure */
1168     if (b_colour (oboard, myc) == 0)
1169     {
1170         return (-999);
1171     }
1172     else if (b_colour (oboard, otherc) == 0)
1173     {
1174         return (999);
1175     }
1176
1177     /* I need to start with a base-value, or I get a lot of
1178     ** problems at the start of tournament games */
1179     wvalue = 20;
1180     bvalue = 20;
1181
1182     /* capturing a piece from your opponent is worth 20 points */
1183     wvalue += 20 * b_black_lost (oboard);
1184     bvalue += 20 * b_white_lost (oboard);
1185
1186     /* 1 point for each piece in use on the board */
1187     if (b_white_gipf (oboard) == -1)
1188         total = 15;
1189     else
1190         total = 18;
1191
1192     wvalue += total - b_white (oboard) - b_white_lost (oboard);
1193     bvalue += total - b_black (oboard) - b_black_lost (oboard);
1194
1195     /* 2 pieces or less left is getting dangerous */
1196
1197     /* one gipf left can be dangerous, subtract 5 points */
1198     if (b_white_gipf (oboard) == 1)
1199     {
1200         wvalue -= 5;
1201     }
1202     if (b_black_gipf (oboard) == 1)
1203     {
1204         bvalue -= 5;
1205     }
1206
1207     /* pieces closer to the center have a higher value */
1208     for (i = 0; i < 19; i++)
1209     {
1210         pos = &(pos_val[i].coor);
1211         piece = b_ppiece (oboard, pos);
1212         if (piece == '.')
1213         {
1214             continue;
1215         }
1216         if (piece == 'o')
1217         {
1218             wvalue += pos_val[i].value;
1219         }
1220         else if (piece == 'O')
1221         {
1222             wvalue += pos_val[i].value * 1.5;
1223         }
1224         else if (piece == 'x')
1225         {
1226             bvalue += pos_val[i].value;
1227         }
1228         else
1229         {
1230             bvalue += pos_val[i].value * 1.5;
1231         }
1232     }
1233
1234     /* normalize the result, should be between 1000 and -1000 */
1235     if (myc == 'o')
1236     {
1237         value = (int) ((wvalue - bvalue) * 1000 / (wvalue + bvalue));
1238     }
1239     else
1240     {
1241         value = (int) ((bvalue - wvalue) * 1000 / (wvalue + bvalue));
1242     }
1243
1244     return (value);
1245 }
1246
1247
1248 void del_move (movestruct * todel)
1249 {
1250     nextmove * movedata;
1251     gipfdata * gipfd;
1252
1253     if (todel->movelist != NULL)
1254     {
1255         while ((movedata = (nextmove *) llrembynr (todel->movelist, 1))
1256                != NULL)
1257         {
1258             if (movedata->remtype == REM_ROW)
1259             {
1260                 free (movedata->rowdata.start);
1261                 free (movedata->rowdata.end);
1262             }
1263             else
1264             {
1265                 while ((gipfd = (gipfdata *)
1266                         llrembynr (movedata->gipflist, 1)) != NULL)
1267                 {
1268                     free (gipfd);
1269                 }
1270                 free (movedata->gipflist);
1271             }
1272
1273             free (movedata);
1274         }
1275         free (todel->movelist);
1276     }
1277
1278     free (todel);
1279     return;
1280 }
1281
1282 #ifdef RANDOMCHOOSE
1283 /*
1284 ** just like a normal compare (<)
1285 ** returns:
1286 **   1 : nr1 < nr2
1287 **   0: nr1 > nr2
1288 **   0/1: when nr1 and nr2 are equal, chooses one at random
1289 **
1290 ** chance is the chance that nr1 will be chosen if nr1 == nr2
1291 ** this parameter will be incremented each time an equal occurs
1292 ** and will be set to 1 if nr1 < nr2
1293 ** (it should be initialised to 1 by the caller and then left alone)
1294 */
1295 int equ_l (int nr1, int nr2, int * chance, minimax_info * me, int depth)
1296 {
1297     int randnr;
1298
1299     if ((me->config.randomchoose == 0) || (depth > 1))
1300         return (nr1 < nr2);
1301
1302     if (nr1 < nr2)
1303     {
1304         *chance = 1;
1305         return (1);
1306     }
1307     if (nr1 > nr2)
1308     {
1309         return (0);
1310     }
1311
1312     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
1313     (*chance)++;
1314
1315     if (randnr < 1)
1316     {
1317         return (1);
1318     }
1319
1320     return (0);
1321 }
1322
1323
1324 /*
1325 ** just like a normal compare (>)
1326 ** returns:
1327 **   1 : nr1 > nr2
1328 **   0: nr1 < nr2
1329 **   0/1: when nr1 and nr2 are equal, chooses one at random
1330 **
1331 ** chance is the chance that nr1 will be chosen if nr1 == nr2
1332 ** this parameter will be incremented each time an equal occurs
1333 ** and will be set to 1 if nr1 > nr2
1334 ** (it should be initialised to 1 by the caller and then left alone)
1335 */
1336 int equ_h (int nr1, int nr2, int * chance, minimax_info * me, int depth)
1337 {
1338     int randnr;
1339
1340     if ((me->config.randomchoose == 0) || (depth > 1))
1341         return (nr1 > nr2);
1342
1343     if (nr1 > nr2)
1344     {
1345         *chance = 1;
1346         return (1);
1347     }
1348     if (nr1 < nr2)
1349     {
1350         return (0);
1351     }
1352
1353     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
1354     (*chance)++;
1355
1356     if (randnr < 1)
1357     {
1358         return (1);
1359     }
1360
1361     return (0);
1362 }
1363 #endif
1364