This week’s Riddler at FiveThirtyEight reruns a puzzle initially run back in February. The game is a “war” between two warlords fighting over 10 castles. Each warlord has 100 soldiers, and the 10 castles are worth from 1 to 10 points each. If you send more soldiers to a given castle than your opponent, you win it and its point value; if you both send exactly the same number of soldiers, the point value for the castle is shared between the two. The winner of the war is the one with more total points, and so ties are possible overall only if you’ve shared at least one castle with an odd point value. The goal of the first Riddler challenge was to have the most success against all other entries in the contest.
They’ve made the entries from the first contest public, and so that gives one a chance to see not only the winners, but all the entrants, and to play around with the data. I quickly hacked up a perl script to take their data and compute the results of the first contest. That ran pretty slowly (doing head-to-head battles for all the nearly 1400 entrants took about 12 seconds on my laptop), but accurately. I then rewrote the code in C, and saw the same thing run in about a tenth of a second, two orders of magnitude faster.
This made me wonder whether brute force might be useful to attack the problem, so first I wrote a C program to count all the possible allocations of the 100 armies across 10 castles. This took, uh, a while to run – about 8 hours – but I got my answer – a little over 4.25 trillion combinations.
That didn’t sound too good, but I quickly modified code so I could start trying combinations in order against the prior entries, and print out any one that did as well or better than the best combination I now tried. Last Sunday night I kicked that program off on my laptop. A week later, the program is still running, and has only gone through about 6 billion combinations, but it did find a few which did better than the best performing entry last time, so I’m entering the best of those today.
I wanted to see if I could speed things up, and one way to do that was to test, not against nearly 1400 entries, but a subset. I figured that people might look at which ones did well last time, and try to do something similar, so my subset was the 179 entries that, by my calculations, won 70% or more of their head-to-head matchups in the prior contest. I found many combinations that beat all 179 of those, so I then tried to compare lots of those against the larger dataset. So far, that has not given me a better result against the whole set from the last contest, but I’m entering one of those also, on the theory that this week’s entries will tend to look more like the very good ones from the last time than the whole set.
So my first entry is:
0 0 2 2 11 21 3 31 26 4
I’ll update this post later with links to the code used to generate these.
Update Wenesday 31 May 2017:
I’ve created a github repository for the code I was using here:
https://github.com/GeoffBuchan/Riddler/tree/master/Castle
Also, I realized that when I first built the C programs, I did not add any optimization switches. The count.c program which took several hours to run before runs in under 10 minutes on my laptop now that I’ve added -O2 optimization with gcc. So if I’d done this in the first place, I’d have been able to search a lot further!