Verstehe Dich dennoch nicht. Egal wieviele Zustände es geben KANN, es ist doch zu jedem Zeitpunkt nur ein einziger. Den gesamten Speicher verbrauchen würdest Du doch nur, wenn eine KI versucht herauszufinden, was sie machen soll, und dazu tatsächlich alle möglichen Züge vorausberechnen will. Und genau das muß man eh nicht tun, weil KIs für solche Spiele mit brute force eh nicht weit kommen. Bzw. kämst Du auch ohne Unendlich schnell an den Punkt, wo der Speicher nicht ausreicht. Sagen wir Du spielst einen Demonic Tutor, der gibt Dir eine beliebige Karte aus dem Deck auf die Hand. Da Du wählen kannst, sind alleine das ein paar Dutzend Optionen und jede eröffnet weitere Möglichkeiten, sobald Du sie auf der Hand hast. Das potenziert sich so schnell, daß die Anzahl möglicher Züge und Dinge, die man tun kann, sehr schnell so groß ist, daß es auch egal ist, ob nun unendlich oder nicht.
Klar, aber verschiedene Spielzustände müssen verschiedene Repräsentationen haben. Damit kannst du für mit begrenzt viel Speicher auch nur begrenzt viele Zustände auflösen.
Es gibt aber (deutlich) mehr Zustände.
Ist in etwa so, wie wenn jemand alle natürlichen Zahlen durchzählt:
Man hat jedesmal nur eine Zahl, lässt aber jede beliebige als obere Grenze gewählte natürliche Zahl hinter sich.
Bevor weiter an einander vorbeireden: Bei welcher Berechnung mußt Du denn ALLE laden?
Im normalen Spiel musst du zu jedem Zeitpunkt nur einen Zustand im Speicher haben.
Bei der ganzen Theorie, die hier behandelt wird, würde mich stattdessen einfach mal interessieren, ob bei den vielen Milliarden HS-Spielen schon ein einziges identisch war, sprich wo beide Spieler dieselben Karten in derselben Reihenfolge mit demselben Ergebnis ausgespielt haben. Wohl eher nicht, weil ja alle 4 Monate Karten dazu kommen und alle 12 Monate 3 Erweiterungen rausfallen. Oder?
Ja, eben. Warum ist ein Spieledesigner dann “bekloppt, wenn er unendlich viele Zustände zuläßt”? Er läßt doch nur zu, daß das Spiel so offen wie möglich ist, um es so interessant und abwechslungsreich wie möglich zu machen. Einer potenziellen game engine kann es auch Wurst sein, solange sie nur den jeweils aktuellen Zustand anzeigen muß. Wo also ist das Problem?
Ist im Grunde genommen dieselbe Berechnung wie beim Geburtstagsparadoxon - nur mit deutlich größeren Zahlen…
(ein Spiel entspricht einer Person; ein Spielverlauf entspricht einem bestimmten Tag).
Wenn du die Reihenfolge der verdeckten Karten in deinem Restdeck nicht mitzählst, dann könnte die Wahrscheinlichkeit möglicherweise genügend hoch sein… ist aber schwer abzuschätzen, da man zu viele Daten nicht kennt.
Wenn es tatsächlich mal zwei identische Spiele gabm dann würde Ich auf kurz nach Naxxramas tippen, bevor der damalige Jäger generft wurde, da waren viele Spiele schön kurz der Kartenpool sehr klein, nur wenige Decks unterwegs und es wurde relativ viel gespielt.
Der Spieleentwickler muss die Kodierung der Spielzustände festlegen, bevor das erste Spiel gespielt wird und egal, wie die Kodierung ist, ein endlicher Speicher hat immer eine größte Zahl, die man dort ablegen kann.
Hat man unendlich viele erreichbare Spielzustände, dann gibt es immer eine Zahl, die einen Spielstand repräsentiert die größer ist, als der Speicher fassen kann.
Ist beispielsweise die Kodierung so gewählt, dass jede natürliche Zahlen genau einem ganz bestimmten einzigartigen Spielzustand entspricht und dein Speicher ist 1 Byte groß, dann kannst du maximal 256 verschieden Zahlen (=Spielzustände) im Speicher darstellen.
Jede andere Spielstand wird durch eine Zahl dargestellt, die größer ist als 256 und somit nicht in den Speicher (von einem Byte) passt.
Ist der Serverspeicher 1 Yobibyte groß, dann passt jeder Spielstand der durch eine Zahl dargestellt wird, die grösser oder gleich als 2^(80*8) ist, nicht in den Speicher.
Edit:
Ich kauf mir jetzt erstmal ein Eis und empfehle das auch allen anderen.
Edit2:
Wieder da, esse ein Eis. Selbst Youtube ist es zu warm… schlägt mir das hier vor… und ich hör mir das bis zum Ende an…
Es wäre außerordentlich dumm bzw. unnötig, auf diese Weise Spielzustände zu speichern. Ich möchte außerdem darauf hinweisen, daß es bereits 1997 Shandalar gab, welches Magic erfolgreich umgesetzt hat inklusive KIs. Und kam mit 16 MB RAM aus.
Ich rede von Spielzuständen und nicht von Spielständen.
Um Spielzustände kommst du nicht herum egal welches Spiel du programmierst. EIn Spiel ist abstrakt gesehen nichts anderes als eine Abfolge von Zuständen, die man mit Eingaben beeinflussen kann.
Ein Spielzustand bei Schach wird zum Beispiel eine Stellung genannt. Programmierst du Schach, dann wird dir nichts anderes übrig bleiben, als die Stellung irgendwie zu kodieren, ob als einzelne Zahl, als Array, als String (etwa „Weiß: König A1, Dame, …; Schwarz: König…“) oder sonstwie:
Alles benötigt Speicher egal, ob als RAM oder als Festspeicher oder sonstwie und ist insgesamt nichts anderes, als eine gigantische einzelne Zahl.
Schafft man es alle Zustände als eine zusammenhängende Teilmenge der natürlichen Zahlen zu kodieren, die die 0 enthält, dann hat man eine minimale Darstellung der Zustände gefunden.
Ich kenne diese Software leider nicht, aber wenn sie tatsächlich versucht unendlich viele Stellungen umzusetzen, dann kann man definitiv eine Stellung angeben, die nicht mehr in den Speicher passt.
Bei 16 MiB muss man nur mehr als 2^(8*20) ~=1.462*10^48 Stellungen finden (etwa 1 Kreatur auf dem Feld, 2 Kreaturen auf dem Feld, … 10^49 Kreaturen auf dem Feld).
Zum Speicherplatz: Das Go-Programm, dessen Name ich jetzt gerade nicht finde, und das extrem gut ist, hat auch nur brute force und abschleißende Stellungsbewertung. Speicherplatz ist heute kein Thema, wir haben große Speicher und Festplatten (kann man ja Datenbanken anlegen und durchgehen, sollte der Arbeitsspeicher knapp werden). Und ja, ich kann auch Go … naja …
Zhool: Hast du Hinweise, wo man sich mal über KI-Programmierung schlau machen kann?
Vielen Dank für die ganzen Beiträge, muss mich leider erstmal mit anderen Dingen beschäftigen. Bin später am Tage wieder da, wenn mich die Hitze nicht schmelzen lässt …
Ouh… KI ist ein schwieriges Thema, da gibts haufenweise Bücher zu.
Das hier halte ich für einen guten Kurs, aber ist nicht unbedingt einfach.
Ansonsten gibts auf http://deeplearning.net/ einiges an Leseempfehlungen, Demos, Software und Tutorials.
Warum zum Teufel mußt Du jeden erdenklichen Zustand mappen? Ist das ein Relikt aus der prozeduralen Programmierung? In der objektorientierten Programmierung, die seit Jahrzehnten Standard ist, siehts do so aus: Wenn es gerade nur 3 Kreaturen gibt, gibts drei entprechende Objekte. Und so kann auch der Spielzustand beschrieben werden. Da muß ich nicht für alle potenziellen Kreaturen Speicher vorhalten und im Vorwege benennen. Wir haben inzwischen sowas wie dynamische Arrays ![:wink:](https://d39ktvutt95kg6.cloudfront.net/de/hearthstone/images/emoji/twitter/wink.png?v=6" ":wink:")
Oder redest Du von dem Fall, wo tatsächlich einer mit einer Combo irgendwas eine Million mal generiert?
Nein, das ist kein Relikt. Der Gesamtspeicher (= ROM + RAM + hdd + … ) eines Computers entspricht immer nur genau einer Zahl.
Ist dein Gesamtspeicher beispielsweise 1KiB groß, dann ist diese Zahl in hexadezimaler Darstellung 1024 Ziffern lang, hast du 1MiB Speicher, dann ist die Zahl 1048576 Ziffern lang, usw.
Egal, was du mit dem Speicher anstellst er bleibt eine Zahlenrepräsentation.
Erreicht ein Spiel einen bestimmten Zustand, so enthält der Gesamtspeicher eine Zahl, die diesen Zustrand repräsentiert.
Ich habe nirgendwo gesagt, dass du Speicher vorhalten musst, sondern, dass du für jeden im Spiel erreichbaren Zustand wissen musst, wie dein Programm diesen im Speicher darstellt.
Dabei ist es egal, ob du die Kodierung explizit (als Zahl die den Gesamtspeicher darstellt) oder (wie in deinem Beispiel mit den 3 Kreaturen) abstrahiert darstellst; es endet alles als Zahl die den Gesamtspeicher in dem jeweiligen Computersystem darstellt.
Wenn du als Kodierung des Spielzustandes Objekte nutzt, dann wird das vermutlich darauf hinauslaufen (z.B. wenn man Diener erzeugt und so anordnet, dass deren Leben den ersten 100 Mio Ziffern der Zahl Pi entspricht).
Bei anderen Kodierungen kann das aber deutlich anders aussehen.
Du verwechselst bestimmt brute force (= Berechnung aller Möglichkeiten und Wahl des besten Zuges) mit irgend etwas anderem.
Würde das Go Programm tatsächlich brute force nuzten, dann müsstest du auf den ersten Spielzug des Computers ein paar hundert Milliarden Jahre warten und es benötigte einen Speicher mit mehr Bits, als es Atome im sichtbaren Universum gibt.
Das ähnlichste zu brute force wäre noch eine begrenzte Breitensuche, wie sie z.B. beim Alpha-Beta-Pruning genutzt wird.
Die besten Programme sind meines Wissens aber AlphaGo und AlphaGo Zero, die beide (unterschiedlich gut trainierte) neuronale Netze sind.
Literatur oder Links die ich empfehlen könnte habe ich jetzt nicht und ein Info-Studium nur dafür wäre etwas overkill.
Eine schnelle google-Suche ergab, z.B. (ich habe mir nur die Inhaltsangabe durchgelesen):
- für
Einführung in die KIdas folgende Skript (Einführung in die Methoden der Künstlichen Intelligenz), das der Übersicht nach einen leichten Einstieg geben sollte, aber auch wirklich nur die Grundlagen enhält (keine neuronalen Netze, Eingabe von Bildern, usw. enthält). - für
Grundlagen der Neuronalen Netzscheint dieses Skript ganz gut zu sein
Für Eingaben von Bildern, etc. habe ich online auf die Schnelle leider nichts gefunden.
Sorry, ich kann Dir nicht folgen. Ich weiß nur, daß von Magic das Shandalar Spiel gab, dann Magic Online, dann Duels of the Planeswalkers, dann Magic Duels und nun Magic Arena. Keines dieser Programme hat Probleme wie Du sie beschreibst, obwohl alle Magic mehr oder weniger 1:1 umsetzt. Wie also kann das sein, wenn bereits das total simplifizierte Modell von Magic aus diesem Artikel turing complete ist und das angeblich ein so großes Problem bei der Speicherallokation darstellt?
Ist es nicht. Nehmen wir vereinfacht mal Shandalar und generierte Token. Es gibt im Grunde nur 3 Möglichkeiten:
- Es gibt keine Möglichkeit unendlich Token zu generieren, damit fällt das Speicher-Problem weg.
- Es gibt eine Möglichkeit, aber Shandalar an sich limitiert die Token die gleichzeitig im Spiel sein können. Das ist ebenfalls kein Problem.
- Es gibt eine Möglichkeit und keine Limitierung. Dann stürzt es einfach ab wenn mehr Speicher gebraucht wird als vorhanden ist.
Ich weiß auch nicht warum wegen Turing-Vollständigkeit irgendein Aufriss gemacht wird. Ich mein selbst die mov Anweisung aus dem x86 Befehlssatz ist Turing-Vollständig… Und das als einzelne Anweisung. Turing-Vollständigkeit hat nun rein gar nix mit Komplexität zu tun.
Genau darauf will ich ja hinaus! Der Artikel spricht ja von nichts anderem als turing complete und schließt daraus, daß deswegen Magic das komplexeste Spiel überhaupt ist. Und das ist mMn völliger Quark.
Ich meine, ja, Magic ist verdammt komplex - aber dieser Test beweist es nicht und geht völlig an dem vorbei, was Magic ausmacht.
Kel, Zool: Vielen Dank! Schau ich mir mal an.
Hm, was ich Brute Force nannte, heißt wohl eher Begrenzte Tiefensuche? Wobei bei steigender Zugzahl dann die möglichen Ergebnisse so zunehmen, daß eine zufällige Auswahl getroffen wird, welche Varianten noch weiter verfolgt werden. Das garantiert natürlich nicht das finden des bestmöglichen Zuges, aber mit zufriedenstellend großer Wahrscheinlichkeit das finden eines sehr guten Zuges in Angemessener Zeit. So habe ich es zumindest bislang verstanden.
Ist schon spät …
@Puschkin:
Vielleicht habe ich mich in meinen Erklärungsversuchen zu sehr ins Detail gestürzt. Ich formulier meine obige Aussage mal mithilfe der Punkte 1-3 die Kel angegeben hat:
Ich finde es bekloppt, als Spieledesigner unbedingt ein Spiel herauszubringen zu wollen, bei dem Möglichkeit 3 eintreten kann, bei dem also das Spiel so designed wurde, dass es bei bestimmten Spielverläufen sicher abstürzt.
Ich tippe darauf, dass keiner von euch beiden Informatik studiert hat:
Ein Informatiker meint mit Komplexität eines Problems (oder Systems) etwas ganz bestimmtes, das eher wenig mit der umgangssprachlichen Nutzung dieses Wortes zu tun hat.
Dazu muss ich aber leider etwas ausholen:
Es gibt zwei Arten von Turingmaschinen.
Je nachdem wie viel Zeit der schnellste Algorithmus auf diesen Turingmaschinen in Abhängigkeit von der Anzahl der benutzten Variablen benötigt, wird ein Problem A bestimmten Mengen zugeordnet (dasselbe wird auch für andere Systeme gemacht, aber da die realisierbaren davon alle schlechter sind…).
Diese Mengen nennt man Komplexitätsklassen, denen man bestimmte (wohlbekannte) Namen gibt z.B. NP (:= Alle Probleme die man auf einer nichtdeterministischen Turingmaschine in polynomieller Laufzeit Lösen kann).
Man sagt dann A liegt in NP, wenn A ∈ NP.
A wird als NP-vollständig bezeichnet, wenn A nicht in einer „schnelleren“ Menge liegt.
Ist ein Problem Turing-vollständig, dann kann benötigt der schnellste Algorithmus auf allen Turningmaschinen unendlich lange, um das Problem zu lösen.
Für Systeme wird Komplexität aus der anderen Sichtweise definiert:
Je nachdem, wie viele Probleme ein System (z.B. eine Turingmaschine) mit dem jeweils optimalsten Algorithmus lösen kann, wird dieses ebenfalls verschiedenen Mengen zugeordnet.
Ist ein System B Turing-vollständig, dann kann es alle Probleme Probleme lösen, die auch eine Turingmaschine lösen kann und alle Probleme, die B lösen kann können auf einer Turingmaschine berechnet werden.
Sagt ihr Umgangssprachlich „MTG ist soundso komplex“, dann meint ihr damit eine Partie MTG zu gewinnen ist ein Problem, dass so und so schwer ist (entpricht der Laufzeitkomplexität).
(Edit: Ein Informatiker würde dieses Problem als „MTG-Problem“ bezeichnen.)
Ein Informatiker meint mit MTG aber das Spiel selbst, das abstrakt betrachtet ein (Regel-)System ist und interessiert sich salopp gesprochen bestenfalls dafür, ob man darauf auch Doom spielen kann, wenn er die Komplexität dieses Systems untersucht.
Dank der oben verlinkten Forschungsgruppe wissen wir jetzt:
Ja, man kann (auch wenn es nicht besonders schnell laufen wird, da es momentan noch „manuell angetrieben“ wird).
(Aber wie schon gesagt… ist wissenschaftlich gesehen nicht so spektakulär… .)
Turing-Vollständigkeit hat dennoch nichts mit Komplexität zu tun. Weder der Umgangssprachlichen, noch der Informationstheorethischen. Weil es weder eine Grundkomplexität (umgangssprachlich) noch eine Anfoderung an Zeit oder Platz (aus der Komplexitätstheorie) stellt. Damit ist lediglich die Möglichkeit gemeint das eine Turingmaschine emuliert werden kann (unter zur hilfe nahme von theorethisch endlosem Speicher).
Und das ist, salopp gesagt, relativ einfach möglich wenn man addieren kann (als einfachste Art der Speicherverschiebung), Bedingte Anweisungen vorhanden sind und schleifen vorhanden sind. Wenn man es also schafft eine Imperative Programmiersprache zu abstrahieren. Als eine von mehreren Möglichkeiten.
Ich bin seit einer Woche Informatikkaufmann ![:slight_smile:](https://d39ktvutt95kg6.cloudfront.net/de/hearthstone/images/emoji/twitter/slight_smile.png?v=6" ":slight_smile:")
Du vergißt einfach, daß Magic als physikalisches Kartenspiel designed wurde und dort waren Begrenzungen nicht nur unnötig sondern ungewollt. Man konnte in Magic anfangs sogar jede Karte so oft im Deck haben, wie man will.
Nun kamen später Computeradaptionen dazu und klar sollte man sich dabei überlegen, Situationen mit einer Million tokens zu vermeiden. Das hat aber doch nichts mit dem ursprünglichen Design von Magic zu tun.
Und der Artikel redet ja auch von Komplexität eher in der ungangssprachlichen bzw. allgemeinen Form, da die Kernaussage ist, “Magic ist das komplexeste Spiel”. Es wird Turing-vollstänigkeit als “Beweis” herangezogen und nur dadurch kommen wir in den Bereich der Informatik.
Aus reiner Informatiksicht und unter der Annahme, Magic wäre als Compterspiel konzipiert worden, magst Du recht haben. Dem ist ja aber nicht so. Und was anderes habe ich auch nie gemeint als: Turing-Vollständigkeit ist irrelevant für die tatsächliche Komplexität eines Spiels - nicht aus der Sicht eines simulierenden Programms sondern aus der Sicht eines Spielers, der versucht, optimale Spielzüge zu finden. Und da gehört dann auch eine KI zu. Und der Test im Artikel darum geht, zu ermitteln, ob diesen Zug ein Sieg möglich ist, reden wir hier durchaus von etwas wie KI.