Game of Risk

The last assignment in the CIS194 Haskell class is to simulate dice-throwing battles in the game of Risk. The combat rules, taken from assignment specs, are:

• There is an attacking army (containing some number of units) and a defending army (containing some number of units). 
• The attacking player may attack with up to three units at a time. However, they must always leave at least one unit behind. That is, if they only have three total units in their army they may only attack with two, and so on. 
• The defending player may defend with up to two units (or only one if that is all they have). 
• To determine the outcome of a single battle, the attacking and defending players each roll one six-sided die for every unit they have attacking or defending. So the attacking player rolls one, two, or three dice, and the defending player rolls one or two dice. 
• The attacking player sorts their dice rolls in descending order. The defending player does the same.
• The dice are then matched up in pairs, starting with the highest roll of each player, then the second-highest.
• For each pair, if the attacking player’s roll is higher, then one of the defending player’s units die. If there is a tie, or the defending player’s roll is higher, then one of the attacking player’s units die.

We assume it is optimal to always attack or defend with as many units as possible.

Given an initial number of attacking and defending units, what is the expected outcome (say, the probability that the attacker wins)? 

It's not obvious that there is a closed-form expression, but we can find programmatically the exact probabilities. 

First, from the game specs, we know that there are only a few primitive battle patterns (A, D), where A is attacked and D is defender: (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2). For each pattern, we can generate all possible permutations of die values. Each permutation represent a battle, with an outcome ("loss scenario") in which A and D both lose some number of units (which can be zero units, if they win all dice rolls).  

For example, for (A,D) of (1,1), both the attacker and defender role one die each, yielding 36 pairs of possible die rolls: (1,1), (1,2), (1,3) ... (6,5), (6,6). Tallying up the proportion of outcomes: A loses 1 unit 21 / 36; D loses 1 unit 15 / 36.

(Incidentally, the closed-form expression for 1 vs 1 is relatively simple: for each N that the defender rolls, with 1/6 probability each, the attacker loses in N/6 scenarios. For example, if the defender rolls 4, the attacker loses for all die values <= 4. So we can evaluate the expression (1/6) * (sum [1..6]) / 6, which equals 21/36. See these notes for a more detailed explanation.)

Once we have the loss scenarios with proportions for each primitive battle pattern, finding the exact win probability for the attacker is recursive: for any given starting pattern (A, D), lookup the relevant primitive battle pattern. For each loss scenario in which the attacker does not lose the game, update the battlefield with the losses and recursively lookup the next loss scenario, chaining the proportions (probabilities) until the game ends for each branch. 

The win probabilities for the attacker for patterns up to (10, 10) are:

The Haskell implementation for the above is in this gist. 

Using Rational numbers in Haskell allows the answers to be expressed exactly. For example for (4,2), the win probability for A is 6610505 % 10077696 (see the rightmost column here). 

Blacksmith Puzzle Solved

The blacksmith puzzle from a previous blog post is now solved!

I experimented with a number of heuristics, but I wasn't able to come up with a very good way to rank next moves.

In the end, the combinatorial solution works fine -- it's just that the solution space was unnecessarily polluted by permutations of the same visited states. Modifying the hash of visited states to use sorting ensures uniqueness, and the solution now runs in a few seconds. Interestingly, the magic number of 13 chain links appears to be necessary, as the solver didn't find a solution when fed 12 chain links as a starting state.

https://gist.github.com/tkuriyama/8de2711675350645349d

Russian Railroad Puzzle

This was a fun and quick puzzle as the technique from Peter Norvig's solution to the Zebra Puzzle can be reused directly. It's very nice to be able to formulate the conditions in terms that are clear and almost like plain English.

https://gist.github.com/tkuriyama/5a0f5d886a3578a72d58

Passengers in a Railroad Compartment 

Six passengers sharing a train compartment are from Moscow, Leningrad, Tula, Kiev, Kharkov, and Odessa.

1. A and the man from Moscow are physicians 
2. E and the Leningrader are teachers. 
3. The man from Tula and C are engineers. 
4. B and F are WWII veterans, but the man from Tula has never served in the armed forces. 
5. The man from Kharkov is older than A. 
6. The man from Odessa is older than C. 
7. At Kiev, B and the man from Moscow got off. 
8. At Vinnitsa, C and the man from Kharkov got off. 

Match initials, professions, and cities. Also, are the facts both sufficient and necessary to solve the problem? 

from Boris A Kordemksy, The Moscow Puzzles: 359 Mathematical Recreations, p111.

Blacksmith Khecho's Ingenuity

Another puzzle from Dover's Moscow Puzzles. Building on similar structures and ideas to The Whims of Three Girls, it was much easier to conceive and develop a combinatorial solution for this one.

However... the solution does not terminate!

Presumably this is due to the combinatorial search space being much larger -- even with a small sub-problem with two people weighing 20 and 30 pounds and six of the 10-pound chains, the solver finds 226 solutions.

Solution # 1 of 226 

[20, 30, 10, 10, 10, 10, 10, 10] | * [] --- []  | []
[10, 10, 10, 10, 10, 20, 30] |  [10] --- [] * | []
[10, 10, 10, 10, 20, 30] |  [10] --- [10] * | []
[10, 10, 10, 20, 30] | * [10] --- [10, 10]  | []
[10, 10, 10, 30] |  [10, 20] --- [10, 10] * | []
[10, 10, 10, 30] | * [10] --- [10, 10]  | [20]
[10, 10, 10, 10, 30] | * [] --- [10, 10]  | [20]
[10, 10, 10, 10] |  [30] --- [10, 10] * | [20]
[10, 10, 10, 10] | * [] --- [10, 10]  | [20, 30]

When I use the problem inputs, the solution candidate stack hovers rises steadily to about 1000 candidates, falls to 700 or so over a minute or two, and begins to rise steadily thereafter.

The optimization is interesting to think about because it is not obvious how to evaluate the merits of different states. The only trivial optimization I've done is to permit people to jump off the balance and crash it, if the move results in a complete puzzle (not explicitly addressed in the problem statement, and a plausible interpretation).

I will come back to this later as I haven't made much progress in the past day.

The Whims of Three Girls

3 girls, each with her father, go for a stroll. They come to a small river. One boat, able to carry 2 persons at a time, is at their disposal. Crossing would be simple for everyone except the girls. None is willing to be in the boat or ashore with 1 or 2 strange fathers, unless her own father is present too. How do they all get across?

I came across the above in a book of puzzles. It's an interesting exercise in modeling a game space and generating correct state progressions. I started working on a Haskell version with a friend but the full script is still well beyond my reach. Meanwhile, my Python version works reasonably well and BFS returns what appears to be a minimum-length solution in approximately 75 ms on my 2014 MacBook Pro.  This served as yet another lesson in the importance of modularity and testing to the end of writing code that's clear and correct. More practice required...

https://github.com/tkuriyama/fording-puzzle