1 /* Hexxagon board game.
2 * Copyright (C) 2001 Erik Jonsson.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
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.
13 *
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-1307, USA.
17 *
18 * Email hexxagon@nesqi.se
19 *
20 */
21
22
23 #include "board.h"
24 #include "move.h"
25
26 #include <stdlib.h>
27 #include <string.h>
28
29 #include <ctime>
30 #include <iostream>
31 #include <algorithm>
32
33 using namespace libhexx;
34
35 char global_count;
alphaBeta(const Board & board,const LookUp & lookup,bool turn,int level,int alpha,int beta,bool (* callback)())36 int alphaBeta(const Board &board, const LookUp &lookup, bool turn, int level, int alpha, int beta, bool (*callback)())
37 {
38 if(!level)
39 return board.evaluate(lookup, turn);
40
41 std::vector<Move> moves;
42 if(!board.generateMoveList(moves, lookup))
43 {
44 if(board.isGameOver(lookup))
45 return board.evaluate(lookup, turn);
46
47 Board newboard = board;
48 newboard.invertColors();
49 return -alphaBeta(newboard, lookup, turn, level - 1, -beta, -alpha, callback);
50 }
51
52 global_count++;
53
54 if(!global_count && callback)
55 {
56 /* Terminate? */
57 if(!callback())
58 return SCR_BREAK;
59 }
60
61 int best = -SCR_INFINITY;
62 for(std::vector<Move>::iterator i = moves.begin(); i != moves.end() && (best < beta); i++)
63 {
64 if(best > alpha)
65 alpha = best;
66
67 Board newboard = Board(board);
68 newboard.applyMove(*i, lookup);
69 int value = -alphaBeta(newboard, lookup, !turn, level - 1, -beta, -alpha, callback);
70
71 if(value == SCR_BREAK)
72 return SCR_BREAK;
73
74 if(value > best)
75 best = value;
76 }
77
78 return best;
79 }
80
81
scoreMoves(std::vector<Move> & moves,const Board board,const LookUp & lookUp,int depth,bool (* callback)(),int maxtime)82 bool libhexx::scoreMoves(std::vector<Move> &moves, const Board board, const LookUp& lookUp, int depth, bool (*callback)(), int maxtime)
83 {
84 time_t t = time(NULL);
85
86 for(int i = 1; (i < depth) && (time(NULL) - t <= maxtime); i++)
87 {
88 int best = -SCR_INFINITY;
89 int alpha = -SCR_INFINITY;
90 int beta = SCR_INFINITY;
91
92 for(std::vector<Move>::iterator j = moves.begin(); (j != moves.end()) && (time(NULL) - t <= maxtime) && (best < beta); j++)
93 {
94 if(best > alpha)
95 alpha = best;
96
97 Board newboard = Board(board);
98 newboard.applyMove(*j, lookUp);
99 int value = -alphaBeta(newboard, lookUp, false, i, -beta, -alpha, callback);
100
101 if(value == SCR_BREAK)
102 return false;
103
104 j->score = value;
105
106 if(value > best)
107 best = value;
108 }
109
110 stable_sort(moves.rbegin(), moves.rend());
111 }
112
113 return true;
114 }
115