feat: initial commitHEADmain

12 files changed, 1296 insertions, 0 deletions

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 <cstdlib>           // Provides EXIT_SUCCESS

+#include <iostream>          // 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 <cassert>

+#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 <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;

+    }

+}

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 <queue>    // Provides queue<string>

+#include <string>   // 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<std::string>& 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 <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);

+    }

+

+}

+

+	

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 <queue>   // Provides queue<string>

+#include <string>  // 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<std::string>& 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 <cassert>    // 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 <cctype>

+#include <cstdlib>

+#include <string>

+#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 <iostream>    // Provides cin, cout

+#include <iomanip>     // Provides setw

+#include <cstdlib>     // Provides EXIT_SUCCESS, rand, size_t

+#include <vector>      // 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<herbivore>& fish, vector<plant>& 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<plant>& collection);

+// Postcondition: The return value is the total mass of all the plants in the

+// collection.

+

+    

+int main( )

+{

+    vector<plant> weeds(MANY_WEEDS, SAMPLE_WEED);    // A vector of weeds

+    vector<herbivore> 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<plant>& collection)

+{

+    double answer;

+    vector<plant>::const_iterator p;

+    answer = 0;

+    for (p = collection.begin( ); p != collection.end( ); ++p)

+        answer += p->get_size( );

+

+    return answer;

+}

+

+void pond_week(vector<herbivore>& fish, vector<plant>& weeds)

+{

+    // Variables for an index and an iterator for the weeds:

+    vector<plant>::iterator      wi;

+    vector<plant>::size_type     weed_index;

+

+    // Variables for an index, an iterator, and counters for the fish:

+    vector<herbivore>::iterator  fi;

+    vector<herbivore>::size_type fish_index;

+    vector<herbivore>::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);

+}