Zwei Briefumschläge und ein probabilistisches Wunder

Zur Abwechslung kommt heute einmal wieder etwas Mathematisches. Rom Pinchasi hat bei uns zum Abschied heute eine Vorlesung über mathematische Puzzles gehalten, und ein besonders Schönes und Überraschendes möchte ich hier kurz vorstellen.

Wir sind Teilnehmer in einer Quiz-Show. Der Quiz-Master zeigt zwei verschlossene Briefumschläge, A und B. In beiden steckt jeweils ein Papier mit einer Zahl darauf. Wir wissen, dass die beiden Zahlen verschieden sind, aber darüber hinaus haben haben wir keinerlei weitere Informationen. Nun müssen wir ansagen, in welchem Briefumschlag die größere Zahl steckt. Wenn unsere Ansage richtig war, kommen wir in die nächste Runde des Wettbewerbs, andernfalls scheiden wir aus.

Was ist das Beste, das wir in dieser Situation können?

Die naheliegende Strategie ist, zufällig einen der beiden Briefumschläge auszuwählen. Dann kommen wir mit Wahrscheinlichkeit 1/2 in die nächste Runde.

Gibt es eine bessere Strategie? Die Intuition sagt Nein. Aber können wir das auch beweisen?

Für einen richtigen Beweis muss das Szenario richtig formalisiert werden. Vor allem müssen wir uns überlegen, was eigentlich zu beweisen ist. Es könnte zum Beispiel sein, dass immer der Umschlag A die größere Zahl enthält. Dann gibt es natürlich eine bessere Strategie. Dies wird auch nicht dadurch ausgeschlossen, dass wir nicht wissen, dass der Umschlag A immer die richtige Antwort ist. Aussagen über Wissen sind notorisch schwer handzuhaben.

Die Lösung besteht darin, den Quiz-Master als Gegenspieler zu verstehen. Wir wollen Folgendes beweisen: Der Quiz-Master kann sich so verhalten, dass wir höchstens mit Wahrscheinlichkeit 1/2 in die nächste Runde kommen können, egal welche Strategie wir verwenden. Also: es existiert eine Strategie für den Quiz-Master, so dass für alle möglichen Strategien, die wir verwenden können, gilt: wir kommen höchstens mit Wahrscheinlichkeit 1/2 weiter.

Und das ist ganz einfach. Der Quiz-Master schreibt die beiden Zahlen auf, und wählt dann zufällig aus, welche Zahl er in welchen Umschlag steckt. Das macht er im Geheimen, so dass unsere Ansage, in welchem Briefumschlag die höhere Zahl steckt, stochastisch unabhängig von der zufälligen Wahl des Quiz-Masters ist.

Um unsere Erfolgswahrscheinlichkeit zu analysieren, sollten wir zuerst ein paar Wahrscheinlichkeitsereignisse definieren. Sei QA das Ereignis, dass der Quiz-Master die höhere Zahl in den Umschlag A steckt, und QB das entsprechende Ereignis für den Umschlag B. Sei WA das Ereignis, dass wir ansagen, die höhere Zahl stecke im Umschlag A, und WB entsprechend für Umschlag B. Aus dem Verhalten des Quiz-Master folgt Pr[QA] = Pr[QB] = 1/2. Die Wahrscheinlichkeiten für WA und WB hängen dagegen davon ab, welche Strategie wir verwenden, aber darauf will ich mich in dem Beweis nicht festlegen (siehe oben!).

Die stochastische Unabhängigkeit bedeutet, dass Pr[QA und WA] = Pr[QA] * Pr[WA] gilt, und so weiter. Das kann man im Beweis gewinnbringend verwenden. Was ist denn die Wahrscheinlichkeit, dass wir weiterkommen? Nun, entweder wir sagen Umschlag A an (WA) und das ist tatsächlich richtig (QA) oder wir sagen Umschlag B an (WB) und das ist richtig (QB). Die Wahrscheinlichkeit ist also:

Pr[QA und WA] + Pr[QB und WB] = Pr[QA] * Pr[WA] + Pr[QB] * Pr[WB] = Pr[WA] / 2 + Pr[WB] / 2 = (Pr[WA] + Pr[WB])/2 = 1/2

Mit anderen Worten: wenn der Quiz-Master sich wie beschrieben verhält, dann kommen wir immer mit Wahrscheinlichkeit 1/2 weiter, egal was wir tun! Und das ist der ganze Beweis.


Variationen

Bis jetzt ist nichts Überraschendes passiert. Deswegen wollen wir die Quiz-Show nun ein wenig abändern, und zwar auf zwei leicht verschiedene Weisen:

1. Bevor wir uns festlegen, öffnet der Quiz-Master einen Umschlag seiner Wahl und zeigt uns, welche Zahl darin enthalten ist.


2. Bevor wir uns festlegen, dürfen wir einen Umschlag unserer Wahl öffnen und uns ansehen, welche Zahl darin enthalten ist.

Was ist in diesen beiden Fällen die beste Strategie für uns? Da ich angekündigt habe, dass etwas Überraschendes passiert, ist klar: in mindestens einem der Fälle gibt es eine Strategie, bei der wir in jedem Fall mit einer Wahrscheinlichkeit von mehr als 1/2 in die nächste Runde kommen.

Aber wie genau soll das gehen? Ich lasse den geneigten Leser darüber nun selbst ein wenig nachdenken, und werde die Lösung in ein paar Tagen hier aufschreiben.

Die blinden Flecken des ifo-Instituts

Der Oeffinger Freidenker verlinkt heute auf ein Papier, das aus dem Dunstkreis der ifo-Instituts kommt, und kommentiert dabei gleichzeitig wahrscheinlich den meisten Lesern aus dem Herzen.

Aber wie ist es mit den Inhalten des Papiers? Es dürfte für den Leser schon einmal interessant sein, zu wissen, dass das ifo-Institut die Heimat des allseits beliebten Prof. Unsinn ist. Dementsprechend wenig überraschend werden in dem Papier einige Dinge geflissentlich ignoriert. Das ist typisch für die Herkunft des Papier, aber leider müssen diese Dinge doch immer wieder dokumentiert werden. Hier sind die drei Wichtigsten:

1. Die Rolle des deutschen Exportwahns wird unterschlagen. Tatsächlich begann die im Papier erwähnte "Kapitalflucht" erst in so richtig überwältigendem Ausmaß, nachdem Deutschland dank Lohn-Dumping zum Netto-Exporteur wurde. Das ist aber auch wenig überraschend: der Leistungsbilanz müssen zwangsläufig entsprechende Kapitalflüsse gegenüberstehen.
   
   Will man die "Kapitalflucht" beenden, so gibt es dazu also ein ganz einfaches Mittel: beendet den Netto-Exportwahn. Eine solche Lösungsmöglichkeit wird in dem Papier aber nicht erwähnt.


2. Fast schon ein Klischee ist der Hinweis auf die Hyperinflation der Weimarer Republik, ohne auf die eigentlichen Ursachen einzugehen. Zu Letzeren gibt es ein gutes Papier von Cullen Roche.
   
   Die Kurzfassung ist: übertrieben hohe Kriegsschulden kombiniert mit einem Kollaps der produktiven Kapazität in Folge der Ruhrbesetzung haben die deutsche Situation untragbar gemacht. Die Hyperinflation war dann das kleinere Übel, da man den Siegermächten auf diese Weise klar machen konnte, dass es so nicht weitergehen kann.


3. Es wird auf Konkurse und die niedrige Verschuldung der Bundesstaaten der USA eingegangen. Das ist richtig. Aber wer auf die USA hinweist, muss auch darauf hinweisen, dass es dort eine zentrale Bundesregierung gibt, deren Haushalt mehr als 20% des BIP ausmacht, und deren Schulden bekanntermaßen auch nicht gerade gering sind.
   
   In der Tat erfordert eine solide Korrektur der Eurozone, dass eine zentrale Regierung mit einem zentralen Haushalt für die gesamte Eurozone geschaffen wird. Der schnellste und demokratischste Weg dorthin wäre, dem Europäischen Parlament die Befugnisse des monetären Souveräns zu geben. Ich habe über diese Option bereits früher geschrieben, z.B. hier.

Auch von der merkwürdigen Fixierung auf die Target-Salden hat sich das ifo-Institut anscheinend immer noch nicht befreien können. Es ist richtig, dass das ESZB nicht vollständig konsolidiert ist und deshalb die nationalen Zentralbanken als Teil des Systems weiter existieren. Genauso richtig ist, dass die Bundesbank innerhalb dieses Systems gigantische Forderungen an andere nationale Zentralbanken angesammelt hat. Das sind Folgen des bereits erwähnten und von mir, nicht aber von den Autoren des Papiers, kritisierten deutschen Netto-Exportwahns. Diese Forderungen würden beim Zerfall des Eurosystems vermutlich wertlos werden.

Falsch ist aber, dass dies zwangsläufig Kosten für "den Steuerzahler" zur Folge hätte. Es handelt sich schließlich um Forderungen. Niemand in Deutschland hat sich in diesem Kontext für etwas verpflichtet, das er nach einem Zerfall des Eurosystems nicht erfüllen könnte. Sicher, die Bilanz der Bundesbank sähe etwas merkwürdig aus. Aber es ist nur eine Bilanz: im Zuge der Gesetzgebung für eine Wiedereinführen der Mark könnte dieses "Problem" mit einem Federstrich gelöst werden.

Für mehr habe ich im Moment keine Zeit. Nur eine abschließende Bemerkung sei mir noch gestattet. Das Papier arbeitet mit einem typischen Trick der Meinungsmache: die meisten Aussagen die in ihm gemacht werden sind durchaus korrekt. Die politische Lüge liegt in den Dingen, die verschwiegen werden. Genau das macht das ifo-Institut so unsympathisch: seine politisch orientierten Veröffentlichungen sind durchtränkt von intellektueller Unehrlichkeit und Manipulation.

Der Vergleich mit den USA ist das Paradebeispiel dafür. Es kann keiner behaupten, dass er die zentrale Bundesregierung dort bei seinen Überlegungen einfach übersehen hat. Warum wird sie in dem Papier trotzdem nicht einmal erwähnt? Die Antwort ist, für mich, ganz einfach: weil den Autoren klar ist, dass eine Erwähnung ein politisches Umdenken erfordern bzw. auslösen würde, und das will man um jeden Preis vermeiden.

The AI Challenge - a look back

For the last four weeks, I have worked on my submission for the Google AI Challenge. The deadline has passed this morning, so it is time to relax while the official final tournament is running on the contest servers. Until yesterday, my submission was ranked quite consistently in the top 20. Then I uploaded my final version (which resets the skill) which was quite consistently better on the unofficial TCP servers, but given that everybody else was doing last minute tweaks, too, it's far too early to call.

I enjoyed the spirit of this contest immensely, and now I would like to document some of my thoughts on how my submission works. I have uploaded the source code to Github (https://github.com/nhaehnle/aiant) so you can peruse it while following this blog entry if you wish.

High level structure

The bot is divided into a number of modules that select high-level goals for the ants it controls. This is done in a very straightforward way. Every ant initially has no direction to go in (the field Ant::assigneddirection is initialized to false each turn). The high-level modules then simply assign directions to ants that do not have one yet, and the order in which the modules are called reflects the relative importance I assign to the various tasks. For example, the HillDefense module will only assign ants that have not been assigned by the FoodSeeker.

There are two modules that fall outside of this basic structure: The Zoc ("zone of control") module does not steer any ants. Instead, it keeps track of how fast my ants vs. enemy ants can reach each square of the map. And the Tactical module overrides the previous decisions if necessary for ants that may be involved in combat.

The strategy modules

The following strategy modules are used by the bot, assigning jobs to ants in the given order:

1. FoodSeeker: Getting enough food is probably the most important problem of the game, and so this module comes first. It greedily sends the closest ant to each item of food that is visible, using several breadth-first-searches.
2. HillDefense: When one of the bot's hills can be reached in few turns by the enemy, this module ensures that a few ants (adjusted based on the number of enemy ants in sight) stick close to the hill.
   
   An important tweak of this code is that it does not send ants back to the hill indiscriminately. Instead, it only recalls an ant if it is too far away from the hill relative to the closest enemy. This way, ants are not needlessly wasted on patrol duty. It would probably be a good idea to treat multi-hill maps specially, but this is not done.
3. OpportunisticAttack: This rather stupid piece of code ensures that the ants move more aggressively towards enemy hills. After all, that is the only way to win the game.
4. Scout: This module assigns a tiny number of ants to re-explore squares that have not been seen in a long time.
   
   This is needed because the rest of the code uses the Zoc module to understand that an enemy can never come out of a cul-de-sac once it's been secured. So without some re-scouting logic, the bot would simply ignore the food in those secured locations!
5. Diffusion: This is a very ad-hoc heuristic to spread out my ants better than they would otherwise. There would probably have been some potential for improvement in this part of the code.
6. Zoc-based movement: any ant that has not been assigned a move up to this point will simply use the Zoc data to move closer to the enemy. This is done in Bot::makeMoves rather than in a separate module.

On a "historical" note, it may be interesting to know that I started out with just the FoodSeeker and the Zoc-based movement. Together with Tactical, this was enough to get into the top 100 a bit more than two weeks before the deadline.

The tactical logic

The idea behind the TacticalSm module is simple:

1. Carve out small Submaps that contain all the ants that could potentially be involved in combat on the next turn.
2. Generate potential moves for both my bot and the enemy. The combination of Submap and associated PlayerMoves is called a Theater.
3. Evaluate those moves using some simple scoring function.
4. Try to find better moves for both parties.
5. Repeat until time runs out.
6. Pick a move using one of two strategies.

Note that my tactical code doesn't understand situations involving enemy ants of more than one enemy player. This is certainly a limitation, but it's hard to tell how bad it really is.

Most of the tactical code is about engineering, and careful consideration of the scoring function. For example, during a major code reorganization halfway through the competition, the tactical code stopped considering proximity to food in the scoring function. That hurt the performance of my bot quite significantly, and my bot's skill recovered when I turned that part of the scoring function back on.

There are really only two clever parts. One is to use a scoring function that, by default, assigns a higher value to the own ants, to avoid costly trades of ants, but to turn on aggressive mode if the own ants overpower the enemy. This switch is done randomly based on the ratio of ants, where the probability to turn on aggressive mode is conceptually a logistic function in the log of the ants ratio.

The second clever part is to use a small bit of rock-paper-scissors logic in the final move selection. My first method to select a move is a simple min-max (or rather, max-min): pick the move that maximizes the minimum scoring value I could possibly get, given all enemy moves under consideration. Since this is a rather conservative choice of moves, especially given that there is absolutely no look-ahead, I implemented max-average as a second strategy: choose the move that maximizes the average scoring value, where the average is over all enemy moves, weighted by their max-min value.

Of course, this strategy may sometimes be too aggressive. What's more, the best strategy may depend on the opponent. Therefore, my bot uses a variant of the randomized weighted majority algorithm to pick the move-selection strategy. At the beginning of each turn, my bot determines what the best strategy would have been in hindsight to update the weights of the strategy. One important tweak is that the weights depend both on which enemy player my bot is facing, and on the number of ants in play.

Discarded experiments

I experimented with adding more move selection strategies, but the results were not convincing at all, perhaps because it takes longer for the bot to learn which strategy to choose, so I scrapped that again.

I also implemented map symmetry detection to guess unseen enemy hills and a corresponding module for a coordinated offense against enemy hills. The code is still there, but I have disabled it. The simple implementation I have is far too aggressive and wasteful, and I didn't feel like trying to tweak it to a point where it becomes useful.

I also did some experiments with an alternative move generation method for my tactical system, as well as a very simple implementation of the sampling-based combat system described by a1k0n on the challenge forums. This simple method performed worse than my tactical code; I have some ideas for improving it (just like a1k0n obviously did), but ultimately did not have the time to try them out. Those experiments can still be found in the Git history if you feel like digging through it.

I tried some automatic tuning of parameters using meta-heuristics (see the test/tune.py script), but somehow that didn't yield very convincing results either.

Code quality?

I have to admit that the code is not very well documented, and some of it is rather hackish. I hope you'll forgive me for this type of one-off code.

There is one thing that I did consistently that I would never do in another type of project, and that is keeping STL containers around as long as possible to avoid re-allocation. I intensively rely on the fact that std::vector::clear does not free the allocated memory, at least in the default implementation of g++. By keeping those vectors around, I want to avoid unpleasant surprises in the performance of memory management.

I don't think this is strictly necessary, given that the bot actually uses surprisingly little memory, but it didn't hurt in this case. It reduces the maintainability of the code, which is why I wouldn't do it on other projects, but maintainability was obviously never a goal for a competition like this one.

A neat randomization trick

"When in doubt, throw a coin" is perhaps the most important lesson that Theoretical Compute Science teaches. When there are several directions to go in that all score the same, which one should you choose? The best approach is to choose randomly.

To facilitate this, I pre-generated all 24 permutations of the 4 directions, and all 120 permutation of the 5 possible moves of an ant, and I randomly choose one of those permutation whenever I have a loop through directions to choose from.

Sometimes, however, I have a loop through variable-sized vectors, for example, when choosing ants for an offensive move in the tactical logic. I would like to have a random permutation for those cases as well, and of course there are algorithms to generate them. But they take time, and the benefit of a perfectly uniform distribution is not that clear.

So here's a little trick I use to permute variable-sized vector of size N. I pick a random prime p out of a decently sized pre-generated list of large primes (larger than any N the code is ever going to see), as well as a random offset ofs and loop through the numbers 0..N-1. But instead of using these numbers i as an index, I use (p*i + ofs) % N as index. Since p is prime different from N, it is invertible modulo N, and therefore the map i -> p*i + ofs is a bijection, aka a permutation. Of course, this is far from a uniformly distributed permutation: there are N! potential permutations, out of which this method can generate at most N * φ(N). But hey: it's good enough for what I need.