1
/* This file is a part of gtkboard, a board games system.
2
Copyright (C) 2003, Arvind Narayanan <arvindn@users.sourceforge.net>
4
This program is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License as published by
6
the Free Software Foundation; either version 2 of the License, or
7
(at your option) any later version.
9
This program is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
GNU General Public License for more details.
14
You should have received a copy of the GNU General Public License
15
along with this program; if not, write to the Free Software
16
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA
30
extern int time_per_move;
32
extern gboolean engine_stop_search;
34
static gboolean ab_tree_exhausted = FALSE;
36
static int ab_leaf_cnt; // how many leaves were eval'd
38
extern int hash_get_eval (byte *, int, int, int, float *);
39
extern void hash_print_stats ();
40
extern void hash_insert (byte *, int, int, int, float, byte *move);
41
extern void hash_clear ();
42
extern void hash_insert_move (byte *, int, int, byte *);
43
extern byte * hash_get_move (byte *, int, int);
45
extern gboolean opt_verbose;
47
// FIXME: move this to ui.c
48
gboolean game_use_hash = TRUE;
50
// FIXME: this function is too complicated
51
float ab_with_tt (Pos *pos, int player, int level,
52
float alpha, float beta, byte *best_movep)
53
/* level is the number of ply to search */
56
float val, cacheval, best= 0, retval;
57
gboolean first = TRUE;
59
byte best_move [4096];
61
gboolean hashed_move = TRUE;
62
float local_alpha = -1e+16, local_beta = 1e+16;
67
if (engine_stop_search) { ab_tree_exhausted = FALSE; return 0; }
69
movlist = game_movegen (pos);
70
if (movlist[0] == -2) /* we have no move left */
73
game_eval (pos, to_play, &val);
75
hash_insert (pos->board, board_wid * board_heit, pos->num_moves, level, val,
81
if (game_use_hash && level > 0)
82
move = hash_get_move (pos->board, board_wid * board_heit, pos->num_moves);
88
// origmove is the owning pointer and move is the aliasing pointer
89
else orig_move = move = movdup (move);
91
newpos.board = (char *) malloc (board_wid * board_heit);
92
assert (newpos.board);
95
newpos.state = (void *) malloc (game_state_size);
96
assert (newpos.state);
101
if (!orig_move || hashed_move || !movcmp_literal (orig_move, move))
103
ResultType result = RESULT_NOTYET;
104
memcpy (newpos.board, pos->board, board_wid * board_heit);
107
void *newstate = game_newstate (pos, move);
108
memcpy (newpos.state, newstate, game_state_size);
110
move_apply (newpos.board, move);
111
newpos.num_moves = pos->num_moves + 1;
112
newpos.search_depth = pos->search_depth + 1;
113
newpos.player = pos->player == WHITE ? BLACK : WHITE;
115
if (game_use_hash && level > 0)
116
retval = hash_get_eval (newpos.board, board_wid * board_heit,
117
newpos.num_moves, level-1, &cacheval);
118
if (retval && fabs (cacheval) < GAME_EVAL_INFTY) val = cacheval;
119
else result = game_eval (&newpos, to_play == WHITE ? BLACK : WHITE, &val);
123
ab_tree_exhausted = FALSE;
124
/* if (game_use_hash)
125
hash_insert (newpos.board, board_wid * board_heit,
126
pos->num_moves, level, val, NULL);
131
if (fabs (val) >= GAME_EVAL_INFTY)
133
else if (result == RESULT_WHITE || result == RESULT_BLACK)
135
else if (result == RESULT_TIE)
139
val = ab_with_tt (&newpos, player == WHITE ? BLACK : WHITE,
140
level-1, alpha, beta, best_move);
143
if((player == WHITE && val > local_alpha)
144
|| (player == BLACK && val < local_beta))
146
if (best_movep) movcpy (best_movep, move);
147
if (player == WHITE) local_alpha = val; else local_beta = val;
150
if((player == WHITE && val > alpha))
152
if ((player == BLACK && val < beta))
154
if (alpha >= beta || alpha >= GAME_EVAL_INFTY || beta <= -GAME_EVAL_INFTY)
160
move = movlist_next (move);
163
while (move[0] != -2);
165
if (game_stateful) free (newpos.state);
169
hash_insert (pos->board, board_wid * board_heit, pos->num_moves, level,
170
player == WHITE ? alpha : beta, best_movep);
171
return player == WHITE ? alpha : beta;
175
// TODO: this is currently unused, and must be merged with the previous function
176
float ab_with_tt_incr (Pos *pos, int player, int level,
177
float eval, float alpha, float beta, byte *best_movep)
178
/* level is the number of ply to search */
180
int to_play = player;
181
float val, cacheval, best= 0, retval;
183
byte *movlist, *move;
184
byte best_move [4096];
185
void *oldstate = NULL; // use the recursion to implement stack of states
187
if (engine_stop_search)
189
ab_tree_exhausted = FALSE;
194
oldstate = (void *) malloc (game_state_size);
197
movlist = game_movegen (pos);
198
if (movlist[0] == -2) /* we have no move left */
201
game_eval (pos, to_play, &val);
207
float neweval = 0, incr_eval;
209
result = game_eval_incr (pos, to_play, move, &incr_eval);
210
neweval = eval + incr_eval;
215
ab_tree_exhausted = FALSE;
218
else if (fabs (incr_eval) >= GAME_EVAL_INFTY
219
|| result != RESULT_NOTYET)
220
// one side has won; search no more
223
val = neweval * (1 + level); // the sooner the better
228
byte *movinv = mov_getinv (pos->board, move);
229
move_apply (pos->board, move);
232
void *newstate = game_newstate (pos, move);
233
memcpy (oldstate, pos->state, game_state_size);
234
memcpy (pos->state, newstate, game_state_size);
237
pos->player = pos->player == WHITE ? BLACK : WHITE;
238
val = 0; // stop compiler warning
241
retval = hash_get_eval (pos->board, board_wid * board_heit,
242
pos->num_moves, level, &cacheval);
243
if (retval && cacheval < GAME_EVAL_INFTY)
244
{ val = cacheval; found = 1; }
247
val = ab_with_tt_incr
248
(pos, player == WHITE ? BLACK : WHITE,
249
level-1, neweval, alpha, beta, best_move);
251
hash_insert (pos->board, board_wid * board_heit,
252
pos->num_moves, level, val, NULL);
253
move_apply (pos->board, movinv);
255
memcpy (pos->state, oldstate, game_state_size);
257
pos->player = pos->player == WHITE ? BLACK : WHITE;
261
if (best_movep) movcpy (best_movep, move);
264
if ((player == WHITE && val > alpha) || (player == BLACK && val < beta))
266
if (best_movep) movcpy (best_movep, move);
267
if (player == WHITE) alpha = val; else beta = val;
271
move = movlist_next (move);
273
while (move[0] != -2);
277
return player == WHITE ? alpha : beta;
281
byte * ab_dfid (Pos *pos, int player)
283
static byte best_move[4096];
284
byte local_best_move[4096];
286
float val = 0, eval = 0, oldval = 0;
287
static GTimer *timer = NULL;
288
gboolean found = FALSE;
290
engine_stop_search = 0;
291
if (!game_movegen || !game_eval)
295
move_list = game_movegen (pos);
296
if (move_list[0] == -2)
299
if (opt_verbose) printf ("No move\n");
302
if (movlist_next (move_list)[0] == -2)
304
movcpy (best_move, move_list);
305
if (opt_verbose) printf ("Only one legal move\n");
309
if (!timer) timer = g_timer_new ();
310
g_timer_start (timer);
312
for (ply = 0; !engine_stop_search; ply++)
315
ab_tree_exhausted = TRUE;
316
pos->search_depth = 0;
317
val = ab_with_tt (pos, player, ply, -1e+16, 1e+16, local_best_move);
318
if (!engine_stop_search)
320
movcpy (best_move, local_best_move);
324
if (ab_tree_exhausted)
327
printf ("Searched whole tree. Moves=%d;\t Ply=%d\n",
328
pos->num_moves, ply);
333
if (fabs (val) >= GAME_EVAL_INFTY)
336
printf ("Solved the game. %s won. Moves=%d;\t Ply=%d\n",
337
val > 0 ? "White" : "Black", pos->num_moves, ply);
345
time_taken = g_timer_elapsed (timer, µ_sec);
346
time_taken += micro_sec / 1000000.0;
347
if (time_taken * 1000 > time_per_move / 2)
363
printf ("ab_dfid(): leaves=%d \tply=%d\teval=%.1f\n",
364
ab_leaf_cnt, ply, oldval);
365
printf ("ab_dfid(): move= ");
366
move_fwrite (best_move, stdout);
368
return found ? best_move : NULL;
added
removed
.pc/debian-changes-0.11pre0-12/src/ab.c
