44 Antworten in diesem Thema

[Johnny B Good]

Moin zusammen,

 

irgendwie habe ich in letzter Zeit viel darüber nachgedacht, ob sich im Bereich Magic bereits jemand mit AI, maschinellem Lernen etc. ernsthaft auseinandergesetzt hat.

 

Grundsätzlich müsste Magic doch ein Spiel sein, dass durch die reine Simulation unendlicher vieler Partien (Gegen sich selbst spielen) quasi unschlagbare Decks und Strategien entwickelt. Den Faktor Zufall mal aussen vor und einen guten Kartenpool vorrausgesetzt.

 

Gibt es hierzu schon wissenschaftliche Insights a la Go, Schach etc. oder mache ich evtl. einen Denkfehler wenn es um AI als solches geht.

 

Bin gespannt auf eure Einschätzung.

 

Cheers 

[Michael W]

Aus der Erinnerung heraus, ja das gab es wohl schon mal. Wenn ich das richtig verstanden habe, ist Magic aber eben nicht einfach für eine AI, weil eben nie alle Informationen für alle offen sind. Damit ist eben nicht nur die nächste Karte die man zieht gemeint, sondern auch die Handkarten der Gegner, die man in der Regel halt nicht kennt, aber das Spiel sehr wohl beeinflussen.

[seizan]

Es gibt eine Draft Bot AI

https://draftsim.com...drafting-paper/

https://arxiv.org/abs/2009.00655

 

Magic the Gathering ist außerdem "turing complete", sodass es anscheinend etwas komplexer und schwieriger für AI ist

https://arxiv.org/abs/1904.09828

[Hellcat]

Vor über 10 Jahren gab es in der "Spektrum Informatik" mal einen Artikel von zwei Studenten, die sich in ihrer Abschlussarbeit damit beschäftigt haben eine KI für Magic zu entwickeln. Ist natürlich schon ziemlich lange her, inzwischen ist das Thema KI ja auch eine ganze Ecke weiter, aber wenn es dich interessiert kann ich gerne mal nachschauen in welcher Ausgabe das war.

[The green one]

Eine AI für unschlagbare Magic Decks klingt für mich wie eine AI für unschlagbares Schere-Stein-Papier ... in eine Trillion mal komplizierter.

[Nekrataal der 2.]

Noch ein Link zum komplexesten Spiel der Welt. https://www.technolo...t-complex-game/

[Hellcat]

Und ohne mich jetzt eingehender damit befasst zu haben: Theoretisch müsste es zwar möglich sein, den die perfekte Strategie zu entwickeln. In der Praxis dürfte es aber daran scheitern, dass schon der Entscheidungsbaum für ein einzelnes Spiel aufgrund der Vielzahl an Handlungsmöglichkeiten so umfangreich wird, dass es ziemlich lange dauern würde den kompletten Baum zu berechnen. (Nichts anderes macht eine KI: aus allen möglichen Spielsituation den optimalen nächsten Zug heraussuchen, ggf. unter Verwendung von Heuristiken )

[Johnny B Good]

Angestoßen hat den Gedanken bei mir eine Netflix Doku über Alpha Go, dass erste Go-Programm das es geschafft hat einen Weltmeister zu schlagen. Sehr empfehlenswert übrigens:

https://de.wikipedia.org/wiki/AlphaGo

 

Für alle die es nicht kennen: Go ist ein klassisches asiatisches Brettspiel, dass im Vergleich zu beispielsweise Schach wesentlich mehr potentielle Möglichkeiten für Züge/Strategien etc. einräumt und lange Zeit als für Computer sehr schwer bis auf top-level unlösbar galt. In dieser Doku wird oft von (vermeintlicher) Kreativität gesprochen und das Alpha Go anders spiele als andere Programme vorher... Magic ist natürlich noch komplexer und hat verdeckte Elemente wie die Karten des Gegners, die es auf ein anderes Level heben.

 

Trotzdem, wenn man aber und aber Millionen Partien simuliert und die AI zusätzlich ständig mit echten Decklisten und Daten füttert, sollte es doch möglich sein relativ problemlos ein Monstrum (nennen wir es mAIgic) zu erschaffen, dass so gut wie alle Partien gewinnt auf die es den nötigen Einfluss nehmen kann.
Boardwipes etc. sind natürlich nicht vorhersehbar, so dass es immer schlagbar sein wird. On the long run sollte mAIgic aber eine bessere Win-Rate haben als jeder menschliche Spieler.

 

Ähnlich wie ein Online-Pokerbot.

 

PS: Danke für die Artikel. Werde mich mal durchkämpfen. :-)

Bearbeitet von Wikipedicards, 20. August 2021 - 10:26.

[Sterni]

Ich denke, Magic AI kann nicht durch Abwägung aller Möglichkeiten erstellt werden.

Schon zu Schach gibt es ein yt Video (60 Sekunden Wissenschaft), dass bei Schach schon schnell Zahlen erreicht werden, die nicht nicht mehr berechnet werden können.


D. H. Man kann eine Magic KI imo nur mit den Daten /Spielen /Decklisten füttern und dann anhand der Möglichkeiten bzw.. Wahrscheinlichkeiten (auf draw) anhand gespielter Partien analysieren lassen.

Das würde dann in Richtung Poker gehen, d. H. Aus den vorliegenden Informationen Wahrscheinlichkeiten auf Lösungen zu berechnen.

Bearbeitet von Sterni, 20. August 2021 - 10:43.

[mcamokk]

Wir spielen halt das komplexeste Spiel der Welt
Muss bei dieser Diskussion an diese Nachricht denken.
 
https://mein-mmo.de/...spiel-der-welt/

Bearbeitet von Nekrataal der 2., 27. August 2021 - 08:39.
Unnötiger Fullquote des Vorgängerposts

[MightyMaz]

Eine Problem ist auch, dass eine der zentralen Leistungen bei Magic schon die Deckerstellung ist. Sollte eine KI also wirklich bei 0 anfangen müssen und sich auch eigene Decks bauen oder sollte sie das nicht können?

Wenn man Decks für eine KI vorgibt wird sie beim aktuellen Stand der Technik mit ziemlicher Sicherheit ein umso besseres Ergebnis erzielen desto linearer ein Deck zu spielen ist.

Gerade rote Aggrodecks könnten schon jetzt relativ gut funktionieren aber Controldecks oder komplexe Combodecks wie Eggs vermutlich noch sehr schlecht.

Der Ansatz eine KI mit vielen Decks zu füttern und gegen sich selbst spielen zu lassen könnte aktuell also schon daran scheitern, dass sie am Ende immer die Decks bevorzugen wird, mit denen sie die besten Ergebnisse erzielen kann, aber nicht die Decks, die tatsächlich insgesamt (in einem bestimmten Umfeld) am häufigsten gewinnen könnten, wenn sie optimal gespielt würden. In überschaubaren Kontexten wird man also aktuell wahrscheinlich noch bessere Ergebnisse mit einer KI erzielen, die gar nicht auf maschinellem Lernen beruht, sondern auf das spielen eines oder weniger Decks hin optimiert wurde.

Durch die Zufallskomponente von Magic ist es aber ohnehin unmöglich absurd hohe Siegraten gegen starke menschliche Spieler zu erzielen. Ich würde eine KI schon als übermenschlich stark bewerten sobald sie in einer Serie von z.B. 1000 Spielen 51% der Spiele gegen einen Profi gewinnen kann.

Bearbeitet von MightyMaz, 11. September 2021 - 19:24.

[P0LTERGEIST]

hatten wir den gleichen Thread nicht schon einmal vor ein paar Monaten?
 
 

...
Trotzdem, wenn man aber und aber Millionen Partien simuliert und die AI zusätzlich ständig mit echten Decklisten und Daten füttert, sollte es doch möglich sein relativ problemlos ein Monstrum (nennen wir es mAIgic) zu erschaffen, dass so gut wie alle Partien gewinnt auf die es den nötigen Einfluss nehmen kann.

 
Nein. Magic ist kein Spiel was die Ai so lernen kann. Eine AI mittels evolutionären Algorithmus lernt nicht wirklich etwas. Mit Hilfe von neuronalen Netzen wird eine Eingabe verarbeitet und führt zu einer Ausgabe. Im nächsten Schritt schaut man ob die Ausgabe positiv oder negativ zu bewerten ist und ändert das neuronale Netz durch eine weiteres Verarbeitungsneuron (oder lässt es weg, oder ändert etwas daran...) 
 
Bei Go/Schach würde eine AI(ohne Mutation) immer die gleiche Zugfolge liefern da sich an den eingaben nichts ändert. Nach dem mutieren einer AI kann man die Ergebnisse hier vergleichen.
 
Bei Magic startet das 2te Spiel mit einer komplett neuen Hand. Ohne den direkten vergleich zu haben kann man nicht sagen welche Mutationen erfolgreich waren und welche AI s ausselektiert werden.
 
60 Karten zu mischen hat 60! (Fakultät) Möglichkeiten bei einem Magic Deck sind es meistens deutlich weniger durch die Duplikate aber immer noch kacke viel (hab keine Lust drüber nach zu denken aber jedes Duplikat sollte die Anzahl halbieren, wobei die hälfte von ~2^280, 2^279 ist)

 

Spoiler

 

 

[MightyMaz]

Weiß zufällig jemand welche AI für Magic aktuell die stärkste ist?

Bei Go/Schach würde eine AI(ohne Mutation) immer die gleiche Zugfolge liefern da sich an den eingaben nichts ändert.

Sieht man übrigens auch schön bei den Partien mit Alphago. Lee Sedol hat im 4. Match (das er gewonnen hat) die selbe Eröffnung gespielt wie im 2. Match und Alpha Go hat exakt gleich darauf reagiert. Da Go viele Symmetrien aufweist kann man aber auch eine gewisse Zufallskomponente einbauen.

Bearbeitet von MightyMaz, 12. September 2021 - 12:39.

[Rotband]

Und ohne mich jetzt eingehender damit befasst zu haben: Theoretisch müsste es zwar möglich sein, den die perfekte Strategie zu entwickeln. 

 

Ich bezweifle das (sowie die Existenz eines perfekten Decks) schon alleine daher, weil sich Meta und Gegner anpassen. Also ein "perfektes" Deck kann man nur gegen ein ganz konkret definiertes Meta konstruieren und das würde ich eine KI eventuell noch zutrauen. Wo es dann aber extrem tough wird ist, wenn eben dieses Meta sich auf die neue Situation einstellt. Zudem gibt es dieses feste Meta eh nur sehr bedingt.

 

Ob Magic nun das komplexeste Game der Welt sei sei mal dahin gestellt, bezweifle auch sehr, dass da wirklich alle Games verglichen wurden. Aber es gibt eben so viele unberechenbare Faktoren, dass das was heute gut ist, morgen schon voll gegen die Wand laufen kann. 

[Sterni]

Also Deckbau stelle ich mir noch recht simpel vor.

Einfach mit allen Decklisten des Formats fütternbund erwartetes Meta angeben.

Ich denke, da die quoten schon recht erfahren /eingespielt sind, halte ich das für das kleinere Problem, zumindest mit entsprechender Vorarbeit (die menschliche ambitionierte Spieler auch machen).

Was ich mir dagegen schwer vorstelle, ist das vermeintlich richtige Play zu machen.

[Rotband]

Wenn du dir die Fluktuation der Top 32 Resultate ansiehst, stellst du fest, dass das so easy eben nicht ist. Klar gibt es ein paar Eckpfeiler, aber da eben gegen genau die permanent gemetagamed wird, gibt es kein so starres Meta.

[MightyMaz]

Einfach mit allen Decklisten des Formats fütternbund erwartetes Meta angeben.

Ich meinte komplett von 0 also quasi nur mit den jeweils im Format verfügbaren Karten als input.

[Sterni]

Wenn du dir die Fluktuation der Top 32 Resultate ansiehst, stellst du fest, dass das so easy eben nicht ist. Klar gibt es ein paar Eckpfeiler, aber da eben gegen genau die permanent gemetagamed wird, gibt es kein so starres Meta.

Naja, kommt aufs Format an.

Eigentlich ist es häufig so, dass von den Top 8 ca 5x das gleiche Deck dabei ist.

D. H. Entweder spielt man das Deck auch, oder ein Anti Deck.

Ist vielleicht heute nicht mehr ganz so schlimm, aber es gab Zeiten und Formate, da war es genau so

[Rusto]

Also für ein ganz spezifisches Matchup ist das wohl möglich so ne AI zu entwickeln, die nach endlich vielen Testspielen irgendwann immer den im Schnitt besten Spielzug findet, aber das stelle ich mir schon sehr kompliziert vor. Dass man keine perfekte Information hat ist erst mal nicht ganz so schlimm, die AI lernt ja aus einer riesigen Zahl an Testspielen, wenn sie also weiß dass bei Gamestate X Spielzug Y im Schnitt am häufigsten zum Sieg führt dann wird sie das auch tun.

Jetzt kommt aber die Krux, denn die Auswahl der möglichen Spielzüge ist eben nicht immer gleich, das Board kann komplett gleich aussehen aber die Hand, der Friedhof, die Lebenspunktezahl, der wie vielte Turn es ist, den wievielten Landdrop der Gegner gemissed hat, wer angefangen hat etc. sind alles Parameter die potenziell relevant sein könnten, der Entscheidungsbaum ist also wie schon jemand hier sagte utopisch Groß. Und das ist ein ganz bestimmtes Matchup bei dem man die Deckliste des Gegners kennt, wenn du die AI dann noch eigene Decks bauen lassen willst, dann viel Spaß.

Bearbeitet von FDPepega, 11. September 2021 - 23:14.

[Genu]

Ich bezweifle das (sowie die Existenz eines perfekten Decks) schon alleine daher, weil sich Meta und Gegner anpassen. Also ein "perfektes" Deck kann man nur gegen ein ganz konkret definiertes Meta konstruieren und das würde ich eine KI eventuell noch zutrauen. Wo es dann aber extrem tough wird ist, wenn eben dieses Meta sich auf die neue Situation einstellt. Zudem gibt es dieses feste Meta eh nur sehr bedingt.

 

Genau das wäre das realistischste Anwendungsgebiet beim heutigen Stand der Technik - denn Deep Learning ist das Prognosemächtigste Werkzeug dass uns derzeit zur Verfügung steht. 

Versteh mich nicht falsch - Die KI wird, wie du sagtest, ohne eigenständig spielen zu können, schlecht darin sein Innovation zu treiben - also neue Karten ohne Datenbasis basierend auf ähnlichen Karten als Spielbar zu bewerten und diese in Decks zu integrieren.

 

Aber wenn man einer KI Zugriff auf alle Daten die bei MTGO anfallen geben würde, z.B. die Winraten von Decks gegen Decks, dann lassen sich die Best-Positionierten Decks ermitteln - und rekursiv auch die dagegen Best-Positionierten Decks. Durch die Historischen Daten der Challenge und Showcases würde man ermitteln können wieviele Ebenen man im Meta am Besten Nextlevelt.

 

Mit den Kompletten Gamelogs kann man auch Bewerten wie gut eine (Sideboard-)Karte in einem Matchup ist und welche Pläne am Besten funktionieren (Verhältnis Sieg/Niederlage wenn Karte X Ymal, oder in Kombination mit Karte Z gespielt wurde), die Punkte lernen ab wann multiple Kopien schädlich werden, gleichermaßen die Karten mit negativem Impact auf die Winraten identifizieren etc. Darauf basierend aus dem bekannten Meta die Core- und Flex-Slots für ein Deck ermitteln, die Optimale Verteilung der Sideboard-Plätze und die Auswahl der besten Karten im Gesamtbild, aber kann auch die Abwägung von Karten die ein Deck stillegen vs flexiblen Karten registrieren und lernen, oder das Identifizieren von Spielplänen.

 

Das frühzeitige Identifizieren von Flavor of the Month und Flash in a pan Decks sollte zumindest im Bereich des möglichen liegen.

Eine KI könnte also schon jetzt, ohne dass Sie Magic spielen kann, schon eine ganze Menge leisten, denn das identifizieren von unbekannten Schlüsselfaktoren und deren Relation zueinander ist quasi DAS Anwendungsgebiet.

 

 

Mich würde wirklich interessieren ob und wenn, dann wie hoch, man die Winrate von einem Pro-Player boosten könnte wenn man diesen in einer Turnierserie wie den Weekly Challenges von einer KI selektierte und adaptierte Decks in die Hand drückt.

Bearbeitet von Genu, 24. September 2021 - 12:59.