Assignment 4

Overview

In this assignment, you will restructure your Go program and add a simple Artificial Intelligence (AI) to make choices for the white (computer) player. The AI will use a technique named one-step lookahead, in which it considers each possible action, assigns a score to each, and then chooses the action with highest score. In our case, the actions are the places where the white player can place a stone for that move. The score used in the one-step lookahead will be the score for the game if it were to end immediately afterwards. After the AI has scored the possible moves, it will sort the moves by score and choose the highest one. If several moves are tied for the highest score, the AI will choose one at random.

You will also add the suicide rule to your game. This rule forbids players from placing a stone where it would be immediately removed again.

The purpose of this assignment is to give you more practice with classes, including composition and implementation inheritance. For Part A, you will refactor your program to move much of the functionality from main.cpp into a new Game module. For Part B, you will update your game to use the Game class. For Part C, you will create a Move module to represent a single possible move. For Part D, you will modify your Search module to search and sort moves. For Part E, you will develop an ArtificialIntelligence module. For Part F, you will update your Game module to use it. For Part G, you will document your ArtificialIntelligence module.

Requirements

Copy the code and data files of your Assignment 3. Do not just modify Assignment 3.

(If you are using Visual Studio, you must start by creating a new project for Assignment 4. Do NOT copy the whole folder including the .sln file or massive confusion will result!)

Part A: The Game Class [Marked with Part B]

Create a Game class to handle some of the functionality from main.cpp. It should be an encapsulated class, i.e., all its member variables should be private. Wherever possible, you should copy code from the existing main function into the functions of the Game class. Input handling will stay in main.cpp. The Game class will not store a list of the player’s moves.

By the end of Part A, your Game type class have the following public member functions:

• Game ();
• Game (const std::string& filename_in);
• void printBoard () const;
• void printWinner () const;
• const Board& getBoard () const;
• void blackPass ();
• bool blackPlay (int row_in, int column_in);
• bool whiteAi ();

The Game class will also have a private member function:

• void printRemoved (const StonesRemoved& removed_in) const;

Perform the following steps:

• Add a header file for your Game module. Add whatever #pragma, #include, and using

lines you need. You should have an #include for your Board module.

• Declare the Game class, which has a Board as its only member variable. Add the function prototypes listed above.
  • Note: This class is using composition.
  • Reminder: In an encapsulated class, all member variables should be private.
• Add a default constructor to the Game class. The function body will be empty.
• Add the second constructor to the Game class, which takes a file name as a parameter. It has a precondition that the filename is not the empty string. After checking the precondition, the function should load the board from that file.
• Add an implementation for the printBoard function. It should print the board.
  • Hint: In the implementation, you should call one function in the Board class.
• Add an implementation for the printWinner function. It should calculate the player scores and print who won.
  • Hint: Copy and adapt your code from main.cpp.
  • Note: This function does not need to print the game board.
  • Reminder: The Game class does not store a list of the player’s moves. You do not have to print the analysis of them.
• Add an implementation for the getBoard function. It will return a constant reference to the game board.
  • Note: You will use this function in Part E.
• Add an implementation for the whiteAi function. For now, it will just print a message saying that white passed.  Then it should return whether or not white played a stone.
  • Note: You will expand the whiteAi function in part E.
• Add an implementation for the blackPass function. It should print a message saying that black passed.
• Add an implementation for the blackPlay function. If row_in and column_in specify a place outside the game board, print that that play is forbidden. Otherwise, if that place is not empty, print that it is forbidden. Otherwise, play the stone there, print a message saying the

stone was placed, and call the printRemoved function to print which stones were removed. If the player successfully placed a stone, the function should return true. Otherwise, it should return false.

• Hint: You already have this functionality in main.cpp. You can copy the code in and adapt it.
• Add an implementation for the printRemoved function. If stones were captured or lost to suicide, it should print how many.
  • Hint: You already have this functionality in main.cpp as well. It may already be a function there.
• Improve your blackPlay function to implement the suicide rule. Do not simply place the stone on the board. Instead, create a copy of the board and place the stone on the copy. Then check if any stones are lost to suicide. If so, print “Forbidden: Suicide rule”. Otherwise, set your game board to the copy and print messages as before.
  • Hint: You can create a copy of a Board using the assignment operator:

Board copied = my_board;

Similarly, you can use the assignment operator to set one Board to another:

my_board = copied;

C++ will just copy the values of the member variables.

• Reminder: This function should return false if the player did not place a stone. In particular, it should return false if the player did not place a stone due to the suicide rule.

Part B: Use the Game class [45% = 15% stability + 30% output, includes Part A and 5% for Part F]

In Part B, you will change your main function to use the refactored Game class. Perform the following steps:

1. In main.cpp, update the program to use the Game class. Replace the Board variable with a Game variable. Remove the variables for storing player moves. Then update the main function to use the Game member functions from Part A.
   1. Hint: If you have any other functions in main.cpp, they are probably no longer needed.
   • Hint: You can copy a Game with the assignment operator, just like you can copy

Boards. To load a game, set your existing Game to a new one created from the file:

my_game = Game(filename);

• When the user enters a “load” command, first print out the scores and winner for the current game. Then ask the player for the file name and load the game.
  • Hint: Use the same function as when printing the scores and winner at the game end.
• When the black (human) player passes, check whether white also passed. If so, end the main loop just as if the player entered the “quit” command.

• Reminder: The whiteAi function returns true if white played a stone and false

otherwise.

• Add “new” as a new command to your game. When the user enters this command, print out the scores and winner and then replace the current Game with one created by the default constructor.
• Test your program with the same tests as for Assignment 3. They should still work (example output).
  • Hint: g++ PlaceString.cpp BoardSize.cpp BoardValue.cpp Board.cpp Game.cpp main.cpp -o game
  • Note: Right now, you do not need to compile Search.cpp. However, you will need it again when compiling the game in Part F.

Part C: The Move Module [10% test program]

In Part C, you will create the types you will need to represent possible moves and choose between them. You will also add two overloaded operators. The Move type will represent a move. The SortableMove type will inherit from the Move type and also store the net score. The net score is the score for this player minus the score for the other player.

By the end of Part C, your Move module will have overloaded operators with the following prototypes:

• bool operator== (const SortableMove& lhs_in,

const SortableMove& rhs_in);

• bool operator< (const SortableMove& lhs_in,

const SortableMove& rhs_in);

Reminder: All overloaded operators are functions. They are declared like functions and can be used as functions in all cases. They are different because they can also be called using operator syntax (e.g. move1 < move2).

Perform the following steps:

1. Create an appropriate header file for the for the Move module.
2. Declare a record (struct) named Move to represent a move in the game. It should have a bool member field named is_played for whether the player placed a stone and int member fields named row and column for where the stone was placed.
3. Declare another record (struct) named SortableMove that inherits from Move using public inheritance. A SortableMove should have all the fields of a Move and an additional float member named net_score.
   1. Hint: Since SortableMove mentions Move, it must be declared after Move.
   • Hint: Inheritance for records (structs) works exactly the same as inheritance for classes. Move has no member functions, but the member variables will be inherited into SortableMove as with classes.

• Note: You must use the name net_score so the test program will work.
  • Note: By default, the member variables of a record (struct) have public access, which is what is wanted in this assignment. It is possible to make them protected or private, but doing so is generally a bad idea.
• Add the function prototypes. They should be declared after the end of the Move type.
• Add an appropriate source file.
• Add an implementation for operator==. It should return true if the net_score fields of the two SortableMoves are equal. Otherwise it should return false.
• Add an implementation for operator<. It should return true if the net_score field of lhs_in is strictly less than the net_score field of rhs_in. Otherwise it should return false.
  • Note: In this context, lhs_in and rhs_in refer to the terms on the left-hand side and right-hand side of the operator. Which side is which didn’t matter for operator==, but it does for operator<.
• Test your Move module with the TestMove4.cpp program provided. You will need the TestHelper.h and TestHelper.cpp files. The resulting program should give you full marks (example output).
  • Hint: g++ Move.cpp TestMove4.cpp TestHelper.cpp -o partc

Part D: Modify the Search Module [5% test program]

In Part D, you will modify your Search module to search and sort an array of SortableMoves instead of an array of strings. The comparisons will be done using the overloaded operators from Part C.

By the end of Part D, your Search module will have functions with the following prototypes:

• int linearSearch (const SortableMove data_in[],

int count_in,

const SortableMove& value_in);

• int unsortedFindSmallest (const SortableMove data_in[],

int count_in);

• int unsortedFindLargest (const SortableMove data_in[],

int count_in);

• void mySort (SortableMove data_in[],

int count_in);

• bool isSorted (const SortableMove data_in[],

int count_in);

• int sortedFindSmallest (const SortableMove data_in[],

int count_in);

• int sortedFindLargest (const SortableMove data_in[],

int count_in);

• int binarySearch (const SortableMove data_in[],

int count_in,

const SortableMove& value_in);

• int binarySearchFirst (const SortableMove data_in[],

int count_in,

const SortableMove& value_in);

Perform the following steps:

1. Change the function prototypes to take a SortableMove parameter instead of a string. You will need a new #include.
2. Change the function implementations to replace all of the strings with SortableMoves. There will be at least one local string variable in a function body that needs to be replaced.
3. If you used any comparison operators on data other than == and <, your program will not compile. Either change your code to use only those operators, or add the necessary operators to the Move module.
   1. Hint: A greater than comparison (a > b) can be rewritten as (b < a). An inequality comparison such as (a != b) can be rewritten as (!(a == b)). Similarly, (a >= b) can be rewritten as (!(b < a)).
   • Note: Starting in C++20, if you write an equality comparison (a == b), the compiler will automatically generate an inequality comparison (a != b) for you. It just returns

!(a == b).

• Test your BoardValue module with the TestSearch4.cpp program provided. You will need the TestHelper.h and TestHelper.cpp files. The resulting program should give you full marks (example output).
  • Hint: g++ Search.cpp Move.cpp TestSearch4.cpp TestHelper.cpp – o partd

Part E: The ArtificialIntelligence Class [30% = 28% test program + 2% output]

In Part E, you will write an ArtificialIntelligence class to contain the code that plays against the human player. The class will also store the colour of the stones that the AI plays. To use the AI, the client will repeatedly call a function in the class to choose the next move.

By the end of Part E, your ArtificialIntelligence class will have the following public

member functions:

• ArtificialIntelligence (char us_value_in);
• Move chooseMove (const Board& board_in) const;

Your ArtificialIntelligence class will have the following private member functions:

• float calculateNetScore (const Board& board_in) const;
• MoveResult getPlayResult (const Board& board_in,

int row_in, int column_in) const;

• bool isInvariantTrue () const;

Perform the following steps:

• Add an appropriate header file for your new module.  Do not put an #include for Game.h. Instead, put a forward declaration:

class Game;

This will allow you to refer to the Game type as a reference. It will not allow you to create a

Game or pass it by value.

• Note: A forward declaration for a class is analogous to a prototype for a function.
  • Note: We are using a forward declaration here because Game.h will have to include ArtificialIntelligence.h in Part F. If ArtificialIntelligence also included Game.h, we would have circular includes, which is a Very Bad Thing. Circular includes typically cause a compiler to fail with obviously-incorrect error messages. E.g. saying a type is not declared on the exact line that declares it.
  • Note: You can use a forward declaration or an #include for Board. Both will work.
• Add a record (struct) named MoveResult to store the result of a move. It should have two member variables: a boolean variable that tells whether the move was legal and a floating point value for the net score.
• Add a class named ArtificialIntelligence. It should have one member variable, which will represent the board value for the stones it plays. The class should also have the function prototypes.
• Add the constructor. It has one precondition, which is that the parameter is a player board value.
  • Reminder: You have a BoardValue function that will help you here.
• Add the isInvariantTrue function, which should return true if the class invariant is true and false otherwise. The class invariant requires that the member variable holding the board value contains a player board value.
• Use an assert to ensure the class invariant is true at the end of the constructor.
  • Reminder: Do not check the class invariant at the beginning of the constructor.
• Add the calculateNetScore function. It should start by determining the board value for the other player besides the “us” player. Then the function should call a function to determine the score for the “us” player. When making the function call, the calculateNetScore function should use its parameter, which is of the Board type. Then it should determine the score for the other player in a similar manner. Finally, it should calculate the difference between the scores of the two players, convert the difference value to a float, and return it.
  • Reminder: You can use a function in the BoardValue module to find the board value for the other player.

• Note: If you do not explicitly typecast the result to a float, you may get a warning on some compilers.
• Add the getPlayResult function. It should return whether or not the proposed move is legal and, if so, what the board would look like after. First, check if the specified place is both on the board and empty. If not, the move is not legal. Next, make a copy of the board and play the stone at the specified place. If any stones are lost to suicide as a result, the move is not legal. Otherwise, the move is legal. In the case of a legal move, do the following: (i) calculate the net score for the board with the added stone, and (ii) return a value indicating that the move is legal and also return the net score.

Over steps 9-13, you will add an implementation for the chooseMove function. Overall, it will construct a list of all valid moves, sort them, and then choose one of the highest-scoring moves at random.

• First, the chooseMove function should declare an array of the SortableMove type to hold all the possible moves that are valid. Declare a constant for the array size. The constant should be equal to the number of places on the game board plus 1 (for passing). This constant says the maximum number of moves that will ever be stored in the array. You will also need a variable to store how many moves are currently stored in the array.  It should start at 0.
  • Note: Normally, there will be fewer valid moves than the maximum because there will be stones on the board blocking some places. However, if black passes as the first move, the AI will need to store moves in every position in the whole array.
• Secondly, the chooseMove function should add the legal moves to the array. Start by adding the “pass” move. Set is_played to false and calculate net_score based on the current game board. Then, for each place on the board, determine the MoveResult for playing there. If the move is legal, add it at that place to the next spot in the array. Set all the member variables for the SortableMove.
  • Hint: When you add a move to the array, use the number of valid moves as the index. Then increment the number of valid moves.
  • Note: If no stone was player, it doesn’t matter what you set the row and column to. Nothing will ever look at them.
• Thirdly, the chooseMove function should sort the moves in the array.
• Fourthly, the chooseMove function should determine the maximum net score. Then it should find the first element in the array with that score. The elements from there to the end are tied for highest net score.
  • Reminder: The array is sorted in ascending order, so the highest-scoring elements are at the end.
  • Hint: There is a function in the Search module that will help you.

1. Finally, the chooseMove function should choose one of the highest-scoring moves at random and return it. You can generate a random number using the rand() function declared in the

<cstdlib> library.

• Hint: You can convert the values returned by rand() into the range you want using the modulus (%) operator.  If you want a random value in the interval [0, n), you can use:

my_value = rand() % n;

For example, rand() % 4 can return 0, 1, 2, or 3.

• Note: The array elements are SortableMoves, but the chooseMove function returns a Move. This works because SortableMove inherits from Move, so all SortableMoves are also Moves. When converting a SortableMove to a Move, the extra fields are sliced off and only the Move fields are returned. The same thing happens when passing parameters by value.
  • Note: Each time you run your program, you will get the same “random” numbers in the same order. This can be very useful for debugging. If you want your random numbers to be different each time, you can seed the random number generator with the current time. Do this by calling the srand function once at the start of your main function:

srand((unsigned int)(time(nullptr)));

You will need to #include <ctime>. You do not have to seed the random number generator for this assignment.

• FYI: rand() returns numbers in the interval [0, RAND_MAX], where RAND_MAX is a constant with a value of at least 2¹⁵-1 = 32767. On POSIX systems (including replit, Mac, and Linux), RAND_MAX is always 2³¹-1 = 2147483647.
• Test your ArtificialIntelligence module with the TestArtificialIntelligence4.cpp program provided. You will need the TestHelper.h and TestHelper.cpp files and the 19to5.txt data file. The resulting program should give you full marks (example output).
  • Hint: g++ BoardSize.cpp BoardValue.cpp Board.cpp Move.cpp Search.cpp ArtificialIntelligence.cpp TestArtificialIntelligence4.cpp TestHelper.cpp -o parte
  • Note: The remaining 2 marks for Part E are for whether the moves are chosen randomly.

Part F: Add AI to the Game [5%, marked with Part B]

In Part F, you will improve your Game class to play stones instead of always passing. Your Game type class will still have the following public member functions:

• Game ();
• Game (const std::string& filename_in);
• void printBoard () const;
• void printWinner () const;
• const Board& getBoard () const;
• void blackPass ();
• bool blackPlay (int row_in, int column_in);

• bool whiteAi ();

The Game class will also still have the same private member function:

• void printRemoved (const StonesRemoved& removed_in) const;

Perform the following steps:

• In the declaration of the Game class, add an ArtificialIntelligence member variable. You will need another #include.
  • Reminder: You must not have an #include for Game.h in

ArtificialIntelligence.h, or you will get circular includes. See Part E, Step 1.

• In the implementation for the Game default constructor, initialize your new member variable using an initializer list. You must use an initializer list because ArtificialIntelligence does not have a default constructor.
  • Hint: An initializer list starts with a colon (‘:’) and goes between the first line of the function and the opening curly brace. For example:

MyClass::MyClass ()

: member_variable(argument1, argument2)

{

// constructor body stuff

}

• Reminder: The Board member is automatically initialized using its default constructor. You can add it to the initializer list with no parameters, but that will have no effect.
• In the other constructor, initialize the new member variable in an analogous manner.
• Improve the implementation for the whiteAi function. It should start by choosing a move. If the move was to not play a stone, it should print that white passed and return false. Otherwise, it should print “White placed a stone at row RRR, column CCC“, where RRR is the row and CCC is the column. Then it should play a stone there, print the stones removed, and return true.
  • Reminder: The whiteAi function should return true if white played a stone and

false otherwise.

• Test your program before handing it in. The white AI should be smart enough to choose moves that capture stones, surround territory, and invade the other player’s territory. It should be smart enough not to fill in its own eyes, but it will not be smart enough to deliberately construct them.
  • Hint: g++ PlaceString.cpp BoardSize.cpp BoardValue.cpp Board.cpp Move.cpp Search.cpp ArtificialIntelligence.cpp Game.cpp main.cpp -o game

• Hint: Testing will be easier if you load the ear.txt or simple.txt board. The shapes.txt board will not work because some of the stones start surrounded and therefore the game will reject every move as violating the suicide rule.
  • Note: The ko rule is not yet implemented, so the AI can sometimes “undo” moves that capture a single stone by capturing it back. This will be fixed in Assignment 6.

Part G: Document Board functions [10% documentation]

In Part G, you will write documentation for your ArtificialIntelligence module in the style described in Section 4 of the online notes. You will write documentation for each public member function and for the class invariant. The format for function documentation is as follows (no bold-face in code):

//

// functionName

//

// Purpose: Explain why would you call this function.

// Parameter(s):

//    <1> parameter1: What it does

//    <2> parameter2: What it does

//    …

// Precondition(s):

//    <1> some precondition

//    <2> another precondition

//    …

// Returns: The meaning of the value the function returns.

// Side Effect: Anything the function does besides return

//               a value.

//

As in Part E, your ArtificialIntelligence class should have the following public member functions:

• ArtificialIntelligence (char us_value_in);
• Move chooseMove (const Game& game_in) const;

Perform the following steps:

1. Document the constructor. Consider how many parameters and preconditions it has. All constructors have a side effect but no return value.
   1. Reminder: Documentation is written for programmers who want to call your functions. Assume the audience can see your header (.h) file but not your source (.cpp) file. Function documentation must be placed in the header file.
   1. Reminder: You do not have to document the data types for your parameters. Your audience can see the function prototype. Instead, describe the purpose of each parameter.
   1. Reminder: The preconditions are normally just the contents of your assert

statements. Copy-paste will be helpful.

• Reminder: Don’t include the class invariant as a precondition. The class invariant is part of the module implementation, so it is hidden as part of data encapsulation.
• Document the chooseMove function.
• Immediately before the class definition, write general documentation for the class. Start with one or two sentences describing the purpose of the class (what it is used for). Then document the class invariant. If possible, use code instead of sentences to describe what the class invariant requires.
  • Hint: The documentation for you class could look something like the following:

//

// FruitTracker

//

// A FruitTracker compares the quality of different types

//    of fruits, such as apples to oranges. Client code

//    can query the best and worst types so far.

//

// Class Invariant:

//    <1> worst_score >= 0.0f

//    <2> best_score >= worst_score

//

• Test that your program still compiles. It is easy to accidentally damage function prototypes while adding documentation around them.
  • Reminder: g++ PlaceString.cpp BoardSize.cpp BoardValue.cpp Board.cpp Move.cpp Search.cpp ArtificialIntelligence.cpp Game.cpp main.cpp -o game

Formatting [ −10% if not done]

1. Neatly indent your program using a consistent indentation scheme.
2. Put spaces around your arithmetic operators:

x = x + 3;

• Use symbolic constants, such as BOARD_SIZE, when appropriate.
• Include a comment at the top of main.cpp that states your name and student number.
• Format your program so that it is easily readable. Things that make a program hard to read include:
  • Very many blank lines. If half or more of your lines are blank, you have too many. Put a blank line between logically distinct sections of your program.
  • Multiple commands on the same line. In general, do not do this. You can do it if it makes the program clearer than if the same commands were on separate lines.
  • Uninformative variable names. For a local variable that is only used for a few lines, the name does not really matter. However, if a variable is used over a larger area (including any global or member variable), it should have a name that documents its purpose.

Similarly, parameters should have self-documenting names because the function will be called from elsewhere in the program.

• No variable names in function prototypes. Function parameters should have the same name in the prototype as in the implementation. Doing so makes calling the function much less confusing. (Contrary to some CS 110 training.)

Submission

• If you are working with replit, download your project as a .zip file. Check that it contains all your .cpp and .h files.
• Submit a complete copy of your source code to UR Courses. You should have the following files with exactly these names:
• ArtificialIntelligence.h
• ArtificialIntelligence.cpp
• Board.h
• Board.cpp
• BoardSize.h
• BoardSize.cpp
• BoardValue.h
• BoardValue.cpp
• Game.h
• Game.cpp
• main.cpp
• Move.h
• Move.cpp
• PlaceString.h
• PlaceString.cpp
• Search.h
• Search.cpp
  • Note: A Visual Studio .sln file does NOT contain the source code; it is just a text file.

You do not need to submit it. Make sure you submit the .cpp files and .h files.

• Note: You do not need to submit the test programs. The marker has those already.
• If possible, convert all your files to a single archive (.zip file) before submitting them to UR Courses
• Do NOT submit a compiled version
• Do NOT submit Visual Studio intermediate files, such as:
  • Debug folder
  • Release folder
  • ipch folder
  • *.ncb, *.sdf, or *.db files
• Do NOT submit a screenshot

Get expert help for Restructure your Go program and many more. 24X7 help, plag free solution. Order online now!