Hidden Gems

Programmierwettbewerb für
Schülerinnen und Schüler
Oktober 2025 – Juni 2026

Mit Zufall ans Ziel (aka Metro­polis-Hastings-Algo­rithmus)

Foto von Paul (Phnt0m)
Paul (Phnt0m)·

Physikstudent und Hobby-Programmierer

Monte-CarloMarkov-ChainSignalsAlgorithmus

Einleitung

Das Hauptproblem der aktuellen Stage Dark Signal ist es, die Positionen der Gems zu bestimmen. Hierzu gibt es verschiedenste Ansätze. Ich habe mich für einen “naiven” Ansatz entschieden: Raten :)

Na gut, ganz so einfach ist es nicht. Grob zusammengefasst rate ich verschiedenste Edelstein-Positionen, bewerte sie und verbessere sie iterativ. Für einen einzelnen Edelstein im Maze ist das Leben einfach: Man kann einfach per Brute-Force alle Positionen testen und die Auswählen, die am besten zu den gemessenen Signalen passen. Bei einer map von 49x29 sind das 1421 Konfigurationen (“States”) die man testen muss. Das geht schnell. Wenn man 2 Gems hat, können es dann schon 2.017.820, das war gerade so machbar ohne wilde Tricks. Bei 3 Gems hört der Spaß leider mit 2.863.286.580 States auf, in 100 ms wird das knapp. Was kann man also machen?

Mathematisch versuchen wir hier ein Inverses Problem zu Lösen (für Menschen die Mathe-Affine sind): Wir haben Messwerte vom einem skalaren Felds an verschiedenen Positionen gegeben und versuchen die Quellen (Gems) zu bestimmen. Mathematisch ist das leider nicht ganz trivial. Da ich meinen Bot in C programmiere, will ich keinen großen Solver basteln.

Vor nicht allzu langer Zeit habe ich ein Paper zum Thema Daten modellieren gelesen (Paper, kann ich sehr empfehlen. Lösungen als ipynb gibt es hier: Repo) Fitten von Daten zu einem Modell ist ein sehr ähnliches Problem. Der Bot misst das Signal an verschiedenen Orten (unsere Messwerte) und will wissen wo die Gems liegen müssen (Modell). Wir wissen (zum Glück) welchen Effekt die Gems auf das Signal haben. Also versucht auch der Bot das Problem zu lösen, welches Modell die gemessenen Werte produziert.

Monte-Carlo

Der Metropolis-Hastings-Algorithmus versucht nun, genau dieses Modell zu bestimmen. Wir wissen, dass zu jedem Zeitpunkt 0–3 Gems im Maze vorhanden sind. Im Fall von zwei Gems gehen wir wie folgt vor: Wir generieren zufällige „States“ – also Positionen für zwei Gems, die zufällig im Maze verteilt sind. Pro State läuft der Prozess iterativ ab:

  • Bewerten: Wir berechnen, wie gut der State zu den Messwerten passt. Wir simulieren das Signal, das diese Edelstein-Positionen erzeugen würden, und nutzen die Abweichung (Fehler) zu den echten Messwerten als Metrik.
  • Mutieren: Wir verändern den State leicht, indem wir einen der Gems ein Stück verschieben. Vergleichen: Wir prüfen den Fehler des mutierten States.
  • Entscheiden: Ist der neue State besser, akzeptieren wir ihn. Ist er schlechter, nehmen wir ihn nur manchmal an: Bei einer Fehlerdifferenz von $\Delta e = e_{neu} - e_{alt}$ liegt die Wahrscheinlichkeit bei $P = \exp(-\Delta e/T)$.

T ist dabei ein Parameter der Temperatur genannt wird (wegen Boltzmann-Gesetz). Je größer T, desto wahrscheinlicher wird der neue State angenommen, sodass der Parameterraum aggressiver abgesucht wird. Es ist wichtig, manchmal ‘schlechtere’ States zu besuchen, um nicht in lokalen Minima steckenzubleiben. Man kann sich das so vorstellen, dass der State durch den Parameterraum läuft und das Optimum sucht. Einen solchen Prozess nennt man auch Markov-Chain. Somit handelt es sich hier um eine Markov-Chain Monte-Carlo Methode.

Mehr zu: Markov-Chain Eine Markov-Chain ist eine Prozess, in dem die Wahrscheinlichkeit, welcher Zustand als nächstes besucht wird, nur vom aktuellen Zustand abhängt. Der Prozess hat in diesem Sinne kein 'Gedächtnis'. Ein einfaches Beispiel dazu wäre ein sogenannten _Random Walk_: Unser Walker startet bei der Position $x=0$. Von da aus hat er eine Wahrscheinlichkeit von $P=0.5$ nach rechts zu auf $x=1$ zu gehen und eine Wahrscheinlichkeit von $P=0.5$ nach links zu $x=-1$ zu gehen. Nachdem er einen Schritt getan hat, sind seine Wahrscheinlichkeiten erneut sie 50/50 links oder rechts zu gehen. Sie hängen nicht davon ab, was in der Vergangenheit passiert ist, wichtig ist nur, an welcher Position er sich momentan befindet.

Dieses Prozedere machen wir nicht nur mit einem State, sondern mit vielen sogenannten Walkern. In der Regel: Je mehr States, desto genauer das Resultat. Außerdem, je länger die Kette an besuchten States, desto besser approximiert sie die tatsächliche Lösung. Dieses Ensemble an Walkern macht der Algorithmus sehr stabil gegen Fehler und lokale Minima.

Da das Signal kein Noise oder ähnliches hat können wir einfach am Ende den State mit dem geringsten Fehler als ‘Wahrheit’, also also bestes Modell für unsere Messwerte benutzen.

Simulation

Hier eine kleine Visualisierung (braucht JavaScript):

> ENSEMBLE_MCMC Temp: 0.20
■ Path | ○ Ensemble
Best SSE: 0.00
Details zur Simulation: Was passiert hier?

Hier sieht man das Ensemble-MCMC in Action:

  • Setup: Die roten Punkte sind die tatsächlichen Gem-Positionen (die "Wahrheit"). Die türkisen Quadrate markieren den Pfad des Bots, also unsere Messpunkte für das Signal.
  • Walker-Ensemble: Die blauen Kreise sind die 100 Walker. Jeder startet mit einer zufälligen Konfiguration aus zwei Gems und versucht, das gemessene Signal bestmöglich zu reproduzieren.
  • Der Algorithmus: In jedem Schritt mutieren die Walker ihre Position. Über das Metropolis-Kriterium wird entschieden, ob der neue State akzeptiert wird. Das Ziel ist es, den Best SSE (den quadratischen Fehler) zu minimieren.
  • Temperatur-Regler:
    • Eine hohe Temp lässt die Walker den gesamten Parameterraum aggressiver absuchen, um lokale Minima zu vermeiden.
    • Niedrige Werte sorgen dafür, dass sie sich eng um das globale Optimum konzentrieren.
  • Konvergenz: Nach dem Start sieht man, wie die Walker aus der anfänglichen Zufallsverteilung heraus die Gems finden und stabil auf den Zielpositionen bleiben.

Fazit

Aktuell verwende ich 200 Walker mit jeweils 500 Iterationen pro möglicher Gem Zahl. Ich finde damit meist in 3-5 Messwerten/Moves die tatsächlichen Edelstein-Positionen. Klingt recht gut, keine Ahnung wie sich das mit anderen Methoden vergleicht. Mit ein paar Optimierungen am Code habe ich eine average response time des Bots von ca. 15 ms. In den letzten Scrims hat sich auch gezeigt, dass nur das finden der Gems alleine noch nicht ausreicht, um Top-Scores zu erzielen. Also heißt es: weiterbasteln. Ich bin gespannt was noch kommt!