1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
/* $Id: minimax.c,v 1.1.1.1 1995/07/25 11:55:21 sverrehu Exp $ */
/**************************************************************************
*
* FILE minimax.c
*
* DESCRIPTION General routines for doing simple minimax game tree
* search. The caller supplies helper functions for doing
* everything that is not directly a part of the algorithm.
*
* WRITTEN BY Sverre H. Huseby & Glenn Terje Lines
*
**************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include "minimax.h"
/**************************************************************************
* *
* P R I V A T E D A T A *
* *
**************************************************************************/
/*
* Define RANDOM_CHOICE to have the routine choose randomly among moves
* giving equal scores. The main part of the program should use srand()
* to initialize the random number generator.
*/
#define RANDOM_CHOICE
/*
* User supplied callback functions.
*/
static void (*pushBoard)(void);
static void (*popBoard)(void);
static PMove *(*getMoves)(Player, int *);
static Player (*doMove)(Player, PMove);
static void (*undoMove)(Player, PMove);
static Score (*evalBoard)(Player);
/**************************************************************************
* *
* P R I V A T E F U N C T I O N S *
* *
**************************************************************************/
/*-------------------------------------------------------------------------
*
* NAME recMiniMax
*
* FUNCTION Do recursive min/max.
*
* INPUT player the player to evaluate.
* move the move to do for this player.
* depth max recursion depth.
*
* RETURNS The score for this move. A positive value indicates
* that the given player is in the lead after the move.
* A negative value means the opposite player is in the
* lead.
*
* DESCRIPTION This function is the core of the implementation.
*
*/
static Score recMiniMax(Player player, PMove move, int depth)
{
int q; /* my favourite counter */
PMove *newmove; /* array of pointers to possible following moves */
int numMoves; /* number of moves in this array */
Player nextPlayer; /* the player to do the move follwing */
Score ret; /* the score we'll return in the end */
Score tmp; /* the score for a single move */
pushBoard();
nextPlayer = doMove(player, move);
if (!depth) {
/*
* We have reached the max recursion depth, so we just evaluate
* the board with no more checking of moves.
*/
ret = evalBoard(player);
goto finish;
}
newmove = getMoves(nextPlayer, &numMoves);
if (!numMoves) {
/*
* No more moves for the next player. Just evaluate the board.
*/
ret = evalBoard(player);
goto finish;
}
/*
* Check all following moves, and choose the one maximizing
* the score for the player in question.
*/
ret = -INF_SCORE;
for (q = 0; q < numMoves; q++) {
tmp = recMiniMax(nextPlayer, *newmove, depth - 1);
if (tmp > ret)
ret = tmp;
++newmove;
}
if (player != nextPlayer)
ret = -ret;
finish:
undoMove(player, move);
popBoard();
return ret;
}
/**************************************************************************
* *
* P U B L I C F U N C T I O N S *
* *
**************************************************************************/
/*-------------------------------------------------------------------------
*
* NAME miniMax
*
* FUNCTION Get the best move for a given player.
*
* INPUT Several userdefined callback functions:
* fncPushBoard
* This is called at the start of each level
* in the recursion. If neccessary it should save
* the status of the board, so it can be restored
* later. This is neccessary if fncUndoMove() is
* unable to undo a move.
* fncPopBoard
* This is called at the end of each level in the
* recursion. It can be used to restore the board.
* fncGetMoves
* Return an array of pointers to the possible
* moves for the given player. Also return the
* number of moves in this array through the pointer
* to the integer. Return NULL if there are no
* possible moves to do.
* The functions in this file don't know what a
* move is, but only what pointers to moves are.
* Therefore, this is an array of pointers to moves,
* not an array of moves.
* It is important that this array lasts through all
* sublevels of the recursion from where it is
* requested. You will probably use fncPushBoard()
* and fncPopBoard() to maintain a list of arrays
* to choose from.
* fncDoMove
* This is also called at the start of each recursion
* level.
* Update the board with the given move. Also, return
* the player that is to move next. For some games
* this may be the player that just moved.
* fncUndoMove
* Undo the given move. The move to undo is always the
* move most recently done. If undoing is hard, you can
* leave it to fncPopBoard() instead, since they
* are both called at the end of a recursion level.
* fncUndoMove() is called before fncPopBoard().
* fncEvalBoard
* function evaluating the current state of the
* board for the player supplied. This function should
* return a positive value if the player is in the
* lead, or a negative value if the opposite player
* is in the lead. A higher (absolute) value indicates
* a better lead.
* player the player to evaluate.
* maxPly max recursion depth.
*
* RETURNS Pointer to the best move to make, or NULL if no move
* available. For some games NULL means game over, for other
* games, it just means that it's the other player's turn.
* You should check the state of the game between each call
* to this function.
*
* Note that the pointer returned points into the array
* returned by fncGetMoves(), so you shouldn't overwrite
* this array before using the move.
*
* DESCRIPTION This is the front end to the minimax algorithm.
* It sets it all up, and uses recMiniMax() to check each
* possible move.
*
*/
PMove miniMax(
void (*fncPushBoard)(void),
void (*fncPopBoard)(void),
PMove *(*fncGetMoves)(Player, int *),
Player (*fncDoMove)(Player, PMove),
void (*fncUndoMove)(Player, PMove),
Score (*fncEvalBoard)(Player),
Player player,
int maxPly
)
{
int q; /* a counter variable */
PMove *move; /* array of pointerts to possible moves to make */
int numMoves; /* number of moves in this array */
PMove bestMove; /* the best move so far */
Score v; /* value for a single move */
Score bestValue; /* the value of the best move so far */
/*
* Set up the callback functions for the recursive routine.
*/
pushBoard = fncPushBoard;
popBoard = fncPopBoard;
getMoves = fncGetMoves;
doMove = fncDoMove;
undoMove = fncUndoMove;
evalBoard = fncEvalBoard;
/*
* Now loop through all possible moves for the given player,
* and find the one with the highest score according to the
* minimax algorithm. If there are no possible moves left,
* we return NULL.
*/
bestMove = NULL;
move = getMoves(player, &numMoves);
bestValue = -INF_SCORE;
for (q = 0; q < numMoves; q++) {
v = recMiniMax(player, *move, maxPly - 1);
#ifdef RANDOM_CHOICE
/*
* If this value equals the previous best value, we choose
* randomly whether we should use this one instead.
*/
if (v > bestValue || (v == bestValue && (rand() & 1))) {
#else
if (v >= bestValue) {
#endif
bestValue = v;
bestMove = *move;
}
++move;
}
return bestMove;
}
|
