ai_player.h

   1 /*
   2 ** $Id$
   3 **
   4 ** a class for minimax-searching.
   5 ** implements methods for minimax with alfa-beta pruning and for
   6 ** mtdf and iterative deepening mtdf
   7 **
   8 ** the class defined here must be subclassed for each game
   9 */
  10 /*
  11 **    Copyright (C) 1999 Kurt Van den Branden
  12 **
  13 ** This program is free software; you can redistribute it and/or modify
  14 ** it under the terms of the GNU General Public License as published by
  15 ** the Free Software Foundation; either version 2 of the License, or
  16 ** (at your option) any later version.
  17 **
  18 ** This program is distributed in the hope that it will be useful,
  19 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  20 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21 ** GNU General Public License for more details.
  22 **
  23 ** You should have received a copy of the GNU General Public License
  24 ** along with this program; if not, write to the Free Software
  25 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26 */
  27
  28 #ifndef _AI_PLAYER_H_
  29 #define _AI_PLAYER_H_ 1
  30
  31 using namespace std;
  32
  33 #include <sys/time.h>
  34 #include <unistd.h>
  35 #include <vector>
  36 #include "linklist.h"
  37
  38 #ifdef MSWIN
  39 #include "gettimeofday.h"
  40 #endif
  41
  42 #ifndef min
  43 #define min(x, y)     (x < y ? x : y)
  44 #endif
  45 #ifndef max
  46 #define max(x, y)     (x > y ? x : y)
  47 #endif
  48
  49 enum {   // for the type of the searchnode
  50     MIN,
  51     MAX
  52 };
  53
  54 enum {   // for the max-player
  55     PLAYER1,
  56     PLAYER2,
  57 };
  58
  59 enum {   // for the status after a search is finished
  60     AI_OK,
  61     AI_TIMEUP,
  62     AI_STOPPED,
  63 };
  64
  65
  66 // nothing special, must be subclassed
  67 class basemove {
  68  private:
  69  public:
  70     basemove () {};
  71 //    virtual basemove (basemove &) {}; // copy constructor necessary
  72
  73     virtual ~basemove () {};
  74
  75     virtual basemove * copy () { return (new basemove); };
  76 };
  77
  78
  79 // structure containing information about nodes from the searchtree
  80 struct searchnode {
  81     void * gameposition;
  82     int finished; /*
  83                   ** -1: gameposition not calculated yet
  84                   ** 0 : not a leafnode
  85                   ** 1 : this position is a leaf-node
  86                   ** 2 : never use this as a leaf-node, not even
  87                   **     if pas maximum depth
  88                   */
  89     int depth;
  90     int value;
  91     int upper;
  92     int lower;
  93     int type;   // MIN or MAX
  94     vector<basemove *> movelist;
  95     vector<searchnode *> childlist;
  96 };
  97
  98
  99 class ai_player {
 100  private:
 101     int maxdepth;            // maximum search-depth
 102     float maxtime;           // maximum allowed search-time in seconds
 103                              // (only used by mtdf_id)
 104     int memorydepth;         // maximum search-depth at which to keep
 105                              // searchnodes in memory
 106     int randomchoose;        // if 2 searchnodes have the same value
 107                              // choose one at random if this flag is set.
 108                              // otherwise, always choose the first one
 109     int player;              // PLAYER1 or PLAYER2
 110                              // this will be given to the evaluation-function
 111                              // as the 2nd parameter
 112     int lastvalue;           // value of the last move
 113     int state;               // status after a search is done
 114
 115     struct timeval basetime;
 116
 117     int stopnow;             // will be set to 1 if stopfunc() returns 1
 118
 119     virtual int evalfunc (void * game, int maxplayer) = 0;
 120                  // evaluation function
 121                  // to be used when the maximum search-depth
 122                  // has been reached, or the game is finished
 123                  // (returns a value between -1000 and 1000)
 124     virtual void listfunc (void * game, vector<basemove *> &) = 0;
 125                  // function that produces a
 126                  // list of possible moves starting from
 127                  // the current game-position
 128     virtual void * newfunc (void * game, basemove * move, int * finished,
 129                             int * depthdelta, int * nodetype) = 0;
 130                  // function that produces
 131                  // a new game-position starting from the
 132                  // the current position and a move
 133                  // the third parameter is a flag to show
 134                  // if the game is finished.
 135                  // (also signals a change in searchdepth and
 136                  //  the nodetype of the new node => MIN or MAX)
 137                  // (the function must return NULL if the move is invalid)
 138 #if 0
 139     virtual void * copymovefunc (void * move) = 0;
 140                  // a function for copying an item
 141                  // from the list as produced by 'listfunc'
 142     virtual void delmovefunc (void * move) = 0;
 143                  // a function for deleting an item
 144                  // from the list as produced by 'listfunc'
 145 #endif
 146     virtual void delgamefunc (void * game) = 0;
 147                  // a function for deleting a
 148                  // a game-position as returned by 'newfunc'
 149     virtual int stopfunc (void) = 0;
 150                  // stop searching immediatly if this function returns 1.
 151                  // this function will be called regularly, so it can also
 152                  // be used for event-checking and things like that.
 153                  // minimax_ab, mtdf and mtdf_id will return NULL when
 154                  // stopfunc returns 1.
 155                  // (preferably make this function inline)
 156
 157 //    listheader * minimax_ab (searchnode * node, int alfa, int beta);
 158     vector<basemove *> * ab_mem (searchnode * node, int alfa, int beta);
 159     vector<basemove *> * mtdf (searchnode * node);
 160
 161     int outoftime (void);
 162     int halfoutoftime (void);
 163
 164     inline searchnode * nodechild (searchnode * node, int nr);
 165     void delmemtree (searchnode * node, int flag = 1);
 166     inline void delmovelist (vector<basemove *> * todel);
 167     void reset_ul (searchnode * node);
 168
 169     int equ_h (int nr1, int nr2, int * chance);
 170     int equ_l (int nr1, int nr2, int * chance);
 171
 172  public:
 173     ai_player ();
 174     virtual ~ai_player ();
 175
 176     void searchdepth (int value) { maxdepth = value; };
 177     int searchdepth (void) { return (maxdepth); };
 178     void random (int flag) { if (flag > 0) randomchoose = 1;
 179                                 else randomchoose = 0; };
 180     void memdepth (int value) { memorydepth = value; };
 181     void maxplayer (int value) { player = value; };
 182     int maxplayer (void) { return (player); };
 183     int gamevalue (void) { return (lastvalue); };
 184     int status (void) { return (state); };
 185
 186     // the three following functions return a list of items as produced
 187     // by 'listfunc'
 188     // this list contains all the moves necessary to get to the best move
 189     // at the maximum searchdepth. you probably will only need the first item
 190
 191     // iterative deepening mtdf
 192     vector<basemove *> * mtdf_id (void * startgame, int starttype = MAX,
 193                           float mtime = 0.0);
 194     // normal mtdf
 195     vector<basemove *> * mtdf (void * startgame, int starttype = MAX);
 196     // minimax with alfabeta pruning
 197     vector<basemove *> * minimax_ab (void * startgame, int starttype = MAX);
 198 };
 199
 200 #endif