Back to index

gcompris  8.2.2
awele_alphaBeta.c
Go to the documentation of this file.
00001 /*
00002  * gcompris - awele.c Copyright (C) 2005 Frederic Mazzarol This program is
00003  * free software; you can redistribute it and/or modify it under the terms 
00004  * of the GNU General Public License as published by the Free Software
00005  * Foundation; either version 2 of the License, or (at your option) any
00006  * later version.  This program is distributed in the hope that it will
00007  * be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
00008  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00009  * General Public License for more details.  You should have received a
00010  * copy of the GNU General Public License along with this program; if not, 
00011  * write to the Free Software Foundation, Inc., 59 Temple Place, Suite
00012  * 330, Boston, MA 02111-1307 USA 
00013  */
00014 
00015 #include "awele_utils.h"
00016 #include <string.h>
00017 #include <stdlib.h>
00018 #include "gcompris/gcompris.h"
00019 
00020 
00021 static gint maxprof;
00022 
00031 gint eval (GNode *node){
00032   AWALE *aw = node->data;
00033 
00034   if (aw->CapturedBeans[COMPUTER] > 24)
00035     return 25;
00036 
00037   if (aw->CapturedBeans[HUMAN] > 24)
00038     return -25;
00039 
00040   return (aw->CapturedBeans[COMPUTER] - aw->CapturedBeans[HUMAN]);
00041 }
00042 
00043 /*
00044  * Evaluation function for level 1-2
00045  * this function returns always 0. The play is random, 
00046  * because tree building is randomised.
00047  *
00048  */
00049 gint eval_to_null (GNode *node){
00050   return 0;
00051 }
00052 
00053 
00054 gint eval_to_best_capture (GNode *node){
00055   AWALE *aw = node->data;
00056 
00057   return (aw->CapturedBeans[COMPUTER]);
00058 }
00059 
00060 /*
00061  * firstChild. create all the childs and return first one
00062  */
00063 GNode *firstChild(GNode *node)
00064 {
00065   AWALE *aw = node->data;
00066   AWALE *tmpaw;
00067   GNode *tmpnode;
00068   gint eval_node = eval(node);
00069   gint rand_play;
00070 
00071   /* Case node is winning one */
00072   if ((eval_node == 25) || (eval_node == -25))
00073     return NULL;
00074 
00075   gint i;
00076   rand_play = RAND(1, 5);
00077 
00078   for (i = 0 ; i < 6; i++)
00079     {
00080       tmpaw = moveAwale((rand_play + i)%6 + ((aw->player == HUMAN )? 6 : 0), aw);
00081       if (tmpaw){
00082        tmpnode = g_node_new(tmpaw);
00083        g_node_insert (node, -1, tmpnode);
00084       }
00085     }
00086   
00087   return g_node_first_child(node);
00088 }
00089 
00090 /* next sibling */
00091 GNode *nextSibling(GNode *node)
00092 {
00093   return g_node_next_sibling(node);
00094 }
00095 
00096 
00097 gboolean free_awale(GNode *node,
00098                   gpointer data){
00099   g_free(data);
00100   return TRUE;
00101 }
00102 
00103 
00114 short int  think( AWALE *static_awale, short int level){
00115 
00116   AWALE *aw = g_malloc(sizeof(AWALE));
00117   memcpy (aw, static_awale, sizeof(AWALE));
00118 
00119   GNode *t = g_node_new(aw) ;
00120 
00121   int best = -1;
00122   int value = 0;
00123   EvalFunction use_eval = NULL;
00124 
00125   switch (level) {
00126   case 1:
00127     maxprof = 1;
00128     use_eval = (EvalFunction)&eval_to_null;
00129     g_warning("search depth 1, evaluation null");
00130     break;
00131   case 2:
00132     maxprof = 1;
00133     use_eval = (EvalFunction)&eval_to_best_capture;
00134     g_warning("search depth 1, evaluation best capture");
00135     break;
00136   case 3:
00137   case 4:
00138     maxprof = 2;
00139     use_eval = (EvalFunction)&eval;
00140     g_warning("search depth %d, evaluation best difference", maxprof);
00141     break;
00142   case 5:
00143   case 6:
00144     maxprof = 4;
00145     use_eval = (EvalFunction)&eval;
00146     g_warning("search depth %d, evaluation best difference", maxprof);
00147     break;
00148   case 7:
00149   case 8:
00150     maxprof = 6;
00151     use_eval = (EvalFunction)&eval;
00152     g_warning("search depth %d, evaluation best difference", maxprof);
00153     break;
00154   case 9:
00155     maxprof = 8;
00156     use_eval = (EvalFunction)&eval;
00157     g_warning("search depth %d, evaluation best difference", maxprof);
00158     break;
00159   default:
00160     maxprof = 8;
00161     use_eval = (EvalFunction)&eval;
00162     g_warning("search depth %d, evaluation best difference", maxprof);
00163     break;
00164   }
00165 
00166   value = gc_alphabeta( TRUE, 
00167                      t, 
00168                      use_eval, 
00169                      &best, 
00170                      (FirstChildGameFunction) firstChild, 
00171                      (NextSiblingGameFunction) nextSibling,
00172                      -INFINI , 
00173                      INFINI,
00174                      maxprof) ;
00175   
00176   if (best < 0){
00177     g_warning("Leaf node, game is over");
00178     return -1;
00179   }
00180   GNode *tmpNode = g_node_nth_child (t, best);
00181   
00182   AWALE *tmpaw = tmpNode->data;
00183   
00184   g_warning("THINK best : %d, play: %d", value, tmpaw->last_play);
00185   
00186   best = tmpaw->last_play;
00187   
00188   /* free awales*/
00189   g_node_traverse (t,
00190                  G_IN_ORDER,
00191                  G_TRAVERSE_ALL,
00192                  -1,
00193                  (GNodeTraverseFunc) free_awale,
00194                  NULL);
00195 
00196   /* free tree */
00197   g_node_destroy(t);
00198 
00199   return (best);
00200 }
00201