ai_player.cxx

   1 /*
   2 ** $Id$
   3 */
   4 /*
   5 **    Copyright (C) 1999 Kurt Van den Branden
   6 **
   7 ** This program is free software; you can redistribute it and/or modify
   8 ** it under the terms of the GNU General Public License as published by
   9 ** the Free Software Foundation; either version 2 of the License, or
  10 ** (at your option) any later version.
  11 **
  12 ** This program is distributed in the hope that it will be useful,
  13 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 ** GNU General Public License for more details.
  16 **
  17 ** You should have received a copy of the GNU General Public License
  18 ** along with this program; if not, write to the Free Software
  19 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20 */
  21
  22 #include <iostream>
  23 #include <malloc.h>
  24 #include <stdlib.h>
  25 #include <time.h>
  26 #include <algorithm>
  27 #include "ai_player.h"
  28
  29
  30 // constructor
  31 ai_player::ai_player  ()
  32 {
  33     maxdepth = 2;
  34     maxtime = 0;
  35     memorydepth = 0;
  36     randomchoose = 1;
  37     player = PLAYER1;
  38     lastvalue = 0;
  39     state = AI_OK;
  40     stopnow = 0;
  41
  42     return;
  43 }
  44
  45
  46 // destructor
  47 ai_player::~ai_player ()
  48 {
  49     return;
  50 }
  51
  52
  53 vector<basemove *> * ai_player::minimax_ab (void * startgame, int starttype)
  54 {
  55     searchnode * firstnode;
  56     vector<basemove *> * move;
  57
  58     state = AI_OK;
  59     stopnow = 0;
  60
  61     if (randomchoose)
  62         srand (time (NULL));
  63
  64     firstnode = new searchnode;
  65
  66     firstnode->gameposition = startgame;
  67     firstnode->finished = 0;
  68     firstnode->depth = 1;
  69     firstnode->value = 0;
  70     firstnode->upper = 1001;
  71     firstnode->lower = -1001;
  72     firstnode->type = starttype;
  73 //    firstnode->movelist = NULL;
  74 //    firstnode->childlist = NULL;
  75
  76 //    move = minimax_ab (firstnode, -1001, 1001);
  77     move = ab_mem (firstnode, -1001, 1001);
  78     lastvalue = firstnode->value;
  79
  80     delmemtree (firstnode, 0);
  81
  82     if (move != NULL)
  83         reverse (move->begin(), move->end());
  84     return (move);
  85 }
  86
  87
  88 #if 0
  89 /*
  90 ** correct, but replaced by ab_mem
  91 */
  92 listheader * ai_player::minimax_ab (searchnode * node, int alfa, int beta)
  93 {
  94     int value,
  95         ddelta,
  96         chance = 1;
  97     unsigned counter;
  98     listheader * movel = NULL,
  99         * newmovel;
 100     void * moveitem;
 101     searchnode * newnode;
 102
 103     // check for leafnode
 104     // (end-of-game or maxdepth exceeded)
 105     if ((node->finished) ||
 106         (node->depth > maxdepth))
 107     {
 108         value = evalfunc (node->gameposition, player);
 109
 110         // create an empty move
 111         movel = (listheader *) malloc (sizeof (listheader));
 112         newlist (movel);
 113     }
 114     // search the tree
 115     else
 116     {
 117         if (node->movelist == NULL)
 118         {
 119             node->movelist = listfunc (node->gameposition);
 120             node->childlist = (listheader *) malloc (sizeof (listheader));
 121             newlist (node->childlist);
 122         }
 123
 124         if (node->type == MAX)
 125         {
 126             value = -1001;
 127
 128             counter = 1;
 129             while ((moveitem = llitembynr (node->movelist, counter)) != NULL)
 130             {
 131                 // generate child (if necessary)
 132                 newnode = nodechild (node, counter);
 133
 134                 counter++;
 135
 136                 if (newnode->finished == -1)
 137                 {   // calculate new position
 138                     newnode->finished = 0;
 139                     newnode->gameposition =
 140                         newfunc (node->gameposition, moveitem,
 141                                  &(newnode->finished), &ddelta,
 142                                  &(newnode->type));
 143                     newnode->depth += ddelta;
 144                 }
 145
 146                 if (newnode->gameposition == NULL)
 147                     continue;
 148
 149                 newmovel = minimax_ab (newnode, alfa, beta);
 150
 151                 // is the new move better then the previous best
 152 //              if (equ_h (newnode->value, value, &chance))
 153                 if (((node->depth == 1) &&
 154                      (equ_h (newnode->value, value, &chance))) ||
 155                     ((node->depth > 1) && (newnode->value > value)))
 156                 {
 157                     value = newnode->value;
 158                     delmovelist (movel);
 159                     movel = newmovel;
 160                     unshiftll (movel, copymovefunc (moveitem));
 161                 }
 162                 else
 163                 {
 164                     delmovelist (newmovel);
 165                 }
 166
 167                 alfa = max (alfa, value);
 168
 169                 if (value > beta)
 170 //              if (value >= beta)
 171                 {
 172                     break;
 173                 }
 174             }
 175         }
 176         else // MIN
 177         {
 178             value = 1001;
 179
 180             counter = 1;
 181             while ((moveitem = llitembynr (node->movelist, counter)) != NULL)
 182             {
 183                 // generate child (if necessary)
 184                 newnode = nodechild (node, counter);
 185
 186                 counter++;
 187
 188                 if (newnode->finished == -1)
 189                 {   // calculate new position
 190                     newnode->finished = 0;
 191                     newnode->gameposition =
 192                         newfunc (node->gameposition, moveitem,
 193                                  &(newnode->finished), &ddelta,
 194                                  &(newnode->type));
 195                     newnode->depth += ddelta;
 196                 }
 197
 198                 if (newnode->gameposition == NULL)
 199                     continue;
 200
 201                 newmovel = minimax_ab (newnode, alfa, beta);
 202
 203                 // is the new move better then the previous best
 204 //              if (equ_l (newnode->value, value, &chance))
 205                 if (((node->depth == 1) &&
 206                      (equ_l (newnode->value, value, &chance))) ||
 207                     ((node->depth > 1) && (newnode->value < value)))
 208                 {
 209                     value = newnode->value;
 210                     delmovelist (movel);
 211                     movel = newmovel;
 212                     unshiftll (movel, copymovefunc (moveitem));
 213                 }
 214                 else
 215                 {
 216                     delmovelist (newmovel);
 217                 }
 218
 219                 beta = min (beta, value);
 220
 221                 if (value < alfa)
 222 //              if (value <= alfa)
 223                 {
 224                     break;
 225                 }
 226             }
 227         }
 228     }
 229
 230     node->value = value;
 231
 232     // cleanup children-nodes
 233     while ((newnode = (searchnode *) llrembynr (node->childlist, 1))
 234            != NULL)
 235     {
 236         delmemtree (newnode);
 237     }
 238
 239     // what if no valid move ?
 240     // is it enough that movel contains NULL in that case ?
 241
 242     return (movel);
 243 }
 244 #endif
 245
 246
 247 vector<basemove *> * ai_player::ab_mem (searchnode * node, int alfa, int beta)
 248 {
 249     int value,
 250         ddelta,
 251         chance = 1,
 252         a, b;
 253     unsigned len, i;
 254     vector<basemove *> * movel = NULL,
 255         * newmovel;
 256     searchnode * newnode;
 257
 258     if (node->lower > beta)  // >=
 259     {
 260         node->value = node->lower;
 261         // create an empty move
 262         movel = new vector<basemove *>;
 263         return (movel);
 264     }
 265     if (node->upper < alfa)  // <=
 266     {
 267         node->value = node->upper;
 268         // create an empty move
 269         movel = new vector<basemove *>;
 270         return (movel);
 271     }
 272     alfa = max (alfa, node->lower);
 273     beta = min (beta, node->upper);
 274
 275     // check for leafnode
 276     // (end-of-game or maxdepth exceeded)
 277     if ((node->finished == 1) ||
 278         ((node->depth > maxdepth) && (node->finished != 2)))
 279     {
 280         value = evalfunc (node->gameposition, player);
 281
 282         // create an empty move
 283         movel = new vector<basemove *>;
 284     }
 285     // search the tree
 286     else
 287     {
 288         if (node->movelist.empty())
 289         {
 290             listfunc (node->gameposition, node->movelist);
 291         }
 292
 293         if (node->type == MAX)
 294         {
 295             value = -1001;
 296             a = alfa;
 297
 298             len = node->movelist.size();
 299             for (i = 0; i < len; i++)
 300 //          while ((moveitem = llitembynr (node->movelist, counter)) != NULL)
 301             {
 302                 // generate child (if necessary)
 303                 newnode = nodechild (node, i);
 304
 305                 if (newnode->finished == -1)
 306                 {   // calculate new position
 307                     newnode->finished = 0;
 308                     newnode->gameposition =
 309                         newfunc (node->gameposition, node->movelist[i],
 310                                  &(newnode->finished), &ddelta,
 311                                  &(newnode->type));
 312                     newnode->depth += ddelta;
 313                 }
 314
 315                 if (newnode->gameposition == NULL)
 316                     continue;
 317
 318                 newmovel = ab_mem (newnode, a, beta);
 319
 320                 if (stopnow)
 321                 {
 322                     delmovelist (movel);
 323                     delmovelist (newmovel);
 324                     return (NULL);
 325                 }
 326                 if (outoftime ())
 327                 {
 328                     stopnow = 1;
 329                     state = AI_TIMEUP;
 330                     delmovelist (movel);
 331                     delmovelist (newmovel);
 332                     return (NULL);
 333                 }
 334                 if (stopfunc () == 1)
 335                 {
 336                     state = AI_STOPPED;
 337                     delmovelist (movel);
 338                     delmovelist (newmovel);
 339                     return (NULL);
 340                 }
 341
 342                 // is the new move better then the previous best
 343                 if (((node->depth == 1) &&
 344                      (equ_h (newnode->value, value, &chance))) ||
 345                     ((node->depth > 1) && (newnode->value > value)))
 346                 {
 347                     value = newnode->value;
 348                     delmovelist (movel);
 349                     movel = newmovel;
 350 //                  unshiftll (movel, node->movelist[i]->copy());
 351                     movel->push_back (node->movelist[i]->copy());
 352
 353                     a = max (a, value);
 354
 355                     if (value > beta)
 356                     {
 357                         break;
 358                     }
 359                 }
 360                 else
 361                 {
 362                     delmovelist (newmovel);
 363                 }
 364             }
 365         }
 366         else // MIN
 367         {
 368             value = 1001;
 369             b = beta;
 370
 371             len = node->movelist.size();
 372             for (i = 0; i < len; i++)
 373 //          while ((moveitem = llitembynr (node->movelist, counter)) != NULL)
 374             {
 375                 // generate child (if necessary)
 376                 newnode = nodechild (node, i);
 377
 378                 if (newnode->finished == -1)
 379                 {   // calculate new position
 380                     newnode->finished = 0;
 381                     newnode->gameposition =
 382                         newfunc (node->gameposition, node->movelist[i],
 383                                  &(newnode->finished), &ddelta,
 384                                  &(newnode->type));
 385                     newnode->depth += ddelta;
 386                 }
 387
 388                 if (newnode->gameposition == NULL)
 389                     continue;
 390
 391                 newmovel = ab_mem (newnode, alfa, b);
 392
 393                 if (stopnow)
 394                 {
 395                     delmovelist (movel);
 396                     delmovelist (newmovel);
 397                     return (NULL);
 398                 }
 399                 if (outoftime ())
 400                 {
 401                     stopnow = 1;
 402                     state = AI_TIMEUP;
 403                     delmovelist (movel);
 404                     delmovelist (newmovel);
 405                     return (NULL);
 406                 }
 407                 if (stopfunc () == 1)
 408                 {
 409                     state = AI_STOPPED;
 410                     delmovelist (movel);
 411                     delmovelist (newmovel);
 412                     return (NULL);
 413                 }
 414
 415                 // is the new move better then the previous best
 416 //              if (equ_l (newnode->value, value, &chance))
 417                 if (((node->depth == 1) &&
 418                      (equ_l (newnode->value, value, &chance))) ||
 419                     ((node->depth > 1) && (newnode->value < value)))
 420                 {
 421                     value = newnode->value;
 422                     delmovelist (movel);
 423                     movel = newmovel;
 424 //                  unshiftll (movel, node->movelist[i]->copy());
 425                     movel->push_back (node->movelist[i]->copy());
 426
 427                     b = min (b, value);
 428
 429                     if (value < alfa)
 430                     {
 431                         break;
 432                     }
 433                 }
 434                 else
 435                 {
 436                     delmovelist (newmovel);
 437                 }
 438             }
 439         }
 440     }
 441
 442     node->value = value;
 443
 444     if (value <= alfa)
 445         node->upper = value;
 446     if ((value > alfa) && (value < beta))
 447         node->lower = node->upper = value;
 448     if (value >= beta)
 449         node->lower = value;
 450
 451     // cleanup children-nodes if past maximum memory-depth
 452     if (node->depth > memorydepth)
 453     {
 454         for (int i = node->childlist.size() - 1; i >= 0; i--)
 455         {
 456             delmemtree (node->childlist[i]);
 457             node->childlist.pop_back();
 458         }
 459     }
 460
 461     // what if no valid move ?
 462     // is it enough that movel contains NULL in that case ?
 463
 464     return (movel);
 465 }
 466
 467
 468 vector<basemove *> * ai_player::mtdf (void * startgame, int starttype)
 469 {
 470     searchnode * firstnode;
 471     vector<basemove *> * move;
 472
 473     state = AI_OK;
 474     stopnow = 0;
 475
 476     if (randomchoose)
 477         srand (time (NULL));
 478
 479     firstnode = new searchnode;
 480
 481     firstnode->gameposition = startgame;
 482     firstnode->finished = 0;
 483     firstnode->depth = 1;
 484     firstnode->value = 0;
 485     firstnode->upper = 1001;
 486     firstnode->lower = -1001;
 487     firstnode->type = starttype;
 488 //    firstnode->movelist = NULL;
 489 //    firstnode->childlist = NULL;
 490
 491     move = mtdf (firstnode);
 492     lastvalue = firstnode->value;
 493
 494     delmemtree (firstnode, 0);
 495
 496     if (move != NULL)
 497         reverse (move->begin(), move->end());
 498     return (move);
 499 }
 500
 501
 502 vector<basemove *> * ai_player::mtdf (searchnode * node)
 503 {
 504     int value,
 505         upper,
 506         lower,
 507         gamma;
 508     vector<basemove *> * bestmove = NULL;
 509
 510     value = node->value;
 511     upper = 1001;
 512     lower = -1001;
 513
 514     while ((lower < upper) && (stopnow == 0))
 515     {
 516         if (value == lower)
 517         {
 518             gamma = value + 1;
 519         }
 520         else
 521         {
 522             gamma = value;
 523         }
 524
 525         delmovelist (bestmove);
 526
 527 //      bestmove = mt (node, gamma);  // werkt niet
 528 //      bestmove = minimax_ab (node, gamma-1, gamma); // werkt wel
 529         bestmove = ab_mem (node, gamma-1, gamma);  // werkt ook, en goed
 530         value = node->value;
 531
 532         if (value < gamma)
 533         {
 534             upper = value;
 535         }
 536         else
 537         {
 538             lower = value;
 539         }
 540     }
 541
 542     return (bestmove);
 543 }
 544
 545
 546 // iterative deepening mtdf
 547 vector<basemove *> * ai_player::mtdf_id (void * startgame,
 548                                          int starttype,
 549                                          float mtime)
 550 {
 551     searchnode * firstnode;
 552     int oldvalue,
 553         newvalue,
 554         savedepth,
 555         i;
 556     vector<basemove *> * bestmove = NULL,
 557         * newmove;
 558     struct timezone tz;
 559
 560     maxtime = mtime;
 561     gettimeofday (&basetime, &tz);
 562     state = AI_OK;
 563     stopnow = 0;
 564
 565     if (randomchoose)
 566         srand (time (NULL));
 567
 568     firstnode = new searchnode;
 569
 570     firstnode->gameposition = startgame;
 571     firstnode->finished = 0;
 572     firstnode->depth = 1;
 573     firstnode->value = 0;
 574     firstnode->upper = 1001;
 575     firstnode->lower = -1001;
 576     firstnode->type = starttype;
 577 //    firstnode->movelist = NULL;
 578 //    firstnode->childlist = NULL;
 579
 580     savedepth = maxdepth;
 581     oldvalue = newvalue = 0;
 582     for (i = 1; i <= savedepth; i++)
 583     {
 584         maxdepth = i;
 585         // each mtdf-call is not started with the value from the previous run
 586         // but with the one before that
 587         firstnode->value = oldvalue;
 588         reset_ul (firstnode);
 589
 590         newmove = mtdf (firstnode);
 591
 592         if (stopnow)
 593         {
 594             delmovelist (newmove);
 595             break;
 596         }
 597
 598         oldvalue = newvalue;
 599         newvalue = firstnode->value;
 600
 601         delmovelist (bestmove);
 602         bestmove = newmove;
 603
 604         if (halfoutoftime ())
 605         {   /* soft timeout */
 606             state = AI_TIMEUP;
 607             break;
 608         }
 609     }
 610
 611     maxdepth = savedepth;
 612     lastvalue = firstnode->value;
 613
 614     delmemtree (firstnode, 0);
 615
 616     if (bestmove != NULL)
 617         reverse (bestmove->begin(), bestmove->end());
 618
 619     return (bestmove);
 620 }
 621
 622
 623 /*
 624 ** if flag is 0, then the gameposition will not be deleted
 625 ** this should be used for the root of the nodetree
 626 */
 627 void ai_player::delmemtree (searchnode * node, int flag)
 628 {
 629 //    searchnode * child;
 630 //    void * moveitem;
 631     int i, len;
 632
 633     if (flag)
 634     {
 635         delgamefunc (node->gameposition);
 636     }
 637
 638     if (!node->movelist.empty())
 639     {
 640         len = node->movelist.size();
 641         for (i = 0; i < len; i++)
 642         {
 643             delete node->movelist[i];
 644         }
 645     }
 646
 647     if (!node->childlist.empty())
 648     {
 649         len = node->childlist.size();
 650         for (i = 0; i < len; i++)
 651         {
 652             delmemtree (node->childlist[i]);
 653         }
 654     }
 655
 656     delete node;
 657
 658     return;
 659 }
 660
 661
 662 /*
 663 ** reset upper and lower limits in all nodes from the memory tree
 664 */
 665 void ai_player::reset_ul (searchnode * node)
 666 {
 667 //    searchnode * child;
 668     int i, len;
 669
 670     node->upper = 1001;
 671     node->lower = -1001;
 672
 673     if (!node->childlist.empty())
 674     {
 675         len = node->childlist.size();
 676         for (i = 0; i < len; i++)
 677         {
 678             reset_ul (node->childlist[i]);
 679         }
 680     }
 681
 682     return;
 683 }
 684
 685
 686 inline void ai_player::delmovelist (vector<basemove *> * todel)
 687 {
 688     if (todel != NULL)
 689     {
 690         int len = todel->size(),
 691             i;
 692
 693         for (i = 0; i < len; i++)
 694             delete (*todel)[i];
 695
 696         delete todel;
 697     }
 698
 699     return;
 700 }
 701
 702
 703 /*
 704 ** just like a normal compare (<)
 705 ** returns:
 706 **   1 : nr1 < nr2
 707 **   0: nr1 > nr2
 708 **   0/1: when nr1 and nr2 are equal, chooses one at random
 709 **
 710 ** chance is the chance that nr1 will be chosen if nr1 == nr2
 711 ** this parameter will be incremented each time an equal occurs
 712 ** and will be set to 1 if nr1 < nr2
 713 ** (it should be initialised to 1 by the caller and then left alone)
 714 */
 715 int ai_player::equ_l (int nr1, int nr2, int * chance)
 716 {
 717     int randnr;
 718
 719     if (randomchoose == 0)
 720         return (nr1 < nr2);
 721
 722     if (nr1 < nr2)
 723     {
 724         *chance = 1;
 725         return (1);
 726     }
 727     if (nr1 > nr2)
 728     {
 729         return (0);
 730     }
 731
 732     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
 733     (*chance)++;
 734
 735     if (randnr < 1)
 736     {
 737         return (1);
 738     }
 739
 740     return (0);
 741 }
 742
 743
 744 /*
 745 ** just like a normal compare (>)
 746 ** returns:
 747 **   1 : nr1 > nr2
 748 **   0: nr1 < nr2
 749 **   0/1: when nr1 and nr2 are equal, chooses one at random
 750 **
 751 ** chance is the chance that nr1 will be chosen if nr1 == nr2
 752 ** this parameter will be incremented each time an equal occurs
 753 ** and will be set to 1 if nr1 > nr2
 754 ** (it should be initialised to 1 by the caller and then left alone)
 755 */
 756 int ai_player::equ_h (int nr1, int nr2, int * chance)
 757 {
 758     int randnr;
 759
 760     if (randomchoose == 0)
 761         return (nr1 > nr2);
 762
 763     if (nr1 > nr2)
 764     {
 765         *chance = 1;
 766         return (1);
 767     }
 768     if (nr1 < nr2)
 769     {
 770         return (0);
 771     }
 772
 773     randnr = (int) ( (*chance + 1.0) * rand() / (RAND_MAX+1.0) );
 774     (*chance)++;
 775
 776     if (randnr < 1)
 777     {
 778         return (1);
 779     }
 780
 781     return (0);
 782 }
 783
 784
 785 /*
 786 ** check if a child-node already exists,
 787 ** if not, create a new one
 788 */
 789 inline searchnode * ai_player::nodechild (searchnode * node, unsigned nr)
 790 {
 791     searchnode * newnode;
 792
 793     if (nr < node->childlist.size())
 794         return (node->childlist[nr]);
 795
 796
 797 #if 0
 798 /* just for testing */
 799 /* check if the previous nr exists, it should */
 800 if ((nr > 1) && (llitembynr (node->childlist, nr-1) == NULL))
 801 {
 802     printf ("\nERROR: ai_player::nodechild\n\n");
 803     exit (0);
 804 }
 805 #endif
 806
 807     /* create a new node */
 808     newnode = new searchnode;
 809     newnode->gameposition = NULL;
 810     newnode->finished = -1;
 811     newnode->depth = node->depth;
 812     newnode->value = 0;
 813     newnode->upper = 1001;
 814     newnode->lower = -1001;
 815     newnode->type = node->type;
 816 //    newnode->movelist = NULL;
 817 //    newnode->childlist = NULL;
 818
 819     node->childlist.push_back (newnode);
 820
 821     return (newnode);
 822 }
 823
 824
 825 inline int ai_player::outoftime ()
 826 {
 827     struct timeval tv;
 828     struct timezone tz;
 829     float timedif;
 830
 831     if (maxtime == 0.0)
 832         return (0);
 833
 834     gettimeofday (&tv, &tz);
 835
 836     timedif = (tv.tv_sec - basetime.tv_sec) +
 837         (float) (tv.tv_usec - basetime.tv_usec) / 1000000;
 838
 839     if ((maxtime - timedif) < 0.0)
 840     {
 841 //cout << "hard timeout\n";
 842         return (1);
 843     }
 844
 845     return (0);
 846 }
 847
 848
 849 inline int ai_player::halfoutoftime ()
 850 {
 851     struct timeval tv;
 852     struct timezone tz;
 853     float timedif;
 854
 855     if (maxtime == 0.0)
 856         return (0);
 857
 858     gettimeofday (&tv, &tz);
 859
 860     timedif = (tv.tv_sec - basetime.tv_sec) +
 861         (float) (tv.tv_usec - basetime.tv_usec) / 1000000;
 862
 863     if ((maxtime/2 - timedif) < 0.0)
 864     {
 865 //cout << "soft timeout\n";
 866         return (1);
 867     }
 868
 869     return (0);
 870 }