Psellos
Contemporary Development With Functional Programming

The Schnapsen Log

July 3, 2012

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.

Doktor Schnaps screenshot

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.


Comments

blog comments powered by Disqus

About the Author

Martin Tompa

Martin Tompa (tompa@psellos.com)

I am a Professor of Computer Science & Engineering at the University of Washington, where I teach discrete mathematics, probability and statistics, design and analysis of algorithms, and other related courses. I have always loved playing games. Games are great tools for learning to think logically and are a wonderful component of happy family or social life.

Read about Winning Schnapsen, the very first and definitive book on the winning strategy for this fascinating game.

Subscribe

Getting Started

Links for Schnapsen and Sixty-Six

Links in German

Links in Hungarian

Recent Columns

April
Homework on Expected Values, Apr 26
March
Thoughtful Actions, Mar 25
Noble Sacrifice, Mar 4
February
Carpe Diem, Feb 10
The Glass is 9/10 Full, Feb 2
January
The Battle and the War, Jan 17

Archives

2017
2016
2015
2014
2013
2012