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
|
// File: connect4.cxx
#include <algorithm> // Provides fill_n
#include <cctype> // Provides isdigit
#include <iomanip> // Provides setw
#include <iostream> // Provides cin, cout
#include <queue> // Provides queue<string> class
#include <string> // Provides string
#include "connect4.h" // Provides definition of connect4 class (derived from game)
using namespace std;
namespace main_savitch_14
{
// Public static member constants. These were defined in connect.h:
const int connect4::ROWS;
const int connect4::COLUMNS;
// Private static member constants, defined here. The COLUMN_DISPLAY_WIDTH
// is the number of characters to use in the display( ) function for each
// column in the output display. The FOUR_VALUE is the value returned by
// the value function when it finds four-in-a-row. For the current
// implementation of evaluate to work, the FOUR_VALUE should be at least
// 24 times as large as the total number of spots on the board.
// MOVE_STRINGS is an array of all possible moves, which must be strings
// corresponding to the integers 0 through COLUMNS-1.
const int connect4::COLUMN_DISPLAY_WIDTH = 3;
const int connect4::FOUR_VALUE = 24*ROWS*COLUMNS;
const string connect4::MOVE_STRINGS[COLUMNS] = {"0","1","2","3","4","5","6"};
connect4::connect4( )
: game( )
{
restart( );
}
game* connect4::clone( ) const
{
// Return a pointer to a copy of myself, made with the automatic copy
// constructor. If I used dynamic memory, I would have to alter this
// copy so that it used its own dynamic memory instead of mine. But
// the connect4 class does not use any dynamic memory, so this is ok:
return new connect4(*this);
}
void connect4::compute_moves(queue<string>& moves) const
{
int i;
for (i = 0; i < COLUMNS; i++)
{
if (many_used[i] < ROWS)
moves.push(MOVE_STRINGS[i]);
}
}
void connect4::display_status( ) const
{
int row, column;
cout << "\nCurrent game status\n(HUMAN = # and COMPUTER = @):\n";
if (moves_completed( ) != 0)
cout << "Most recent move in column " << most_recent_column << endl;
for (row = ROWS-1; row >= 0; --row)
{
for (column = 0; column < COLUMNS; ++column)
{
switch (data[row][column])
{
case HUMAN: cout << setw(COLUMN_DISPLAY_WIDTH) << "#"; break;
case COMPUTER: cout << setw(COLUMN_DISPLAY_WIDTH) << "@"; break;
case NEUTRAL: cout << setw(COLUMN_DISPLAY_WIDTH) << "."; break;
}
}
cout << endl;
}
for (column = 0; column < COLUMNS; ++column)
cout << setw(COLUMN_DISPLAY_WIDTH) << column;
if (is_game_over( ))
cout << "\nGame over." << endl;
else if (last_mover( ) == COMPUTER)
cout << "\nHuman's turn to move (by typing a column number)" << endl;
else
cout << "\nComputer's turn to move (please wait)..." << endl;
}
int connect4::evaluate( ) const
{
// NOTE: Positive answer is good for the last_mover( ).
int row, column;
int answer = 0;
// For each possible starting spot, calculate the value of the spot for
// a potential four-in-a-row, heading down, left, and to the lower-left.
// Normally, this value is in the range [-3...+3], but if a
// four-in-a-row is found for the player, the result is FOUR_VALUE which
// is large enough to make the total answer larger than any evaluation
// that occurs with no four-in-a-row.
// Value moving down from each spot:
for (row = 3; row < ROWS; ++row)
for (column = 0; column < COLUMNS; ++column)
answer += value(row, column, -1, 0);
// Value moving left from each spot:
for (row = 0; row < ROWS; ++row)
for (column = 3; column < COLUMNS; ++column)
answer += value(row, column, 0, -1);
// Value heading diagonal (lower-left) from each spot:
for (row = 3; row < ROWS; ++row)
for (column = 3; column < COLUMNS; ++column)
answer += value(row, column, -1, -1);
// Value heading diagonal (lower-right) from each spot:
for (row = 3; row < ROWS; ++row)
for (column = 0; column <= COLUMNS-4; ++column)
answer += value(row, column, -1, +1);
return (last_mover( ) == COMPUTER) ? answer : -answer;
}
bool connect4::is_game_over( ) const
{
int row, column;
int i;
// Two simple cases:
if (moves_completed( ) == 0)
return false;
if (moves_completed( ) == ROWS*COLUMNS)
return true;
// Check whether most recent move is part of a four-in-a-row
// for the player who just moved.
column = most_recent_column;
row = many_used[column] - 1;
// Vertical:
if (abs(value(row, column, -1, 0)) == FOUR_VALUE) return true;
for (i = 0; i <= 3; i++)
{
// Diagonal to the upper-right:
if (abs(value(row-i, column-i, 1, 1)) == FOUR_VALUE) return true;
// Diagonal to the lower-right:
if (abs(value(row-i, column+i, 1, -1)) == FOUR_VALUE) return true;
// Horizontal:
if (abs(value(row, column-i, 0, 1)) == FOUR_VALUE) return true;
}
return false;
}
bool connect4::is_legal(const string& move) const
{
int column = atoi(move.c_str( ));
return
(!is_game_over( ))
&&
(move.length( ) > 0)
&&
(isdigit(move[0]))
&&
(column < COLUMNS)
&&
(many_used[column] < ROWS);
}
void connect4::make_move(const string& move)
{
int row, column;
assert(is_legal(move));
column = atoi(move.c_str( ));
row = many_used[column]++;
data[row][column] = next_mover( );
most_recent_column = column;
game::make_move(move);
}
void connect4::restart( )
{
fill_n(&(data[0][0]), ROWS*COLUMNS, NEUTRAL);
fill_n(&(many_used[0]), COLUMNS, 0);
game::restart( );
}
int connect4::value(int row, int column, int delta_r, int delta_c) const
{
// NOTE: Positive return value is good for the computer.
int i;
int end_row = row + 3*delta_r;
int end_column = column + 3*delta_c;
int computer_count= 0;
int opponent_count = 0;
if (
(row < 0) || (column < 0) || (end_row < 0) || (end_column < 0)
||
(row >= ROWS) || (end_row >= ROWS)
||
(column >= COLUMNS) || (end_column >= COLUMNS)
)
return 0;
for (i = 1; i <= 4; ++i)
{
if (data[row][column] == COMPUTER)
++computer_count;
else if (data[row][column] != NEUTRAL)
++opponent_count;
row += delta_r;
column += delta_c;
}
if ((computer_count > 0) && (opponent_count > 0))
return 0; // Neither player can get four-in-a-row here.
else if (computer_count == 4)
return FOUR_VALUE;
else if (opponent_count == 4)
return -FOUR_VALUE;
else
return computer_count - opponent_count;
}
}
|