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