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/Makefile | 14 +++ chapter14/blob.cxx | 32 +++++++ chapter14/clocks.cxx | 137 +++++++++++++++++++++++++++ chapter14/clocks.h | 102 ++++++++++++++++++++ chapter14/connect4.cxx | 225 ++++++++++++++++++++++++++++++++++++++++++++ chapter14/connect4.h | 58 ++++++++++++ chapter14/game.cxx | 167 ++++++++++++++++++++++++++++++++ chapter14/game.h | 86 +++++++++++++++++ chapter14/organism.cxx | 126 +++++++++++++++++++++++++ chapter14/organism.h | 193 +++++++++++++++++++++++++++++++++++++ chapter14/play_connect4.cxx | 30 ++++++ chapter14/pondlife.cxx | 126 +++++++++++++++++++++++++ 12 files changed, 1296 insertions(+) create mode 100644 chapter14/Makefile create mode 100644 chapter14/blob.cxx create mode 100644 chapter14/clocks.cxx create mode 100644 chapter14/clocks.h create mode 100644 chapter14/connect4.cxx create mode 100644 chapter14/connect4.h create mode 100644 chapter14/game.cxx create mode 100644 chapter14/game.h create mode 100644 chapter14/organism.cxx create mode 100644 chapter14/organism.h create mode 100644 chapter14/play_connect4.cxx create mode 100644 chapter14/pondlife.cxx (limited to 'chapter14') diff --git a/chapter14/Makefile b/chapter14/Makefile new file mode 100644 index 0000000..fc66f53 --- /dev/null +++ b/chapter14/Makefile @@ -0,0 +1,14 @@ +play_connect4.exe: connect4.h play_connect4.cxx game.o connect4.o + g++ -Wall -gstabs play_connect4.cxx game.o connect4.o -o play_connect4 + +play_othello.exe: othello.h play_othello.cxx game.o othello.o + g++ -Wall -gstabs play_othello.cxx game.o othello.o -o othello + +game.o: game.h game.cxx + g++ -Wall -gstabs -c game.cxx + +connect4.o: connect4.h game.h connect4.cxx + g++ -Wall -gstabs -c connect4.cxx + +othello.o: othello.h game.h othello.cxx + g++ -Wall -gstabs -c othello.cxx diff --git a/chapter14/blob.cxx b/chapter14/blob.cxx new file mode 100644 index 0000000..e2c09a3 --- /dev/null +++ b/chapter14/blob.cxx @@ -0,0 +1,32 @@ +// FILE: blob.cxx +// This small demonstration shows how the organism class is used. +#include // Provides EXIT_SUCCESS +#include // Provides cout and cin +#include "organism.h" // Provides the organism class + +int main( ) +{ + main_savitch_14::organism blob(20.0, 100000.0); + int week; + + // Untroubled by conscience or intellect, the Blob grows for three weeks. + for (week = 1; week <= 3; ++week) + { + blob.simulate_week( ); + cout << "Week " << week << ":" << " the Blob is "; + cout << blob.get_size( ) << " ounces." << endl; + } + + // Steve McQueen reverses the growth rate to -80000 ounces per week. + blob.assign_rate(-80000.0); + while (blob.is_alive( )) + { + blob.simulate_week( ); + cout << "Week " << week << ":" << " the Blob is "; + cout << blob.get_size( ) << " ounces." << endl; + ++week; + } + + cout << "The Blob (or its son) shall return." << endl; + return EXIT_SUCCESS; +} diff --git a/chapter14/clocks.cxx b/chapter14/clocks.cxx new file mode 100644 index 0000000..c3ed0ae --- /dev/null +++ b/chapter14/clocks.cxx @@ -0,0 +1,137 @@ +// FILE: clocks.cxx (part of the namespace main_savitch_14) +// CLASSES IMPLEMENTED: clock, cuckoo_clock, clock24 (see clock.h) +// INVARIANT for the clock ADT: +// 1. The current hour is stored in my_hour, using 12-hour notation. +// 2. The current minute is stored in my_minute. +// 3. If the time is from midnight to 11:59 am (inclusive), then +// my_morning is true; otherwise my_morning is false. + +#include +#include "clocks.h" + +namespace main_savitch_14 +{ + clock::clock( ) + { + my_hour = 12; + my_minute = 0; + my_morning = true; + } + + void clock::set_time(int hour, int minute, bool morning) + // Library facilities used: cassert + { + assert(1 <= hour); + assert(hour <= 12); + assert(0 <= minute); + assert(minute <= 59); + + my_hour = hour; + my_minute = minute; + my_morning = morning; + } + + void clock::advance(int minutes) + { + const int MINUTES_IN_DAY = 24*60; + const int MINUTES_IN_HOUR = 60; + + // Change the minutes so that 0 <= minutes < MINUTES_IN_DAY + if (minutes < 0) + minutes += MINUTES_IN_DAY * (1 - minutes/MINUTES_IN_DAY); + if (minutes >= MINUTES_IN_DAY) + minutes -= MINUTES_IN_DAY * (minutes/MINUTES_IN_DAY); + + // Advance the clock any full hours + while (minutes > 60) + { + minutes -= MINUTES_IN_HOUR; + my_hour++; + if (my_hour == 12) + my_morning = !my_morning; + if (my_hour == 13) + my_hour = 1; + } + + // Advance any remaining minutes + my_minute += minutes; + if (my_minute >= MINUTES_IN_HOUR) + { + my_minute -= MINUTES_IN_HOUR; + my_hour++; + if (my_hour == 12) + my_morning = !my_morning; + if (my_hour == 13) + my_hour = 1; + } + } + + int clock::get_hour( ) const + { + return my_hour; + } + + int clock::get_minute( ) const + { + return my_minute; + } + + bool clock::is_morning( ) const + { + return my_morning; + } + + bool cuckoo_clock::is_cuckooing( ) const + { + return (get_minute( ) == 0); + } + + bool operator <(const clock& c1, const clock& c2) + { + // Check whether one is morning and the other is not + if (c1.is_morning( ) && !c2.is_morning( )) + return true; + else if (c2.is_morning( ) && !c1.is_morning( )) + return false; + + // Check whether one is 12 o'clock and the other is not + else if ((c1.get_hour( ) == 12) && (c2.get_hour( ) != 12)) + return true; + else if ((c2.get_hour( ) == 12) && (c1.get_hour( ) != 12)) + return false; + + // Check whether the hours are different from each other + else if (c1.get_hour( ) < c2.get_hour( )) + return true; + else if (c2.get_hour( ) < c1.get_hour( )) + return false; + + // The hours are the same, so check the minutes + else if (c1.get_minute( ) < c2.get_minute( )) + return true; + else + return false; + } + + int clock24::get_hour( ) const + { + int ordinary_hour; + + ordinary_hour = clock::get_hour( ); + if (is_morning( )) + { + if (ordinary_hour == 12) + return 0; + else + return ordinary_hour; + } + else + { + if (ordinary_hour == 12) + return 12; + else + return ordinary_hour + 12; + } + } + +} diff --git a/chapter14/clocks.h b/chapter14/clocks.h new file mode 100644 index 0000000..f918983 --- /dev/null +++ b/chapter14/clocks.h @@ -0,0 +1,102 @@ +// FILE: clocks.h (part of namespace main_savitch_14) +// CLASSES PROVIDED: +// clock (keeps track of a single time value) +// cuckoo_clock (clock descendant with a cuckoo that makes noise on the hour) +// clock24 (clock descendant for time in 24-hour version) +// +// CONSTRUCTOR for the clock class: +// clock( ) +// Postcondition: The clock is set to 12:00 (midnight). +// +// MODIFICATION MEMBER FUNCTIONS for the clock class: +// void set_time(int hour, int minute, bool morning) +// Precondition: 1 <= hour <= 12, and 0 <= minute <= 59. +// Postcondition: The clock's time has been set to the given hour and +// minute (using usual 12-hour time notation). If the third parameter, +// morning, is true, then this time is from 12:00 midnight to 11:59am. +// Otherwise this time is from 12:00 noon to 11:59pm. +// +// void advance(int minutes) +// Postcondition: The clock has been moved forward by the indicated +// number of minutes. +// Note: A negative argument moves the clock backward. +// +// CONSTANT MEMBER FUNCTIONS for the clock class: +// int get_hour( ) const +// Postcondition: The value returned is the current hour using a 12-hour +// clock. +// +// int get_minute( ) const +// Postcondition: The value returned is the current minute on the clock. +// +// bool is_morning( ) const +// Postcondition: If the clock's time lies from 12:00 midnight to +// 11:59am (inclusive), the function returns true; otherwise it +// returns false. +// +// NONMEMBER FUNCTIONS for the clock class: +// bool operator <(const clock& c1, const clock& c2) +// Postcondition: Returns true if the time on c1 is earlier than the time +// on c2 over a usual day (starting at midnight); otherwise returns false. +// +// INHERITED MEMBER FUNCTIONS for the cuckoo_clock class: +// The cuckoo_clock inherits all public members from the clock class. +// +// ADDITIONAL CONSTANT MEMBER FUNCTION for the cuckoo_clock class: +// bool is_cuckooing( ) const; +// Postcondition: The return value is true if the current minute is zero +// (so that the cuckoo is making noise). +// +// INHERITED MEMBER FUNCTIONS for the clock24 class: +// The clock24 class inherits all public members from the clock class, +// except for get_hour, which is overriden (as described below): +// +// OVERRIDEN CONSTANT MEMBER FUNCTION for the clock24 class: +// int get_hour( ) const +// Postcondition: The value returned is the current hour using a 24-hour +// clock. +// +// VALUE SEMANTICS for the clock, cuckoo_clock, and clock24 classes: +// Assignments and the copy constructor may be used with any of +// these objects. + +#ifndef CLOCK_H +#define CLOCK_H + +namespace main_savitch_14 +{ + class clock + { + public: + // CONSTRUCTOR + clock( ); + // MODIFICATION FUNCTIONS + void set_time(int hour, int minute, bool morning); + void advance(int minutes); + // CONSTANT FUNCTIONS + int get_hour( ) const; + int get_minute( ) const; + bool is_morning( ) const; + private: + int my_hour; + int my_minute; + int my_morning; + }; + + class cuckoo_clock : public clock + { + public: + bool is_cuckooing( ) const; + }; + + class clock24 : public clock + { + public: + int get_hour( ) const; + }; + + // NONMEMBER FUNCTION for the clock class: + bool operator <(const clock& c1, const clock& c2); +} + +#endif 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; + } +} diff --git a/chapter14/connect4.h b/chapter14/connect4.h new file mode 100644 index 0000000..459f2f3 --- /dev/null +++ b/chapter14/connect4.h @@ -0,0 +1,58 @@ +// File: connect4.h (part of the namespace main_savitch_14) +#ifndef MAIN_SAVITCH_CONNECT4 +#define MAIN_SAVITCH_CONNECT4 +#include // Provides queue +#include // Provides string +#include "game.h" // Provides the game base class + +namespace main_savitch_14 +{ + class connect4 : public game + { + public: + // STATIC CONSTANTS + static const int ROWS = 6; + static const int COLUMNS = 7; + + // CONSTRUCTOR + connect4( ); + + protected: + // ******************************************************************* + // VIRTUAL FUNCTIONS (these are overridden from the game base class) + // ******************************************************************* + // Return a pointer to a copy of myself: + virtual game* clone( ) const; + // Compute all the moves that the next player can make: + virtual void compute_moves(std::queue& moves) const; + // Display the status of the current game: + virtual void display_status( ) const; + // Evaluate the current board position. + // NOTE: Positive values are good for the last_mover( ). + virtual int evaluate( ) const; + // Return true if the current game is finished: + virtual bool is_game_over( ) const; + // Return true if the given move is legal for the next player: + virtual bool is_legal(const std::string& move) const; + // Have the next player make a specified move: + virtual void make_move(const std::string& move); + // Restart the game from the beginning: + virtual void restart( ); + + private: + // HELPER FUNCTIONS + int value(int row, int column, int delta_r, int delta_c) const; + + // HELPER CONSTANTS. See connect4.cxx for their values. + static const int COLUMN_DISPLAY_WIDTH; + static const int FOUR_VALUE; + static const std::string MOVE_STRINGS[COLUMNS]; + + // MEMBER VARIABLES TO TRACK THE STATE OF THE GAME + who data[ROWS][COLUMNS]; + int many_used[COLUMNS]; + int most_recent_column; + }; +} + +#endif diff --git a/chapter14/game.cxx b/chapter14/game.cxx new file mode 100644 index 0000000..e9c45ec --- /dev/null +++ b/chapter14/game.cxx @@ -0,0 +1,167 @@ +// File: game.cxx + +#include // Provides assert +#include // Provides INT_MAX and INT_MIN +#include // Provides cin, cout +#include // Provides queue +#include // 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 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 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); + } + +} + + diff --git a/chapter14/game.h b/chapter14/game.h new file mode 100644 index 0000000..e1c27e8 --- /dev/null +++ b/chapter14/game.h @@ -0,0 +1,86 @@ +// File: game.h (part of the namespace main_savitch_14) + + +#ifndef MAIN_SAVITCH_GAME +#define MAIN_SAVITCH_GAME +#include // Provides queue +#include // Provides string + +namespace main_savitch_14 +{ + class game + { + public: + // ENUM TYPE + enum who { HUMAN, NEUTRAL, COMPUTER }; // Possible game outcomes + + // CONSTRUCTOR and DESTRUCTOR + game( ) { move_number = 0; } + virtual ~game( ) { } + + // PUBLIC MEMBER FUNCTIONS + // The play function should not be overridden. It plays one game, + // with the human player moving first and the computer second. + // The computer uses an alpha-beta look ahead algorithm to select its + // moves. The return value is the winner of the game (or NEUTRAL for + // a tie). + who play( ); + + protected: + // ******************************************************************* + // OPTIONAL VIRTUAL FUNCTIONS (overriding these is optional) + // ******************************************************************* + virtual void display_message(const std::string& message) const; + virtual std::string get_user_move( ) const; + virtual who last_mover( ) const + { return (move_number % 2 == 1 ? HUMAN : COMPUTER); } + virtual int moves_completed( ) const { return move_number; } + virtual who next_mover( ) const + { return (move_number % 2 == 0 ? HUMAN : COMPUTER); } + virtual who opposite(who player) const + { return (player == HUMAN) ? COMPUTER : HUMAN; } + virtual who winning( ) const; + + // ******************************************************************* + // VIRTUAL FUNCTIONS THAT MUST BE OVERRIDDEND: + // The overriding function should call the original when it finishes. + // ******************************************************************* + // Have the next player make a specified move: + virtual void make_move(const std::string& move) { ++move_number; } + // Restart the game from the beginning: + virtual void restart( ) { move_number = 0; } + + // ******************************************************************* + // PURE VIRTUAL FUNCTIONS + // ******************************************************************* + // (these must be provided for each derived class) + // Return a pointer to a copy of myself: + virtual game* clone( ) const = 0; + // Compute all the moves that the next player can make: + virtual void compute_moves(std::queue& moves) const = 0; + // Display the status of the current game: + virtual void display_status( ) const = 0; + // Evaluate a board position: + // NOTE: positive values are good for the player who most recently moved + // (positive values are good for last_mover). + virtual int evaluate( ) const = 0; + // Return true if the current game is finished: + virtual bool is_game_over( ) const = 0; + // Return true if the given move is legal for the next player: + virtual bool is_legal(const std::string& move) const = 0; + + private: + // MEMBER VARIABLES + int move_number; // Number of moves made so far + + // STATIC MEMBER CONSTANT + static const int SEARCH_LEVELS = 4; // Levels for look-ahead evaluation + + // PRIVATE FUNCTIONS (these are the same for every game) + int eval_with_lookahead(int look_ahead, int beat_this); + void make_computer_move( ); + void make_human_move( ); + }; +} + +#endif diff --git a/chapter14/organism.cxx b/chapter14/organism.cxx new file mode 100644 index 0000000..3a544d0 --- /dev/null +++ b/chapter14/organism.cxx @@ -0,0 +1,126 @@ +// FILE: organism.cxx +// CLASSES IMPLEMENTED: +// organism, plant, animal, herbivore (see organism.h for documentation) +// +// INVARIANT for the organism class: +// 1. The member variable size contains the organism's size, in ounces. +// 2. The member variable rate contains the organism's growth rate, in +// ounces per week. +// +// INVARIANT for the animal class: +// 1. The member variable need_each_week contains the organism's food +// requirement, in ounces per week. +// 2. The member variable eaten_this_week contains the number of ounces of +// food eaten by the organism in the current week. +// +// The plant and herbivore classes have no extra member variables, so there +// is no need for an invariant. + +#include // Provides assert +#include "organism.h" + +namespace main_savitch_14 +{ + organism::organism(double init_size, double init_rate) + { + if (init_size == 0) + assert(init_rate == 0); + else + assert(init_size >= 0); + + size = init_size; + rate = init_rate; + } + + void organism::alter_size(double amount) + { + size += amount; + if (size <= 0) + death( ); + } + + void organism::death( ) + { + size = rate = 0; + } + + plant::plant(double init_size, double init_rate) + : organism(init_size, init_rate) + { + // All work is done by the organism constructor + } + + void plant::nibbled_on(double amount) + // Library functions used: cassert + { + assert(amount >= 0); + assert(amount <= get_size( )); + alter_size(-amount); + } + + animal::animal(double init_size, double init_rate, double init_need) + : organism(init_size, init_rate) + // Library facilities used: cassert + { + assert(0 <= init_need); + need_each_week = init_need; + eaten_this_week = 0; + } + + void animal::assign_need(double new_need) + // Library facilities used: cassert + { + assert(new_need >= 0); + need_each_week = new_need; + } + + void animal::eat(double amount) + // Library facilities used: cassert + { + assert(amount >= 0); + eaten_this_week += amount; + } + + void animal::simulate_week( ) + { + organism::simulate_week( ); + if (eaten_this_week < need_each_week) + death( ); + eaten_this_week = 0; + } + + double animal::still_need( ) const + { + if (eaten_this_week >= need_each_week) + return 0; + else + return need_each_week - eaten_this_week; + } + + herbivore::herbivore(double init_size, double init_rate, double init_need) + : animal(init_size, init_rate, init_need) + { + // All work is done by the animal constructor + } + + void herbivore::nibble(plant& meal) + { + const double PORTION = 0.5; // Eat no more than this portion of plant + const double MAX_FRACTION = 0.1; // Eat no more than this fraction of weekly need + double amount; // How many ounces of the plant will be eaten + + // Set amount to some portion of the plant, but no more than a given + // maximum fraction of the total weekly need, and no more than what the + // herbivore still needs to eat this week. + amount = PORTION * meal.get_size( ); + if (amount > MAX_FRACTION * total_need( )) + amount = MAX_FRACTION * total_need( ); + if (amount > still_need( )) + amount = still_need( ); + + // Eat the plant + eat(amount); + meal.nibbled_on(amount); + } + +} diff --git a/chapter14/organism.h b/chapter14/organism.h new file mode 100644 index 0000000..e551056 --- /dev/null +++ b/chapter14/organism.h @@ -0,0 +1,193 @@ +// FILE: organism.h (part of the namespace main_savitch_14) +// CLASSES PROVIDED: organism, plant, animal, herbivore +// +// +// DOCUMENTATION for the organism class: +// The organism class can simulate any growing organism, such as a plant or +// animal. +// +// CONSTRUCTOR for the organism class: +// organism(double init_size = 1, double init_rate = 0) +// Precondition: init_size >= 0. Also, if init_size = 0, then init_rate is +// also zero. +// Postcondition: The organism being simulated has been initialized. The +// value returned from get_size( ) is now init_size (measured in ounces), +// and the value returned from get_rate( ) is now init_rate (measured in +// ounces per week). +// +// MODIFICATION MEMBER FUNCTIONS for the organism class: +// void simulate_week( ) +// Postcondition: The size of the organism has been changed by its current +// growth rate. If the new size is less than zero, then the actual size is +// set to zero rather than to a negative value, and the growth rate is also +// set to zero. +// +// void assign_rate(double new_rate) +// Postcondition: The organism's growth rate has been changed to new_rate +// (measured in ounces per week). +// +// void alter_size(double amount) +// Postcondition: The given amount (in ounces) has been added to the +// organism's current size. If this results in a new size less than zero, +// then the actual size is set to zero rather than to a negative value, and +// the growth rate is also set to zero. +// +// void death( ) +// Postcondition: The organism's current size and growth rate have been +// set to zero. +// +// CONSTANT MEMBER FUNCTIONS for the organism class: +// double get_size( ) const +// Postcondition: The value returned is the organism's current size +// (in ounces). +// +// double get_rate( ) const +// Postcondition: The value returned is the organism's current growth rate +// (in oz/week). +// +// bool is_alive( ) const +// Postcondition: If the current size is greater than zero, then the return +// value is true; otherwise the return value is false. +// +// +// DOCUMENTATION for the plant class: +// plant is a derived class of the organism class. All the organism public +// member functions are inherited by a plant. In addition, a plant has +// these extra member functions: +// +// CONSTRUCTOR for the plant class: +// plant(double init_size=0, double init_rate=0) +// Same as the organism constructor. +// +// MODIFICATION MEMBER FUNCTIONS for the plant class: +// void nibbled_on(double amount) +// Precondition: 0 <= amount <= get_size( ). +// Postcondition: The size of the plant has been reduced by amount. +// If this reduces the size to zero, then death is activated. +// +// +// DOCUMENTATION for the animal class: +// animal is a derived class of the organism class. All the organism public +// member functions are inherited by an animal. In addition, an animal has +// these extra member functions: +// +// CONSTRUCTOR for the animal class: +// animal(double init_size=0, double init_rate=0, double init_need=0) +// Precondition: init_size >= 0, and init_need >= 0. Also, if +// init_size = 0, then init_rate is also zero. +// Postcondition: The organism being simulated has been initialized. The +// value returned from get_size( ) is now init_size (measured in ounces), +// the value returned from get_rate( ) is now init_rate (measured in ounces +// per week), and the animal must eat at least init_need ounces of food +// each week to survive. +// +// MODIFICATION MEMBER FUNCTIONS for the animal class: +// void assign_need(double new_need) +// Precondition: new_need >= 0. +// Postcondition: The animal's weekly food requirement has been changed to +// new_need (measured in ounces per week). +// +// void eat(double amount) +// Precondition: amount >= 0. +// Postcondition: The given amount (in ounces) has been added to the amount +// of food that the animal has eaten this week. +// +// void simulate_week( ) -- overriden from the organism class +// Postcondition: The size of the organism has been changed by its current +// growth rate. If the new size is less than zero, then the actual size is +// set to zero rather than to a negative value, and the growth rate is also +// set to zero. Also, if the animal has eaten less than its required need +// over the past week, then death has been activated. +// +// CONSTANT MEMBER FUNCTIONS for the animal class: +// double still_need( ) const +// Postcondition: The return value is the ounces of food that the animal +// still needs to survive the current week (i.e., its total weekly need +// minus the amount that it has already eaten this week.) +// +// double total_need( ) const +// Postcondition: The return value is the total amount of food that the +// animal needs to survive one week (measured in ounces). +// +// +// DOCUMENTATION for the herbivore class: +// plant is a derived class of the animal class. All the animal public +// member functions are inherited by a herbivore. In addition, a herbivore has +// this extra member function: +// +// CONSTRUCTOR for the herbivore class: +// herbivore(double init_size=0, double init_rate=0, double init_need=0) +// Same as the animal constructor. +// +// MODIFICATION MEMBER FUNCTIONS for the herbivore class: +// void nibble(plant& meal) +// Postcondition: eat(amount) and meal.nibbled_on(amount) have both been +// activated. The amount is usually half of the plant, but it will never be +// more than 10% of the herbivore's weekly need, nor more than the amount that +// the animal still needs to eat to survive this week. +// +// +// VALUE SEMANTICS for the organism class and its derived classes: +// Assignments and the copy constructor may be used with all objects. + +#ifndef ORGANISM_H // Prevent duplicate definition +#define ORGANISM_H + +namespace main_savitch_14 +{ + class organism + { + public: + // CONSTRUCTOR + organism(double init_size = 1, double init_rate = 0); + // MODIFICATION FUNCTIONS + void simulate_week( ) { alter_size(rate); } + void assign_rate(double new_rate) { rate = new_rate; } + void alter_size(double amount); + void death( ); + // CONSTANT FUNCTIONS + double get_size( ) const { return size; } + double get_rate( ) const { return rate; } + bool is_alive( ) const { return (size > 0); } + private: + double size; + double rate; + }; + + class plant : public organism + { + public: + // CONSTRUCTOR + plant(double init_size = 1, double init_rate = 0); + // MODIFICATION FUNCTIONS + void nibbled_on(double amount); + }; + + class animal : public organism + { + public: + // CONSTRUCTOR + animal(double init_size = 1, double init_rate = 0, double init_need = 0); + // MODIFICATION FUNCTIONS + void assign_need(double new_need); + void eat(double amount); + void simulate_week( ); // Overriden from the organism class + // CONSTANT FUNCTIONS + double still_need( ) const; + double total_need( ) const { return need_each_week; } + private: + double need_each_week; + double eaten_this_week; + }; + + class herbivore : public animal + { + public: + // CONSTRUCTOR + herbivore(double init_size = 1, double init_rate = 0, double init_need = 0); + // MODIFICATION FUNCTIONS + void nibble(plant& meal); + }; +} + +#endif diff --git a/chapter14/play_connect4.cxx b/chapter14/play_connect4.cxx new file mode 100644 index 0000000..c15bf5c --- /dev/null +++ b/chapter14/play_connect4.cxx @@ -0,0 +1,30 @@ +#include +#include +#include +#include "connect4.h" +using namespace main_savitch_14; + +int main( ) +{ + connect4 instance; + connect4::who winner; + char answer; + string restline; + + do + { + winner = instance.play( ); + switch (winner) + { + case connect4::HUMAN: cout << "You win" << endl; break; + case connect4::COMPUTER: cout << "I win" << endl; break; + case connect4::NEUTRAL: cout << "A draw" << endl; break; + } + cout << "Do you want to play again? [Y/N] "; + cin >> answer; + getline(cin, restline); + } while (toupper(answer) == 'Y'); + + return EXIT_SUCCESS; +} + diff --git a/chapter14/pondlife.cxx b/chapter14/pondlife.cxx new file mode 100644 index 0000000..87fc20e --- /dev/null +++ b/chapter14/pondlife.cxx @@ -0,0 +1,126 @@ +// FILE: pondlife.cxx +// A simple simulation program to model the fish and weeds in a pond + +#include // Provides cin, cout +#include // Provides setw +#include // Provides EXIT_SUCCESS, rand, size_t +#include // Provides the vector template class +#include "organism.h" // Provides Herbivore, Plant classes +using namespace std; +using namespace main_savitch_14; + +// PROGRAM CONSTANTS +const size_t MANY_WEEDS = 2000; // Number of weeds in the pond +const double WEED_SIZE = 15; // Initial size of each weed, in ounces +const double WEED_RATE = 2.5; // Growth rate of weeds, in ounces/week +const size_t INIT_FISH = 300; // Initial number of fish in the pond +const double FISH_SIZE = 50; // Fish size, in ounces +const double FRACTION = 0.5; // A fish must eat FRACTION times its size + // during one week or it will die. +const int AVERAGE_NIBBLES = 30; // Average number of plants nibbled by + // a fish over one week. +const double BIRTH_RATE = 0.05; // At the end of each week, some fish have + // babies. The total number of new fish + // born is the current number of fish times + // the BIRTH_RATE (rounded down to an + // integer). + +// Samples weed and fish objects to copy into the vectors of the main program: +const plant SAMPLE_WEED(WEED_SIZE, WEED_RATE); +const herbivore SAMPLE_FISH(FISH_SIZE, 0, FISH_SIZE * FRACTION); + +// PROTOTYPES for the functions used in the program: +void pond_week(vector& fish, vector& weeds); +// Precondition: weeds.size( ) > 0. +// Postcondition: On average, each fish has nibbled on AVERAGE_NIBBLES plants, +// and then simulate_week has been activated for each fish and each weed. Any +// fish that died are removed from the fish bag, and then +// BIRTH_RATE * fish.size( ) new fish have been added to the fish bag. + +double total_mass(const vector& collection); +// Postcondition: The return value is the total mass of all the plants in the +// collection. + + +int main( ) +{ + vector weeds(MANY_WEEDS, SAMPLE_WEED); // A vector of weeds + vector fish(INIT_FISH, SAMPLE_FISH); // A vector of weeds + int many_weeks; // Number of weeks to simulate + int i; // Loop control variable + + // Get number of weeks, and format the output. + cout << "How many weeks shall I simulate? "; + cin >> many_weeks; + cout.setf(ios::fixed); + cout << "Week Number Plant Mass" << endl; + cout << " of Fish (in ounces)" << endl; + + // Simulate the weeks. + for (i = 1; i <= many_weeks; i++) + { + pond_week(fish, weeds); + cout << setw(4) << i; + cout << setw(10) << fish.size( ); + cout << setw(14) << setprecision(0) << total_mass(weeds); + cout << endl; + } + + return EXIT_SUCCESS; +} + +double total_mass(const vector& collection) +{ + double answer; + vector::const_iterator p; + answer = 0; + for (p = collection.begin( ); p != collection.end( ); ++p) + answer += p->get_size( ); + + return answer; +} + +void pond_week(vector& fish, vector& weeds) +{ + // Variables for an index and an iterator for the weeds: + vector::iterator wi; + vector::size_type weed_index; + + // Variables for an index, an iterator, and counters for the fish: + vector::iterator fi; + vector::size_type fish_index; + vector::size_type new_fish_population; + + size_t many_iterations; // How many random nibbles to simulate + size_t i; // Loop counter + + // Have randomly selected fish nibble on randomly selected plants. + many_iterations = AVERAGE_NIBBLES * fish.size( ); + for (i = 0; i < many_iterations; ++i) + { + fish_index = rand( ) % fish.size( ); // Index of a random fish + weed_index = rand( ) % weeds.size( ); // Index of a random weed + fish[fish_index].nibble(weeds[weed_index]); + } + + // Simulate the weeks for the weeds. + for (wi = weeds.begin( ); wi != weeds.end( ); ++wi) + wi->simulate_week( ); + + // Simulate the weeks for the fish, and count how many died. + fi = fish.begin( ); + while (fi != fish.end( )) + { + fi->simulate_week( ); + if (!fi->is_alive( )) + fish.erase(fi); + else + ++fi; + } + + // Calculate the new number of fish, and reset the fish vector to this size. + // If this adds new fish to the vector, then those new fish will be equal to + // the SAMPLE_FISH that is used for all our fish: + new_fish_population = (1 + BIRTH_RATE) * fish.size( ); + fish.resize(new_fish_population, SAMPLE_FISH); +} -- cgit v1.2.3