From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter14/connect4.cxx | 225 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 chapter14/connect4.cxx (limited to 'chapter14/connect4.cxx') diff --git a/chapter14/connect4.cxx b/chapter14/connect4.cxx new file mode 100644 index 0000000..53d87ba --- /dev/null +++ b/chapter14/connect4.cxx @@ -0,0 +1,225 @@ +// File: connect4.cxx + +#include // Provides fill_n +#include // Provides isdigit +#include // Provides setw +#include // Provides cin, cout +#include // Provides queue class +#include // 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& 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; + } +} -- cgit v1.2.3