Back to index

gcompris  8.2.2
gcompris_alphabeta.c
Go to the documentation of this file.
00001 /* gcompris - gcompris_alphabeta.c
00002  *
00003  * Time-stamp: <2006/08/21 23:28:14 bruno>
00004  *
00005  * Copyright (C) 2000 Bruno Coudoin
00006  *
00007  * This program is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00020  */
00021 
00022 #include "gcompris.h"
00023 
00024 /* gc_alphabeta returns the best value of evaluation functions */
00025 /* set the bestChild to the index of child with this value */
00026 /* maximize : TRUE if depth is maximize one, neither FALSE. */
00027 /* treeGame : pointer on game to pass to others functions, */
00028 /* bestChild : pointer on GList wich will contains list of indexes fo best plays. */
00029 /* isLeaf : TRUE if game correspond to a Leaf of Tree. */
00030 /* firstChild : return pointer on first  child of a node. */
00031 /* nextSibling : return pointer on next sibling of a node. */
00032 /* heuristic : evaluation function of game. */
00033 /* depth is max depth of recursion */
00034 gint gc_alphabeta (gboolean maximize,
00035                       gpointer treeGame,
00036                       EvalFunction heuristic,
00037                       gint *bestChild,
00038                       FirstChildGameFunction firstChild,
00039                       NextSiblingGameFunction nextSibling,
00040                       gint alpha,
00041                       gint beta,
00042                       gint depth
00043                       )
00044 {
00045   gpointer child;
00046   gint m, t, nextBest, index;
00047 
00048   g_assert (depth >= 0);
00049   
00050   child = firstChild(treeGame);
00051 
00052   *bestChild = -1;
00053 
00054 /*   g_warning("gc_alphabeta %d %d %d", depth, alpha, beta); */
00055   
00056   /* directly return value for leaf node*/
00057   if ((!child) || (depth == 0)){
00058 /*     g_warning("gc_alphabeta %d returns %d bestChild %d", depth, heuristic(treeGame), *bestChild); */
00059     return heuristic(treeGame);
00060   }
00061 
00062   index = 0;
00063       
00064   if (maximize) {
00065     m = alpha;
00066     while (child){
00067       t = gc_alphabeta (!maximize,
00068                            child,
00069                            heuristic,
00070                            &nextBest,
00071                            firstChild,
00072                            nextSibling,
00073                            m,
00074                            beta,
00075                            depth - 1
00076                            );
00077       if (t > m){
00078        m = t;
00079        *bestChild = index;
00080       }
00081       if ( m >= beta){
00082 /*     g_warning("gc_alphabeta %d returns %d bestChild %d", depth, heuristic(treeGame), *bestChild); */
00083        return m;
00084       }
00085       index++;
00086       child = nextSibling(child);
00087     }
00088 /*     g_warning("gc_alphabeta %d returns %d bestChild %d", depth, heuristic(treeGame), *bestChild); */
00089     return m;
00090   }
00091   else {
00092     /* minimize */
00093     m = beta;
00094     while (child){
00095       t = gc_alphabeta (!maximize,
00096                            child,
00097                            heuristic,
00098                            &nextBest,
00099                            firstChild,
00100                            nextSibling,
00101                            alpha,
00102                            m,
00103                            depth - 1
00104                            );
00105       if (t < m){
00106        m = t;
00107        *bestChild = index;
00108       }
00109       if ( m <= alpha){
00110 /*     g_warning("gc_alphabeta %d returns %d bestChild %d", depth, heuristic(treeGame), *bestChild); */
00111        return m;
00112       }
00113       index++;
00114       child = nextSibling(child);
00115     }
00116 /*     g_warning("gc_alphabeta %d returns %d bestChild %d", depth, heuristic(treeGame), *bestChild); */
00117     return m;
00118 
00119   }
00120 
00121 }