Special Chapter: Chess AI Flashcards
Wofür kann KI verwendet werden?
Non-Player Charaktere in Spielen
Content Generation (Bilder, Musik)
Datenanalyse
Was ist ein Game Tree?
Ein Game Tree ist eine Baumrepräsentation aller möglichen Spielzüge und Zustände
Was ist eine Transposition?
Eine Transposition ist, wenn man zum selben Board Zustand aus verschiedenen Game States kommt - es gibt Äste die sich aufteilen und die wieder zusammenkommen
Wie wird beim Schach ein Move ausgewählt?
Der Game State wird über eine statische Evaluierungsfunktion berechnet - dieser wird, ausgehend vom View des Spielers, evaluiert - der Computer nimmt von einer Auswahl an Moves immer den, der den höchsten Score wiedergibt
Wie funktioniert der Minimax Algorithmus?
Wir als Spieler versuchen immer den maximalen Wert zu ermitteln, während wir für die Runde unseres Gegner den minimalen Score ermitteln - wir müssen also auch die möglichen Moves des Gegners in Betracht ziehen
Wie funktioniert Alpha-Beta Pruning?
Minimax schaut sich mehr Moves als notwendig an - bei Alpha Beta Pruning gibt es einen Alpha-Wert (Maximizer) und einen Beta Wert (Minimizer) - wenn Alpha >= Beta, dann wird gepruned (wir müssen uns die restlichen Moves gar nicht mehr anschauen, da diese sowieso nicht funktionieren)
Die Alpha und Beta Werte werden von oben herab nur nach unten weitergereicht, wenn Max ist, darf nur Alpha updated werden, bei Min dann nur Beta
Was ist AB Search Window? Welche Rolle spielt da Aspiration Search?
Das AB Search Window ist das Fenster, indem sich Alpha und Beta befinden müssen, damit es zu updates kommt - bei Aspiration Search werden Alpha und Beta nicht mit -unendlich und +unendlich respectively initialisiert, sondern mit den Resultaten aus vorherigen Evaluationen, um den AB Algorithmus zu beschleunigen, wenn es allerdings kein Resultat gibt, wird die Suche mit einem breiteren Fenster wiederholt
Was ist Iterative Deepening? Was ist Move Ordering?
Iterative Deepening ist ein trade-off zwischen Zeit und Qualität von Zügen - Minimax wird mit langsam steigender Tiefe ausgeführt, und wenn die Zeit aus ist, wird der bisher berechnete beste Move angewandt - dabei muss das Ergebnis der vorherigen Züge abgespeichert werden und sortiert werden nach dem besten Move (Move Ordering), um bessere Ergebnisse zu erzielen
Was sind Transposition Tabellen?
Bei Schach kommt es oft vor, dass es zu gleichen Game States kommt - um diese nicht wieder erneut berechnen zu müssen, werden diese in sogenannten Transposition Tabellen gespeichert
Was ist ein Zobrist Key?
Ein Zobrist Key ist ein random Bit-Muster für jedes mögliche Board State (768 Einträge) - wenn ein Feld nicht leer ist, muss der Zobrist Key nachgeschaut werden und geXOR’d werden, um den richtigen Eintrag wieder herauszufinden - man spart sich mit dem Lookup unnötige Berechnungen für diesen Board State
Was ist Quiescence Search?
Wenn eine Schlagserie beginnt, kann der Horizon Effekt auftreten - man muss eigentlich schauen, was am Ende der Schlagserie passiert, um das bestmögliche Ergebnis zu bestimmen - also erweitert man den Tree so lange, bis kein Schlagen oder Schach setzen möglich ist
Was ist das Opening Book?
Das Opening Book enthält Daten über die statistisch besten Spielzüge zu Beginn vom Spiel - diese werden von Profi-Schachspielern auswendig gelernt und auch von Chess AI Bots verwendet, um zu Beginn vom Spiel schnell die besten Züge herauszufinden
Wie funktioniert der Monte Carlo Tree Search? Erkläre den Algorithmus anhand von vier Stationen.
1) Selektion: Zugang anschauen (Knoten auswählen und bei diesem anhand von Regeln tiefer gehen
Explore: Jeden Knoten besuchen und nicht zu selektiv sein
Exploit: “Vielversprechende” Knoten erneut besuchen und schauen, ob diese eventuell nicht der beste Move sind
2) Expansion: Ein “Unterzug” wird genauer angeschaut
3) Simulation: Es werden 10, 100, 1000 Spiele simuliert und aus diesen werden die Informationen den Eltern zurückgegeben
4) Back-Propagation: Zurückgeben der Werte bis zur Wurzel zurück (optimaler Move)
