A8-Multi-Function Programs

Table of Contents


Objectives

  • Use function declarations (prototypes).
  • Code void functions.
  • Design a program using multiple functions as modules.
  • Develop functions as black boxes.
  • Add block comments to function declarations.

Academic Honesty

Read the Scholastic Honesty Policy and Assignment Integrity policies of the syllabus. Here are some clarifications for this particular assignment:

  • You are encouraged to work with one other student of this class following the rules of Pair Programming for Homework Assignments. If you choose to pair program, there is a bonus applied.
  • You may not give a copy of your code to your designated pair-programming partner if you did not develop the code together.
  • You may not look at another student's code until you complete and submit this assignment, except for code you develop code together with your pair-programming partner.
  • You may get help from people other than your pair-programming partner if you get stuck, but only if they do not show or tell you the code to type.
  • Remember that the instructor performs similarity tests on programming project submissions, and copied or plagiarized code is usually very easy to detect.

Preparation

  1. Make sure you have completed the exercises from lesson 8.
  2. Complete the Review Exercises in CodeLab 8. These exercises will help prepare you for the problem-solving programs and should be completed first.
  3. Read lesson 8.1.4: Arrays as Function Parameters.

Project Specifications

Your solutions to these projects must only use techniques we have covered so far.

Programming Style

For all programs, remember to follow all the style rules we covered including the recent items:

  1. Avoid duplicating code (see textbook page 208)
  2. Function comment blocks (See: Function Comment Block)
  3. Function naming conventions (See: Function Names)
  4. Indentation in functions and placement of curly braces (See: Indentation)
  5. No magic numbers. (Hint: make arrays of numbers const)
  6. Indentation in while statements and placement of curly braces
  7. No tab characters in your code.

    You can remove tab characters by either setting up TextPad correctly (see here) or by running a program named astyle (see here).

  8. Meaningful variable names and consistent naming style (caps vs. underbars).
  9. Create the README.txt file following the instructions.

Image

Project 1: Function Worksheet Sequel

Functions are an important part of programming, allowing us to break up long sequences of code into shorter reusable parts. We then assemble the parts to create larger programs.

In this project we complete several functions. Each function is like a smaller program inside of a our larger program. Notice that we can focus on each function separately, allowing our full attention on each part of the problem.

Project Specifications
  1. Start by downloading the worksheet: funwork2.cpp.

    Keep the same filename and add to the existing code to complete the project. Leave the existing code unchanged, except for comments as instructed.

  2. Add your name and the date to the file comment block at the top of the file, replacing the words Your Name with your first and last name and Date Here with the current date.
  3. No user input is required for this project and do not add any.
  4. Write the required functions as described by the function signature and comment block.

    Do NOT change any of the function headers and do NOT make any changes to the main() function besides uncommenting code.

  5. Write the function definitions below main(), and their prototypes above main().
  6. Do not turn in code with cout in any function besides printArray() and the cout statements already coded in main().

    You may add cout to debug code but please remove it before turning in your code.

  7. Compile and run the code when finished with each function to verify correctness. Check the test results and make any alterations to your function definitions as necessary. Do NOT change any code in main() beyond removing comments to call the functions and do not change the function headers.

    When you first start you will see warnings when compiling. Remember that code with warnings compiles but the warning is giving you hints about problems with the code.

  8. Example Run: The outputs of the program must look exactly like the following for full credit, including the same order and format of the output. The exception is that the random numbers will change every time you run the program.
    ***Testing alternate***
    Variable turn is set to a 1.
    alternate1 must change turn to (2): 2
    alternate2 must change turn to (1): 1
    alternate3 must change turn to (2): 2
    
    ***Testing sumData***
    sumData0 must return (3): 3
    sumData1 must return (6): 6
    sumData2 must return (9): 9
    
    ***Testing randSum***
    randSum0 must return numbers from (1 to 3): 2 3 3 3 1 2 2 3 1 3
    randSum1 must return numbers from (1 to 6): 6 6 3 6 6 1 5 6 2 6
    randSum2 must return numbers from (1 to 9): 9 2 1 8 1 8 8 3 9 1
    
    ***Testing weightedRand***
    weightedRand0 must mostly show (1): 1 1 1 1 1 2 2 1 1 2 1
    weightedRand1 must mostly show (2): 2 2 2 2 2 2 2 2 2 2 1
    weightedRand2 must mostly show (3): 2 3 3 1 3 3 2 3 3 3 3
    
    ***Testing printArray***
    printArray1 must cout (A1=1 2 3): A1=1 2 3
    printArray2 must cout (A2=10 30 50 79 10): A2=10 30 50 79 10
    printArray3 must cout (A3=3): A3=3
    
    ***Testing addOne***
    addOne1 must show three arrays as follows
    (1=2 2 2): 1=2 2 2
    (2=1 1 1): 2=1 1 1
    (3=1 1 1): 3=1 1 1
    addOne2 must show three arrays as follows
    (1=2 1 1): 1=2 1 1
    (2=1 2 1): 2=1 2 1
    (3=1 1 2): 3=1 1 2
    addOne3 must show three arrays as follows
    (1=1 1 2): 1=1 1 2
    (2=1 2 1): 2=1 2 1
    (3=2 1 1): 3=2 1 1
    
    *** End of Tests ***
    
  9. When all of the tests pass, upload your completed source code file with the rest of the assignment as described in Deliverables.
Hints:
  • Remember that a warning is not a failure to compile but must be corrected before submitting the project.
  • For an example of printing the elements of an array, see lesson 8.1.4: Arrays as Function Parameters.

Sticks lying on surface
Image credit

Project 2: Improving the Game AI

In this project, we continue development of our game of sticks from assignment 7, Project 2 by improving our AI such that it can learn and improve its strategy. To accomplish our goal, the assignment has two required parts and an optional third:

  1. Improving the AI so that it can learn
  2. Adding an option for training the AI against another AI
  3. For extra credit, analyzing the trained AI's strategy and crafting a simpler replacement

This project is adapted from the Stanford University Nifty Assignments, "Game of Sticks" [1].

AI Description

We will design the AI to operate as follows:

  • The only possible moves in a game are drawing one, two or three sticks, and the AI keeps a tally of which moves allowed it to win a game for a given number of sticks remaining on the board.
  • Initially, all three moves are equally possible and the AI's tally has one mark for each possible move: one, two or three sticks to draw.
  • To make a move, the AI randomly selects from its tallies for the number of sticks remaining, giving more weight to the moves that allowed it to win in the past.
  • An AI keeps track of all its moves during a game, that is how many sticks it draws for a given number of sticks remaining on the board.
  • If the AI wins a game, then for each move it recorded the AI increases the tally for the number of sticks it drew. If the AI loses, it erases its move records.
  • As more and more games are played, the tally increases for the better number of sticks to take. When the AI selects its move, randomly weighted by the tallies, it becomes more likely to make a good move.
Example

Consider an example where there are 10 sticks at the beginning. Here is the initial tally record for the AI:

index 1 2 3 4 5 6 7 8 9 10
one 1 1 1 1 1 1 1 1 1 1
two 1 1 1 1 1 1 1 1 1 1
three 1 1 1 1 1 1 1 1 1 1

The index of the array element is the number of sticks remaining. Under the index is the weighting for drawing a one, two or three. The weight is calculated by taking the indexed number and dividing by the sum of all three numbers in a column. Thus initially, the AI has 1/3 chance for selecting one, 1/3 for two, and 1/3 for three.

Assume that the game proceeds as follows:

  1. Player takes 3 sticks, there are 7 sticks remaining.
  2. AI randomly picks a two from the move tally for 7 sticks. This means that the AI takes 2 sticks, and there are 5 sticks remaining.
  3. Player takes 1 stick, there are 4 sticks remaining.
  4. AI randomly picks a 3 from the move tally for 4 sticks. This means that AI takes 3 sticks, and there is 1 stick remaining.
  5. Player has to take the final stick and thus loses.

Now at the end of the game, the AI recorded these moves that it made. We can see that when 7 sticks remained, the AI selected 2 sticks. Similarly, when 4 sticks remained, the AI selected 3 sticks.

index 1 2 3 4 5 6 7 8 9 10
move 3 2

Since the AI won the game, it takes its move records and updates the tallies to add the successful moves. The tally sheet now looks like:

index 1 2 3 4 5 6 7 8 9 10
one 1 1 1 1 1 1 1 1 1 1
two 1 1 1 1 1 1 2 1 1 1
three 1 1 1 2 1 1 1 1 1 1

Now, with weighted random numbers, the AI will more likely draw 2 sticks when 7 sticks remain on the board because it has 1/4 chance for selecting one, 2/4 for two, and 1/4 for three. Similarly, the AI will more likely draw a 3 when four sticks remain on the board.

How does Random Weighting Work?

Here is an algorithm in psuedocode for selecting a weighted random number from our tallies:

For the current move sum the tallies of one, two and three
Get a random number between 1 and the sum
If the random number is <= than the tally for one, select one
Else if the random number is <= the tallies for one + two, select two
Else select three

As an example, consider the tally sheet for index 7 above which has the tallies for when there are seven sticks remaining on the board.

Sum of tallies for 7 sticks: 4
Random number between 1 and 4: 3
if 2 <= 1 (false so skip)
else if 2 <= 1 + 2 (true so select and choose two)

In our example we used random weighting to select two, which is 2 sticks for the move.

Part 1: Making the AI Learn

Your task is to modify the human vs. computer version of the game so that the AI works as described above. After each game that it wins, the AI updates the tallies for its winning moves. The AI will play relatively randomly at first, like the random AI, but will start to "learn" a strategy as you play against it.

Part 1 Specifications
  1. Update the Game of Sticks project from assignment 7, Project 2 by modifying the human vs. computer version of the game so that the player AI works as described above. The program must meet all the prior specifications except for the changes noted below.
  2. Name the source code file sticks8.cpp and include all your code for both parts of this project in this single file.

    Be careful of the spelling, including capitalization, as you will lose points for a misspelled name. Naming is important in programming.

  3. Offer the same game selections as before, either to play against a human or a computer.
  4. Continue the game as before by alternating between the two players, allowing each to pick up between 1 and 3 sticks as shown in the Example Runs.

    If the user chooses option 2, the second player is the AI; otherwise, if the user chooses option 1 the other player is a human.

  5. Modify the moveAI() function as shown below by adding three array parameters for the tallies.
    /**
        Generates an AI move.
    
        @param sticks The number of sticks remaining.
        @param one The tally numbers for 1 stick moves.
        @param two The tally numbers for 2 stick moves.
        @param three The tally numbers for 3 stick moves.
        @return a valid move.
    */
    int moveAI(int sticks, int one[], int two[], int three[])
    
  6. Within the moveAI() function, call rand() to calculate the number of sticks selected. Check if the number of sticks selected is less than or equal to the number of sticks remaining and return a valid move.

    Hint: select a random number based on the weighted sum of the three arrays indexed by the number of sticks remaining. See the weightedRand() function in funwork2.cpp.

    Hint: when the program starts in main(), initialize all three arrays once so all elements have the value 1.

  7. As in the prior game version, call the moveAI() function to get the number of sticks selected by the AI. Make sure to record the moves made by the AI.

    Hint: save the AI moves in a separate array like we did for sticks7.cpp.

  8. If and only if the AI wins a game, update the three arrays to record the successful moves and allow the AI to improve.

    Hint: See the addOne() function in funwork2.cpp.

  9. As in the prior game version, include a do or while loop that allows the user to repeat the game with the same number of sticks by entering a "1" (without the quotes) at the end of each game as shown in the Example Runs.
  10. Seed the random number generator in main() before any loop or function call.
  11. Example Runs: The input prompts and outputs of the program must look like the following for full credit, including the same order of input and exact wording of the output. For the input shown you must get the same output. However, the output must change properly if the inputs are different.
    Welcome to the game of sticks!
    How many sticks to start with (10-100)? 10
    Play options:
    1. Play against a human
    2. Play against the computer
    Choice (1-2): 2
    
    There are 10 sticks on the board.
    Player 1:How many sticks to take (1-3)? 1
    AI takes 1
    
    There are 8 sticks on the board.
    Player 1:How many sticks to take (1-3)? 3
    AI takes 2
    
    There are 3 sticks on the board.
    Player 1:How many sticks to take (1-3)? 2
    AI takes 1
    
    AI loses
    Play again (1 = yes, 0 = no)? 1
    
    There are 10 sticks on the board.
    Player 1:How many sticks to take (1-3)? 3
    AI takes 2
    
    There are 5 sticks on the board.
    Player 1:How many sticks to take (1-3)? 1
    AI takes 3
    
    There are 1 sticks on the board.
    Player 1:How many sticks to take (1-3)? 1
    
    You lose
    Play again (1 = yes, 0 = no)? 0
    
    Welcome to the game of sticks!
    How many sticks to start with (10-100)? 12
    Play options:
    1. Play against a human
    2. Play against the computer
    Choice (1-2): 1
    
    There are 12 sticks on the board.
    Player 1:How many sticks to take (1-3)? 3
    
    There are 9 sticks on the board.
    Player 2:How many sticks to take (1-3)? 2
    
    There are 7 sticks on the board.
    Player 1:How many sticks to take (1-3)? 3
    
    There are 4 sticks on the board.
    Player 2:How many sticks to take (1-3)? 3
    
    There are 1 sticks on the board.
    Player 1:How many sticks to take (1-3)? 1
    
    Player 1 loses.
    Play again (1 = yes, 0 = no)? 0
    

    In the above example runs, the users entered the values shown in aqua italics (for emphasis) to produce the output. Your program does NOT print the characters in aqua italics, nor does the user input appear in aqua italics.

When the learning AI is working well, continue on to the next part of this project.

Hints:
  • Boxes are computer memory. We want to use arrays to store the tokens and record the AI moves.
Part 2: Training the AI

In the previous part we created an AI that is able to learn from playing against the player. However, it takes a considerable time before the before the AI is able to perform well against a human player. To speed up this process, we add an option to pre-train the AI before play.

To pre-train the AI, we add an option to the game that allows two AIs to battle against each other -- say a hundred thousand times (after the training is working, try out different numbers as well!) -- and after that the player will be set to play against the trained AI.

But how do we know if our AI is working? One way is that the human wins fewer games against the computer. Another way is to look at the data in the tally arrays and check if the best moves show up as higher numbers.

Training AI, please wait...
n= 1     2     3     4     5     6     7     8     9    10
1= 1   136     1     5    89   225     6   120   241     1
2= 1     1  1474     1    11     4   359    19   152     1
3= 1     1     1  2365     8     2    10  3105    32     1
Part 2 Specifications
  1. In addition to the previous two options, add a third option (3) to play against a trained computer as shown in the Example Run below.
  2. After training the AI, print the contents of the first ten elements (boxes) of the arrays and ensure the tally pattern is similar to the Example Run below.

    Hint: see the printArray() function in funwork2.cpp. After submitting the assignment you may comment out or remove the display code to make playing the game more challenging.

  3. For the completed project, define between three and seven functions besides the main() function. At least one function must be called from another function besides main(). Use Stepwise Refinement to organize your code into functions.
  4. Define the functions after main() and their declarations (prototypes) before main().
  5. Example Run: The input prompts and outputs of the program must look like the following for full credit, including the same order of input and exact wording of the output. For the input shown you must get the similar output. However, the output must change properly if the inputs are different. The training data in particular will change each run, though the overall pattern of the moves will be the same.
    Welcome to the game of sticks!
    How many sticks to start with (10-100)? 10
    Play options:
    1. Play against a human
    2. Play against the computer
    3. Play against a trained computer
    Choice (1-3): 3
    Training AI, please wait...
    n= 1     2     3     4     5     6     7     8     9    10
    1= 1   136     1     5    89   225     6   120   241     1
    2= 1     1  1474     1    11     4   359    19   152     1
    3= 1     1     1  2365     8     2    10  3105    32     1
    
    There are 10 sticks on the board.
    Player 1: How many sticks to take (1-3)? 3
    AI takes 2
    
    There are 5 sticks on the board.
    Player 1: How many sticks to take (1-3)? 3
    AI takes 1
    
    There are 1 sticks on the board.
    Player 1: How many sticks to take (1-3)? 1
    
    You lose
    Play again (1 = yes, 0 = no)? 1
    
    There are 10 sticks on the board.
    Player 1: How many sticks to take (1-3)? 2
    AI takes 3
    
    There are 5 sticks on the board.
    Player 1: How many sticks to take (1-3)? 2
    AI takes 2
    
    There are 1 sticks on the board.
    Player 1: How many sticks to take (1-3)? 1
    
    You lose
    Play again (1 = yes, 0 = no)? 0
    

    In the above example run, the user entered the values shown in aqua italics (for emphasis) to produce the output. Your program does NOT print the characters in aqua italics, nor does the user input appear in aqua italics.

  6. Submit the source code file sticks8.cpp with the rest of the assignment as described in Deliverables.
Hints:
  • To train the AI, call moveAI() for both player 1 and player 2 for a hundred thousand times or so. However only save the player 2 results because the strategy for player 1 is different than for player 2.
  • To check and debug the AI, write code to display the contents of one or more arrays.
References and More Information
  1. Game of Sticks: from Stanford University Nifty Assignments
  2. BOXES: an Experiment in Adaptive Control: using the boxes AI paradigm for developing games like nim and tic-tac-toe

Extra Credit and Extensions

The following are optional and worth extra credit points if the main program works well:

  1. Complete the programming project using pair programming. (2 points)
  2. Create the correct spacing for the output of sticks8.cpp between each array element using the setw() formatting manipulator described on pages 49-51 (1/e: 53-55) of the textbook or here. (1 point)

    For example:

    cout << setw(WIDTH) << arr[i];
    

    To use this manipulator, include the iomanip library. For credit, the sticks8.cpp program must compile and function well enough to produce correct output.

Make certain that your README.txt file describes any extra credit attempted.

Tutorial Lab

In preparation for next weeks lessons, complete the following:

  1. Read the assigned reading in the textbook
  2. Complete the Tutorial Exercises in CodeLab 8 before the specified due date.

    Refer to the assigned reading for the next lesson to help you understand the problems. Also, you can use the online lecture notes for more information as the notes become available. You can look at solutions if you miss your first few attempts and are stuck by clicking the "Solution" tab.

Grading Criteria

The instructor will evaluate your assignment using the following criteria. Thus you should check your assignment against these criteria to maximize your score.

Each criteria represents a specific achievement of your assignment and has a scoring guide. The scoring guide explains the possible scores you can receive. Some scoring guides have a list of indicators. These indicators are a sign of meeting, or a symptom of not meeting, the specific criterion. Note that a single indicator may not always be reliable or appropriate in a given context. However, as a group, they show the condition of meeting the criterion.

For information on grading policies, including interpretation of scores, see the syllabus.

Lesson Exercises

  • 2: All lesson exercises attempted and turned in
  • 1: Some lesson exercises completed and turned in
  • 0: No lesson exercises completed or turned in

Function Worksheet

  • 5: All functions completed and program generates the correct output without error
  • 4: All functions completed but has a minor error
  • 3: Most functions completed or has some small errors
  • 2: At least half the functions completed or has some errors
  • 1: Few functions completed or has many errors
  • 0: Does not compile or wrong file turned in

Sticks 8 Project

  • 10: Demonstrates mastery of the assignment
    • Applies concepts from the lessons appropriately
    • Meets all specifications (see above) with particularly elegant solutions
    • Runs to completion with no abnormal error conditions
    • Generates correct output given correct input
    • Behaves in a reasonable way in response to incorrect data
  • 8: Has all the functionality expected of the assignment
    • Demonstrates many techniques from the lesson
    • Attempts to meet all specifications (see above)
    • Implementation seems more complicated than necessary.
    • May have one minor error
  • 6: Has most of the functionality expected of the assignment
    • Demonstrates some techniques from the lesson
    • Attempts to meet all but one of the specifications (see above)
    • Implementation seems excessively complicated.
    • May have 2-3 minor errors
  • 4: Has some of the functionality expected of the assignment
    • Demonstrates some techniques from the lesson
    • Attempts to meet at least 1/2 of the specifications (see above)
    • Implementation seems excessively complicated.
    • May have more than 3 minor errors
    • AI not correctly trained
  • 2: Serious functional problems but shows some effort and understanding
    • Attempts to meet less than 1/2 of the of the specifications (see above)
    • Has a major error or many minor errors
    • Implementation seems very convoluted
    • Demonstrates few techniques from the lesson
  • 1: Does not compile or wrong file turned in
  • 0: Does not execute, not turned in or uses techniques not covered in course

Program Style

  • 3: Code is well-documented including:
    • Correct file name used
    • Name, date, and program description in file comment block
    • Follows specified format for file comment block
    • Has a function comment block for all function declarations following the specified format
    • Proper use of spaces around operators
    • No tab characters are present in the source code
    • As described in How To Document and Organize C++ Code
    • Correct file name used
  • 2: Code has a minor documentation error
  • 1: Code has some documentation errors
  • 0: No apparent attempt to follow documentation standards or write documentation comments

CodeLab Exercises

Number completed correctly / number exercises * 8 and rounded up to the nearest integer.

README.txt File

  • 2: README.txt file submitted following the instructions
  • 1: README.txt file submitted but some information was missing
  • 0: No README.txt file submitted

Total possible: 30, plus extra credit

Deliverables

Submit your assignment to Canvas, in the assignment folder A8-Multi-Function Programs, following the instructions for submitting homework. Include the following items for grading:

  1. README.txt file
  2. All the exercise files from Lesson 8
  3. funwork2.cpp
  4. sticks8.cpp

You must submit all the files needed to complete your assignment. Your assignment must work as submitted. Remember to test and double check your files before submitting them. If you make a mistake, you can resubmit up to the deadline. If you resubmit, you must include all your assignment files in the last submission as Canvas hides prior submissions.

Last Updated: October 28 2018 @21:54:10