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)

• Wieviele Kombinationen gibt es?
  • Upper Bound: $7!\cdot3^7 = 11022480$ Kombinationen
    1. Einen Stein betrachten wir als fix und orientieren uns dran.
    2. Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, also $(8-1)!$ Kombinationen
    3. jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $3^7$ 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$
  • andere Ansätze (Bitfield…)
• Objektorientierter Ansatz:
  • Codierung ist interne Angelegenheit des Würfels

• Brute-Force
  • 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?

• 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)