Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor Begriff Zusammenfassung/Zitate Quellen

KI-Forschung über Computerspiele - Lexikon der Argumente

Norvig I 189
Computerspiele/Künstliche Intelligenz/Algorithmen/Norvig/Russell: Ein Spiel kann durch den Ausgangszustand (wie das Brett eingerichtet ist), die erlaubten Handlungen in jedem Zustand, das Ergebnis jeder Handlung, einem abschließenden Test (terminal test) (der sagt, wann das Spiel zu Ende ist) und eine Nutzenfunktion (utility function) definiert werden, die für Endzustände gilt.
In Nullsummenspielen für zwei Spieler mit perfekten Informationen kann der Minimax-Algorithmus die optimalen Züge durch eine depth-first Aufzählung des Spielbaums auswählen.
Der Alpha-Beta-Suchalgorithmus berechnet die gleiche optimale Bewegung wie Minimax, erreicht aber eine viel höhere Effizienz, indem er Teilbäume eliminiert, die nachweislich irrelevant sind.
Normalerweise ist es nicht möglich, den gesamten Spielbaum zu betrachten (auch nicht mit alpha-beta),
Norvig I 190
also müssen wir die Suche irgendwann unterbrechen und eine heuristische Bewertungsfunktion anwenden, die den Nutzen eines Zustands abschätzt.
Viele Spielprogramme berechnen Tabellen der besten Züge im Eröffnungs- und Endspiel vor, sodass sie einen Zug nachschlagen und nicht suchen können.
Glücksspiele können durch eine Erweiterung des Minimax-Algorithmus verarbeitet werden, der einen Zufallsknoten bewertet, indem er den durchschnittlichen Nutzen aller seiner Kinder nimmt, gewichtet nach der Wahrscheinlichkeit jedes einzelnen Kindes.
Optimales Spiel in Spielen mit unvollkommenen Informationen, wie Kriegsspiel und Bridge, erfordert eine Überlegung über die aktuellen und zukünftigen belief states jedes Spielers. Eine einfache Annäherung kann durch Mittelung des Wertes einer Handlung über jede mögliche Konfiguration fehlender Informationen erreicht werden.
>Minimax-Algorithmus
.
Geschichte mechanischer Spiele: Das berüchtigtste von ihnen war Baron Wolfgang von Kempelens (1734-1804) "Der Türke", ein angeblich schachspielender Automat, der Napoleon besiegte, bevor er als Trickkasten eines Magiers enthüllt wurde, in dem sich ein menschlicher Schachexperte befand (siehe Levitt, 2000)(1).
Computerschach: 1846 scheint Charles Babbage (der vom Türken fasziniert war) die erste ernsthafte Diskussion über die Machbarkeit von Computerschach und Dame beigetragen zu haben (Morrison und Morrison, 1961)(2).
VsBabbage: Er verstand die exponentielle Komplexität der Suchbäume nicht und behauptete, dass "die Kombinationen, die in der Analytischen Maschine involviert waren, alle geforderten enorm übertrafen, selbst beim Schachspiel".
Schach: Das NSS-Schachprogramm (Newell et al., 1958)(3) verwendete eine vereinfachte Version von alpha-beta; es war das erste Schachprogramm, das dies tat. Der Alpha-beta-Pruning wurde von Hart und Edwards (1961)(4) und Hart et al. (1972)(5) beschrieben. Alpha-beta wurde vom Schachprogramm "Kotok - McCarthy" verwendet, das von einem Schüler von John McCarthy (Kotok, 1962) geschrieben wurde(6). Knuth and Moore (1975)(7) bewiesen die Richtigkeit von alpha-beta und analysierten die zeitliche Komplexität. Pearl (1982b)(8) zeigt, dass alpha-beta unter allen game-tree Suchalgorithmen mit fester Tiefe asymptotisch optimal ist.
>Schach/Künstliche Intelligenz/Norvig/Russell.

1. Levitt, G. M. (2000). The Turk, Chess Automaton. McFarland and Company.
2. Morrison, P. and Morrison, E. (Eds.). (1961). Charles Babbage and His Calculating Engines: Selected
Writings by Charles Babbage and Others. Dover.
3. Newell, A., Shaw, J. C., and Simon, H. A. (1958). Chess playing programs and the problem of complexity. IBM Journal of Research and Development, 4(2), 320–335.
4. Hart, T. P. and Edwards, D. J. (1961). The tree prune (TP) algorithm. Artificial intelligence project memo 30, Massachusetts Institute of Technology.
5. Hart, P. E., Nilsson, N. J., and Raphael, B. (1972). Correction to “A formal basis for the heuristic determination of minimum cost paths”. SIGART Newsletter, 37, 28–29.
6. Kotok, A. (1962). A chess playing program for the IBM 7090. AI project memo 41, MIT Computation
Center.
7. Knuth, D. E. (1975). An analysis of alpha–beta pruning. AIJ, 6(4), 293–326.

_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.
KI-Forschung

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z