The Schnapsen Log
Group Theory and Random Sampling
Martin Tompa
I am going to break from our normal format for today’s column, in order to tell you about a very interesting scholarly article by Florian Wisser, a Ph.D. student at the Vienna University of Technology.
Wisser’s goal is to show that methods from Artificial Intelligence can be used to design the world’s best Schnapsen-playing computer program. He has already made remarkable progress toward this goal with a program whimsically named Doktor Schnaps. At the time of this writing, I have played 132 games against the good Doktor, and I can report that it is a very intimidating opponent! Wisser hasn’t yet found anyone who can beat Doktor Schnaps in 50% of games played, which is a great achievement, given how difficult it is to design programs that play such games of strategy at expert levels.
Some of the central ideas implemented in Doktor Schnaps are described in Wisser’s paper “Creating Possible Worlds Using Sims Tables for the Imperfect Information Card Game Schnapsen”, which was presented at the October 2010 22nd IEEE International Conference on Tools with Artificial Intelligence in Arras, France. Ideally, what the perfect Schnapsen program would do is to systematically go through all possible arrangements of the cards (where an “arrangement” means any possible hand the opponent could hold plus any possible ordering for the remaining face-down cards in the stock) and, for each such arrangement, analyze all possible plays by both players. The program would pick the play that maximizes the average game points gained, averaging over all possible arrangements. This averaging idea will be familiar to readers who have read my column on Expected Game Points.
Unfortunately, the number of possible arrangements at early tricks is prohibitively large. At the beginning of trick 5, as we’ve seen repeatedly in earlier columns, there are at most 6 possible arrangements: there are at most 6 cards that remain unseen and, once one of those cards is chosen as the face-down stock card, that determines the 5 remaining cards that comprise the opponent’s hand. One trick earlier, at trick 4, there are 8⋅7⋅6 = 336 possible arrangements. If we go all the way back to the beginning of trick 1, there are
14⋅13⋅12⋅11⋅10⋅9⋅8⋅7⋅6 = 726,485,760
possible arrangements. This is far too many to go through and analyze in a short time, even on a very fast computer.
Faced with too many things to inspect, what statisticians routinely do is to randomly sample a feasible but large enough number of the things, and assume that the random sample provides a good estimate for the entire collection. This is what Wisser wanted to do in the early tricks, sample randomly from the huge number of arrangements.
The challenge that he faced was that, by the time his program got to trick 4, he wanted it to systematically go through all 336 possible arrangements rather than sample from them randomly. Maybe he could even afford to go through all possible arrangements at trick 3, if he were using a fast enough computer. So, somehow, he wanted to make a graceful transition from random sampling to full enumeration of arrangements sometime between trick 1 and trick 4. This is where “Sims tables” come in, named for the mathematician Charles Sims who described them in a 1970 publication.
I am not going to explain Sims tables here, because they require somewhat sophisticated mathematics. Let’s just say that Sims tables rely on some concepts from Group Theory called permutation groups, quotient groups, and cosets, and leave it at that. Wisser’s first technical contribution was to extend Sims tables from permutation groups to quotient groups, where they provide an elegant mechanism for systematically going through all possible arrangements of the cards, no matter what trick you are up to. Wisser’s second technical contribution was to suggest a certain permuted ordering of this list of arrangements, with the property that, if you inspect the first x arrangements of this permuted ordering, the result will be very much like sampling x arrangements at random.
With these ideas, what Wisser could do was to set some reasonable time limit on each of his program’s moves (let’s say 15 seconds of elapsed time), let it start working its way through the permuted ordering of arrangements, and make it stop either when 15 seconds had elapsed or when it had gone through all the arrangements, whichever came first. In this way, in the early tricks the program would effectively be doing random sampling, and in the later tricks the program would be systematically going through all possible arrangements. Where it makes the transition depends automatically on the speed of the computer. It’s a clever and elegant solution, and the fact that it rests on Group Theory makes it all the more elegant.
And, as I can attest from many resounding personal defeats at the hands of the good Doktor, it has resulted in a very impressive Schnapsen program, the most intimidating opponent I have faced to date.
© 2012 Martin Tompa. All rights reserved.
