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 enum {   // for the type of the searchnode
  43     MIN,
  44     MAX
  45 };
  46
  47 enum {   // for the max-player
  48     PLAYER1,
  49     PLAYER2,
  50 };
  51
  52 enum {   // for the status after a search is finished
  53     AI_OK,
  54     AI_TIMEUP,
  55     AI_STOPPED,
  56 };
  57
  58
  59 // nothing special, must be subclassed
  60 class basemove {
  61  private:
  62  public:
  63     basemove () {};
  64 //    virtual basemove (basemove &) {}; // copy constructor necessary
  65
  66     virtual ~basemove () {};
  67
  68     virtual basemove * copy () { return (new basemove); };
  69 };
  70
  71
  72 // structure containing information about nodes from the searchtree
  73 struct searchnode {
  74     void * gameposition;
  75     int finished; /*
  76                   ** -1: gameposition not calculated yet
  77                   ** 0 : not a leafnode
  78                   ** 1 : this position is a leaf-node
  79                   ** 2 : never use this as a leaf-node, not even
  80                   **     if pas maximum depth
  81                   */
  82     int depth;
  83     int value;
  84     int upper;
  85     int lower;
  86     int type;   // MIN or MAX
  87     vector<basemove *> movelist;
  88     vector<searchnode *> childlist;
  89 };
  90
  91
  92 class ai_player {
  93  private:
  94     int maxdepth;            // maximum search-depth
  95     float maxtime;           // maximum allowed search-time in seconds
  96                              // (only used by mtdf_id)
  97     int memorydepth;         // maximum search-depth at which to keep
  98                              // searchnodes in memory
  99     int randomchoose;        // if 2 searchnodes have the same value
 100                              // choose one at random if this flag is set.
 101                              // otherwise, always choose the first one
 102     int player;              // PLAYER1 or PLAYER2
 103                              // this will be given to the evaluation-function
 104                              // as the 2nd parameter
 105     int lastvalue;           // value of the last move
 106     int state;               // status after a search is done
 107
 108     struct timeval basetime;
 109
 110     int stopnow;             // will be set to 1 if stopfunc() returns 1
 111
 112     virtual int evalfunc (void * game, int maxplayer) = 0;
 113                  // evaluation function
 114                  // to be used when the maximum search-depth
 115                  // has been reached, or the game is finished
 116                  // (returns a value between -1000 and 1000)
 117     virtual void listfunc (void * game, vector<basemove *> &) = 0;
 118                  // function that produces a
 119                  // list of possible moves starting from
 120                  // the current game-position
 121     virtual void * newfunc (void * game, basemove * move, int * finished,
 122                             int * depthdelta, int * nodetype) = 0;
 123                  // function that produces
 124                  // a new game-position starting from the
 125                  // the current position and a move
 126                  // the third parameter is a flag to show
 127                  // if the game is finished.
 128                  // (also signals a change in searchdepth and
 129                  //  the nodetype of the new node => MIN or MAX)
 130                  // (the function must return NULL if the move is invalid)
 131 #if 0
 132     virtual void * copymovefunc (void * move) = 0;
 133                  // a function for copying an item
 134                  // from the list as produced by 'listfunc'
 135     virtual void delmovefunc (void * move) = 0;
 136                  // a function for deleting an item
 137                  // from the list as produced by 'listfunc'
 138 #endif
 139     virtual void delgamefunc (void * game) = 0;
 140                  // a function for deleting a
 141                  // a game-position as returned by 'newfunc'
 142     virtual int stopfunc (void) = 0;
 143                  // stop searching immediatly if this function returns 1.
 144                  // this function will be called regularly, so it can also
 145                  // be used for event-checking and things like that.
 146                  // minimax_ab, mtdf and mtdf_id will return NULL when
 147                  // stopfunc returns 1.
 148                  // (preferably make this function inline)
 149
 150 //    listheader * minimax_ab (searchnode * node, int alfa, int beta);
 151     vector<basemove *> * ab_mem (searchnode * node, int alfa, int beta);
 152     vector<basemove *> * mtdf (searchnode * node);
 153
 154     int outoftime (void);
 155     int halfoutoftime (void);
 156
 157     inline searchnode * nodechild (searchnode * node, unsigned nr);
 158     void delmemtree (searchnode * node, int flag = 1);
 159     inline void delmovelist (vector<basemove *> * todel);
 160     void reset_ul (searchnode * node);
 161
 162     int equ_h (int nr1, int nr2, int * chance);
 163     int equ_l (int nr1, int nr2, int * chance);
 164
 165  public:
 166     ai_player ();
 167     virtual ~ai_player ();
 168
 169     void searchdepth (int value) { maxdepth = value; };
 170     int searchdepth (void) { return (maxdepth); };
 171     void random (int flag) { if (flag > 0) randomchoose = 1;
 172                                 else randomchoose = 0; };
 173     void memdepth (int value) { memorydepth = value; };
 174     void maxplayer (int value) { player = value; };
 175     int maxplayer (void) { return (player); };
 176     int gamevalue (void) { return (lastvalue); };
 177     int status (void) { return (state); };
 178
 179     // the three following functions return a list of items as produced
 180     // by 'listfunc'
 181     // this list contains all the moves necessary to get to the best move
 182     // at the maximum searchdepth. you probably will only need the first item
 183
 184     // iterative deepening mtdf
 185     vector<basemove *> * mtdf_id (void * startgame, int starttype = MAX,
 186                           float mtime = 0.0);
 187     // normal mtdf
 188     vector<basemove *> * mtdf (void * startgame, int starttype = MAX);
 189     // minimax with alfabeta pruning
 190     vector<basemove *> * minimax_ab (void * startgame, int starttype = MAX);
 191 };
 192
 193 #endif