Homework 09

[zender991]

Enumeration

All sequences of outcomes

Given a set of outcomes, a standard problem in combinatorics is to enumerateall possible sequences of outcomes formed by repeatedly choosing an outcome from the set. For this class page, we will restrict our attention to the case where repeated outcomes are allowed. This problem typically arises when one is analyzing the probabilities associated with a sequence of trials.

As a starting point, let's consider the question of how many sequences of length n are possible if the set of outcomes has size m. This question can be answered using a simple counting argument. There are mm choices for the first element in the sequence. Since repetitions are allowed, there are also mm choices for the second item and so on. In general, the number of sequences of length n is:

m * m * m * ... * m = m ** n

This program computes the set of all possible sequences of outcomes of a specified length using the function gen_all_sequences . Note that these functions represent sequences as tuples since the members of a set must be immutable. http://www.codeskulptor.org/#poc_enumeration.py

Sorted sequences of outcomes

In some applications, the ordering of the outcomes in each sequence is unimportant. For example, in most dice games (including Yahtzee), the two sequences of rolls (4, 3, 2, 1, 2) and (1, 2, 2, 3, 4) each represent the same hand. In cases such as these, it may make sense to treat these two sequences as being equivalent to improve the performance of your program.

A standard technique for accomplishing this goal is to group all sequences of outcomes that have the same number of instances of each outcome (but in different orders) in a single cluster and then choose a single representative sequence for this cluster. One simple choice for this representative is to take the sequence in which the outcomes appear in sorted (ascending) order. In the dice example in the previous paragraph, the sorted sequence (1, 2, 2, 3, 4) would be the representative sequence for all sequences that contain one 1, two 2's, one 3, and one 4. Your Yahtzee mini-project will use this idea and represent Yahtzee hands as a sorted tuple of die values to avoid having multiple representations for the same Yahtzee hand.

While building a function that directly generates these sorted sequences is possible, we note that a simpler approach is to generate all possible sequences, sort each individual sequence, and add them into a new set. Insertion into the set will automatically eliminate the duplicate sequences that arise from sorting. The function gen_sorted_sequences generates the set of all sorted sequences using this method. Note that this is a substantially smaller subset of the set of sequences produced by gen_all_sequences

Permutations and Combinations

In some cases where a sequence of trials is conducted, we would like to preclude having the same outcome occur twice. For example, consider the case of a lottery in which ping-pong balls are drawn one at a time from a lottery machine. Once the first ball is drawn, it is set aside and that ball cannot be redrawn later in the drawing process. In cases like this one, we are often interested in the number of possible sequences associated with this process.

This question is a well-studied one and two mathematical tools are available to help in the analysis. Both of these tools rely on a mathematical function that you may be familiar with. The factorial of a non-negative integer m (denoted m!) is the product of the numbers 1 * 2 * 3 *4 ... * (m - 1) * m. For example, 4! = 1 * 2 * 3 * 4 = 24. To simplify various formula involving factorials, 0!0! is defined to be 11. The factorial function can be accessed in Python using the math module. For example:
import math
print math.factorial(6)

Permutations

Given a set of outcomes, a sequence of outcomes of length n with no repetition is a permutation of size n of this set. For our lottery example, if the set of outcomes is {1,2,3,...,59}, the ordered sequence (34, 12, 27, 56, 58) is a permutation of length five. Observe that the sequence (23, 11, 23, 3, 47) would not be a permutation since the outcome 23 is repeated. Also, note that the permutation (34, 12, 27, 56, 58) is distinct from the permutation (56,12,27,34,58) since the ordering of the elements in the permutation matters.

A common question when working with permutations is "How many permutations of length n are possible given a set of outcomes of size m?" Computing the answer requires a little counting. In generating the ordered sequence associated with the permutation, there are m choices for the first element, m−1 choices for the second element, and so on, with m - n + 1 choices for the n-th element. Thus, in total, there are:

m * (m - 1) * ... * (m - n + 1)

possible permutations. This product can be conveniently written as m! / (m - n)! since all of the terms in products in the numerator and denominator that are less than or equal to m−n cancel out leaving the desired product.

Combinations

As was the case when repetition was allowed, the order of the resulting sequence may not matter in some applications. The standard technique for handling this situation is to group all sequences that correspond to the same set of outcomes in a single cluster. (Note we can use a set here instead of a sorted sequence since repetition is not allowed.) The sets of outcomes associated with each cluster is a combination of this set. For example, most lotteries require only that your set of numbers match those drawn during the lottery to win. The order in which the numbers are drawn is irrelevant. In this case, the sets {34, 12, 27, 56, 58} and {56, 12, 27, 34, 58} represent the same combination of lottery numbers.

The number of combinations of size n associated with a set of outcomes of size mm also has a simple formula in terms of factorials. As noted previously, there are (m−n)! / m! permutations of length n. These permutations can be grouped into clusters where all of the permutations in a single cluster involve the same outcomes, but in different orders. Note that in this model, each cluster corresponds to a combination. Since there are n!n! possible ordered sequences of outcomes in each cluster, the total number of possible combinations is m! / (m−n)!n!.

Mini-project Game Yahtzee

Yahtzee is a dice game played with 5 dice where you try to score the most points by matching certain combinations. You can play the game here https://cardgames.io/yahtzee/ . In Yahtzee, you get to roll the dice three times on each turn. After the first roll, you may hold as many dice as you would like and roll the remaining free dice. After this second roll, you may again hold as many dice as you would like and roll the rest. Once you stop (either because you have exhausted your three rolls or you are satisfied with the dice you have), you score the dice in one box on the score card.

For this mini-project, we will implement a strategy function designed to help you choose which dice to hold after your second roll during the first turn of a game of Yahtzee. This function will consider all possible choices of dice to hold and recommend the choice that maximizes the expected value of your score after the final roll.

To simplify the mini-project, we will only consider scores corresponding to the "upper" section of the scorecard. Boxes in the upper section correspond to numbers on the dice. After each turn, you may choose one empty box and enter the sum of the dice you have with the corresponding number. For example, if you rolled (2, 3, 3, 3, 4), you could score 2 in the Twos box, 9 in the Threes box, or 4 in the Fours box. (Restricting scoring to the upper section will also allow you to debug/test your strategy function on smaller numbers of dice.)

Testing your mini-project

The provided template http://www.codeskulptor.org/#poc_yahtzee_template.py includes the function gen_all_sequences as well as a run_example function that you may modify as you see fit while developing, debugging, and testing your strategy function. The template includes the stubs for the four functions that you will need to implement for this mini-project. Remember you should be testing each function as you write it. Don't try to implement all of the functions. If you do, you will have errors that will interact in inexplicable ways making your program hard to debug.

If you try to test your code with five dice, it will be more difficult to understand what is going on. Instead, we recommend that you should test first with two dice. In particular, you may want to work out some examples by hand with two dice and create a small test suite that checks these examples.

Finally, submit your code (with the calls to run_example commented out) to this Owltest page http://codeskulptor.appspot.com/owltest?urlTests=poc.poc_yahtzee_tests.py&urlPylintConfig=poc.pylint_config.py . This page will automatically test your mini-project. It will run faster if you comment out the call to run_example before submitting.

Implementation

Your task is to implement the following four functions: score, expected_value, gen_all_holds, and strategy. These four functions should do the following:

• score(hand): This function takes as input a tuple hand that represents the die values in the given Yahtzee hand. Since ordering of the die values in Yahtzee hands is unimportant, tuples corresponding to Yahtzee hands will always be stored in sorted order to guarantee that each tuple corresponds to a unique Yahtzee hand. The function score(hand) computes a score for hand as the maximum of the possible values for each choice of box in the upper section of the Yahtzee scorecard.
• expected_value(held_dice, num_die_sides, num_free_dice): This function computes the expected value of the scores for the possible Yahtzee hands that result from holding some dice and rolling the remaining free dice. The dice being held are specified by the sorted tuple held_dice. The number of sides and the number of dice that are free to be rolled are specified by num_die_sides and num_free_dice, respectively. You should use gen_all_sequences to compute all possible rolls for the dice being rolled. As an example, in a standard Yahtzee game using five dice, the length of held_dice plus num_free_dice should always be five.
• gen_all_holds(hand): This function takes a sorted tuple hand and returns the set of all possible sorted tuples formed by discarding a subset of the entries in hand. The entries in each of these tuples correspond to the dice that will be held. If the tuple hand has the entries (h[0], h[1], ..., h[m-1]), the returned tuples should have the form (h[i0], h[i1], ..., h[i(k-1)]) where 0 ≤ k ≤ m and the integer indices satisfy 0 ≤ i[0] < i[1] < ... < i[k-1] < m. In the case where values in the tuple hand happen to be distinct, the set of tuples returned by gen_all_holds will correspond to all possible subsets of hand.
• strategy(hand,num_die_sides): This function takes a sorted tuple hand and computes which dice to hold to maximize the expected value of the score of the possible hands that result from rolling the remaining free dice (with the specified number of sides). The function should return a tuple consisting of this maximal expected value and the choice of dice (specified as a sorted tuple) that should be held to achieve this value. If there are several holds that generate the maximal expected value, you may return any of these holds.

Coding gen_all_holds

Implementing gen_all_holds is one of the main challenges of this mini-project. While its implementation is short, the actual code requires thought. Since tuples are immutable, your algorithm for computing the required set of tuples cannot directly delete from the tuple hand. Instead, gen_all_holds should compute the set of all possible holds in a manner very similar to that of gen_all_sequences. In particular, your implementation should iterate over the entries of hand and compute all possible holds for the first k entries in hand using all possible holds for the first k - 1 entries of hand.