# 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.