Some Design Patterns

The best way to learn object-oriented design is to look at patterns for common solutions to ubiquitous problems. These patterns are often described with a synopsis that gives you several essential features. The writer of a pattern will describe a programming context, the specific problem, the forces that lead to various kinds of solutions, a solution that optimizes the competing forces, and any consequences of choosing this solution.

There are a number of outstanding books on patterns. We’ll pick a few key patterns from one of the books, and develop representative classes in some depth. The idea is to add a few additional Python programming techniques, along with a number of class design techniques.

Most of these patterns come from the “Gang of Four” design patterns book, Design Patterns: Elements of Reusable Object-Oriented Software [Gamma95]. We’ll look at a few design patterns that illustrate some useful Python programming techniques.

Factory:This is a pattern for designing a class which is used as a factory for a family of other classes. This allows a client program to use a very flexible and extensible “Factory” to create necessary objects.
State:This is a pattern for desiging a hierarchy of classes that describes states (or status) and state-specific processing or data.
Strategy:This is a pattern that helps create a class that supports an extension in the form of alternative strategies for implementing methods.

Factory

When we add subclasses to a class hierarchy, we may also need to rearrange the statements where objects are created. To provide a flexible implementation, it is generally a good idea to centralize all of the object creation statements into a single extendable class. When we extend the subclass hierarchy we can also create a relevant subclass of the centralized object creation class.

The design pattern for this kind of centralized object creator can be called a Factory. It contains the details for creating an instance of each of the various subclasses.

In the next section, Components, Modules and Packages, we’ll look at how to package a class hierarchy in a module. Often the classes and the factory object are bundled into one seamless module. Further, as the module evolves and improves, we need to preserve the factory which creates instances of other classes in the module. Creating a class with a factory method helps us control the evolution of a module. If we omit the Factory class, then everyone who uses our module has to rewrite their programs when we change our class hierarchy.

Extending the Card Class Hierarchy. We’ll extend the Card class hierarchy, introduced in Inheritance. That original design had three classes: Card, FaceCard and AceCard.

While this seems complete for basic Blackjack, we may need to extend these classes. For example, if we are going to simulate a common card counting technique, we’ll need to separate 2-6 from 7-9, leading to two more subclasses. Adding subclasses can easily ripple through an application, leading to numerous additional, sometimes complex changes. We would have to look for each place where the various subclasses of cards were created. The Factory design pattern, however, provides a handy solution to this problem.

An object of a class based on the Factory pattern creates instances of other classes. This saves having to place creation decisions throughout a complex program. Instead, all of the creation decision-making is centralized in the factory class.

For our card example, we can define a CardFactory that creates new instances of Card (or the appropriate subclass.)

class CardFactory( object ):
    def newCard( self, rank, suit ):
        if rank == 1:
            return Ace( rank, suit )
        elif rank in [ 11, 12, 13 ]:
            return FaceCard( rank, suit )
        else:
            return Card( rank, suit )

We can simplify our version of Deck using this factory.

class Deck( object ):
    def __init__( self ):
        factory= CardFactory()
        self.cards = [ factory.newCard( rank+1, suit )
            for suit in range(4)
                for rank in range(13) ]
     Rest of the class is the same

Tip

Centralized Object Creation

While it may seem like overhead to centralize object creation in factory objects, it has a number of benefits.

First, and foremost, centralizing object creation makes it easy to locate the one place where objects are constructed, and fix the constructor. Having object construction scattered around an application means that time is spent searching for and fixing things that are, in a way, redundant.

Additionally, centralized object creation is the norm for larger applications. When we break down an application into the data model, the view objects and the control objects, we find at least two kinds of factories. The data model elements are often created by fetching from a database, or parsing an input file. The control objects are part of our application that are created during initialization, based on configuration parameters, or created as the program runs based on user inputs.

Finally, it makes evolution of the application possible when we are creating a new version of a factory rather than tracking down numerous creators scattered around an application. We can assure ourselves that the old factory is still available and still passes all the unit tests. The new factory creates the new objects for the new features of the application software.

Extending the Factory. By using this kind of Factory method design pattern, we can more easily create new subclasses of Card. When we create new subclasses, we do three things:

  1. Extend the Card class hierarchy to define the additional subclasses.
  2. Extend the CardFactory creation rules to create instances of the new subclasses. This is usually done by creating a new subclass of the factory.
  3. Extend or update Deck to use the new factory. We can either create a new subclass of Deck, or make the factory object a parameter to Deck.

Let’s create some new subclasses of Card for card counting. These will subdivide the number cards into low, neutral and high ranges. We’ll also need to subclass our existing FaceCard and Ace classes to add this new method.

class CardHi( Card ):
    """Used for 10."""
    def count( self ): return -1
class CardLo( Card ):
    """Used for 3, 4, 5, 6, 7."""
    def count( self ): return +1
class CardNeutral( Card ):
    """Used for 2, 8, 9."""
    def count( self ): return 0
class FaceCount( FaceCard ):
    """Used for J, Q and K"""
    def count( self ): return -1
class AceCount( Ace ):
    """Used for A"""
    def count( self ): return -1

A counting subclass of Hand can sum the count() values of all Card instances to get the count of the deck so far.

Once we have our new subclasses, we can create a subclass of CardFactory to include these new subclasses of Card. We’ll call this new class HiLoCountFactory. This new subclass will define a new version of the newCard() method that creates appropriate objects.

By using default values for parameters, we can make this factory option transparent. We can design Deck to use the original CardFactory by default. We can also design Deck to accept an optional CardFactory object, which would tailor the Deck for a particular player strategy.

class Deck( object ):
    def __init__( self, factory=CardFactory() ):
        self.cards = [ factory.newCard( rank+1, suit )
            for suit in range(4)
                for rank in range(13) ]
     Rest of the class is the same

The Overall Main Program. Now we can have main programs that look something like the following.

d1 = Deck()
d2 = Deck(HiLoCountFactory())

In this case, d1 is a Deck using the original definitions, ignoring the subclasses for card counting. The d2 Deck is built using a different factory and has cards that include a particular card counting strategy.

We can now introduce variant card-counting schemes by introducing further subclasses of Card and CardFactory. To pick a particular set of card definitions, the application creates an instance of one of the available subclasses of CardFactory. Since all subclasses have the same newCard() method, the various objects are interchangeable. Any CardFactory object can be used by Deck to produce a valid deck of cards.

This evolution of a design via new subclasses is a very important technique of object-oriented programming. If we add features via subclasses, we are sure that the original definitions have not been disturbed. We can be completely confident that adding a new feature to a program will not break old features.

State

Objects have state changes. Often the processing that an object performs depends on the state. In non-object-oriented programming languages, this state-specific processing is accomplished with long, and sometimes complex series of if statements. The State design pattern gives us an alternative design.

As an example, the game of Craps has two states. A player’s first dice roll is called a come out roll. Depending on the number rolled, the player immediately wins, immediately loses, or the game transitions to a point roll. The game stays in the point roll state until the player makes their point or crap out with a seven. The following table provides a complete picture of the state changes and the dice rolls that cause those changes.

Craps State Change Rules
State Roll Bet Resolution Next State
Point Off; the Come Out Roll; only Pass and Don’t Pass bets allowed. 2, 3, 12 “Craps”: Pass bets lose, Don’t Pass bets win. Point Off
  7, 11 “Winner”: Pass bets win, Don’t Pass bets lose. Point Off
  4, 5, 6, 8, 9, 10 No Resolution Point On the number rolled, p.
Point On; any additional bets may be placed. 2, 3, 12 No Resolution Point still on
  11 No Resolution Point still on
  7 “Loser”: all bets lose. The table is cleared. Point Off
  Point, p “Winner”: point is made, Pass bets win, Don’t Pass bets lose. Point Off
  Non-p number Nothing; Come bets are activated Point still on

The State design pattern is essential to almost all kinds of programs. The root cause of the hideous complexity that characterizes many programs is the failure to properly use the State design pattern.

The Craps Class. The overall game of craps can be represented in an object of class Craps. A Craps object would have a play1Round() function to initialize the game in the come out roll state, roll dice, pay off bets, and possibly change states.

Following the State design pattern, we will delegate state-specific processing to an object that represents just attributes and behaviors unique to each state of the game. We pan to create a CrapsState class with two subclasses: CrapsStateComeOutRoll and CrapsStatePointRoll.

The overall Craps object will pass the dice roll to the CrapsState object for evaluation. The CrapsState object calls methods in the original Craps object to pay or collect when there is a win or loss. The CrapsState object can also return an object for the next state. Additionally, the CrapsState object will have to indicate then the game actually ends.

We’ll look at the Craps object to see the context in which the various subclasses of CrapsState must operate.

craps.py

import dice
class Craps( object ):
    """Simple game of craps."""
    def __init__( self ):
        self.state= None
        self.dice= dice.Dice()
        self.playing= False
    def play1Round( self ):
        """Play one round of craps until win or lose."""
        self.state= CrapsStateComeOutRoll()
        self.playing= True
        while self.playing:
           self.dice.roll()
           self.state= self.state.evaluate( self, self.dice )
    def win( self ):
        """Used by CrapsState when the roll was a winner."""
        print "winner"
        self.playing= False
    def lose( self ):
        """Used by CrapsState when the roll was a loser."""
        print "loser"
        self.playing= False
  1. The Craps class constructor, __init__(), creates three instance variables: state, dice and playing. The state variable will contain an instance of CrapsState, either a CrapsStateComeOutRoll or a CrapsStatePointRoll. The dice variable contains an instance of the class Dice, defined in Class Definition: the class Statement. The playing variable is a simple switch that is True while we the game is playing and False when the game is over.

  2. The play1Round() method sets the state to CrapsStateComeOutRoll, and sets the playing variable to indicate that the game is in progress. The basic loop is to roll the dice and the evaluate the dice.

    This method calls the state-specific evaluate() function of the current CrapsState object. We give this method a reference to overall game, via the Craps object. That reference allows the CrapsState to call the win() or lose() method in the Craps object. The evaluate() method of CrapsState is also given the Dice object, so it can get the number rolled from the dice. Some propositions (called “hardways”) require that both dice be equal; for this reason we pass the actual dice to evaluate(), not just the total.

  3. When the win() or lose() method is called, the game ends. These methods can be called by the the evaluate() method of the current CrapsState. The playing variable is set to False so that the game’s loop will end.

The CrapsState Class Hierarchy. Each subclass of CrapsState has a different version of the evaluate() operation. Each version embodies one specific set of rules. This generally leads to a nice simplification of those rules; the rules can be stripped down to simple if statements that evaluate the dice in one state only. No additional if statements are required to determine what state the game is in.

class CrapsState( object ):
    """Superclass for states of a craps game."""
    def evaluate( self, crapsGame, dice ):
        raise NotImplementedError
    def __str__( self ):
        return self.__doc__

The CrapsState superclass defines any features that are common to all the states. One common feature is the definition of the evaluate() method. The body of the method is uniquely defined by each subclass. We provide a definition here as a formal place-holder for each subclass to override. In Java, we would declare the class and this function as abstract. Python lacks this formalism, but it is still good practice to include a placeholder.

Subclasses for Each State. The following two classes define the unique evaluation rules for the two game states. These are subclasses of CrapsState and inherit the common operations from the superclass.

class CrapsStateComeOutRoll ( CrapsState ):
    """Come out roll rules."""
    def evaluate( self, crapsGame, dice ):
        if dice.total() in [ 7, 11 ]:
            crapsGame.win()
            return self
        elif dice.total() in [ 2, 3, 12 ]:
            crapsGame.lose()
            return self
        return CrapsStatePointRoll( dice.total() )

The CrapsStateComeOutRoll provides an evaluate() function that defines the come out roll rules. If the roll is an immediate win (7 or 11), it calls back to the Craps object to use the win() method. If the roll is an immediate loss (2, 3 or 12), it calls back to the Craps object to use the lose() method. In all cases, it returns an object which is the next state; this might be the same instance of CrapsStateComeOutRoll or a new instance of CrapsStatePointRoll.

class CrapsStatePointRoll ( CrapsState ):
    """Point roll rules."""
    def __init__( self, point ):
        self.point= point
    def evaluate( self, crapsGame, dice ):
        if dice.total() == 7:
            crapsGame.lose()
            return None
        if dice.total() == self.point:
            crapsGame.win()
            return None
        return self

The CrapsStatePointRoll provides an evaluate() method that defines the point roll rules. If a seven was rolled, the game is a loss, and this method calls back to the Craps object to use the lose() method, which end the game. If the point was rolled, the game is a winner, and this method calls back to the Craps object to use the win() method. In all cases, it returns an object which is the next state. This might be the same instance of CrapsStatePointRoll ` or a new instance of :class:`CrapsStateComeOutRoll.

Extending the State Design. While the game of craps doesn’t have any more states, we can see how additional states are added. First, a new state subclass is defined. Then, the main object class and the other states are updated to use the new state.

An additional feature of the state pattern is its ability to handle state-specific conditions as well as state-specific processing. Continuing the example of craps, the only bets allowed on the come out roll are pass and don’t pass bets. All other bets are allowed on the point rolls.

We can implement this state-specific condition by adding a validBet() method to the Craps class. This will return True if the bet is valid for the given game state. It will return False if the bet is not valid. Since this is a state-specific condition, the actual processing must be delegated to the CrapsState subclasses.

Strategy

Objects can often have variant algorithms. The usual textbook example is an object that has two choices for an algorithm, one of which is slow, but uses little memory, and the other is fast, but requires a lot of storage for all that speed. In our examples, we can use the Strategy pattern to isolate the details of a betting strategy from the rest of a casino game simulation. This will allow us to freely add new betting strategies without disrupting the simulation.

One strategy in Roulette is to always bet on black. Another strategy is to wait, counting red spins and bet on black after we’ve seen six or more reds in a row. These are two alternate player strategies. We can separate these betting decision algorithms from other features of player.

We don’t want to create an entire subclass of player to reflect this choice of algorithms. The Strategy design pattern helps us break something rather complex, like a Player, into separate pieces. The essential features are in one object, and the algorithm(s) that might change are in separate strategy object(s). The essential features are defined in the core class, the other features are strategies that are used by the core class. We can then create many alternate algorithms as subclasses of the plug-in Strategy class. At run time, we decide which strategy object to plug into the core object.

The Two Approaches. As mentioned in Design Approaches, we have two approaches for extending an existing class: wrapping and inheritance. From an overall view of the collection of classes, the Strategy design emphasizes wrapping. Our core class is a kind of wrapper around the plug-in strategy object. The strategy alternatives, however, usually form a proper class hierarchy and are all polymorphic.

Let’s look at a contrived, but simple example. We have two variant algorithms for simulating the roll of two dice. One is quick and dirty and the other more flexible, but slower.

First, we create the basic Dice class, leaving out the details of the algorithm. Another object, the strategy object, will hold the algorithm

class Dice( object ):
    def __init__( self, strategy ):
        self.strategy= strategy
        self.lastRoll= None
    def roll( self ):
        self.lastRoll= self.strategy.roll()
        return self.lastRoll
    def total( self ):
        return reduce( lambda a,b:a+b, self.lastRoll, 0 )

The Dice class rolls the dice, and saves the roll in an instance variable, lastRoll, so that a client object can examine the last roll. The total() method computes the total rolled on the dice, irrespective of the actual strategy used.

The Strategy Class Hierarchy. When an instance of the Dice class is created, it must be given a strategy object to which we have delegated the detailed algorithm. A strategy object must have the expected interface. The easiest way to be sure it has the proper interface is to make each alternative a subclass of a strategy superclass.

import random
class DiceStrategy( object ):
    def roll( self ):
        raise NotImplementedError

The DiceStrategy class is the superclass for all dice strategies. It shows the basic method function that all subclasses must override. We’ll define two subclasses that provide alternate strategies for rolling dice.

The first, DiceStrategy1 is simple.

class DiceStrategy1( DiceStrategy ):
    def roll( self ):
        return ( random.randrange(6)+1, random.randrange(6)+1 )

This DiceStrategy1 class simply uses the random module to create a tuple of two numbers in the proper range and with the proper distribution.

The second alternate strategy, DiceStrategy2, is quite complex.

class DiceStrategy2( DiceStrategy ):
    class Die:
        def __init__( self, sides=6 ):
            self.sides= sides
        def roll( self ):
            return random.randrange(self.sides)+1
    def __init__( self, set=2, faces=6 ):
        self.dice = tuple( DiceStrategy2.Die(faces) for d in range(set) )
    def roll( self ):
        return tuple( x.roll() for x in self.dice )

This DiceStrategy2 class has an internal class definition, Die that simulates a single die with an arbitrary number of faces. An instance variable, sides shows the number of sides for the die; the default number of sides is six. The roll() method returns are random number in the correct range.

The DiceStrategy2 class creates a number of instances of Die objects in the instance variable dice. The default is to create two instances of Die objects that have six faces, giving us the standard set of dice for craps. The roll() function creates a tuple by applying a roll() method to each of the Die objects in self.dice.

Creating Dice with a Plug-In Strategy. We can now create a set of dice with either of these strategies.

dice1= Dice( DiceStrategy1() )
dice2 = Dice( DiceStrategy2() )

The dice1 instance of Dice uses an instance of the DiceStrategy1 class. This strategy object is used to constuct the instance of Dice. The dice2 variable is created in a similar manner, using an instance of the DiceStrategy2 class.

Both dice1 and dice2 are of the same class, Dice, but use different algorithms to achieve their results. This technique gives us tremendous flexibility in designing a program.

Multiple Patterns. Construction of objects using the strategy pattern works well with a Factory pattern, touched on in Factory. We could, for instance, use a Factory Method to decode input parameters or command-line options. This give us something like the following.

class MakeDice( object ):
    def newDice( self, strategyChoice ):
        if strategyChoice == 1:
            strat= DiceStrategy1()
        else:
            strat= DiceStrategy2()
        return Dice( strat )

This allows a program to create the Dice with something like the following.

dice = MakeDice().newDice(  :replaceable:`someInputOption` )

When we add new strategies, we can also subclass the MakeDice class to include those new strategy alternatives.

Design Pattern Exercises

Alternate Counting Strategy

A simple card counting strategy in Blackjack is to score +1 for cards of rank 3 to 7, 0 for cards of rank 2, 8 and 9 and -1 for cards 10 to King and Ace. The updates to the Card class hierarchy are shown in the text.

Create a subclass of CardFactory, which replaces newCard() with a version that creates the correct subclass of Card, based on the rank.

Six Reds

A common strategy in Roulette is to wait until six reds in a row are spun and then start betting on only black. There are three player betting states: waiting, counting and betting.

A full simulation will require a RouletteGame class to spin the wheel and resolve bets, a Wheel object to produce a sequence of random spins, and a Table to hold the individual bets. We’d also need a class to represent the Bet s. We’ll skim over the full game and try to focus on the player and player states.

A Player has a stake which is their current pool of money. The RouletteGame offers the Player an opportunity to bet, and informs the player of the resulting spin of the wheel. The Player uses a SixRedsState to count reds and bet on black.

The various SixRedsState classes have two methods, a bet() method decides to bet or not bet, and an outcome() method that records the outcome of the previous spin. Each class implements these methods differently, because each class represents a different state of the player’s betting policy.

counting:In the counting state, the player is counting the number of reds in a row. If a red was spun and the count is < 6, add one to a red counter and stay in this state. If a red is spun and the count is = 6, add one to a red counter and transition to the betting state. If black or green is spun, reset the count to zero.
:betting : In the betting state, the player is
betting on black. In a more advanced version, the player would also increase their bet for each red count over six. If a red was spun, add one to a red counter and stay in the betting state. If black was spun, transition to the counting state. If green was spun, transition to the counting state.

Caution

Caution

We’ll focus on the SixRedsState design. We won’t spend time on the actual betting or payouts. For now, we can simply log wins and losses with a print statement.

First, build a simple Player class, that has the following methods.

class Player
Player.__init__(self, stake)

Sets the player’s initial stake. For now, we won’t do much with this. In other player strategies, however, this may influence the betting.

More importantly, this will set the initial betting state of Counting.

Player.__str__(self) → string
Returns a string that includes the current stake and state information for the player.
Player.getBet(self) → Bet
This will use the current state to determine what bet (if any) to place.
Player.outcome(self, spin)
This will provide the color information to the current state. It will also update the player’s betting state with a state object returned the current state. Generally, each state will simple return a copy of itself. However, the counting state object will return a betting state object when six reds have been seen in a row.

Second, create a rudimentary RouletteGame that looks something like the following.

class RouletteGame
RouletteGame.__init__(self, player)
A RouletteGame is given a Player instance when it is constructed.
RouletteGame.__str__(self) → string
It’s not clear what we’d display. Maybe the player? Maybe the last spin of the wheel?
RouletteGame.play1Round(self)

The play1Round() method gets a bet from the Player object, spins the wheel, and reports the spin back to the Player object. A more complete simulation would also resolve the bets, and increase the player’s stake with any winnings.

Note that calling the Player‘s outcome() method does two things. First, it provides the spin to the player

RouletteGame.playRounds(self, rounds=12)
A simple loop that calls self.play1Round as many times as required.

For guidance on designing the Wheel used by the RouletteGame, see Class Variables and Function Definition: The def and return Statements.

State Class Hierarchy. The best approach is to get the essential features of RouletteGame, Wheel and Player to work. Rather than write a complete version of the player’s getBet() and outcome() methods, we can use simple place-holder methods that simply print out the status information. Once we have these objects collaborating, then the three states can be introduced.

The superclass, SixRedsState, as well as the two subclasses, would all be similar to the following.

class SixRedsState
SixRedsState.__init__(self, player)
The superclass initialization saves the player object. Some subclasses will initialize a count to zero.
SixRedsState.__str__(self) → string
The superclass __str__() method should return a NotImplemented value, to indicate that the superclass was used improperly.
SixRedsState.getBet(self) → bet
The getBet() method either returns None in the waiting and counting states, or returns a bet on red in the betting state. The superclass can return None, since that’s a handy default behavior.
SixRedsState.outcome(self, spin)
The outcome() method is given a tuple with a number and a color. Based on the rules given above, each subclass of SixRedsState will do slightly different things. The superclass can return NotImplemented.

We need to create two subclasses of SixRedState :

SixRedCounting:In this state, the getBet() method returns None ; this behavior is defined by the superclass, so we don’t need to implement this method. The outcome() method checks the spin. If it is Red, this object increments the count by one. If it is black it resets the count to zero. If the count is six, return an instance of SixRedBetting . Otherwise, return self as the next state.
SixRedBetting:In this state, the getBet() method returns a bet on Black; for now, this can be the string "Black". The outcome() method checks the spin. If it is Red, this object increments the count by one and returns self. If the spin is black it returns an instance of SixRedCounting. This will stop the betting and start counting.

Once we have the various states designed, the Player can then be revised to initialize itself with an instance of the wating class, and then delegate the getBet() request from the game to the state object, and delegate the outcome() information from the game to the state object.

Roulette Wheel Alternatives

There are several possible implementations of the basic Roulette wheel. One variation simply uses random.randrange() to generate numbers in the range of 0 to 37, and treats 37 as double zero. To separate double zero from zero, it’s best to use character string results.

Another strategy is to create a sequence of 38 strings (‘00’, ‘0’, ‘1’, etc.) and use random.choice() to pick a number from the sequence.

Create a superclass for WheelStrategy and two subclasses with these variant algorithms.

Create a class for Wheel which uses an instance of WheelStrategy to get the basic number. This class for Wheel should also determine whether the number is red, black or green. The Wheel class spin() method should return a tuple with the number and the color.

Create a simple test program to create an instance of Wheel with an instance of WheelStrategy. Collect 1000 spins and print the frequency distribution.

Shuffling Alternatives

Shuffling rearranges a deck or shoe of multiple decks; there are many possible algorithms. First, you will need a Card class to keep basic rank and suit information. Next, you will need a basic Deck class to hold cards. See Playing Cards and Decks for additional details.

We looked at shuffling in an earlier exercise, but packaged it as part of the Deck class, not as a separate strategy. See Advanced Class Definition Exercises. We can rework those exercises to separate shuffing from Deck.

The Deck class must have a shuffle() function; but this should simply call a method of the shuffle strategy object. Because the Deck is a collection of Card s, the Deck object should be passed to the shuffle strategy. The call would like something like this:

class Deck( object ):
     Other parts of Deck

def shuffle( self ): self.shuffleStrategy.shuffle( self )

Create a superclass for shuffle strategies. Create a subclass for each of the following algorithms:

  • For each card position in the deck, exchange it with a card position selected randomly
  • For even-numbered card position (positions 0, 2, 4, 6, etc.) exchange it with an odd-numbered card position, selected randomly (random.choice from 1, 3, 5, 7, 9, etc.)
  • Swap two randomly-selected positions; do this 52 times

Create a simple test program that creates a Deck with each of the available a Shuffle strategy objects.

Shuffling Quality

An open issue in the shuffling exercise is the statistical quality of the shuffling actually performed. Statistical tests of random sequences are subtle, and more advanced than we can cover in this set of exercises. What we want to test is that each card is equally likely to land in each position of the deck.

We can create a dictionary, with the key of each card, and the item associated with that key is a list of positions in which the card occured. We can evaluate a shuffle algorithm as follows.

Test A Shuffle

Setup. Create a Deck .

Create an empty dictionary, positions for recording card positions.

For each Card in the Deck, insert the Card in the positions dictionary; the value associated with the Card is a unique empty list used to record the positions at which this Card is found.

For Each Strategy. Perform the following evaluation for an instance of each Shuffle class, s.

Create Deck. Set the Deck‘s current shuffle strategy to s.

Shuffle. Shuffle the Deck.

Record All Positions. For each card in the deck, d.

Record Card Position. Locate the Card‘s position list in the positions dictionary; append the position of this Card to the list in the positions dictionary.

Chi-Squared. The chi-squared statistical test can be used to compare the actual frequency histogram to the expected frequency histogram. If you shuffle each deck 520 times, a given card should appear in each of the positions approximately 10 times. Ideally, the distribution is close to flat, but not exactly.

The chi-squared test compares sequence of actual frequencies, a, and a sequence of expected frequencies, e. It returns the chi-squared metric for the comparison of these two sequences. Both sequences must be the same length and represent frequencies in the same order.

\chi^2 = \sum_{0 \leq i \le n}\dfrac{(a_i-e_i)^2}{e_i}

We can use the built-in zip() function to interleave the two lists, creating a sequence of tuples of ( actual, expected ). This sequence of tuples can be used with the multiple-assignment for loop to assign a value from actual to one variable, and a value from expected to another variable. This allows a simple, elegant for statement to drive the basic comparison function.

Table Of Contents

Previous topic

Advanced Class Definition

Next topic

Creating or Extending Data Types

This Page