blob: e9c45ec8d500a172310839998a51b43779e69c0c (
plain) (
blame)
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
|
// File: game.cxx
#include <cassert> // Provides assert
#include <climits> // Provides INT_MAX and INT_MIN
#include <iostream> // Provides cin, cout
#include <queue> // Provides queue<string>
#include <string> // Provides string
#include "game.h" // Provides definition of game class
using namespace std;
namespace main_savitch_14
{
//*************************************************************************
// STATIC MEMBER CONSTANTS
const int game::SEARCH_LEVELS;
//*************************************************************************
// PUBLIC MEMBER FUNCTIONS
game::who game::play( )
// The play function should not be overridden. It plays one round of the
// game, with the human player moving first and the computer second.
// The return value is the winner of the game (or NEUTRAL for a tie).
{
restart( );
while (!is_game_over( ))
{
display_status( );
if (last_mover( ) == COMPUTER)
make_human_move( );
else
make_computer_move( );
}
display_status( );
return winning( );
}
//*************************************************************************
// OPTIONAL VIRTUAL FUNCTIONS (overriding these functions is optional)
void game::display_message(const string& message) const
{
cout << message;
}
string game::get_user_move( ) const
{
string answer;
display_message("Your move, please: ");
getline(cin, answer);
return answer;
}
game::who game::winning( ) const
{
// Positive evaluation is good for last_mover( ).
int value = evaluate( );
if (value > 0)
return last_mover( );
else if (value < 0)
return next_mover( );
else
return NEUTRAL;
}
//*************************************************************************
// PRIVATE FUNCTIONS (these are the same for every game)
int game::eval_with_lookahead(int look_ahead, int beat_this)
// Evaluate a board position with lookahead.
// --int look_aheads: How deep the lookahead should go to evaluate the move.
// --int beat_this: Value of another move that we're considering. If the
// current board position can't beat this, then cut it short.
// The return value is large if the position is good for the player who just
// moved.
{
queue<string> moves; // All possible opponent moves
int value; // Value of a board position after opponent moves
int best_value; // Evaluation of best opponent move
game* future; // Pointer to a future version of this game
// Base case:
if (look_ahead == 0 || is_game_over( ))
return evaluate( );
// Recursive case:
// The level is above 0, so try all possible opponent moves. Keep the
// value of the best of these moves from the opponent's perspective.
compute_moves(moves);
assert(!moves.empty( ));
best_value = INT_MIN;
while (!moves.empty( ))
{
future = clone( );
future->make_move(moves.front( ));
value = future->eval_with_lookahead(look_ahead-1, best_value);
delete future;
if (value > best_value)
{
if (-value <= beat_this)
return INT_MIN + 1; // Alpha-beta pruning
best_value = value;
}
moves.pop( );
}
// The value was calculated from the opponent's perspective.
// The answer we return should be from player's perspective, so multiply times -1:
return -best_value;
}
void game::make_computer_move( )
{
queue<string> moves;
int value;
int best_value;
string best_move;
game* future;
// Compute all legal moves that the computer could make.
compute_moves(moves);
assert(!moves.empty( ));
// Evaluate each possible legal move, saving the index of the best
// in best_index and saving its value in best_value.
best_value = INT_MIN;
while (!moves.empty( ))
{
future = clone( );
future->make_move(moves.front( ));
value = future->eval_with_lookahead(SEARCH_LEVELS, best_value);
delete future;
if (value >= best_value)
{
best_value = value;
best_move = moves.front( );
}
moves.pop( );
}
// Make the best move.
make_move(best_move);
}
void game::make_human_move( )
{
string move;
move = get_user_move( );
while (!is_legal(move))
{
display_message("Illegal move.\n");
move = get_user_move( );
}
make_move(move);
}
}
|