23 Antworten in diesem Thema

[throrthor]

Hi.

Weis nicht ob jemand von euch auch das Bretrtspiel GO kennt oder spielt.

Es hatte eine Vormachtstellung unter den Strategiespielen, war mit einfachen Algorhytmen nicht zu knacken und das einzige Strategiespiel wo der Mensch demComputer weit überlegen war.

2017 hatte dann die KI um DeepMind mit AlphaGO selbstlernend eine solche Spielstärke erreicht das es erstmals den Weltmeister schlug.

Mittlerweile ist es ein unschlagbarer GO-Guru, der Mensch lernt allerdings auch von ihm an agresivität  und nöhert sich wieder an.

Vieleicht ist der Wettkampf noch nicht entschieden, aber es bedarf wohl eines Genies.

 

Was glaubt ihr, wie würde DeepMind Magic spielen ?

Die bekannten Tier Decks und wenn ja welche oder doch eigene Kreationen ? Wieviel stärker wär er, oder wie random ist Magic?

[Sanitoeter]

Ich bin leider nicht in der Go-Szene aktiv, deshalb wird sich meine Argumentation quasi ausschließlich auf das Schachmatch zwischen Stockfish (3438 ELO, https://www.ichess.n...chess-engines/) und AlphaZero (mindestens 3750 ELO, z.B. https://www.quora.co...-of-Alpha-Zero) beziehen. Bitte bedenkt, dass die Zahlen zwar veraltet, aber das Match in der Zeit stattgefunden hat.

 

Ausgehend von den Wertungszahlen hat AlphaZero gegen Stockfish eine 85.77% erwartete Winrate. Bedenkt man dabei noch, dass Stockfish weit jenseits der besten Spieler liegt kann man schon recht gut das Ausmaß erkennen. Magnus Carlsens beste ELO liegt bei 2882, was für Stockfish eine erwartete Winrate von 96.09% und für AlphaZero von mindestens 99.33% bedeutet.

 

Varianz bei Magic kann man getrost ignorieren, weil sie beide Spieler gleichermaßen treffen kann. Man muss eben nur eine ausreichend große Samplesize nehmen.

Je geringer der Cardpool eines Formats, desto näher wird das Kollektiv an die optimale Liste gekommen sein. D.h. bei Standard werden wir wohl keine neuen Decks sehen, allerdings dann die wirklich besten Varianten des Archetypes.

Interessant wäre ob z.B. der Landcount aufgrund des dummen MTGA Algorithmus verändert werden könnte, weil immer die Hand gewählt wird, die näher an 2/3 Lands liegt.

 

Ein ähnliches Thema ist OpenAI und im speziellen OpenAI Five (https://openai.com/blog/openai-five/), die bei Dota 2, einem Spiel in Echtzeit und wsl deutlich mehr Variablen als MTG, das beste Team der Welt ziemlich rund gemacht haben.

 

Ich glaube also nicht, dass AI vs Human bei MTG in irgendeiner Form knapp wäre.

Bearbeitet von Sanitoeter, 26. Dezember 2020 - 10:59.

[Sterni]

Sowohl bei Go als au h bei Schach ist das Spiel quasi berechenbar, weil es in quasi jeder Situation nur abhängig vom Board einen "besten" Zug gibt.

Und es lässt sich auch berechnen, wie wohl der Gegner reagiert usw.


Bei Magic ist es ungleich komplizierter, da der Carddraw von random Karten das ganze deutlich schwieriger macht.

Man kann zwar für jede Situation die outs berechnen, wie z. B. Beim Poker.

Aber ein Zug ist womöglich nicht mehr der beste Zug, weil eben nicht die Wahrscheinlichste Karte als out gekommen ist, sondern eine andere.


Also tl dr

Ich denke, es wäre möglich, aber nicht in absehbarer Zeit, da noch deutlich komplexer.

[Assimett]

Ich glaube also nicht, dass AI vs Human bei MTG in irgendeiner Form knapp wäre.

 

Ich frage mich da eher, wie viele Matches man spielen müsste, um den bei Magic recht hohen Anteil der Varianz auszuschließen.

 

Randomness ist in Schach und Go quasi nonexistent, bei DotA bin ich mir gerade nicht sicher ob da Werte ausgewürfelt werden, aber afaik gewinnt dort auch immer das Team mit dem höheren Skill.
 

[throrthor]

Nur selbst gängige Schachprogramme berechnen  den nächsten Zug nicht wirklich voraus sondern bewerten die Stellung weil sich das ganze viel zu schnell Richtung Unendlich annähert-

Wie das ne KI macht weis eigentlich keiner und von daher wäre es bei Magic keinesfalls schwieriger als bei GO.

Du musst der KI vereinfacht gesagt nur die Karten und Regeln beibringen und mit genug Spielen füttern, den Rest macht sie von allein.

[Assimett]

Sowohl bei Go als au h bei Schach ist das Spiel quasi berechenbar, weil es in quasi jeder Situation nur abhängig vom Board einen "besten" Zug gibt.

Und es lässt sich auch berechnen, wie wohl der Gegner reagiert usw.


Bei Magic ist es ungleich komplizierter, da der Carddraw von random Karten das ganze deutlich schwieriger macht.

Man kann zwar für jede Situation die outs berechnen, wie z. B. Beim Poker.

Aber ein Zug ist womöglich nicht mehr der beste Zug, weil eben nicht die Wahrscheinlichste Karte als out gekommen ist, sondern eine andere.

 

Je nach Architektur "lernt" die KI solche Zusammenhänge selbst. Es kommt natürlich darauf an, welche Informationen man der KI vorgibt ("feature selection"), hier kann man schon viel richtig oder falsch machen. In dem verlinkten Blogeintrag zu DotA sieht man so eine Architektur, die Inputs sind in Gelb dargestellt: https://cdn.openai.c...rchitecture.pdf

 

Man könnte auch einen komplett anderen Ansatz wählen, nämlich der KI nur das aktuelle Bild von MTGA zeigen und dann alles andere selbst herausfinden lassen. Also quasi das emulieren, was ein Mensch auch sieht.

Aber da ist die Lernkurve so dermaßen hoch, dass ich bezweifle dass das irgendwie funktionieren wird, weil die zu extrahierenden Informationen wie Game- und Boardstate etc viel zu abstrakt sind. Es braucht halt immer noch den Menschen, der die KI "in die richtige Richtung schubst" bzw die Informationen "vorkaut".

Du musst der KI vereinfacht gesagt nur die Karten und Regeln beibringen

 

Hier bin ich mir nicht einmal sicher, ob das notwendig ist. Natürlich wäre es von Vorteil, wenn die KI die Regeln schon hard-coded hätte, aber eigentlich ist das nicht notwendig, denn sowohl bei MTGA als auch MTGO lassen sich keine illegalen Spielzüge machen.

 

Und auch die Bedeutung der Kartentexte müsste imho die KI selber lernen. Natürlich bekommt sie diese in Textform präsentiert. Aber den Zusammenhang "mein Gegner hat keine Blocker mit Flying oder Reach, also kann ich mit meinem Flieger ungeblockt angreifen" muss erlernt werden. Sowas vorzugeben wäre Schummelei.

Bearbeitet von MettRosé, 26. Dezember 2020 - 11:27.

[Sanitoeter]

Randomness ist in Schach und Go quasi nonexistent, bei DotA bin ich mir gerade nicht sicher ob da Werte ausgewürfelt werden, aber afaik gewinnt dort auch immer das Team mit dem höheren Skill.

 

Streich das quasi im ersten Teil.

 

Zum zweiten Teil:

Es gibt einige wenige Randomelemente, die allerdings wirklich vernachlässigbar sind, weil sie über ein Spiel gesehen immer auf +-0 rauslaufen. Beispiele hierfür sind Schaden, der in einem Intervall (z.B. 52-62) liegt und Bounty, das man bei Creepkills erhält (z.B. 42-48). Von beiden gibt es aber so wahnsinnig viele Ereignisse im Verlauf des Spiels, dass es einfach irrelevant ist.

Weitere Randomelemente werden über Pseudo Random Distribution (https://liquipedia.n...om_Distribution) aufgefangen.

Du hast im Spiel also so gut wie keine Randomness, aber dafür non perfect Information.

 

Hier bin ich mir nicht einmal sicher, ob das notwendig ist. Natürlich wäre es von Vorteil, wenn die KI die Regeln schon hard-coded hätte, aber eigentlich ist das nicht notwendig, denn sowohl bei MTGA als auch MTGO lassen sich keine illegalen Spielzüge machen.

 

Damit die KI gegen sich selbst üben kann, wäre Regelkenntnis durchaus angebracht. Man könnte die KI natürlich die Regeln mithilfe der Programme lernen lassen, aber muss halt nicht sein finde ich, weil die Nutzung solcher Programme einfach unnötig Zeit beim Lernen verschwendet.

 

Und auch die Bedeutung der Kartentexte müsste imho die KI selber lernen. Natürlich bekommt sie diese in Textform präsentiert. Aber den Zusammenhang "mein Gegner hat keine Blocker mit Flying oder Reach, also kann ich mit meinem Flieger ungeblockt angreifen" muss erlernt werden. Sowas vorzugeben wäre Schummelei.

 

Sowas vorzugeben wäre auch kontraproduktiv, was wenn ich mit dem Flieger eigentlich blocken müsste? Die KI kriegt solche Basicsachen unglaublich schnell selbst raus.

Bearbeitet von Sanitoeter, 26. Dezember 2020 - 11:42.

[Rotband]

Ihr wollt alle so tun als wäre die Varianz nicht relevant, aber irgendwie vermisse ich dann völlig den Faktor Deckvarianz. Wenn ihr eurem Deep Mind Jund gebt und dem Gegner Tron könnt ihr ja mal gucken wie fantastisch die Win-Rate wird ^^

[Assimett]

Natürlich müsste man jeweils ein Dutzend Matches mit unterschiedlichen Kombinationen von Decks machen, aber das ist, denke ich, sowieso klar.

[Rotband]

Diese Matches machen ja aber die erwähnte absurde Win-Rate völlig unrealistisch. Die hast du, wenn alles komplett gegeben ist, wie eben beim Schach. Beim Magic würde eine KI alleine durch diese Deckunterschiede solche Zahlen niemals erreichen können, weil sie eben mit z.B. Jund gegen Tron einfach ständig verliert, da ihr Skill eine wesentlich kleinere Rolle spielt.

 

Und falls die Maschine das Deck selbst wählen müsste wäre sogar spannend, wie man verhindert, dass das vom menschlichen Gegner abused wird, da diese objektive Deckwahl ja durchaus vorhersehbarer ist als Pet-Deck Timmy.

 

Je mehr ich drüber nachdenke, desto weniger verstehe ich wie Varianz nur deswegen ignoriert werden sollte, weil sie auf beide zutrifft. Alleine Würfelwurf wird die Win-Rate stark beeinflussten und jeder Faktor, der Skill weniger relevant macht, wird sich entsprechend positiv auf die Win-Rate des "schlechteren" Spielers auswirken. Also selbst wenn Varianz beiden mal hilft: Die KI benötigt sie nicht, sie schlägt aber in relativ hohem Maße die KI. Und das wird auch eine hohe Anzahl an Spielen ja nicht ändern, da allein der Würfelwurf dann eben immernoch rund 50% beträgt und sich stark auf die Win-Rate auswirken wird.

Bearbeitet von Nuggets Reborn, 26. Dezember 2020 - 13:05.

[throrthor]

Diese Matches machen ja aber die erwähnte absurde Win-Rate völlig unrealistisch. Die hast du, wenn alles komplett gegeben ist, wie eben beim Schach. Beim Magic würde eine KI alleine durch diese Deckunterschiede solche Zahlen niemals erreichen können, weil sie eben mit z.B. Jund gegen Tron einfach ständig verliert, da ihr Skill eine wesentlich kleinere Rolle spielt.

 

Und falls die Maschine das Deck selbst wählen müsste wäre sogar spannend, wie man verhindert, dass das vom menschlichen Gegner abused wird, da diese objektive Deckwahl ja durchaus vorhersehbarer ist als Pet-Deck Timmy.

 

Natürlich ist die Varianz so groß das solche Gewinnraten nicht entstehen.Auserdem würde die KI das Deck nicht nur wählen sondern gegebenfalls neu bauen.Genau die spannende Frage ist ja was für ein deck eine KI spielen würde und wie stark sie wär.

Ich denke du überschätzt aber auch die Berechenbarkeit einer solchen KI.Theoretisch könnte sie wenn man ihr die Möglichkeit lässt.auch vor dem Spiel alle Informationen im Netz von ihrem Gegner analysieren und ein Spielerprofil erstellen und wüsste wohl besser was du spielen wirst als umgekehrt.

[Rotband]

Dazu müsste es erstmal Daten und vor allem eine Konstanz geben. Gibt genug Leute, die jede Woche irgendwelche neuen Haufen spielen und auch ich saß schon mit meinen Fatal Pushes und kam gut ins Schwitzen, als meine Inquisition of Kozilek zig 5+ Mana Dinos zeigte

 

"Problem" bei Magic ist eben, dass "optimal" immer situativ ist und ein bestes Deck immer nur auf dem basiert, was man bisher wusste. Eventuell kann eine KI ein gutes Antibest-Deck bauen, aber wie wird dieses dann auf exakt diesen Versuch der anderen Spieler eingestellt sein?

 

Mir sagt Go übrigens genau nichts, daher beziehe ich mich immer nur beim Vergleich auf Schach. Und da ist die Ausgangslage einfach so drastisch unterschiedlich, dass Rückschlüsse wie sie Sani weiter oben zog vermutlich nicht funktionieren werden.

Bearbeitet von Nuggets Reborn, 26. Dezember 2020 - 13:16.

[Ragnaroktoktok]

Sowohl bei Go als au h bei Schach ist das Spiel quasi berechenbar, weil es in quasi jeder Situation nur abhängig vom Board einen "besten" Zug gibt.

Und es lässt sich auch berechnen, wie wohl der Gegner reagiert usw.

Theoretisch ist das genau so, wie Du sagst. Aber dieses Finden des perfekten Zuges kann bei Go bei einem einfachen Durchprobieren schon mal Erdzeitalter dauern, da die Komplexität sehr schnell steigt. 

 

Alleine, um auszurechnen, wie viele legale Stellungen es auf einem 19x19-Go-Brett gibt, braucht es:

Trotz des raffinierten Algorithmus ist die Berechnung von L19 – Anzahl der legalen Stellungen auf dem 19×19-Brett – kein Pappenstiel. Die Berechnung erfolgte nämlich mit modularer Arithmetik: Statt einer Berechnung mit riesigen Zahlen führt man dabei mehrere Berechnungen parallel durch, jeweils modulo einer großen Primzahl. Der chinesische Restsatz liefert einem dann daraus am Ende das vollständige Ergebnis. Falls Sie einen dicken Server übrig haben: 15 Terabyte schneller Plattenspeicher, 8 bis 16 Kerne und 192 GByte RAM werden empfohlen; die Laufzeit beträgt dann einige Monate.
Quelle: 

https://www.heise.de...ls-3130017.html

Auch DeepMind schafft es nicht immer, den perfekten Zug zu finden, aber Beweise mal das Gegenteil. :-)

 

Er hat es auf jeden Fall geschafft, Züge zu machen, die die besten Spieler unserer Zeit nicht einordnen konnten und erst später sahen, welchem Zweck sie gedient haben. Das ist bei Go immer so, dass schwächere Spielern die Voraussicht fehlt. Und DeepMind hat hier die Latte höher gelegt.

 

Bei Magic ist die Komplexität höher, aber wenn man DeepMind darauf trainieren würde und er nach einer gewissen Zeit Decks bauen soll, dürften da schon interessante Konstruktionen dabei sein. Oder es bestätigt sich die bestehende Meta. 

Spielen könnte er die dann auch, aber das wäre sehr teuer, viel Aufwand und bringt nicht so viel.

 

Auch aus der Go-Nummer wurde nicht viel mehr als ein Pressehit. Das Ding kann nicht mehr, als gut Go spielen und damit verdient man dann am Ende doch kein Geld und die Erkenntnisse für die Wissenschaft sind auch nicht bahnbrechend. Aber es hat Aufmerksamkeit und damit für die Macher doch auch Kapital gebracht.

 

Go hat spieltechnisch eine hohe Komplexität aus unserer Sicht, aber das Regelwerk ist bestechend simpel. Dann geht es nur noch darum, zu probieren, und das kann ein Computer gut.

 

Magic hat mehr Regeln und das steigert die Zahl der Möglichkeiten, aber das wäre beherrschbar. Und das Spielen selbst ist aufgrund der natürlichen Beschränkung durch die Karten in den Decks dann ja doch recht überschaubar. Das könnte Deep Mind gut, behaupte ich.

Bearbeitet von Ragnaroktoktok, 26. Dezember 2020 - 13:24.

[Nekrataal der 2.]

Ich denke Magic unterscheidet sich hochgradig in seiner Komplexität von Schach und auch Go. KI hilft bei NP vollständigen Systemen m.W.n. auch nur bedingt. Dazu mal folgender Artikel ...

https://www.spektrum...taendig/1645896

Bearbeitet von Nekrataal der 2., 27. Dezember 2020 - 00:40.

[» Arcanis «]

Gerade beim aktuelle 3CB (Three Card Blind) Turnier der Forenliga hat sich wieder gezeigt, wie komplex es sein kann, eine Auswertung von nur drei Karten gegen drei andere Karten durchzuführen.

 

Wollte bei der Auswertung unterstützen und ausnahmsweise einmal systematisch vorgehen. Doch als ich die ganzen Optionen alleine für den ersten Zug eines Spielers (erst nur für den Fall, dass dieser anfangen darf) darlegen wollte, habe ich gemerkt, dass es zu viele Varianten gibt, als dass ich diese systematisch mappen könnte. Skizze im Anhang:   3CB Tabernacle vs BlackLotus.pdf   135,59K   11 Mal heruntergeladen

 

Letzten Endes war es effizienter, das schlicht zu durchdenken und mit Cockatrice ein paar Situationen nachzustellen, die mir attraktiv erschienen.

Hier merkt man erst, wie unglaublich viele Varianten von unserem geschulten Hirn zusammengefasst, als irrelevant abgestempelt oder als beachtenswert gelabelt werden. 

Vor oder nach dem Spielen eines Black Lotus anzugreifen erscheint uns (bei offenen Karten) irrelevant, doch woher sollte das ein Computer wissen?

 

Genau diese Arbeit des "Labelns" wird beim Machine Learning mit Hilfe immens vieler Beispiele erst antrainiert. Dazu muss es eine Metrik geben, die angibt, welchen "Erfolg" bzw. welche "Belohnung" in (letzter) Konsequenz gezogen werden kann.

 

Beispiele für Belohnungen beim Training:

• Anzahl an Lebenspunkten, die abgezogen wurden ist gestiegen
• Maß der Differenz zwischen eigenen und gegnerischen Lebenspunkten ist gestiegen
• Gesamtstärke an Kreaturen auf der eigenen Seite ist gestiegen
• Größter Stärke-Wert an Kreaturen auf der eigenen Seite ist gestiegen
• Sieg des Spiels

Dazu ein paar "Bestrafungen", die im Wesentlichen gegenteilig zu den Belohnungen sind und dem Bot auf die Finger hauen, falls etwas nicht gut läuft. Beides muss mit Parametern bewertet werden, wobei Bestrafungen sich negativ auswirken.

 

Die Summe an erwarteten Belohnungen und Bestrafungen für das Resultat nach einem oder mehreren Zügen ermöglicht dann die Perspektive eines Lern-Algorithmus auf Spiele, die sich in dem Lerndatensatz befinden. Die Sensoren oder Neuronen eines entsprechenden Netzwerks werden dann entweder bevorzugt genutzt oder in ihrem Einfluss herunter skaliert, je nachdem, welches Resultat mit der aktuellen erfassten Situation vorliegt. Züge, die sich als gut herausgestellt haben, werden (hoffentlich) generalisiert und veranlassen die KI dann in Spielen mit neuen Situationen dazu, dass die passend skalierten "Neuronen" auch feuern und einen guten Spielzug veranlassen.

 

Die größten Herausforderungen sind Belohnungen, die in Bezug auf aktuelle Spielzüge weit in der Zukunft liegen (z.B. Nachtstahlreaktor als einzige Wincon). Auch die Abwägung, kurzfristige Bestrafungen in Kauf zu nehmen, um eine langfristige Belohnung (Sieg des Spiels) zu verfolgen ist schwer zu skalieren.

 

"Erst hauen, dann bauen" ist einer der Grundsätze, die uns vielleicht anfangs durch einen Mentor beigebracht wurden, damit man möglichst spät Informationen Preis gibt, doch wann wertet man den +1/+1 Bonus eines Lord of Atlantis über dem Wert, Informationen zurück zu halten?

 

Ich bin mir sicher, dass mit genügend Aufwand eine KI mit entsprechend guten Lerndatensätzen auch Magic recht competitive spielen könnte. Und mit fortschreitender Entwicklung der KI könnten wir - wie auch die menschlichen GO-Spieler - etwas von der "Denkweise" der KI lernen.

Denkt doch alleine mal an das vergleichsweise junge Paradigma, neben Brainstorm auch Ponder im Playset zu spielen. Oder wie stark wir auf manch andere Paradigmen wie "60-Karten Decks sind das Optimum" eingeschossen sind. Manch "erfrischende" Neuerungen werden in der Community mit gutem Grund "unterdrückt". Manche haben vielleicht das Potential unser großes "Neuronales Netzwek" (oder Hive-Mind?) der Magic-Szene zu bereichern

[demon_mfg]

Das finde ich eine sehr interessante Fragestellung, mit der ich mich vor einiger Zeit auch etwas intensiver beschäftigt habe.

 

Eine adäquate "KI" zu trainieren (wobei man im Falle von AlphaGo & Co. eher von Machine Learning oder Neuronalen Netzen spricht, anstatt von einer klassischen KI im herkömmlichen Sinne) sollte heutzutage, in Zeiten unzähliger Deep Learning Frameworks, für jeden, der schon mal ein wenig in Python programmiert hat, kein großes Problem mehr darstellen. Die große Herausforderung sehe ich in der Bereitstellung einer Simulation, also der Regeln und Spielmechaniken, die ja ständig erweitert werden. Hat man erst einmal so eine Simulation, kann man die Algorithmen wie bei AlphaGo gegen sich selbst antreten lassen und so mit entsprechenden Rechenkapazitäten beliebig lange trainieren lassen. Theoretisch könnte man die Trainingsphase auch durch aufgezeichnete Partien menschlicher Spieler verkürzen, dies würde jedoch nichts weltbewegendes an der prinzipiellen Erlernbarkeit oder der Stärke der KI ändern.

 

Mit XMage gibt es ja bereits ein relativ großes OpenSource Projekt, welches die aktuellsten MtG-Regeln und -Karten implementiert. Ich weiß allerdings nicht, welcher Algorithmik sich die Entwickler momentan bedienen, geschweige denn wie sie implementiert ist. Leider ist der Code auch etwas undurchsichtig, sodass es mir bisher noch nicht gelungen ist, die KI durch ein selbst implementiertes/trainiertes Modell zu ersetzten. Falls dort irgendwer schon weiter ist, wäre ich sehr gespannt auf Erfahrungsberichte.

 

Eine weitere Komponente in MtG ist ja der Deckbau, der dem Ganzen nochmal eine gewisse Varianz verleiht. Streng genommen müsste man die KI vor Beginn jeder Partie ein komplettes Deck bauen lassen. Ich denke, auch dieses Verhalten ließe sich antrainieren, da der Fundus wirklich spielbarer Karten(-kombinationen) ja sehr überschaubar ist und diese sich im Allgemeinen auch sehr ähneln.

[The green one]

Ich denke, auch dieses Verhalten ließe sich antrainieren, da der Fundus wirklich spielbarer Karten(-kombinationen) ja sehr überschaubar ist und diese sich im Allgemeinen auch sehr ähneln.

 

I beg to differ:

Statistisch und ganz grob-dumm gesagt gibt es beim 60-Karten-Deckbau ("20.000 über 60") Möglichkeiten, das sind - praktisch - unendlich viele und es hilft wenig, dass 99,99999..% davon sinnlos oder synergiearm sind.

Dazu kommt, dass Synergien zwischen Karten unterschiedlichste Dimensionen haben (Manafarbe, Wordingsynergien, Combopotential etc.)

Weiter kommen Metabetrachtungen hinzu. Es gibt ja kein "bestes" Deck.

 

Ich hab im Urin, dass Go mit seinen zweifarbigen Steinchen, dreieinhalb Regeln und 361 Felderchen ein Staubkorn im Vergleich zur MTG-Milchstraße ist. Aber ich hab Go auch nur 2 Jahre lang gespielt, weiß also nix davon (das war nicht unbedingt Ironie^^).
 

 

P.S.: Das alles war unter der Prämisse "Dominieren wie ein Weltmeister". Die Hearthstone-KI kann heute schon ab und zu ein bisschen auf Casual / Anfängerniveau mitspielen.

Bearbeitet von The green one, 02. Januar 2021 - 20:01.

[Nekrataal der 2.]

Eine adäquate "KI" zu trainieren (wobei man im Falle von AlphaGo & Co. eher von Machine Learning oder Neuronalen Netzen spricht, anstatt von einer klassischen KI im herkömmlichen Sinne) sollte heutzutage, in Zeiten unzähliger Deep Learning Frameworks, für jeden, der schon mal ein wenig in Python programmiert hat, kein großes Problem mehr darstellen. Die große Herausforderung sehe ich in der Bereitstellung einer Simulation, also der Regeln und Spielmechaniken, die ja ständig erweitert werden. Hat man erst einmal so eine Simulation, kann man die Algorithmen wie bei AlphaGo gegen sich selbst antreten lassen und so mit entsprechenden Rechenkapazitäten beliebig lange trainieren lassen. Theoretisch könnte man die Trainingsphase auch durch aufgezeichnete Partien menschlicher Spieler verkürzen, dies würde jedoch nichts weltbewegendes an der prinzipiellen Erlernbarkeit oder der Stärke der KI ändern.

 

Eine weitere Komponente in MtG ist ja der Deckbau, der dem Ganzen nochmal eine gewisse Varianz verleiht. Streng genommen müsste man die KI vor Beginn jeder Partie ein komplettes Deck bauen lassen. Ich denke, auch dieses Verhalten ließe sich antrainieren, da der Fundus wirklich spielbarer Karten(-kombinationen) ja sehr überschaubar ist und diese sich im Allgemeinen auch sehr ähneln.

 

Ein Deck im Vacuum zu bauen ohne dieses zu Testen führt wohl zu keinem guten Deck, insofern geht das eine nicht ohne das andere.

 

Einfach eine grosse KI zu trainieren ist wohl nicht der Weisheit letzter Schluß, sonst hätte jeder Dumbo schon das Travelling Salesman Problem vor Jahren gelöst. Der Clue bei Magic dürfte sein (mit Verweis auf oben verlinkten Artikeln) mit welchen Verfahren und ob man überhaupt derart komplexe Probleme lösen kann .

 

Die Simulationumgebung gibt es ja z.B. in MTGO. Kann man sicher mit einfachen APIs fernsteuern.

Bearbeitet von Nekrataal der 2., 02. Januar 2021 - 21:26.

[demon_mfg]

Ein Deck im Vacuum zu bauen ohne dieses zu Testen führt wohl zu keinem guten Deck, insofern geht das eine nicht ohne das andere.

 

Einfach eine grosse KI zu trainieren ist wohl nicht der Weisheit letzter Schluß, sonst hätte jeder Dumbo schon das Travelling Salesman Problem vor Jahren gelöst. Der Clue bei Magic dürfte sein (mit Verweis auf oben verlinkten Artikeln) mit welchen Verfahren und ob man überhaupt derart komplexe Probleme lösen kann .

 

Die Simulationumgebung gibt es ja z.B. in MTGO. Kann man sicher mit einfachen APIs fernsteuern.

 

Wenn wir von künstlicher Intelligenz sprechen, dann geht es ja nicht darum, irgendwelche Probleme in ihrer Vollständigkeit zu lösen, sondern eine möglichst gute Lösung zu approximieren. Gerade weil diese Probleme so komplex sind und wir die Lösung nicht einfach berechnen können, brauchen wir lernende Systeme. Ich gebe dir Recht, dass ein paar Neuronen zusammenklicken höchstwahrscheinlich nicht ausreicht, um ein Spiel wie MtG zu lernen. Dazu ist der Aktionsraum viel zu groß. Aber mit einer geschickten Wahl der Lernparameter und einer vernünftigen Regularisierung kann ich mir schon vorstellen, dass man in absehbarer Zeit einer KI Magic spielen beibringen kann. Der Vorteil einer Simulation wäre ja, dass man sich beliebig viele Daten erzeugen könnte, sodass als limitierender Faktor dann nur noch die Rechenzeit übrig bleibt.

 

Da MTGO nicht frei verfügbar ist, habe ich mich damit noch nicht auseinandergesetzt. Gut möglich, dass es hier entsprechende APIs gibt, die sich dafür anbieten.
 

I beg to differ:

Statistisch und ganz grob-dumm gesagt gibt es beim 60-Karten-Deckbau ("20.000 über 60") Möglichkeiten, das sind - praktisch - unendlich viele und es hilft wenig, dass 99,99999..% davon sinnlos oder synergiearm sind.

Dazu kommt, dass Synergien zwischen Karten unterschiedlichste Dimensionen haben (Manafarbe, Wordingsynergien, Combopotential etc.)

Weiter kommen Metabetrachtungen hinzu. Es gibt ja kein "bestes" Deck.

[...]

 

Ich bin kein kompetitiver MtG-Spieler, aber ich vermute selbst in den Eternal Formaten sieht man max. nur 1000 bis 2000 verschiedene Karten regelmäßig. Natürlich sind das immer noch viel zu viele, um alle sinnvollen Möglichkeiten durchzuprobieren, aber wie oben bereits geschrieben ist das ja auch gar nicht unser Anspruch. Ich würde einer KI wahrscheinlich erstmal von Menschen konstruierte Decks geben und ihr Magic spielen beibringen. Wenn sie das beherrscht, kann man vielleicht ein paar Karten nach jedem Match tauschen lassen. Mit einem entsprechend cleveren Clusteralgorithmus lässt sich auch hier der Aktionsraum massiv einschränken. Ich würde schon erwarten, dass sich die Auswirkungen bestimmter Karten auf das Spielgeschehen bemerkbar machen und dass man auf dieser Grundlage einer KI auch den Deckbau beibringen kann.

Bearbeitet von demon_mfg, 02. Januar 2021 - 23:19.

[P0LTERGEIST]

Bei Schach, Go oder irgendwelchen Arcade Games startet man immer aus der gleichen Position und hat immer den gleichen weg. Bei einem 60 Karten Deck gibt es 60! (*) mögliche Reihenfolgen in denen das Deck initial gemischt werden kann. Selbst wenn die Anzahl der Starthände vergleichsweise klein ist bleiben 53! Wege wie sich das eigene Spiel entwickelt. Damit eine AI ohne vorgaben lernen kann braucht sie aber immer wieder die gleiche Aufgabe und ein Bewertungskriterium. Da man aber bei Magic wohl niemals das gleiche Spiel 2 mal spielt müsste man anfangen vorgaben zu machen. Wie z.B. Anzahl der Handkarten im vergleich zu den Handkarten des Gegners, Lp ... Board Power. Letzteres ist z.B. auch wieder ein Problem es gibt Decks mit Boardwipes usw. 

 

Aber angenommen man schafft es Bewertungskriterien für alle Matchups zu schreiben, man schafft es mit hoher Wahrscheinlichkeit die gespielten Deck Karten vorherzusagen und und und  dann hat man das äquivalent zu einem "klassischen" Schach Computer der aber durch die Menschlichen, vermutlich nicht perfekten, Vorgaben sich davon unterscheidet was deepLearning bei ALphaGo und co liefert. 

 

 

* je nach deck weniger durch Duplikate.