ai_mtdf.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 /*
  23 ** keep a tree of all searched nodes
  24 ** this is not useful for the normal minimax with alfabeta-pruning
  25 ** but can be used for negascout or mtd(f), algoritms wich do re-searching
  26 */
  27
  28 #include "ai_mtdf.h"
  29
  30 #ifdef WINGIPF
  31 extern void checkwindowevents (void);
  32 extern int interrupt_computer;
  33 #endif
  34
  35 /* structures for keeping my own info in */
  36 typedef struct {
  37     char colour;
  38     int game;
  39     int lastvalue;
  40     struct {
  41         int searchdepth;
  42         int remoppgipf;
  43         int maxgipf;
  44         int memorydepth;
  45         int randomchoose;
  46     } config;
  47     listheader * movelist;  /* list of items of type nextmove */
  48 } mtdf_info;
  49
  50 typedef struct {
  51     int remtype;   /* REM_GIPF or REM_ROW */
  52     listheader * gipflist; /* list of items of type gipfdata */
  53     struct {
  54         char * start;
  55         char * end;
  56     } rowdata;
  57 } nextmove;
  58
  59 #define REM_GIPF 1
  60 #define REM_ROW  2
  61
  62 typedef struct {
  63     char from[3];
  64     char to[3];
  65     char type;
  66     listheader * movelist; /* list of items of type nextmove */
  67     int value;
  68 } movestruct;
  69
  70 typedef struct {
  71     board * sboard;
  72     char to[3];
  73 } saveboard;
  74
  75 typedef struct {
  76     char pos[3];
  77     char flag;
  78 } gipfdata;
  79
  80 typedef struct {
  81     rem_gipf * gipf;
  82     int flag;
  83 } gipfitem;
  84
  85 /* things for the node-tree */
  86 typedef struct {
  87     board * father;
  88     int upper;
  89     int lower;
  90     listheader * children;  /* list of treeitems */
  91 } treenode;
  92
  93
  94 struct {
  95     position coor;
  96     int value;
  97 } mem_pos_val[] = {
  98     {{4, 5}, 5},
  99     {{3, 4}, 2},{{3, 5}, 2},{{4, 6}, 2},{{5, 5}, 2},{{5, 4}, 2},{{4, 4}, 2},
 100     {{2, 3}, 1},{{2, 4}, 1},{{2, 5}, 1},{{3, 6}, 1},{{4, 7}, 1},{{5, 6}, 1},
 101     {{6, 5}, 1},{{6, 4}, 1},{{6, 3}, 1},{{5, 3}, 1},{{4, 3}, 1},{{3, 3}, 1}
 102 };
 103
 104 #define MINNODE 1
 105 #define MAXNODE 2
 106
 107 #define min(x, y)     (x < y ? x : y)
 108 #define max(x, y)     (x > y ? x : y)
 109
 110 movestruct * mtdf_id (board * oboard, treenode * node, int f, mtdf_info * me,
 111                       int type);
 112 movestruct * mtdf (board * oboard, treenode * node, int f, mtdf_info * me,
 113                    int type);
 114
 115 movestruct * mem_ab_move (board * oboard, treenode * node, int alfa, int beta,
 116                           int minmax, int depth, mtdf_info * me);
 117 movestruct * mem_move (board * oboard, treenode * node, int alfa, int beta,
 118                        int minmax, int depth, mtdf_info * me, fromto * todo,
 119                        saveboard * lmove);
 120 movestruct * mem_ab_gipf (board * oboard, treenode * node, int alfa, int beta,
 121                           int minmax, int depth, mtdf_info * me);
 122 movestruct * mem_rem_gipflist (board * oboard, treenode * node, int alfa,
 123                                int beta, int minmax, int depth,
 124                                mtdf_info * me, listheader * myg,
 125                                listheader * otherg);
 126 movestruct * mem_ab_row (board * oboard, treenode * node, int alfa, int beta,
 127                          int minmax, int depth, mtdf_info * me);
 128 movestruct * mem_rem_row (board * oboard, treenode * node, int alfa, int beta,
 129                           int minmax, int depth, mtdf_info * me, int rem);
 130 int mem_evaluate (board * oboard, mtdf_info * me);
 131 void mem_del_move (movestruct * todel);
 132
 133 void mem_deltree (treenode * node);
 134 void mem_delnode (void * item);
 135 treenode * mem_makeroot (board * father, mtdf_info * me);
 136 treenode * mem_child (treenode * node, int nr, mtdf_info * me, int depth);
 137 void mem_resetul (void * item);
 138
 139 int mem_equ_l (int nr1, int nr2, int * chance, mtdf_info * me);
 140 int mem_equ_h (int nr1, int nr2, int * chance, mtdf_info * me);
 141
 142 void * mtdf_new (char colour, int game)
 143 {
 144     mtdf_info * me;
 145     listheader * configlist;
 146
 147     me = (mtdf_info *) malloc (sizeof (mtdf_info));
 148     me->colour = colour;
 149     me->game = game;
 150     me->lastvalue = 0;
 151     me->movelist = NULL;
 152
 153     /* check for config-values from the config-file */
 154     configlist = readconfigfile ("gf1.cfg");
 155
 156     me->config.searchdepth = findconfigvalue (configlist, "searchdepth",
 157                                               colour, 3);
 158     me->config.remoppgipf = findconfigvalue (configlist, "remoppgipf",
 159                                              colour, 1);
 160     me->config.maxgipf = findconfigvalue (configlist, "maxgipf",
 161                                           colour, 3);
 162     me->config.memorydepth = findconfigvalue (configlist, "memorydepth",
 163                                               colour, 3);
 164     me->config.randomchoose = findconfigvalue (configlist, "randomchoose",
 165                                               colour, 1);
 166
 167     clearconfiglist (configlist);
 168
 169     return ((void *) me);
 170 }
 171
 172
 173 void mtdf_move (board * oboard, void * self,
 174                 char * type, char * from, char * to)
 175 {
 176     mtdf_info * me = self;
 177     movestruct * move;
 178     treenode * root;
 179
 180     b_nolog (oboard);
 181
 182     root = mem_makeroot (oboard, me);
 183 /*
 184     move = mtdf (oboard, root, me->lastvalue, me, 1);
 185 */
 186     move = mtdf_id (oboard, root, me->lastvalue, me, 1);
 187
 188     mem_deltree (root);
 189
 190     from[0] = move->from[0];
 191     from[1] = move->from[1];
 192     to[0] = move->to[0];
 193     to[1] = move->to[1];
 194     *type = move->type;
 195
 196     me->movelist = move->movelist;
 197
 198     move->movelist = NULL;
 199     mem_del_move (move);
 200
 201     return;
 202 }
 203
 204
 205 char mtdf_gipf (board * oboard, void * self, char * pos)
 206 {
 207     mtdf_info * me = self;
 208     nextmove * movedata;
 209     gipfdata * gipfd;
 210     int counter;
 211     char val;
 212     treenode * root;
 213
 214     b_nolog (oboard);
 215
 216     /* check if movelist contains info about removing gipf-pieces */
 217     if (me->movelist == NULL)
 218     {
 219         /*
 220         ** no info in movelist, my opponent made 4 in a row
 221         ** with my pieces (only possible explanation)
 222         */
 223         movestruct * nmove;
 224
 225         /* remark: I have to start this as a min-node,
 226         ** because this is really my opponents move */
 227         root = mem_makeroot (oboard, me);
 228 /*
 229         nmove = mtdf (oboard, root, me->lastvalue, me, 2);
 230 */
 231         nmove = mtdf_id (oboard, root, me->lastvalue, me, 2);
 232         mem_deltree (root);
 233
 234         me->movelist = nmove->movelist;
 235         nmove->movelist = NULL;
 236         mem_del_move (nmove);
 237     }
 238
 239     /* now check the movelist for the move we have to make */
 240     if (((movedata = (nextmove *) llitembynr (me->movelist, 1)) == NULL) ||
 241         (movedata->remtype != REM_GIPF))
 242     {
 243         /* very wrong */
 244         exit (0);
 245     }
 246
 247     /* look for the gipf to remove */
 248     counter = 1;
 249     while ((gipfd = (gipfdata *) llitembynr (movedata->gipflist, counter))
 250            != NULL)
 251     {
 252         if ((gipfd->pos[0] == pos[0]) && (gipfd->pos[1] == pos[1]))
 253         {
 254             break;
 255         }
 256         counter++;
 257     }
 258     if (gipfd == NULL)
 259     {
 260         /* very wrong */
 261         exit (0);
 262     }
 263     /* remove gipf from list */
 264     gipfd = (gipfdata *) llrembynr (movedata->gipflist, counter);
 265
 266     /* remove nextmove from movelist if gipflist is empty */
 267     if (llitembynr (movedata->gipflist, 1) == NULL)
 268     {
 269         movedata = (nextmove *) llrembynr (me->movelist, 1);
 270         free (movedata->gipflist);
 271         free (movedata);
 272
 273         /* remove movelist if empty */
 274         if (llitembynr (me->movelist, 1) == NULL)
 275         {
 276             free (me->movelist);
 277             me->movelist = NULL;
 278         }
 279     }
 280
 281     val = gipfd->flag;
 282     free (gipfd);
 283
 284     return (val);
 285 }
 286
 287
 288 char mtdf_row (board * oboard, void * self, char * start, char * end)
 289 {
 290     mtdf_info * me = self;
 291     nextmove * movedata;
 292     int correct;
 293     treenode * root;
 294
 295     b_nolog (oboard);
 296
 297     /* check if movelist contains info about removing rows */
 298     if (me->movelist == NULL)
 299     {
 300         /*
 301         ** no info in movelist, my opponent made several "4 in a row"s
 302         ** with my pieces (only possible explanation)
 303         */
 304         movestruct * nmove;
 305
 306         /* remark: I have to start this as a min-node,
 307         ** because this is really my opponents move */
 308         root = mem_makeroot (oboard, me);
 309 /*
 310         nmove = mtdf (oboard, root, me->lastvalue, me, 3);
 311 */
 312         nmove = mtdf_id (oboard, root, me->lastvalue, me, 3);
 313         mem_deltree (root);
 314
 315         me->movelist = nmove->movelist;
 316         nmove->movelist = NULL;
 317         mem_del_move (nmove);
 318     }
 319
 320     /* now check the movelist for the move we have to make */
 321     if (((movedata = (nextmove *) llitembynr (me->movelist, 1)) == NULL) ||
 322         (movedata->remtype != REM_ROW))
 323     {
 324         /* very wrong */
 325         exit (0);
 326     }
 327
 328     correct = 0;
 329     /* check if this is the correct row to be removed */
 330     if ((start[0] == movedata->rowdata.start[0]) &&
 331         (start[1] == movedata->rowdata.start[1]))
 332     {
 333         if ((end[0] == movedata->rowdata.end[0]) &&
 334             (end[1] == movedata->rowdata.end[1]))
 335         {
 336             correct = 1;
 337         }
 338     }
 339     else if ((start[0] == movedata->rowdata.end[0]) &&
 340              (start[1] == movedata->rowdata.end[1]))
 341     {
 342         if ((end[0] == movedata->rowdata.start[0]) &&
 343             (end[1] == movedata->rowdata.start[1]))
 344         {
 345             correct = 1;
 346         }
 347     }
 348
 349     if (correct)
 350     {
 351         /* remove nextmove from movelist */
 352         movedata = (nextmove *) llrembynr (me->movelist, 1);
 353         free (movedata->rowdata.start);
 354         free (movedata->rowdata.end);
 355         free (movedata);
 356
 357         /* remove movelist if empty */
 358         if (llitembynr (me->movelist, 1) == NULL)
 359         {
 360             free (me->movelist);
 361             me->movelist = NULL;
 362         }
 363
 364         return ('y');
 365     }
 366
 367     /* don't remove the row */
 368     return ('n');
 369 }
 370
 371
 372 void mtdf_end (void * self)
 373 {
 374     mtdf_info * me = self;
 375
 376     /* do I have to clean up the movelist first */
 377
 378     free (me);
 379     return;
 380 }
 381
 382
 383 /*
 384 ** iterative deepening around mtdf
 385 **
 386 ** REMARK: doesn't work, don't know why yet
 387 */
 388 movestruct * mtdf_id (board * oboard, treenode * node, int f, mtdf_info * me,
 389                       int type)
 390 {
 391     int savemaxdepth,
 392         i;
 393     movestruct * bestmove = NULL;
 394
 395     savemaxdepth = me->config.searchdepth;
 396
 397     for (i = 1; i <= savemaxdepth; i++)
 398     {
 399         if (bestmove != NULL)
 400         {
 401             mem_del_move (bestmove);
 402
 403             /* reset upper and lower limits in the memory-tree */
 404             mem_resetul (node);
 405         }
 406
 407         me->config.searchdepth = i;
 408         bestmove = mtdf (oboard, node, f, me, type);
 409     }
 410
 411     me->config.searchdepth = savemaxdepth;
 412
 413     return (bestmove);
 414 }
 415
 416 movestruct * mtdf (board * oboard, treenode * node, int f, mtdf_info * me,
 417                    int type)
 418 {
 419     int value,
 420         upper,
 421         lower,
 422         beta;
 423     movestruct * bestmove = NULL;
 424
 425     value = f;
 426     upper = 1001;
 427     lower = -1001;
 428
 429     while (lower < upper)
 430     {
 431         if (value == lower)
 432         {
 433             beta = value + 1;
 434         }
 435         else
 436         {
 437             beta = value;
 438         }
 439
 440         if (bestmove != NULL)
 441         {
 442             mem_del_move (bestmove);
 443         }
 444
 445         switch (type)
 446         {
 447         case 1:
 448             bestmove = mem_ab_move (oboard, node, beta-1, beta,
 449                                     MAXNODE, 1, me);
 450             break;
 451
 452         case 2:
 453             bestmove = mem_ab_gipf (oboard, node, beta-1, beta,
 454                                     MINNODE, 1, me);
 455             break;
 456
 457         case 3:
 458             bestmove = mem_ab_row (oboard, node, beta-1, beta,
 459                                     MINNODE, 1, me);
 460             break;
 461         }
 462         value = bestmove->value;
 463
 464         if (value < beta)
 465         {
 466             upper = value;
 467         }
 468         else
 469         {
 470             lower = value;
 471         }
 472     }
 473
 474     me->lastvalue = value;
 475     return (bestmove);
 476 }
 477
 478
 479 movestruct * mem_ab_move (board * oboard, treenode * node, int alfa, int beta,
 480                           int minmax, int depth, mtdf_info * me)
 481 {
 482     movestruct * nmove,
 483         * bestmove = NULL;
 484     fromto * allmoves;
 485     int maxmoves,
 486         value,
 487         chance = 1,
 488         i;
 489     saveboard lastmove;
 490     treenode * childnode;
 491
 492     /* maximum search depth or end of game */
 493     if ((b_game_finished (oboard)) ||
 494         (depth > me->config.searchdepth))
 495     {
 496         nmove = (movestruct *) malloc (sizeof (movestruct));
 497         nmove->from[0] = '\0';
 498         nmove->to[0] = '\0';
 499         nmove->type = 0;
 500         nmove->movelist = NULL;
 501         nmove->value = mem_evaluate (oboard, me);
 502         return (nmove);
 503     }
 504
 505 #ifdef WINGIPF
 506     if ((depth == 1) || (depth < me->config.searchdepth))
 507     {
 508         checkwindowevents ();
 509     }
 510 #endif
 511
 512     /* list of moves to try depends on the question if we can
 513     ** place a gipf or not.
 514     ** cutoff after a predetermined number of gipf-pieces */
 515     if ((b_colour_type (oboard, b_next_piece (oboard)) == 'g') &&
 516         (b_colour_gipf (oboard, b_next_piece (oboard)) <
 517          me->config.maxgipf))
 518     {
 519         allmoves = allmovesg;
 520         maxmoves = 84;
 521     }
 522     else
 523     {
 524         allmoves = allmovesn;
 525         maxmoves = 42;
 526     }
 527
 528     lastmove.sboard = NULL;
 529
 530     if (minmax == MAXNODE)
 531     {
 532         value = -1001;
 533
 534         for (i = 0; i < maxmoves; i++)
 535         {
 536             childnode = mem_child (node, i+1, me, depth);
 537             nmove = mem_move (oboard, childnode, alfa, beta, minmax,
 538                               depth, me, &(allmoves[i]), &lastmove);
 539             if (nmove == NULL)
 540             {
 541                 continue;
 542             }
 543             if (mem_equ_h (nmove->value, value, &chance, me))
 544             {
 545                 value = nmove->value;
 546                 if (bestmove != NULL)
 547                 {
 548                     mem_del_move (bestmove);
 549                 }
 550                 bestmove = nmove;
 551             }
 552             else
 553             {
 554                 mem_del_move (nmove);
 555             }
 556             alfa = max (alfa, value);
 557
 558             if (value > beta)
 559             {
 560                 /*
 561                 ** problems if value is the same as beta, this means that
 562                 ** when randomly selecting a move from the moves with the
 563                 ** same value, this one could be chosen.
 564                 ** solution: change value to (-1001 or 1001)
 565                 **           or the current value (+1 or -1)
 566                 **
 567                 ** is this correct? or does it depend on the fact if
 568                 ** this was called from a min- or a max-node?
 569                 */
 570                 break;
 571             }
 572         }
 573     }
 574     else
 575     {
 576         value = 1001;
 577
 578         for (i = 0; i < maxmoves; i++)
 579         {
 580             childnode = mem_child (node, i+1, me, depth);
 581             nmove = mem_move (oboard, childnode, alfa, beta, minmax,
 582                               depth, me, &(allmoves[i]), &lastmove);
 583             if (nmove == NULL)
 584             {
 585                 continue;
 586             }
 587             if (mem_equ_l (nmove->value, value, &chance, me))
 588             {
 589                 value = nmove->value;
 590                 if (bestmove != NULL)
 591                 {
 592                     mem_del_move (bestmove);
 593                 }
 594                 bestmove = nmove;
 595             }
 596             else
 597             {
 598                 mem_del_move (nmove);
 599             }
 600             beta = min (beta, value);
 601
 602             if (value < alfa)
 603             {
 604                 break;
 605             }
 606         }
 607     }
 608
 609     if ((childnode == NULL) && (lastmove.sboard != NULL))
 610     {
 611         b_del (lastmove.sboard);
 612     }
 613
 614     return (bestmove);
 615 }
 616
 617
 618 movestruct * mem_move (board * oboard, treenode * node, int alfa, int beta,
 619                        int minmax, int depth, mtdf_info * me, fromto * todo,
 620                        saveboard * lmove)
 621 {
 622     board * newboard;
 623     char piece;
 624     int newminmax;
 625     movestruct * mymove,
 626         * nmove;
 627
 628     if ((node != NULL) && (node->children != NULL))
 629     {   /* node already visited, reuse from memory */
 630         if (node->father == NULL)
 631         {
 632             return (NULL);
 633         }
 634         newboard = node->father;
 635
 636 #if 0
 637 /*
 638 ** removing this solves the problem of bad play
 639 ** but it makes the computerplayer twice as slow as ai_minimax
 640 **
 641 ** it also solves the problem of iterative deepening not working
 642 */
 643         if (node->lower >= beta)
 644         {
 645             nmove = (movestruct *) malloc (sizeof (movestruct));
 646             nmove->from[0] = todo->from[0];
 647             nmove->from[1] = todo->from[1];
 648             nmove->to[0] = todo->to[0];
 649             nmove->to[1] = todo->to[1];
 650             nmove->type = 0;
 651             nmove->movelist = NULL;
 652             nmove->value = node->lower;
 653             return (nmove);
 654         }
 655         if (node->upper <= alfa)
 656         {
 657             nmove = (movestruct *) malloc (sizeof (movestruct));
 658             nmove->from[0] = todo->from[0];
 659             nmove->from[1] = todo->from[1];
 660             nmove->to[0] = todo->to[0];
 661             nmove->to[1] = todo->to[1];
 662             nmove->type = todo->type;
 663             nmove->movelist = NULL;
 664             nmove->value = node->upper;
 665             return (nmove);
 666         }
 667         alfa = max (alfa, node->lower);
 668         beta = min (beta, node->upper);
 669 #endif
 670     }
 671     else
 672     {
 673         if (node != NULL)
 674         {
 675             /* create children list */
 676             node->children = (listheader *) malloc (sizeof (listheader));
 677             newlist (node->children);
 678         }
 679
 680         if (todo->type == 'g')
 681         {
 682             piece = b_otherpiece (b_next_piece (oboard));
 683         }
 684         else
 685         {
 686             piece = b_next_piece (oboard);
 687         }
 688
 689         newboard = b_move (oboard, todo->from, todo->to, piece);
 690         if (node != NULL)
 691         {
 692             node->father = newboard;
 693         }
 694
 695         if (newboard == NULL)
 696         {
 697             return (NULL);
 698         }
 699
 700         /* check if the result is the same as the last move */
 701         if ((lmove->sboard != NULL) &&
 702             ((lmove->to[0] == todo->to[0]) && (lmove->to[1] == todo->to[1])) &&
 703             (b_compare (newboard, lmove->sboard) == 0))
 704         {
 705             b_del (newboard);
 706             if (node != NULL)
 707             {
 708                 node->father = NULL;
 709             }
 710             return (NULL);
 711         }
 712         if ((node == NULL) && (lmove->sboard != NULL))
 713         {
 714             b_del (lmove->sboard);
 715         }
 716         lmove->sboard = newboard; /* don't delete the board at the end */
 717         lmove->to[0] = todo->to[0];
 718         lmove->to[1] = todo->to[1];
 719     }
 720
 721     /* create new movestruct */
 722     mymove = (movestruct *) malloc (sizeof (movestruct));
 723     mymove->from[0] = todo->from[0];
 724     mymove->from[1] = todo->from[1];
 725     mymove->to[0] = todo->to[0];
 726     mymove->to[1] = todo->to[1];
 727     mymove->type = todo->type;
 728     mymove->movelist = NULL;
 729
 730     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 731     if ((b_status (newboard) == S_NORMAL) ||
 732         (b_status (newboard) == S_FINISHED))
 733     {
 734         nmove = mem_ab_move (newboard, node, alfa, beta, newminmax,
 735                              depth+1, me);
 736         mymove->value = nmove->value;
 737         mem_del_move (nmove);
 738     }
 739     else if (b_status (newboard) == S_REMOVEROW)
 740     {
 741         nmove = mem_ab_row (newboard, node, alfa, beta, minmax, depth, me);
 742         mymove->movelist = nmove->movelist;
 743         mymove->value = nmove->value;
 744         nmove->movelist = NULL;
 745         mem_del_move (nmove);
 746     }
 747     else if (b_status (newboard) == S_REMOVEGIPF)
 748     {
 749         nmove = mem_ab_gipf (newboard, node, alfa, beta, minmax, depth, me);
 750         mymove->movelist = nmove->movelist;
 751         mymove->value = nmove->value;
 752         nmove->movelist = NULL;
 753         mem_del_move (nmove);
 754     }
 755     else
 756     {   /* impossible */
 757         exit (0);
 758     }
 759
 760     if (node != NULL)
 761     {
 762         if (mymove->value <= alfa)
 763         {
 764             node->upper = mymove->value;
 765         }
 766         else if ((mymove->value > alfa) && (mymove->value < beta))
 767         {   /* this shouldn't happen with zero window searches */
 768             node->upper = node->lower = mymove->value;
 769         }
 770         else if (mymove->value >= beta)
 771         {
 772             node->lower = mymove->value;
 773         }
 774     }
 775
 776     return (mymove);
 777 }
 778
 779
 780 movestruct * mem_ab_gipf (board * oboard, treenode * node, int alfa, int beta,
 781                           int minmax, int depth, mtdf_info * me)
 782 {
 783     movestruct * nmove,
 784         * bestmove = NULL;
 785     int value,
 786         realminmax,
 787         counter,
 788         mynr,
 789         i,
 790         maxnr;
 791     unsigned char bits1,
 792         bits2;
 793     rem_gipf * gipfi;
 794     listheader * myg,
 795         * otherg;
 796     char * gipfpos;
 797     gipfitem * gipfflag;
 798     treenode * childnode;
 799
 800     gipfi = (rem_gipf *) llitembynr (b_gipf_extra (oboard), 1);
 801
 802     /*
 803     ** I may have to change if I am a min or a max-node here
 804     ** it's possible that my opponent won a row, so he has to
 805     ** decide if gipf-pieces must be removed
 806     */
 807     if (b_gipf_owner(gipfi) == b_next_piece (oboard))
 808     {
 809         realminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
 810     }
 811     else
 812     {
 813         realminmax = minmax;
 814     }
 815
 816     /* always remove gipf-pieces from my opponent if the flag is set */
 817     myg = (listheader *) malloc (sizeof (listheader));
 818     newlist (myg);
 819     otherg = (listheader *) malloc (sizeof (listheader));
 820     newlist (otherg);
 821     counter = 1;
 822     mynr = 0;
 823     while ((gipfi = (rem_gipf *) llitembynr (b_gipf_extra (oboard), counter))
 824            != NULL)
 825     {
 826         counter++;
 827         gipfflag = (gipfitem *) malloc (sizeof (gipfitem));
 828         gipfflag->gipf = gipfi;
 829         gipfflag->flag = 1;
 830
 831         gipfpos = b_gipf_position (gipfi);
 832         if ((me->config.remoppgipf == 1) &&
 833             (b_otherpiece (b_gipf_owner (gipfi)) !=
 834              b_piece (oboard, gipfpos)))
 835         {
 836             pushll (otherg, (void *) gipfflag);
 837         }
 838         else
 839         {
 840             mynr++;
 841             pushll (myg, (void *) gipfflag);
 842         }
 843         free (gipfpos);
 844     }
 845
 846     maxnr = 1 << mynr; /* 2 ^ mynr */
 847
 848     if (realminmax == MAXNODE)
 849     {
 850         value = -1001;
 851
 852         for (bits1 = 0; bits1 < maxnr ; bits1++)
 853         {
 854             bits2 = bits1;
 855             for (i = 0; i < mynr; i++)
 856             {
 857                 gipfflag = (gipfitem *) llitembynr (myg, i+1);
 858                 gipfflag->flag = bits2 & 1;
 859                 bits2 = bits2 >> 1;
 860             }
 861             childnode = mem_child (node, bits1 + 1, me, depth);
 862             nmove = mem_rem_gipflist (oboard, childnode, alfa, beta,
 863                                       minmax, depth, me, myg, otherg);
 864
 865             if (nmove->value > value)
 866             {
 867                 value = nmove->value;
 868                 if (bestmove != NULL)
 869                 {
 870                     mem_del_move (bestmove);
 871                 }
 872                 bestmove = nmove;
 873             }
 874             else
 875             {
 876                 mem_del_move (nmove);
 877             }
 878             alfa = max (alfa, value);
 879
 880             if (value > beta)
 881             {
 882                 break;
 883             }
 884         }
 885     }
 886     else
 887     {
 888         value = 1001;
 889
 890         for (bits1 = 0; bits1 < maxnr ; bits1++)
 891         {
 892             bits2 = bits1;
 893             for (i = 0; i < mynr; i++)
 894             {
 895                 gipfflag = (gipfitem *) llitembynr (myg, i+1);
 896                 gipfflag->flag = bits2 & 1;
 897                 bits2 = bits2 >> 1;
 898             }
 899             childnode = mem_child (node, bits1 + 1, me, depth);
 900             nmove = mem_rem_gipflist (oboard, childnode, alfa, beta,
 901                                       minmax, depth, me, myg, otherg);
 902
 903             if (nmove->value < value)
 904             {
 905                 value = nmove->value;
 906                 if (bestmove != NULL)
 907                 {
 908                     mem_del_move (bestmove);
 909                 }
 910                 bestmove = nmove;
 911             }
 912             else
 913             {
 914                 mem_del_move (nmove);
 915             }
 916             beta = min (beta, value);
 917
 918             if (value < alfa)
 919             {
 920                 break;
 921             }
 922         }
 923     }
 924
 925     /* cleanup temporary lists */
 926     while ((gipfflag = (gipfitem *) llrembynr (myg, 1)) != NULL)
 927     {
 928         free (gipfflag);
 929     }
 930     free (myg);
 931     while ((gipfflag = (gipfitem *) llrembynr (otherg, 1)) != NULL)
 932     {
 933         free (gipfflag);
 934     }
 935     free (otherg);
 936
 937     return (bestmove);
 938 }
 939
 940
 941 movestruct * mem_rem_gipflist (board * oboard, treenode * node, int alfa,
 942                                int beta, int minmax, int depth,
 943                                mtdf_info * me, listheader * myg,
 944                                listheader * otherg)
 945 {
 946     board * nboard,
 947         * newboard;
 948     movestruct * mymove,
 949         * nmove;
 950     int counter;
 951     gipfitem * gipfflag;
 952     listheader * remlist;
 953     gipfdata * gipfd;
 954     char * strpos,
 955         owner;
 956     nextmove * movedata;
 957     int newminmax;
 958
 959     if ((node != NULL) && (node->children != NULL))
 960     {   /* node already visited, reuse from memory */
 961         if (node->father == NULL)
 962         {
 963             return (NULL);
 964         }
 965         newboard = node->father;
 966
 967         /* I have to produce remlist here again */
 968         remlist = (listheader *) malloc (sizeof (listheader));;
 969         newlist (remlist);
 970         /* list of gipf-pieces that may or may not have to be removed */
 971         counter = 1;
 972         while ((gipfflag = (gipfitem *) llitembynr (myg, counter)) != NULL)
 973         {
 974             counter++;
 975             gipfd = (gipfdata *) malloc (sizeof (gipfdata));
 976             strpos = b_gipf_position (gipfflag->gipf);
 977             owner = b_gipf_owner (gipfflag->gipf);
 978             gipfd->pos[0] = strpos[0];
 979             gipfd->pos[1] = strpos[1];
 980             gipfd->pos[2] = '\0';
 981             free (strpos);
 982
 983             if (gipfflag->flag == 1)
 984             {
 985                 gipfd->flag = 'y';
 986             }
 987             else
 988             {
 989                 gipfd->flag = 'n';
 990             }
 991             pushll (remlist, (void *) gipfd);
 992         }
 993         /* list of gipf-pieces that always have to be removed */
 994         counter = 1;
 995         while ((gipfflag = (gipfitem *) llitembynr (otherg, counter)) != NULL)
 996         {
 997             counter++;
 998             gipfd = (gipfdata *) malloc (sizeof (gipfdata));
 999             strpos = b_gipf_position (gipfflag->gipf);
1000             owner = b_gipf_owner (gipfflag->gipf);
1001             gipfd->pos[0] = strpos[0];
1002             gipfd->pos[1] = strpos[1];
1003             gipfd->pos[2] = '\0';
1004             free (strpos);
1005
1006             gipfd->flag = 'y';
1007             pushll (remlist, (void *) gipfd);
1008         }
1009
1010     }
1011     else
1012     {
1013         if (node != NULL)
1014         {
1015             /* create children list */
1016             node->children = (listheader *) malloc (sizeof (listheader));
1017             newlist (node->children);
1018         }
1019
1020         newboard = oboard;
1021         remlist = (listheader *) malloc (sizeof (listheader));;
1022         newlist (remlist);
1023         /* list of gipf-pieces that may or may not have to be removed */
1024         counter = 1;
1025         while ((gipfflag = (gipfitem *) llitembynr (myg, counter)) != NULL)
1026         {
1027             counter++;
1028             gipfd = (gipfdata *) malloc (sizeof (gipfdata));
1029             strpos = b_gipf_position (gipfflag->gipf);
1030             owner = b_gipf_owner (gipfflag->gipf);
1031             gipfd->pos[0] = strpos[0];
1032             gipfd->pos[1] = strpos[1];
1033             gipfd->pos[2] = '\0';
1034             free (strpos);
1035
1036             if (gipfflag->flag == 1)
1037             {
1038                 gipfd->flag = 'y';
1039                 nboard = b_remove_gipf (newboard, gipfflag->gipf);
1040                 if (newboard != oboard)
1041                 {
1042                     b_del (newboard);
1043                 }
1044                 newboard = nboard;
1045             }
1046             else
1047             {
1048                 gipfd->flag = 'n';
1049             }
1050             pushll (remlist, (void *) gipfd);
1051         }
1052
1053         /* list of gipf-pieces that always have to be removed */
1054         counter = 1;
1055         while ((gipfflag = (gipfitem *) llitembynr (otherg, counter)) != NULL)
1056         {
1057             counter++;
1058             gipfd = (gipfdata *) malloc (sizeof (gipfdata));
1059             strpos = b_gipf_position (gipfflag->gipf);
1060             owner = b_gipf_owner (gipfflag->gipf);
1061             gipfd->pos[0] = strpos[0];
1062             gipfd->pos[1] = strpos[1];
1063             gipfd->pos[2] = '\0';
1064             free (strpos);
1065
1066             gipfd->flag = 'y';
1067             nboard = b_remove_gipf (newboard, gipfflag->gipf);
1068             if (newboard != oboard)
1069             {
1070                 b_del (newboard);
1071             }
1072             newboard = nboard;
1073             pushll (remlist, (void *) gipfd);
1074         }
1075
1076         /* check again for 4 in a row */
1077         nboard = b_checkfour (newboard);
1078         if (newboard != oboard)
1079         {
1080             b_del (newboard);
1081         }
1082
1083         newboard = nboard;
1084         if (node != NULL)
1085         {
1086             node->father = newboard;
1087         }
1088     }
1089
1090     mymove = (movestruct *) malloc (sizeof (movestruct));
1091     mymove->from[0] = '\0';
1092     mymove->to[0] = '\0';
1093     mymove->type = 0;
1094     mymove->movelist = (listheader *) malloc (sizeof (listheader));
1095     newlist (mymove->movelist);
1096
1097     /*
1098     ** only add actions to the movelist if they have to be executed
1099     ** by the max-player
1100     ** this means moves for the min-player will not be executable,
1101     ** but that really isn't necessary
1102     */
1103     if (me->colour == owner)
1104     {
1105         movedata = (nextmove *) malloc (sizeof (nextmove));
1106         movedata->remtype = REM_GIPF;
1107         movedata->gipflist = remlist;
1108         pushll (mymove->movelist, (void *) movedata);
1109     }
1110     else
1111     {   /* remove remlist, we don't need it here */
1112         while ((gipfd = (gipfdata *) llrembynr (remlist, 1)) != NULL)
1113         {
1114             free (gipfd);
1115         }
1116         free (remlist);
1117     }
1118
1119     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
1120
1121     if ((b_status (newboard) == S_NORMAL) ||
1122         (b_status (newboard) == S_FINISHED))
1123     {
1124         nmove = mem_ab_move (newboard, node, alfa, beta, newminmax,
1125                              depth+1, me);
1126         mymove->value = nmove->value;
1127         mem_del_move (nmove);
1128     }
1129     else if (b_status (newboard) == S_REMOVEROW)
1130     {
1131         nmove = mem_ab_row (newboard, node, alfa, beta, minmax, depth, me);
1132
1133         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1134                != NULL)
1135         {
1136             pushll (mymove->movelist, (void *) movedata);
1137         }
1138
1139         mymove->value = nmove->value;
1140         mem_del_move (nmove);
1141     }
1142     else if (b_status (newboard) == S_REMOVEGIPF)
1143     {
1144         nmove = mem_ab_gipf (newboard, node, alfa, beta, minmax, depth, me);
1145
1146         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1147                != NULL)
1148         {
1149             pushll (mymove->movelist, (void *) movedata);
1150         }
1151
1152         mymove->value = nmove->value;
1153         mem_del_move (nmove);
1154     }
1155     else
1156     {   /* impossible */
1157         exit (0);
1158     }
1159
1160     /* check if the movelist of mymove contains something */
1161     if (llitembynr (mymove->movelist, 1) == NULL)
1162     {
1163         free (mymove->movelist);
1164         mymove->movelist = NULL;
1165     }
1166
1167     if (node == NULL)
1168     {
1169         b_del (newboard);
1170     }
1171     else
1172     {
1173         if (mymove->value <= alfa)
1174         {
1175             node->upper = mymove->value;
1176         }
1177         else if ((mymove->value > alfa) && (mymove->value < beta))
1178         {   /* this shouldn't happen with zero window searches */
1179             node->upper = node->lower = mymove->value;
1180         }
1181         else if (mymove->value >= beta)
1182         {
1183             node->lower = mymove->value;
1184         }
1185     }
1186
1187
1188     return (mymove);
1189 }
1190
1191
1192 movestruct * mem_ab_row (board * oboard, treenode * node, int alfa, int beta,
1193                          int minmax, int depth, mtdf_info * me)
1194 {
1195     int counter,
1196         value,
1197         realminmax;
1198     movestruct * nmove,
1199         * bestmove = NULL;
1200     rem_row * rowi;
1201     listheader * rowlist;
1202     treenode * childnode;
1203
1204     rowlist = b_row_extra (oboard);
1205     rowi = (rem_row *) llitembynr (rowlist, 1);
1206
1207     /*
1208     ** I may have to change if I am a min or a max-node here
1209     ** it's possible that my opponent won several rows, so he has to
1210     ** decide what row to remove
1211     */
1212     if (row_owner(rowi) == b_next_piece (oboard))
1213     {
1214         realminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
1215     }
1216     else
1217     {
1218         realminmax = minmax;
1219     }
1220
1221     if (realminmax == MAXNODE)
1222     {
1223         value = -1001;
1224
1225         counter = 1;
1226         while ((rowi = (rem_row *) llitembynr (rowlist, counter))
1227                != NULL)
1228         {
1229             childnode = mem_child (node, counter, me, depth);
1230             nmove = mem_rem_row (oboard, childnode, alfa, beta, minmax,
1231                                  depth, me, counter);
1232             counter++;
1233
1234             if (nmove->value > value)
1235             {
1236                 value = nmove->value;
1237                 if (bestmove != NULL)
1238                 {
1239                     mem_del_move (bestmove);
1240                 }
1241                 bestmove = nmove;
1242             }
1243             else
1244             {
1245                 mem_del_move (nmove);
1246             }
1247             alfa = max (alfa, value);
1248
1249             if (value > beta)
1250             {
1251                 break;
1252             }
1253         }
1254     }
1255     else
1256     {
1257         value = 1001;
1258
1259         counter = 1;
1260         while ((rowi = (rem_row *) llitembynr (rowlist, counter))
1261                != NULL)
1262         {
1263             childnode = mem_child (node, counter, me, depth);
1264             nmove = mem_rem_row (oboard, childnode, alfa, beta, minmax,
1265                                 depth, me, counter);
1266             counter++;
1267
1268             if (nmove->value < value)
1269             {
1270                 value = nmove->value;
1271                 if (bestmove != NULL)
1272                 {
1273                     mem_del_move (bestmove);
1274                 }
1275                 bestmove = nmove;
1276             }
1277             else
1278             {
1279                 mem_del_move (nmove);
1280             }
1281             beta = min (beta, value);
1282
1283             if (value < alfa)
1284             {
1285                 break;
1286             }
1287         }
1288     }
1289
1290     return (bestmove);
1291 }
1292
1293
1294 movestruct * mem_rem_row (board * oboard, treenode * node, int alfa, int beta,
1295                           int minmax, int depth, mtdf_info * me, int rem)
1296 {
1297     board * newboard;
1298     movestruct * nmove,
1299         * mymove;
1300     rem_row * remi;
1301     nextmove * movedata;
1302     int newminmax;
1303
1304     if ((node != NULL) && (node->children != NULL))
1305     {   /* node already visited, reuse from memory */
1306         if (node->father == NULL)
1307         {
1308             return (NULL);
1309         }
1310         newboard = node->father;
1311     }
1312     else
1313     {
1314         if (node != NULL)
1315         {
1316             /* create children list */
1317             node->children = (listheader *) malloc (sizeof (listheader));
1318             newlist (node->children);
1319         }
1320
1321         newboard = b_remove_row (oboard, rem);
1322         if (node != NULL)
1323         {
1324             node->father = newboard;
1325         }
1326     }
1327
1328     mymove = (movestruct *) malloc (sizeof (movestruct));
1329     mymove->from[0] = '\0';
1330     mymove->to[0] = '\0';
1331     mymove->type = 0;
1332     mymove->movelist = (listheader *) malloc (sizeof (listheader));
1333     newlist (mymove->movelist);
1334
1335     /*
1336     ** only add actions to the movelist if they have to be executed
1337     ** by the max-player
1338     ** this means moves for the min-player will not be executable,
1339     ** but that really isn't necessary
1340     */
1341     remi = (rem_row *) llitembynr (b_row_extra (oboard), rem);
1342     if (me->colour == row_owner (remi))
1343     {
1344         movedata = (nextmove *) malloc (sizeof (nextmove));
1345         movedata->remtype = REM_ROW;
1346         movedata->gipflist = NULL;
1347         movedata->rowdata.start = postostr (remi->startpos);
1348         movedata->rowdata.end = postostr (remi->endpos);
1349         pushll (mymove->movelist, (void *) movedata);
1350     }
1351
1352     newminmax = (minmax == MINNODE ? MAXNODE : MINNODE);
1353
1354     if ((b_status (newboard) == S_NORMAL) ||
1355         (b_status (newboard) == S_FINISHED))
1356     {
1357         nmove = mem_ab_move (newboard, node, alfa, beta, newminmax,
1358                              depth+1, me);
1359         mymove->value = nmove->value;
1360         mem_del_move (nmove);
1361     }
1362     else if (b_status (newboard) == S_REMOVEROW)
1363     {
1364         nmove = mem_ab_row (newboard, node, alfa, beta, minmax, depth, me);
1365
1366         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1367                != NULL)
1368         {
1369             pushll (mymove->movelist, (void *) movedata);
1370         }
1371
1372         mymove->value = nmove->value;
1373         mem_del_move (nmove);
1374     }
1375     else if (b_status (newboard) == S_REMOVEGIPF)
1376     {
1377         nmove = mem_ab_gipf (newboard, node, alfa, beta, minmax, depth, me);
1378
1379         while ((movedata = (nextmove *) llrembynr (nmove->movelist, 1))
1380                != NULL)
1381         {
1382             pushll (mymove->movelist, (void *) movedata);
1383         }
1384
1385         mymove->value = nmove->value;
1386         mem_del_move (nmove);
1387     }
1388     else
1389     {   /* impossible */
1390         exit (0);
1391     }
1392
1393     /* check if the movelist of mymove contains something */
1394     if (llitembynr (mymove->movelist, 1) == NULL)
1395     {
1396         free (mymove->movelist);
1397         mymove->movelist = NULL;
1398     }
1399
1400     if (node == NULL)
1401     {
1402         b_del (newboard);
1403     }
1404     else
1405     {
1406         if (mymove->value <= alfa)
1407         {
1408             node->upper = mymove->value;
1409         }
1410         else if ((mymove->value > alfa) && (mymove->value < beta))
1411         {   /* this shouldn't happen with zero window searches */
1412             node->upper = node->lower = mymove->value;
1413         }
1414         else if (mymove->value >= beta)
1415         {
1416             node->lower = mymove->value;
1417         }
1418     }
1419
1420
1421     return (mymove);
1422 }
1423
1424 /*
1425 ** calculate the value of a certain board position
1426 **
1427 ** returns a value between 1000 and -1000 (inclusive)
1428 **   1000 : I win
1429 **  -1000 : my opponent wins
1430 */
1431 int mem_evaluate (board * oboard, mtdf_info * me)
1432 {
1433     int total,
1434         i,
1435         value;
1436     double wvalue,
1437         bvalue;
1438     char myc,
1439         otherc;
1440     position * pos;
1441
1442     myc = me->colour;
1443     otherc = b_opponent (myc);
1444
1445     if (b_game_finished (oboard))
1446     {
1447         if (b_winner (oboard) == myc)
1448         {
1449             return (1000);
1450         }
1451         else
1452         {
1453             return (-1000);
1454         }
1455     }
1456
1457     /* maybe I can return 1000 or -1000, but I'm not completely sure */
1458     if (b_colour (oboard, myc) == 0)
1459     {
1460         return (-999);
1461     }
1462     else if (b_colour (oboard, otherc) == 0)
1463     {
1464         return (999);
1465     }
1466
1467     /* I need to start with a base-value, or I get a lot of
1468     ** problems at the start of tournament games */
1469     wvalue = 20;
1470     bvalue = 20;
1471
1472     /* capturing a piece from your opponent is worth 20 points */
1473     wvalue += 20 * b_black_lost (oboard);
1474     bvalue += 20 * b_white_lost (oboard);
1475
1476     /* 1 point for each piece in use on the board */
1477     if (b_white_gipf (oboard) == -1)
1478         total = 15;
1479     else
1480         total = 18;
1481
1482     wvalue += total - b_white (oboard) - b_white_lost (oboard);
1483     bvalue += total - b_black (oboard) - b_black_lost (oboard);
1484
1485     /* 2 pieces or less left is getting dangerous */
1486
1487     /* one gipf left can be dangerous, subtract 5 points */
1488     if (b_white_gipf (oboard) == 1)
1489     {
1490         wvalue -= 5;
1491     }
1492     if (b_black_gipf (oboard) == 1)
1493     {
1494         bvalue -= 5;
1495     }
1496
1497     /* pieces closer to the center have a higher value */
1498     for (i = 0; i < 19; i++)
1499     {
1500         pos = &(mem_pos_val[i].coor);
1501         switch (b_ppiece (oboard, pos))
1502         {
1503         case '.':
1504             break;
1505
1506         case 'o':
1507             wvalue += mem_pos_val[i].value;
1508             break;
1509
1510         case 'O':
1511             wvalue += mem_pos_val[i].value * 1.5;
1512             break;
1513
1514         case 'x':
1515             bvalue += mem_pos_val[i].value;
1516             break;
1517
1518         default:
1519             bvalue += mem_pos_val[i].value * 1.5;
1520         }
1521 /*
1522         piece = b_ppiece (oboard, pos);
1523         if (piece == '.')
1524         {
1525             continue;
1526         }
1527         if (piece == 'o')
1528         {
1529             wvalue += mem_pos_val[i].value;
1530         }
1531         else if (piece == 'O')
1532         {
1533             wvalue += mem_pos_val[i].value * 1.5;
1534         }
1535         else if (piece == 'x')
1536         {
1537             bvalue += mem_pos_val[i].value;
1538         }
1539         else
1540         {
1541             bvalue += mem_pos_val[i].value * 1.5;
1542         }
1543 */
1544     }
1545
1546     /* normalize the result, should be between 1000 and -1000 */
1547     if (myc == 'o')
1548     {
1549         value = (int) ((wvalue - bvalue) * 1000 / (wvalue + bvalue));
1550     }
1551     else
1552     {
1553         value = (int) ((bvalue - wvalue) * 1000 / (wvalue + bvalue));
1554     }
1555
1556     return (value);
1557 }
1558
1559 void mem_del_move (movestruct * todel)
1560 {
1561     nextmove * movedata;
1562     gipfdata * gipfd;
1563
1564     if (todel->movelist != NULL)
1565     {
1566         while ((movedata = (nextmove *) llrembynr (todel->movelist, 1))
1567                != NULL)
1568         {
1569             if (movedata->remtype == REM_ROW)
1570             {
1571                 free (movedata->rowdata.start);
1572                 free (movedata->rowdata.end);
1573             }
1574             else
1575             {
1576                 while ((gipfd = (gipfdata *)
1577                         llrembynr (movedata->gipflist, 1)) != NULL)
1578                 {
1579                     free (gipfd);
1580                 }
1581                 free (movedata->gipflist);
1582             }
1583
1584             free (movedata);
1585         }
1586         free (todel->movelist);
1587     }
1588
1589     free (todel);
1590     return;
1591 }
1592
1593
1594 /*
1595 ** create the root of the tree
1596 **
1597 ** parameter:
1598 **     father: the board at the root of the tree
1599 */
1600 treenode * mem_makeroot (board * father, mtdf_info * me)
1601 {
1602     treenode * newnode;
1603
1604     if (me->config.memorydepth == 0)
1605     {
1606         return (NULL);
1607     }
1608
1609     newnode = (treenode *) malloc (sizeof (treenode));
1610     newnode->father = father;
1611     newnode->upper = 1001;
1612     newnode->lower = -1001;
1613
1614     newnode->children = (listheader *) malloc (sizeof (listheader));
1615     newlist (newnode->children);
1616
1617     return (newnode);
1618 }
1619
1620
1621 /*
1622 ** delete a tree
1623 ** don't delete the father from the root-node
1624 */
1625 void mem_deltree (treenode * node)
1626 {
1627     if (node == NULL)
1628     {
1629         return;
1630     }
1631
1632     emptyll (node->children, mem_delnode);
1633     free (node->children);
1634     free (node);
1635
1636     return;
1637 }
1638
1639 void mem_delnode (void * item)
1640 {
1641     treenode * node = item;
1642
1643     b_del (node->father);
1644     emptyll (node->children, mem_delnode);
1645     free (node->children);
1646     free (node);
1647
1648     return;
1649 }
1650
1651
1652 /*
1653 ** reset upper and lower limits in the memory-tree
1654 */
1655 void mem_resetul (void * item)
1656 {
1657     treenode * node = item;
1658
1659     node->upper = 1001;
1660     node->lower = -1001;
1661     doll (node->children, mem_resetul);
1662
1663     return;
1664 }
1665
1666
1667 /*
1668 ** check if a child-node already exists,
1669 ** if not, create a new one
1670 */
1671 treenode * mem_child (treenode * node, int nr, mtdf_info * me, int depth)
1672 {
1673     treenode * newnode;
1674
1675     if (me->config.memorydepth < depth)
1676     {
1677         return (NULL);
1678     }
1679
1680     newnode = (treenode *) llitembynr (node->children, nr);
1681     if (newnode != NULL)
1682     {   /* this node has already been handled, return it */
1683         return (newnode);
1684     }
1685
1686 #if 0
1687 /* just for testing */
1688 /* check if the previous nr exists, it should */
1689 if ((nr > 1) && (llitembynr (node->children, nr-1) == NULL))
1690 {
1691     printf ("\nERROR: mem_child\n\n");
1692     exit (0);
1693 }
1694 #endif
1695
1696     /* create a new node */
1697     newnode = (treenode *) malloc (sizeof (treenode));
1698     newnode->father = NULL;
1699     newnode->children = NULL;
1700     newnode->upper = 1001;
1701     newnode->lower = -1001;
1702     pushll (node->children, newnode);
1703
1704     return (newnode);
1705 }
1706
1707 /*
1708 ** just like a normal compare (<)
1709 ** returns:
1710 **   1 : nr1 < nr2
1711 **   0: nr1 > nr2
1712 **   0/1: when nr1 and nr2 are equal, chooses one at random
1713 **
1714 ** chance is the chance that nr1 will be chosen if nr1 == nr2
1715 ** this parameter will be incremented each time an equal occurs
1716 ** and will be set to 1 if nr1 < nr2
1717 ** (it should be initialised to 1 by the caller and then left alone)
1718 */
1719 int mem_equ_l (int nr1, int nr2, int * chance, mtdf_info * me)
1720 {
1721     int randnr;
1722
1723     if (me->config.randomchoose == 0)
1724         return (nr1 < nr2);
1725
1726     if (nr1 < nr2)
1727     {
1728         *chance = 1;
1729         return (1);
1730     }
1731     if (nr1 > nr2)
1732     {
1733         return (0);
1734     }
1735
1736     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
1737     (*chance)++;
1738
1739     if (randnr < 1)
1740     {
1741         return (1);
1742     }
1743
1744     return (0);
1745 }
1746
1747
1748 /*
1749 ** just like a normal compare (>)
1750 ** returns:
1751 **   1 : nr1 > nr2
1752 **   0: nr1 < nr2
1753 **   0/1: when nr1 and nr2 are equal, chooses one at random
1754 **
1755 ** chance is the chance that nr1 will be chosen if nr1 == nr2
1756 ** this parameter will be incremented each time an equal occurs
1757 ** and will be set to 1 if nr1 > nr2
1758 ** (it should be initialised to 1 by the caller and then left alone)
1759 */
1760 int mem_equ_h (int nr1, int nr2, int * chance, mtdf_info * me)
1761 {
1762     int randnr;
1763
1764     if (me->config.randomchoose == 0)
1765         return (nr1 > nr2);
1766
1767     if (nr1 > nr2)
1768     {
1769         *chance = 1;
1770         return (1);
1771     }
1772     if (nr1 < nr2)
1773     {
1774         return (0);
1775     }
1776
1777     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
1778     (*chance)++;
1779
1780     if (randnr < 1)
1781     {
1782         return (1);
1783     }
1784
1785     return (0);
1786 }