Kombinatorik

Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? Wie zählt man sie systematisch durch? Zustand (State) und Zustandsübergang (Transition / Move).

• Beschränkte Komplexität
• Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik)
• Komplexitätsrechnung an einem einfachen Beispiel einführen (z.B. 2x2x2 Rubik)
  • Wieviele Kombinationen gibt es?
    • Upper Bound: $7!\cdot7^3 = 1728720$ Kombinationen
      • Einen Stein betrachten wir als fix und orientieren uns dran.
      • Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, also $(8-1)!$ Kombinationen
      • jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $7^3$ Möglichkeiten für jede Kombination
    • Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation.
• Wie lässt sich ein Würfel darstellen / codieren?
  • Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right)
  • Koordinatennetz mit planarer Sicht
  • String oder Array mit Länge $6*4 = 24$

    • Brute-Force-Ansätze
      • Wie kann ich alle systematisch durchprobieren?
        • Suchbaum
        • Tiefensuche (DFS)
        • Breitensuche (BFS) (s.a. Graphenalgorithmen)
        • Iteratives DFS mit inkrementell steigendem Tiefenhorizont.
        • Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf?)
      • Wie lange dauert es?

    ## 3er Rubik

• Gute Quelle / JS Implementierung (für 3×3 Rubik): https://observablehq.com/@onionhoney/how-to-model-a-rubiks-cube

• Grenzen von Brute-Force
  • Transfer zu Passwort-Attacke: 8 vs. 12 Zeichen
  • Schach: Abschätzung der möglichen Zustände
• Probleme mit unbekanntem Zustand (Markov-Probleme)