## Tuesday, September 27, 2011

### Set Competition

As an applied probability exercise, I had my class compute empirically the probability of a game failing on the nth round for the game of Set.  (See my previous post about this;  here failure means there's no set on the nth round, and they were asked to implement the "choose a random set" strategy if there was more than one.)  They were also supposed to try to calculate the probability of using all 81 cards in sets through the course of the game -- what we might call a perfect game.

Some students explored a bit and noted that changing from the random strategy could significantly increase the probability of a perfect game.  So I think the next time I decide to use this assignment, I'll turn it into a competition.  Students will have to develop a strategy that maximizes the probability of achieving a perfect game.  Prizes will go to the best strategy (which hopefully could be easily determined after a few billion runs or so -- I suppose I'll have to introduce some sort of computational limits on the strategy to ensure that many runs can be done in a suitable time frame), and the best "succinct" strategy -- that is, the best strategy that can be described in English in at most a few reasonable sentences.

It's also interesting to think about optimal strategies in the offline case, where the permutation determining how the cards will be dealt out is given in advance.  I keep thinking maybe there's a way to effectively calculate whether a perfect game can be found for a given permutation, and then thinking there can't be.  (Though, admittedly, I haven't thought a lot yet.)  So maybe it makes sense to run the competition for both the online and offline versions of the problem.