Wie man künstliche Intelligenz im Computerschach benutzt

In einigen (historischen) Veröffentlichungen wurde Schach als Drosophila der künstlichen Intelligenz bezeichnet. Während ich denke, dass in der gegenwärtigen Forschung die bloße Anwendung eines Suchalgorithmus bestenfalls fortgeschrittene Informatik ist , glaube ich, dass es immer noch Bereiche gibt, in denen AI-Techniken angewendet (und praktiziert) werden können.

Ein einfaches Beispiel wäre das Öffnen eines Lernbuchs, in dem dem Programm beigebracht werden kann , ob bestimmte Züge in der Eröffnung verwendet werden sollen oder nicht, da das Programm für bestimmte Positionstypen ungeeignet ist. Wir können eine Form des Re-Inforcement-Lernens verwenden und dies automatisieren: Ich nehme an, ich könnte das Programm gegen sich selbst spielen und die Wahrscheinlichkeit von Gewinnlinien erhöhen und die Wahrscheinlichkeit von Verlustlinien verringern.

Das komplexeres Beispiel ist eine Lern verwenden Auswertungsfunktion (beispielsweise könnte man die Werte von zwicken stück quadratischen Tabellen ). Ich denke jedoch:

angesichts des Rauschens aufgrund der enormen Anzahl realistischer Positionen (im Gegensatz zur Anzahl realistischer Eröffnungslinien)
und mit den Kosten (Dauer) eines Computerschachspiels und der Notwendigkeit, Lasten zu spielen.

Wie kann man das effektiv machen? (Oder sollte ich mir andere Techniken ansehen, zum Beispiel neuronale Netze?)

artificial-intelligence board-games ljgw
quelle

Der Standardansatz ist Alpha-Beta-beschnittener Minimax. mit einer Heuristik. Es ist aus der Search-Familie von AI, eher aus der Familie des maschinellen Lernens.

Lyndon White

Tatsächliche Schachmeister erinnern sich im Grunde nur an alle Partien, die sie zuvor gespielt haben ... Sie haben also ein starkes Memo.

Es gibt auch die Gegenforderung. Ich kann mich nicht erinnern, wer es gesagt hat, aber es geht so. Biologen verwenden Experimente mit Drosophila, um ein tieferes Verständnis der Physiologie, der Genetik usw. zu erlangen. KI-Leute schreiben Schachcomputer, um immer besser Schach spielen zu können. Dies lehrt uns überhaupt nicht viel über Informatik; Es wäre, als würden die Biologen superschnelle, superstarke Drosophila züchten und sie gegeneinander kämpfen lassen.

David Richerby

wrt die Metapher, es denkbar mehr als „drosophila der künstlichen Intelligenz“ WRT verschiedene Aspekte ist, besonders wenn man bedenkt es entscheidend die Top-Mensch bis ~ 1997 & Forschung in sie weiter, etc schlagen den Ball hielt

VZN

Antworten:

Der gesamte staatliche Raum für Schach ist enorm - er kann ungefähr auf 10 ⁴³ geschätzt werden (Shannon-Nummer (Shannon, 1950) , ( Wikipedia )).

Die Idee, die Sie hier präsentieren - Agenten, die das Reinforcement-Lernen miteinander spielen, um das Spiel zu lernen - wurde erfolgreich auf Backgammon - TD-Gammon (Tesauro, 1995) angewendet ( Kapitel in Reinforcement Learning von Sutton & Barto ). Es verwendete auch neuronale Netze, um die Wertfunktion des Spiels zu schätzen. Dieses Problem ist jedoch viel einfacher, da die Anzahl der Zustände im Backgammon erheblich geringer ist als im Schach, nämlich: 18.528.584.051.601.162.496 ( Backgammon Forum Archive Thread ).

Wenn Sie jedoch das Spiel nach wenigen Anfangszügen beenden und nur "gute Eröffnungen" lernen möchten, könnten Sie mit einem analogen Ansatz Erfolg haben. Das Hauptproblem wäre, das Spiel nach dem Eröffnungsspiel zu bewerten, was schwierig erscheint. Nur ein Ähnlichkeitsmaß zu den festgelegten Positionen nach bekannten Eröffnungen reicht nicht aus, da die Position weit von ihnen entfernt sein kann, wenn der Gegner einen dummen Zug machen würde (also nicht aufgrund eines Fehlers des Lernagenten, also der Position, auch wenn "falsch" "sollte als gutes Ergebnis gewertet werden).

Verweise:

BartoszKP
quelle

Das Schwierigste ist in der Tat, einen empirischen Weg zu finden, um das Ergebnis von Eröffnungen zu bewerten. Unterschiedliche Öffnungen sind auf unterschiedliche Weise gut, daher gibt es wahrscheinlich eine Vielzahl akzeptabler Öffnungen.

JDong

Ich bin mir ziemlich sicher, dass jede mögliche (oder seltsame) Methode von KI oder ML in Lehrbüchern ausprobiert wurde und im Vergleich zu einfacher Brute Force so gut wie gescheitert ist.

Meine persönliche Sichtweise ist, dass Schach per se für die moderne KI nicht mehr von Interesse ist ... Ganz einfach, weil es gelöst wird : indem man nur einen modernen Computer und rohe Gewalt einsetzt. Ich glaube nicht, dass es notwendig ist, ein "intelligentes" System zu schaffen, um es effizienter zu lösen (funktioniert in meinem Handy einwandfrei), und ich glaube, dass es nicht einmal die Notwendigkeit für etwas Unbekanntes und mehr gibt "intelligenter" Ansatz zu existieren.

iliasfl
quelle

Ich bin nicht sicher, warum dies abgelehnt wurde. Das Argument, Schach sei "gelöst", ist insofern etwas ungenau, als kein Computer eine mögliche Position erkennen und perfekt auswerten kann. Trotzdem ist iliasfl genau richtig, dass das Schachspiel den größten Teil seiner Attraktivität für die KI-Forschung verloren hat. Zum einen sind die besten Computerschachprogramme jetzt bei ausreichender Rechenleistung und Zeit erheblich stärker als die besten Menschen. Dies erschwert es Programmierern zunehmend, die Funktionsweise eines Algorithmus zu bewerten.

Elixenid

Danke, sagte ich gelöst in dem Sinne, dass rohe Gewalt eine Lösung ist. Natürlich ist die KI-Community (im Allgemeinen nicht nur hier) mit dieser "Lösung" nicht zufrieden. Wir haben jedoch bereits ein Rechensystem, das "intelligentes" Verhalten zur Lösung dieser Aufgabe darstellt und sogar die besten Menschen gewinnt. Persönlich glaube ich, dass Schach für die KI nach ein paar Jahren nicht mehr zum Thema wird, wenn sich die derzeitige Masse von Akademikern, die Karriere gemacht haben, um es anzugreifen, zurückzieht.

Ich würde die aktuellen Computer-Schach-Implementierungen nicht als "gelöst durch Brute Force" bezeichnen - sie suchen immer noch nach riesigen Mengen an Gamestates, aber es gibt dort viele Komponenten von Non-Brute Force. Natürlich sind sie keine "menschliche" Lösung, die sich gut auf andere Probleme verallgemeinern lässt, aber ich wäre nicht überrascht, wenn wir eine "menschliche" Schach-KI hätten, dann wären sie um mehrere Größenordnungen geringer effizienter als die aktuellen Speziallösungen, was es einfach schlechter macht.

Peteris

Ich denke, diese Antwort und ihre Kommentare wurden von Googles AlphaZero ganz klar widerlegt: en.wikipedia.org/wiki/AlphaZero Auch wenn Sie die Kritik an der Einrichtung für Stockfish akzeptieren und sie alle Übereinstimmungen gezogen haben, ein System, das auf dieses Niveau gekommen ist mit ein paar Stunden Training ist klar überlegen.

Kamal

Ich denke, es ist erwähnenswert, dass Sie ein AI-Problem definieren müssen, um zu bestimmen, wie es angegangen werden soll. Ob es vollständig beobachtbar oder teilweise beobachtbar ist und ob es deterministisch oder stochastisch / zufällig ist.

Schach ist vollständig beobachtbar (im Gegensatz zu Backgammon, Monopoly oder Poker zum Beispiel). Es ist auch deterministisch (wie Checkers und Go zum Beispiel). Schließlich gibt es Gegner, und aus diesem Grund ist es nützlich, bei der Bestimmung des nächstbesten Zuges den Adversarial Search- Typ von zu verwenden Algorithmen wie MiniMax. Das Klassifizieren eines Problems kann uns dabei helfen, festzustellen, welche Art von Suchalgorithmus wir anwenden möchten. Und im Falle von Schach wäre Adversarial Search geeignet.

Insbesondere Minimax hat a

$O(b^n)$

$O(bm)$

Im Fall von Schach wäre b also 35 und m wäre 100. Es gibt Möglichkeiten, dies zu umgehen, oder Strategien, um es effizienter zu machen, wie z. B. Alpha-Beta-Cutoff.

Iancovici
quelle

In diesem Zusammenhang ist auch zu erwähnen, dass Schachendspiele für bis zu wenige Figuren bereits tabellarisch dargestellt sind - eine weitere Optimierung.

BartoszKP

Dies ist der normale Ansatz, jedoch kein Ansatz für maschinelles Lernen. Die Frage verwendet das Tag "Maschinelles Lernen".

Lyndon White

@Oxinabox Obwohl dies früher der Fall war, erwähnte der Fragesteller im Titel oder im Text nicht, wo er sich für den Ansatz des maschinellen Lernens interessierte, sondern nur am Ende, als er ein Beispiel für einen Ansatz mitteilte, den er vorhatte. Das Problem muss weder auf maschinelles Lernen noch auf einen einzelnen Lernalgorithmus (NN) beschränkt werden.

Iancovici

In der Tat ist dies gut

Lyndon White

Um genau zu sein, Schach ist nicht vollständig beobachtbar, da bei einer uns unbekannten Position beispielsweise ein König oder ein Turm bereits bewegt wurde oder nicht, obwohl dies für die Erzeugung von Zügen wichtig ist (ist eine Rochade noch möglich?). Ein Programmierer kann es jedoch vollständig beobachtbar machen, indem er die Positionsdarstellung ändert und nicht bewegten König / Turm und bewegten König / Turm als unterschiedliche Figuren unterscheidet, obwohl dies einige Schwierigkeiten mit sich bringt.