← Back to branch summary

~ml-launchpad/ubuntu/natty/gcompris/fix-for-777349

« back to all changes in this revision

Viewing changes to src/awele-activity/awele_alphaBeta.c

  • Committer: Bazaar Package Importer
  • Author(s): Marc Gariepy, Marc Gariepy, Stephane Graber
  • Date: 2010-01-04 17:42:49 UTC
  • mfrom: (1.1.14 upstream)
  • Revision ID: james.westby@ubuntu.com-20100104174249-7bupatd9dtxyhvs4
Tags: 9.0-0ubuntu1
[Marc Gariepy]
* New upstream release (9.0).
* Remove cache.c from POTFILES to avoid FTBFS
* Remove unneeded rm in debian/rules (file no longer exists upstream)

[Stephane Graber]
* Bump Debian standards to 3.8.3
* Add patch system (dpatch)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/awele-activity/awele_alphaBeta.c
 
1
/*
 
2
 * gcompris - awele.c
 
3
 * Copyright (C) 2005, 2008 Frederic Mazzarol
 
4
 *
 
5
 *   This program is free software; you can redistribute it and/or modify
 
6
 *   it under the terms of the GNU General Public License as published by
 
7
 *   the Free Software Foundation; either version 3 of the License, or
 
8
 *   (at your option) any later version.
 
9
 *
 
10
 *   This program is distributed in the hope that it will be useful,
 
11
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *   GNU General Public License for more details.
 
14
 *
 
15
 *   You should have received a copy of the GNU General Public License
 
16
 *   along with this program; if not, see <http://www.gnu.org/licenses/>.
 
17
 */
 
18
 
 
19
#include "awele_utils.h"
 
20
#include <string.h>
 
21
#include <stdlib.h>
 
22
#include "gcompris/gcompris.h"
 
23
 
 
24
 
 
25
static gint maxprof;
 
26
 
 
27
/**
 
28
* Fonction d'evaluation d'un plateau
 
29
* La fonction d'evaluation va evaluer la difference du nombre de graines capturees (Facteur preponderant),\n
 
30
* la difference de la mobilite des deux joueurs, la difference des cases menacantes,\n
 
31
* et la difference du nombre de graine active de chaque joueur.\n
 
32
* @param AWALE *aw Pointeur sur la structure AWALE a evaluer
 
33
* @return Une note d'evaluation du plateau.
 
34
*/
 
35
gint eval (GNode *node){
 
36
  AWALE *aw = node->data;
 
37
 
 
38
  if (aw->CapturedBeans[COMPUTER] > 24)
 
39
    return 25;
 
40
 
 
41
  if (aw->CapturedBeans[HUMAN] > 24)
 
42
    return -25;
 
43
 
 
44
  return (aw->CapturedBeans[COMPUTER] - aw->CapturedBeans[HUMAN]);
 
45
}
 
46
 
 
47
/*
 
48
 * Evaluation function for level 1-2
 
49
 * this function returns always 0. The play is random,
 
50
 * because tree building is randomised.
 
51
 *
 
52
 */
 
53
gint eval_to_null (GNode *node){
 
54
  return 0;
 
55
}
 
56
 
 
57
 
 
58
gint eval_to_best_capture (GNode *node){
 
59
  AWALE *aw = node->data;
 
60
 
 
61
  return (aw->CapturedBeans[COMPUTER]);
 
62
}
 
63
 
 
64
/*
 
65
 * firstChild. create all the childs and return first one
 
66
 */
 
67
GNode *firstChild(GNode *node)
 
68
{
 
69
  AWALE *aw = node->data;
 
70
  AWALE *tmpaw;
 
71
  GNode *tmpnode;
 
72
  gint eval_node = eval(node);
 
73
  gint rand_play;
 
74
 
 
75
  /* Case node is winning one */
 
76
  if ((eval_node == 25) || (eval_node == -25))
 
77
    return NULL;
 
78
 
 
79
  gint i;
 
80
  rand_play = g_random_int_range(1, 5);
 
81
 
 
82
  for (i = 0 ; i < 6; i++)
 
83
    {
 
84
      tmpaw = moveAwale((rand_play + i)%6 + ((aw->player == HUMAN )? 6 : 0), aw);
 
85
      if (tmpaw){
 
86
        tmpnode = g_node_new(tmpaw);
 
87
        g_node_insert (node, -1, tmpnode);
 
88
      }
 
89
    }
 
90
 
 
91
  return g_node_first_child(node);
 
92
}
 
93
 
 
94
/* next sibling */
 
95
GNode *nextSibling(GNode *node)
 
96
{
 
97
  return g_node_next_sibling(node);
 
98
}
 
99
 
 
100
 
 
101
gboolean free_awale(GNode *node,
 
102
                    gpointer data){
 
103
  g_free(data);
 
104
  return TRUE;
 
105
}
 
106
 
 
107
 
 
108
/**
 
109
* Fonction de jeu de la machine
 
110
* Cette Fonction est appelee pour faire jouer l'ordinateur, \n
 
111
* la racine de l'arbre est cree, puis passe en argument a la fonction AlphaBeta\n
 
112
* La profondeur augmente au fur et mesure de la partie quand le nombre de graines diminue.\n
 
113
* @param aw Un pointeur sur le plateau a partir duquel reflechir
 
114
* @return Le meilleur coup calcule par la machine
 
115
* le player est celui qui a joué le dernier coup.
 
116
*/
 
117
 
 
118
short int  think( AWALE *static_awale, short int level){
 
119
 
 
120
  AWALE *aw = g_malloc(sizeof(AWALE));
 
121
  memcpy (aw, static_awale, sizeof(AWALE));
 
122
 
 
123
  GNode *t = g_node_new(aw) ;
 
124
 
 
125
  int best = -1;
 
126
  int value = 0;
 
127
  EvalFunction use_eval = NULL;
 
128
 
 
129
  switch (level) {
 
130
  case 1:
 
131
    maxprof = 1;
 
132
    use_eval = (EvalFunction)&eval_to_null;
 
133
    g_warning("search depth 1, evaluation null");
 
134
    break;
 
135
  case 2:
 
136
    maxprof = 1;
 
137
    use_eval = (EvalFunction)&eval_to_best_capture;
 
138
    g_warning("search depth 1, evaluation best capture");
 
139
    break;
 
140
  case 3:
 
141
  case 4:
 
142
    maxprof = 2;
 
143
    use_eval = (EvalFunction)&eval;
 
144
    g_warning("search depth %d, evaluation best difference", maxprof);
 
145
    break;
 
146
  case 5:
 
147
  case 6:
 
148
    maxprof = 4;
 
149
    use_eval = (EvalFunction)&eval;
 
150
    g_warning("search depth %d, evaluation best difference", maxprof);
 
151
    break;
 
152
  case 7:
 
153
  case 8:
 
154
    maxprof = 6;
 
155
    use_eval = (EvalFunction)&eval;
 
156
    g_warning("search depth %d, evaluation best difference", maxprof);
 
157
    break;
 
158
  case 9:
 
159
    maxprof = 8;
 
160
    use_eval = (EvalFunction)&eval;
 
161
    g_warning("search depth %d, evaluation best difference", maxprof);
 
162
    break;
 
163
  default:
 
164
    maxprof = 8;
 
165
    use_eval = (EvalFunction)&eval;
 
166
    g_warning("search depth %d, evaluation best difference", maxprof);
 
167
    break;
 
168
  }
 
169
 
 
170
  value = gc_alphabeta( TRUE,
 
171
                        t,
 
172
                        use_eval,
 
173
                        &best,
 
174
                        (FirstChildGameFunction) firstChild,
 
175
                        (NextSiblingGameFunction) nextSibling,
 
176
                        -INFINI ,
 
177
                        INFINI,
 
178
                        maxprof) ;
 
179
 
 
180
  if (best < 0){
 
181
    g_warning("Leaf node, game is over");
 
182
    return -1;
 
183
  }
 
184
  GNode *tmpNode = g_node_nth_child (t, best);
 
185
 
 
186
  AWALE *tmpaw = tmpNode->data;
 
187
 
 
188
  g_warning("THINK best : %d, play: %d", value, tmpaw->last_play);
 
189
 
 
190
  best = tmpaw->last_play;
 
191
 
 
192
  /* free awales*/
 
193
  g_node_traverse (t,
 
194
                   G_IN_ORDER,
 
195
                   G_TRAVERSE_ALL,
 
196
                   -1,
 
197
                   (GNodeTraverseFunc) free_awale,
 
198
                   NULL);
 
199
 
 
200
  /* free tree */
 
201
  g_node_destroy(t);
 
202
 
 
203
  return (best);
 
204
}
 
205