Assignment 2: Telephone game

Adhere to the Code of Academic Integrity. You may discuss background issues and general strategies with others and seek help from course staff, but the implementations that you submit must be your own. In particular, you may discuss general ideas with others, but you may not work out the detailed solutions with others. It is never OK for you to see or hear another student’s code and it is never OK to copy code from published/Internet sources. If you feel that you cannot complete the assignment on you own, seek help from the course staff.

Do not use the break, continue, and return statements in any homework or test in CS 1132. Furthermore, use only the built-in functions that we have discussed in class (lecture and lab). The purpose of this assignment is to give you practice on the important concepts learned in the course, not to avoid using those concepts by looking up other functions.

The popular game of “telephone” is often used to illustrate the effects of cumulative error in human communication. To start the game, all players form a line, and the first player comes up with a message and whispers the message to the second player. The second player then whispers the received message to the third, and this process is repeated until it reaches the last player in the line. The last player then announces what they understand the message to be, and this is compared with the initial message. The objective of the game is to pass the message with minimal corruption. Any error within each communication step accumulates, typically leading to a final message that is humorously divergent from the original.

In this assignment, you are asked to simulate a generalized version of this game, where each player randomly picks the next player to whisper to from a set of neighbors. You will do this by first implementing a function to simulate a single random step, and then implementing a function to simulate the entire sequence of whispers from the starting player to a “goal” player. Finally, you will write a script to analyze empirical statistics of the game and visualize how they change as the number of players increases.

Single whisper

The n players in a game form a network whose connectivity is indicated by an n-by-n matrix A, often called an adjacency matrix (see notes from lecture 5). A value 1 in A(i,j) indicates that the player indexed by i is reachable by the player indexed by j. In our game, player j being able to reach (whisper to) player i does not necessarily imply that player i can whisper back to player j. The main diagonal of A contains zeros since a player does not pass a message to themself.

Each step—a single whisper—is governed by the adjacency matrix and another matrix indicating the probability that a message passed from one player to another gets corrupted during communication. Implement the following function as specified:

function [nextPlayer, corrupted] = whisper(A, E, player)
% Simulate a single whisper of the telephone game on network `A`.
% A: a square (n-by-n) matrix indicating the connections among n players. 
%   A(i,j)=1 indicates that player i is reachable by player j; A(i,j)=0 
%   otherwise.  Assume that the number of rows is at least 4. 
% E: error probability when i hears from j.  E has the same size as A.
% player: the person who attempts to pass a message; player is a column 
%   index of A.
% nextPlayer: the person who receives the message.  nextPlayer is equally 
%   likely to be any of the people reachable by player.  nextPlayer is a  
%   row index of A.  
% corrupted: 1 if the message from player to nextPlayer has been corrupted;
%   0 othewise.
% If player cannot pass the message to anyone else on the network then 
%   nextPlayer is 0 and corrupted is 0.

Test your function! Start a script a2test and write code in it to test your function:

You need an adjacency matrix. You may hardcode one, or you can use the function RandomLinks() from lecture 5 to generate one. Create a small test case, e.g., A=RandomLinks(5), for a random 5-player network. Adjust A as necessary to allow you to test both the case when the initial player has reachable neighbors and the case when the initial player does not have any reachable neighbor.
Hardcode or generate an error probability matrix, e.g., E=rand(5,5). You can also test the extreme cases when E contains only 1s (message always corrupted) or contains only 0s (message never corrupted).
Make several calls to your whisper() function with different starting players. Do the results look right given your matrices A and E?

You will submit your file a2test.m to document your testing. We are not looking for specific formal tests, but you must show evidence that you were able to invoke your function and interpret its results. Get comfortable with each function via tests before moving on to the next part of the assignment.

Sequence of whispers to reach goal player

Given the whisper function above, we can simulate the entire telephone game on a network. We start the game with a given player and continue the game until either the message reaches the goal player, a maximum allowed number of whispers have been made, or a player cannot pass the message onward given the adjacency matrix. By making effective use of function whisper, implement the following function as specified:

function [path, nCorruptions, finish] = telephone(A, E, st, gl, maxW)
% Simulate a game of telephone from player st until a message reaches
%   player gl, until a receiver of a whisper cannot be found, or until maxW 
%   whispers have been made, whichever occurs first.
% A: a square (n-by-n) matrix indicating the connections among n players. 
%   A(i,j)=1 indicates that player i is reachable by player j; A(i,j)=0 
%   otherwise.  Assume that the number of rows is at least 4. 
% E: error probability when i hears from j.  E has same size as A.
% st: index of starting player, st is a column index of A.
% gl: index of goal player, gl is a row index of A not equal to st.
% maxW: maximum number of whisper attempts allowed in the game
% path: a row vector storing the path of the message such that path(k) is
%   the index of the person making the kth whisper.  So path(1) stores st
%   and the last entry in path is the final recipient of the message.
% nCorruptions: the number of corruptions made when passing the message in 
%   the game. 
% finish: 1 if goal player is reached; 0 otherwise

Note that the length of path should be 1 greater than the number of whispers made.

Test your function in script a2test using the small network that you have created for your previous tests. Display the values returned from calling your function telephone(). Do they make sense?

Game statistics

Now we are interested in the statistics of the telephone game as we increase n, the number of players. Suppose the network has a connectivity given by function RandomLinks() of lecture 5, i.e.,

$$ A(i,j) = \begin{cases} 1 \text{ with probability } \frac{1}{1 + \left| i-j \right|} & \text{if $i \neq j$} \\ 0 & \text{otherwise} \end{cases} $$

In other words, there is more likely to be a connection if i is close to j. We are interested in answering the following questions:

What is the probability that one player can pass a message to a target player in no more than 2n whispers?
Considering only the cases when the target player is reached with no more than 2n whispers, on average how many whispers are made and how many corruptions are there?

Since the connectivity between players is not uniformly random, you will evaluate two scenarios:

Scenario 1: Player 1 attempts to reach player n (the player farthest away)
Scenario 2: One player attempts to reach another who is 2 indices away, e.g., player floor(n/2) attempts to reach player floor(n/2)+2.

Write a script a2sim to simulate the telephone game and produce two figures that answer the above questions. Since there is variability in both the random network (adjacency matrix) generation and in the random selection of a receiver of a message from the set of reachable neighbors, you will need the following simulations:

For each of nSize=10 network sizes ranging from 10 to 100:
- Generate nNetworks=100 networks (adjacency matrices). For each network:
  - Simulate nTrials=50 games of Scenario 1
  - Simulate nTrials=50 games of Scenario 2

Parameterize your script by using variables for nSize, nNetworks, and nTrials (and optionally other constant quantities) wherever those values are needed.

For simplicity we will use uniform probability for the error matrix, E=rand(n,n), where n is the size of the network. Furthermore, for each size network you can use just one error matrix for all the game simulations. Notice that you will have, for each size of network, nNetworks×nTrials simulation runs of Scenario 1 and nNetworks×nTrials simulation runs of Scenario 2. With those simulation results, produce these figures:

Probability of reaching the goal player as a function of n. No more than 2n whispers are allowed in the game. The x-axis shows n, which ranges from 10 to 100. The y-axis shows the probability. Recall that the probability of an event can be approximated as the number of times that the event happens divided by the number of trials in the experiment. There are two curves on this figure, one for Scenario 1 and the other for Scenario 2.
Average number of whispers and errors as a function n. No more than 2n whispers are allowed in the game. The x-axis shows n, which ranges from 10 to 100. The y-axis shows the average counts. There are two curves (number of whispers, number of errors) for each scenario, so four curves in all.

Be sure to give each figure a title, label the axes, and label the curves; the relevant built-in functions for the figures include figure, plot, title, xlabel, ylabel, and legend.

Program organization and development hints

Make a plan for how you will store the data from the simulation runs in order to calculate the statistics. Do you need to store all the returned values? How many are there? How will 1-d arrays and 2-d arrays be useful? Take some time to think about data storage before you code.
Make effective use of nested loops and/or local functions in order to avoid duplicating code. If you find yourself copying code from one part of your script to paste to another part, it is a sign that you should re-organize that to-be-duplicated code as a local function instead, and/or nest a loop to carry out the repetition instead of duplicating the code. (An exception is the code needed for drawing the figures; you will write similar but separate code for each figure.)
During program development, use a small number of trials to speed up testing! You don’t need to start with 10 sizes of network, 100 networks of each size, and 50 runs of each network. Use smaller values, e.g., just 4 sizes, 20 networks of each size, and 10 runs of each network when you develop your code. Once you get the code working then do the full set of simulation runs as specified.

Self-check list

The following is a list of the minimum necessary criteria that your assignment must meet in order to be considered satisfactory. Failure to satisfy any of these conditions will result in an immediate request to resubmit your assignment. Save yourself and the graders time and effort by going over it before submitting your assignment for the first time. Although all these criteria are necessary, meeting all of them might still not be sufficient to consider your submission satisfactory. We cannot list everything that could be possibly wrong with any particular assignment!

Comment your code! Make sure your functions are properly commented, regarding function purpose and input/output parameters. If the function specification is given in this document, just copy it exactly to your function file!
Make sure your functions’ names are exactly the ones we have specified, including case.
Check that the number and order of input and output parameters for each of the functions match exactly the specifications we have given.
Suppress unnecessary output by ending assignment statements with semicolons (;). At the same time, make sure that all output that your program intentionally produces is formatted in a user-friendly way.
Test each one of your functions independently, whenever possible, or write short scripts to test them.
Check that your scripts do not crash (i.e., end unexpectedly with an error message) or run into infinite loops. Check your script several times in a row. Before each test run, type the commands clear all; close all to delete all variables in the workspace and close all figure windows.

Submission instructions

Upload your files whisper.m, telephone.m, a2test.m, and atsim.m to CMS before the deadline. Late submission is accepted up to 24 hours after the deadline with a 10% penalty. If you upload or re-upload any file during the late submission period, the 10% penalty will apply to the whole assignment.
Submission will be closed during grading. After grading, we will re-open CMS for A2 resubmission. If you want to resubmit the assignment, upload your corrected files and be sure to click the Request Regrade button. If you don’t click that button, the course staff will not be notified of your resubmission.