Implementierung surrealer Zahlen für Spiele

11

Es gibt eine sehr schöne Konstruktion von Conway mit surrealen Zahlen. Sie sind "Zahlen", die sowohl reelle Zahlen als auch Ordnungszahlen enthalten, vollständig geordnet sind und alle Eigenschaften eines Feldes haben (außer sie bilden keine Menge, sondern eine Klasse).

Eine Einführung finden Sie beispielsweise in diesem PDF oder in Wikipedia .

Sie können noch allgemeiner auf sogenannte "Spiele" verallgemeinert werden, die ursprünglich zur Untersuchung kombinatorischer Spiele eingeführt wurden. Die ursprüngliche Motivation von Conway war es, das Go-Spiel zu analysieren. Insbesondere das Endspiel eignet sich besonders für die Modellierung mit "surrealen Spielen".

Meine Frage ist: Weißt du, ob jemand diesen Ansatz in einer KI (dh einem Computerspieler) implementiert hat, um sein Level bei einem Spiel zu verbessern? Ich interessiere mich besonders für den Fall Go, aber auch für andere. Wenn nicht, gibt es ein Hindernis oder einen Grund, warum dies keine gute Idee wäre?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Denis
quelle
1
Laut dem Buch "Mathematical Go" scheint es früher ein Begleitprogramm von Raymond Chen zur Lösung der Endspielprobleme in dem Buch gegeben zu haben, aber ich weiß nicht, wo es zu finden ist. Ich habe auch eine vage Erinnerung an Berlekamp, ​​der sich auf "Go Explorer" bezieht, was in der Veröffentlichung "Smart Game Board und Go Explorer: Eine Studie in Software und Knowledge Engineering" erwähnt werden könnte. Ich glaube jedoch nicht, dass die kombinatorische Spieltheorie derzeit wirklich in den Top-Go-Programmen verwendet wird.
Mark S.
3
Wenn ich mich richtig erinnere (vielleicht nicht mehr wie vor langer Zeit), kann man laut David Wolfe (Co-Autor von Mathematical Go) Go-Endspielpositionen zusammenstellen, bei denen Top-Profispieler dazu neigen, nicht so optimal zu spielen als Punkt, während der spieltheoretische Ansatz von Conway / Berlekamp / Wolfe es ermöglicht, das Optimum relativ einfach zu berechnen. Solche Positionen sind jedoch erfunden. Dieses Phänomen ist bei Spielen, die im realen Spiel auftreten, selten.
Neal Young

Antworten:

8

Ich habe keine Antwort auf Ihre Frage, ob die Theorie der Conway-Spiele beim Erstellen von Spielprogrammen verwendet wurde, aber Sie könnten dennoch an der Combinatorial Game Suite interessiert sein , einem Open-Source-Programm zur Unterstützung der kombinatorischen Forschung Spieltheorie "(die ich hier zuerst kennengelernt habe ). Es enthält eine Implementierung verschiedener Standardoperationen für Conway-Spiele in kanonischer Form sowie eine Skriptsprache zur Beschreibung neuer Spiele.

Noam Zeilberger
quelle
3

Bei einigen Suchanfragen scheint es nicht viel veröffentlichte allgemeine Implementierungen surrealer Zahlen zu geben. Hier ist eine Implementierung von surrealen Zahlen in coq .

  • Surreale Zahlen in coq / Mamane, TYPES'04 Proceedings der internationalen Konferenz 2004 über Typen für Beweise und Programme

    Surreale Zahlen bilden ein vollständig geordnetes (kommutatives) Feld, das Kopien der Realzahlen und (aller) Ordnungszahlen enthält. Ich habe den größten Teil der Ringstruktur surrealer Zahlen in Coq codiert. Diese Kodierung beruht auf Aczels Kodierung der Mengenlehre in der Typentheorie.

    In diesem Artikel werden insbesondere die Definitions- oder Beweispunkte erörtert, an denen ich von Conways oder dem natürlichsten Weg abweichen musste, wie die Trennung der gleichzeitigen Induktionsrekursion in zwei Induktionen, wobei die Definition der Ordnung in eine gegenseitig induktive Definition von „höchstens“ umgewandelt wurde. und "zumindest" und Einpassen der ziemlich komplizierten Induktions- / Rekursionsschemata in die Typentheorie von Coq.

Es gibt einige Teilimplementierungen der surrealen Arithmetik für ein Spiel namens Hackenbush (Davis), das von Conway, Berlekamp und Guy populär gemacht wurde, von denen es einige Referenzen gibt.

Go ist in der Tat einer der Spitzenbereiche der KI-Forschung im Spiel (als wesentlich schwieriger angesehen als Schach, das die KI jahrzehntelang beschäftigte), aber es scheint, dass es wenig Forschung speziell zur Verwendung surrealer Zahlen zum Modellieren / Spielen gibt. Go wird als Grenze für maschinelles Lernen / KI-Algorithmen angesehen, da es auch einen relativ einzigartigen Status / Unterschied aufweist, da die besten softwarebasierten Algorithmen ("noch / aktuell") die menschlichen Meister nicht übertreffen.

In diesem Artikel The Mystery of Go, dem alten Spiel, das Computer immer noch nicht gewinnen können (Wired Mag), finden Sie eine anständige Übersicht über die aktuellen Go AI-Techniken / Forscher / Leads.

vzn
quelle