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