Random Wars

PA 7 — Due: Fri Nov 17 11pm CT

Recall the academic integrity policy: turn in your own work and cite all sources. Portions of the following are adapted from a post by Brian Hempel; his mercurial Ph.D. advisor is to blame for the rest.

Image Credit: WhiteDr4ag0n via Wikipedia
(CC BY-SA 4.0, no changes to original)

How long do wars last? That’s a difficult question involving complex factors. Sometimes there are dictators, sometimes there is scarcity, typically it is senseless.

The goal for this assignment is to answer that question for the simple case when war is completely random — that is, when two halves of a shuffled deck of cards go to war with each other.

The first two portions of this assignment attend to the representation of playing cards and the use of randomness to shuffle a deck. After that, you will develop a Monte Carlo simulation — a fancy way to say “using randomness” — to measure how long purely random wars last.

Starter Code

The starter code contains the following files, with several tasks to complete:

Representing Cards

Haskell provides expressive building blocks for representing custom data: type synonyms, datatypes, record type syntax, type classes, derived instances, and more that will we not cover in this course.

Representing the card values and suits in a standard 52-card deck is straightforward. (“Pip cards” and “numeral cards” are synonymous.)

data CardValue
  = King
  | Queen
  | Jack
  | PipCard Int -- From 1 to 10
      deriving (Show)

data Suit
  = Hearts
  | Diamonds
  | Spades
  | Clubs
      deriving (Show)

Then we might define a Card to be a pair of these.

data Card =
  Card CardValue Suit

We will order suits alphabetically. Less clear is how to represent two different standard orderings of card values: aces high and aces low. (The rules of war dictate that aces are high. But to implement Cards more generally so they may be used in different games, we will support the choice between aces high or aces low.)

Multiple Orderings

The essential question is: how to arrange two implementations of the following?

(<=) :: Card -> Card -> Bool

Option A

One option is to keep track of whether aces are high or low “off to the side.” We could define two separate functions

lessThanOrEquals_AcesHigh :: Card -> Card -> Bool
lessThanOrEquals_AcesLow  :: Card -> Card -> Bool

and then pick one depending on how acesHigh is configured for a game:

lessThanOrEquals :: Bool -> Card -> Card -> Bool
lessThanOrEquals acesHigh
  | acesHigh  = lessThanOrEquals_AcesHigh
  | otherwise = lessThanOrEquals_AcesLow

This would be fine for our little program. But ideally, we would actually plug our definitions of ordering into the Ord interface.

Option B: Run-Time Tags

Another option is to “hide” the different notions of ordering from the type system, embedding them entirely within the run-time behavior of Card-manipulating programs.

data Aces = AcesHigh | AcesLow           -- essentially a Bool

data Card =
  Card AcesHigh CardValue Suit

instance Ord Card where
  (<=) :: Card -> Card -> Bool
  Card acesHigh1 value1 suit1 <= Card acesHigh2 value2 suit2
    | acesHigh1 /= acesHigh2 =
        error "(<=) @Card: Don't mix aces-high and aces-low cards!"
    | acesHigh1 =
        ...
    | otherwise =
        ...

A downside is that we may accidentally mix aces-high and aces-low cards in the same deck. It is easy to avoid violating this intended invariant, but let’s strive for a more direct route. (This approach also suffers the minor affront that these ordering flags need to be carried around in the run-time data.)

Option C: Wrapper Types

A third option, which is common when multiple instances for the same type-and-class are desired, is to define wrapper types — distinct datatypes for each of the desired orderings:

data CardAcesHigh = CardAcesHigh Card
data CardAcesLow  = CardAcesLow  Card

instance Ord CardAcesHigh where
  (<=) :: CardAcesHigh -> CardAcesHigh -> Bool
  card1 <= card2 = ...

instance Ord CardAcesLow where
  (<=) :: CardAcesLow -> CardAcesLow -> Bool
  card1 <= card2 = ...

This would work out just fine. But if there were a suitable alternative that did not involve wrapping and unwrapping Card values, that would be preferable.

Option D: Phantom Types (The Winner!)

Our final approach combines the best of the above: we will define a single Card datatype (no wrappers) to be a member of Ord with two different implementations that are tracked completely at compile-time (no extra run-time data). The trick is to define Card with a phantom type variable.


data Card (a :: *) =
  Card CardValue Suit

Card now requires one type argument (Card has kind * -> *), but Card values do not rely on that type at all. So, we can instantiate that type argument however we like, for example:

> :set -fprint-explicit-foralls

> :t Card King Hearts
Card King Hearts :: forall {a}. Card a

> :t Card @Int King Hearts
Card @Int King Hearts :: Card Int

> :t Card @Bool King Hearts
Card @Bool King Hearts :: Card Bool

> :t Card @(Int -> Bool) King Hearts
Card @(Int -> Bool) King Hearts :: Card (Int -> Bool)

The type argument has no effect on how Card values are represented and manipulated at run-time. It does, however, allow the type system to distinguish between different types of Cards.

For our purposes, we will define two (singleton) types to represent different orderings…

data AcesHigh = AcesHigh
data AcesLow  = AcesLow

… and then define two instances for Card depending on its type argument:

instance Ord (Card AcesHigh) where
  (<=) :: Card AcesHigh -> Card AcesHigh -> Bool
  card1 <= card2 = ...

instance Ord (Card AcesLow) where
  (<=) :: Card AcesLow -> Card AcesLow -> Bool
  card1 <= card2 = ...

Interesting!

This general idea is not just a spooky Haskell trick. A quick search reveals enthusiastic blog posts about phantom types in F# (here’s the article from which I cribbed the photo above), Elm, Swift, Flow, TypeScript… Maybe there is hope for the world.

Your Tasks (Cards.hs)

1. Card Ordering

Implement the Ord (Card AcesHigh) and Ord (Card AcesLow) instances — and any instances upon which they depend. For full style points, rely on derived instances for CardValue and Suit to simplify the two Card-Ordering instances.

Hint: In addition to adding additional classes to the deriving clauses, you may reorder the data constructors in CardValue and Suit. (But make sure the data constructor definitions are otherwise exactly the same.)

2. Full Decks

Implement the following function to produce a full deck (52 cards) in ascending order, treating aces high (True) or low (False):

fullDeck :: Bool -> [Card a]

Each type of full deck is thus:

fullDeckAcesHigh :: [Card AcesHigh]
fullDeckAcesLow  :: [Card AcesLow]

fullDeckAcesHigh = fullDeck True
fullDeckAcesLow  = fullDeck False

For full style points, make good use of local variables (via let or where), lists, functions, etc. You should not, for example, write a list literal with 52, or 13, elements.

Tests

Check that your implementation produces:

> :load Tester

> fullDeckAcesHigh
[2♣,2♦,2♥,2♠,3♣,3♦,3♥,3♠,4♣,4♦,4♥,4♠,5♣,5♦,5♥,5♠,6♣,6♦,6♥,6♠,7♣,7♦,7♥,7♠,8♣,8♦,8♥,8♠,9♣,9♦,9♥,9♠,10♣,10♦,10♥,10♠,J♣,J♦,J♥,J♠,Q♣,Q♦,Q♥,Q♠,K♣,K♦,K♥,K♠,A♣,A♦,A♥,A♠]

> fullDeckAcesLow
[A♣,A♦,A♥,A♠,2♣,2♦,2♥,2♠,3♣,3♦,3♥,3♠,4♣,4♦,4♥,4♠,5♣,5♦,5♥,5♠,6♣,6♦,6♥,6♠,7♣,7♦,7♥,7♠,8♣,8♦,8♥,8♠,9♣,9♦,9♥,9♠,10♣,10♦,10♥,10♠,J♣,J♦,J♥,J♠,Q♣,Q♦,Q♥,Q♠,K♣,K♦,K♥,K♠]

Shuffling Cards

The next task is to support randomly shuffling a deck of cards — or any type of list, for that matter.

Randomness

A common requirement for computer programs is that there should be some randomness in the behaviour of the program. For this you need a random number generator, which can generate an unlimited sequence of random numbers. Typically these numbers are not truly random, but pseudo-random.

A pseudo-random number generator generates a sequence of numbers based on an initial state s using a function f. The states are s_1 = f (s), s_2 = f (f (s)), s_3 = f (f (f (s))), etc. Each random number is then derived from each of these intermediate states (typically by taking a small proportion of the 0’s and 1’s from the state).

The f function has to be chosen so that subsequent states have no obvious correlation, so for most intents and purposes the numbers generated are random, but the sequence of numbers is in fact entirely determined by the initial state s.

In many programming languages, the random number generator state is hidden from the programmer, but because of the purity of Haskell, the random number generator state must explicitly be passed through your program — or “implicitly” with stateful functions, as covered here.

Your Tasks (RawShuffle.hs)

To start, implement the following with “raw” stateful functions of the form StdGen -> (output, StdGen) — in such functions, StdGen is the type of “state objects” that are passed along.

3. Remove Random Element

Given a list, pick a random index into the list, then return the element at the given index as well as the list with that element removed. This is a basic function that can help you shuffle.

removeRandom :: [a] -> StdGen -> ((a, [a]), StdGen)

The uniformR library function is a handy way to generate an index:

uniformR :: (RandomGen g, UniformRange a) => (a, a) -> g -> (a, g)

Then (you are required to) define and use the helper function:

removeAt :: Int -> [a] -> (a, [a])

4. Shuffling

Next implement (deck) shuffling:

shuffle :: [a] -> StdGen -> ([a], StdGen)

Write this function recursively: (a) handling the base case for an empty list, and (b) handling the non-empty lists inductively by calling removeRandom and recursing.

A shuffling function should induce a uniform probability distribution over all permutations — all orderings of the cards should be equally likely. Test the uniformity of shuffles by looking at small decks and checking statistics.

Tests

Some deterministic tests (also accessible via cabal run tests):

> :load Tester

> let g0 = mkStdGen 22300
> let (out1, g1) = RawShuffle.removeRandom [1..5] g0
> let (out2, g2) = RawShuffle.removeRandom [1..5] g1
> let (out3, g3) = RawShuffle.removeRandom [1..5] g2
> (out1, out2, out3)
((4,[1,2,3,5]),(1,[2,3,4,5]),(3,[1,2,4,5]))

> let g0 = mkStdGen 22300
> let (list1, g1) = RawShuffle.shuffle [1..5] g0
> let (list2, g2) = RawShuffle.shuffle [1..5] g1
> let (list3, g3) = RawShuffle.shuffle [1..5] g2
> (list1, list2, list3)
([4,3,1,5,2],[3,1,5,2,4],[1,5,4,2,3])

And some non-deterministics tests via initStdGen :: IO StdGen :

> :load Tester

> fst . RawShuffle.removeRandom [1..5] <$> initStdGen
> fst . RawShuffle.removeRandom [1..5] <$> initStdGen
> fst . RawShuffle.removeRandom [1..5] <$> initStdGen

> fst . RawShuffle.shuffle [1..5] <$> initStdGen
> fst . RawShuffle.shuffle [1..5] <$> initStdGen
> fst . RawShuffle.shuffle [1..5] <$> initStdGen

Your Tasks (MonadicShuffle.hs)

Copy-paste your solutions from RawShuffle.hs…

5/6. Remove Random Element and Shuffling

… and then port the following definitions to now use the Monadic interface of State:

removeRandom :: [a] -> State StdGen (a, [a])
shuffle      :: [a] -> State StdGen [a]

For full style points, these should not call {run,eval,exec}State nor explicitly manipulate StdGen values. Use Functor-Applicative-Monad operations to hide such plumbing.

Tests

The deterministic test results should be the same. For example:

> (evalState $ MonadicShuffle.shuffle [1..5]) $ mkStdGen 22300
[4,3,1,5,2]

The random test results should be, well, random:

> (evalState $ MonadicShuffle.shuffle [1..5]) <$> initStdGen
> (evalState $ MonadicShuffle.shuffle [1..5]) <$> initStdGen
> (evalState $ MonadicShuffle.shuffle [1..5]) <$> initStdGen

Simulating War (RandomWars.hs)

How long do purely random wars last? Your final task is to design and implement a simulation that produces an answer to this question.

Your simulation should generally follow the rules of war between two players, starting with a full deck (done!), shuffling it (done!), dealing two halves (a small exercise), and then beginning battle. Keep going until one of the players runs of out cards, counting the number of turns along the way. Run some reasonable number of trials, and report the average number of turns among the completed trials.

To fend off games that are not converging, as well as buggy simulations, it is recommended to pick some threshold for maximum number of steps at which point a trial is abandoned. You can always increase, or remove, the threshold as you gain confidence that your simulation will terminate in a reasonable amount of time. In the meantime, be ready to killall random-wars (or some such) from another terminal.

This assignment does not specify every decision required to turn the rules of war into executable code. Such design decisions are for you to make, and document using comments.

Compared to the discussion about aces-high and aces-low orderings from before, in war — and many other card games — the suit does not actually contribute to the comparison, only the card value. It’s up to you how to handle this. For example, you could: add a third kind of ordering on Card values; refactor the CardValue type to take its own phantom type variable, passed down from the enclosing Card; or you could simply project CardValues out of the existing Card definitions. If you choose to make any changes to Cards themselves, please define a new Card type local to the RandomWars.hs file; do not make any changes to Cards.hs from before.

The main definition, triggered by

% cabal run random-wars

should run your experiment from start to finish. Choose a number of trials and other configuration parameters such that the running time is, say, between 1 and 60 seconds. We may or may not actually run your simulations. Instead, you should copy-and-paste the average number that comes out from one of your own invocations into the starter file:

howLongDoWarsLast :: Int

The point of this exercise is to write some beautiful code involving randomness, not to discover new truths about war. (But if you did, that would be some seriously functional programming…)

So, consider that a simple search about simulating war will turn up many endeavors similar to ours. It’s totally fine to read these and draw from their approaches — as usual, cite your sources, explain what you’ve learned from them, and how they influenced your work.

Constraints

Remember, the goal is to use the State StdGen monad to “automatically” thread the random number generators through your code; the bind (>>=) function will handle transmitting the state behind the scenes.

Your simulation should (i) call initStdGen only once, and (ii) call evalState only once when kicking off a call to simulateGames :: Int -> State StdGen [Int]. (And these two expressions are already in the starter code.)

To figure out if a function needs to be in the State StdGen monad, ask yourself, “If I call this function twice in sequence, do I want different results the second time?” If yes, the function needs to be monadic so the generator is properly transmitted from one call to the next. Also, the function itself should be used in a monadic context so calls to it are properly glued together with bind (>>=). That is, rely on the monad so you do as little explicit management of the state as possible.

If you find yourself using evalState (or runState) elsewhere, or are unpacking the generator in every random function, you are defeating the purpose of the State StdGen monad and will lose points. Handling the transmission of state is (>==)’s job.

Grading

Here is an outline of the grading rubric (10 points total):

Sanity Check

Once you are finished, check that you added, committed, and pushed everything to your repository before the deadline (or within an eligible late period):

https://github.com/UChicago-PL/cs223-fa23-pa-7-random-wars-USERNAME

Misc