by ·2 Comments

When I was a kid, one of my favorite card games was War. In retrospect, I don’t really understand why I got so much enjoyment out of it, given that there is absolutely no strategy to the game whatsoever. If you happened to miss this game during your childhood, the rules are simple:

The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the process is repeated until there is no tie.

A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck face-up and still have a chance to stay in the game.

As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.

The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.

It turns out that the answer is “about 277” (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.

Continue reading

by ·0 Comments

Today brings us, at long last, the latest installment in my article series on exploration of the Lottery Problem.

In the previous article, I discussed the design decisions that were made in the greedy lottery wheel generator in order to get around the computational problems inherent in even a simple greedy generator for realistically-sized lotteries. In this article, I will walk through the mechanics of generating all tickets and matches, selecting a ticket for the wheel, and updating ticket meta-data in order to allow the next selection.

You can read the whole article here. In essence, this is a walkthrough, using text, diagrams, and pseudocode, of how exactly I went about implementing a greedy algorithm based lottery wheel generator. This article addresses my solutions to problems of time complexity, much as the previous article largely addressed the solutions to problems of space complexity.

The actual generator was implemented in, of course, C++. However this article contains no actual code, only pseudocode, so as to put emphasis on the algorithms and not the details. Besides, full details of any program can only really be understood by reading code itself, not descriptions of it with snippets. I have still not yet made available the source code to this generator, although that will be forthcoming. Hopefully I will have it cleaned up enough to be suitable for public consumption before the next article in the series is posted.

by ·0 Comments

The newest article in my series on the Lottery Problem describes the design decisions I made when making my first attempt at an implementation of an efficient wheel generator based on the simple greedy algorithm for set cover. The design decisions described were influenced by three key insights I had when considering how one might attempt to generate a close-to-optimal wheel for a 6-from-49 lottery in a reasonable amount of time.

  1. Once the relationships between tickets have been completely expressed, the actual numbers that constitute the tickets are of no significance and can be discarded.
  2. It is only necessary to keep track of how many uncovered tickets an unselected ticket could potentially cover if selected. It is unnecessary to know exactly which tickets those are.
  3. Every ticket initially covers the same number of other tickets, and this number can be computed through combinatorics alone.

You can read the full article here. It primarily addresses the challenges involved in expressing the problem within a reasonable amount of memory, and gives an overview of how the computation will be approached. The computation itself will be described in detail in the next article.

by ·0 Comments

I can’t remember exactly how I got there (I suspect that Wikipedia was involved), but some weeks ago I ended up reading the UK National Lottery Wheeling Challenge website. The “challenge” involved is to generate a lottery wheel as small as possible for winning at least £10 in the United Kingdom’s national lottery. What exactly is a wheel, and why should it be small? To quote my own introduction:

A lottery wheel is a set of tickets for a lottery drawing which, if purchased in its entirety, guarantees a certain type of win, according to the rules of the lottery, no matter which ticket is actually drawn. […] The goal is straightforward. Each ticket we purchase costs money, so we want to generate a lottery wheel that is as small as possible while still guaranteeing a win of some minimum desired prize.

Now, obviously, such a thing no matter how good is not going to let you turn playing the lottery into a reliable money-maker, but in fact the reason that this is interesting has nothing to do with actually playing the lottery. I’ve only bought one lottery ticket in my entire life, and needless to say I lost.

The reason that this was initially interesting to me was that the site showcased a wheel of 163 tickets, which seems quite good for a 6-from-49 lottery, but went on to solicit for better wheels (indicating that the 163-ticket wheel was not known to be optimal) and to note that no wheel generation algorithm was known. The more I thought about how to create a generation algorithm, the more intriguing the problem became. The problem turns out to be a very special, highly symmetric form of minimum set covering. From what I was able to find, this problem has been studied academically, but with minimal results, and rarely on realistically-sized problems.

So, inspired by this, I set out to do two things: write a program that runs in a reasonable amount of time on a modern personal computer that can generate good lottery wheels for realistically-sized lotteries, and if possible prove whether this problem is NP-Hard or not.

I am documenting this project in a series of articles on the lottery problem. To start with, I have posted the first three articles which describe the problem, its relationship to set covering, and the challenges involved in implementing a generator algorithm for realistically-sized lotteries. Further articles will be posted later documenting my progress on the problem.