spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

So, da bin ich wieder
Erst mal Gratulation an Domin für der ersten Punkt!

Über Nacht sind auch Davids Ergebnisse fertig geworden: Siehe hier. Wie erwartet ist seine KI die beste, ist aber auch beachtlich komplex. Ich blicke da ohne weiteres nicht durch Ich würde empfehlen sie nicht anzufassen und eine andere weiter zu verbessern. Eine gute KI kann definitiv simpler sein.

Interessant finde ich übrigens LuggLuggs KI. Er hat die KI bereits Montag abgeschickt, hat den Angsthasen lediglich ein wenig erweitert und kann trotzdem fast alle anderen KIs besiegen. Ich denke an seiner KI lohnt es sich am meisten, sie weiter zu entwickeln.

Im Paket ist jetzt übrigens eine Exe enthalten, mit der man sich ganz einfach jedes Spiel ansehen kann. Auch meine KI kann man sich darin angucken, die Ergebnisse dürften nur leicht abweichen, weil ich gerade noch einen Bug darin fixen musste (hab ausversehen an einer Stelle die Standard rand() Funktion aufgerufen). Sobald meine KI geschlagen wird werde ich auch den Sourcecode veröffentlichen, aber bis dahin will ich warten, weil ich ja bei der Entwicklung einen Vorteil hatte.

Noch ein paar Anmerkungen zu einigen Fehlern, die gemacht wurden:
- for each ist kein Standard C++, sondern eine Microsoft Erweiterung.
- Standardtypen werden nicht default mit 0 initialisiert. Bitte setzt alle Member in der Reset Funktion zurück und fügt einen ctor zu jeder eigenen Klasse hinzu, in der alle Member initialisiert werden.
- Wenn eine Funktion einen Rückgabewert hat sollten auch wirklich alle möglichen Pfade der Funktion eine return Anweisung haben. (zumindest die, die erreicht werden können)

Glücklicherweise war Domins Einsendung korrekt, weshalb es mir erspart geblieben ist, Beiträge disqualifizieren zu müssen Ich habe die Fehler in den Einsendungen mit entsprechenden Kommentaren korrigiert.

Zitat von »Koschi«

Kleinen Verbesserungsvorschlag hätte ich, die Tabelle wer gegen wen gespielt hat komplett zu füllen, so kann jeder Teilnehmer in einer einzigen Spalte/Zeile lesen wie die Ergebnisse waren. Aktuell muss man die Ergebnisse in seiner Zeile und seiner Spalte nachlesen (ausgenommen erster und letzter in der Tabelle).

Einfacher gesagt als getan. Ich find's so auch eigentlich übersichtlicher, weil keine doppelte Information vorhanden ist.

Zitat von »TGGC«

Tja, wie gesagt, ich finds eigentlich Scheisse. Man hat einen Arsch voll Rechenzeit und alle guten KIs benutzen daher den gleichen Brute Force Algorithmus und welche gewinnt haengt davon ab, wer in der erlaubten Rechenzeit mit ein paar Tricks und Optimierungen die meisten Iterationen hinbekommt. Ich habe ja extra 2 KIs mit unterschiedlichen Ansaetzen eingeschickt, leider gibt es keine absolute Messung der Zeit, aber die "schlechte" hat pro verbrauchte Rechenzeit vermutlich hundert mal mehr Punkte gemacht. Und der Witz ist, das man die schnelle immer noch als Heuristik in die langsame einsetzen kann, um die langsame besser zu machen.

Also wenn ich die verfügbare CPU Zeit verkürzen würde glaube ich nicht, dass das irgendwas an den KIs verändern würde. Sie würden einfach nur schlechter sein. Der Grund ist einfach, dass das Spiel nicht abstrahiert werden kann, zumindest nicht ohne riesigen Aufwand. Das finde ich aber nicht schlecht. Im Gegenteil, so schreibt man eine KI, die relativ unabhängig von dem eigentlichen Spiel ist und lernt so Konzepte, die auf völlig andere Bereiche anwendbar sind. Und Bruteforce ist nicht gleich Bruteforce. Es ist unmöglich alle Zustände vorauszuberechnen und man muss den Suchbaum sinnvoll einschränken. Ich denke da ist viel Potential für viele Ideen.

Zitat von »LuggLugg«

Ich kann den neuen Contest Code unter Ubuntu nicht mehr bauen.
Folgende Datei wird nicht gefunden:
...
woher soll diese Datei kommen ?

Hab's gefixt. (kannst aber auch einfach auskommentieren)

Zitat von »David Scherfgen«

Sehe ich das richtig, dass deine KI davon ausgeht, dass es nur 36 verschiedene x-Positionen gibt, die man erreichen kann? Tatsächlich sind es ja doppelt so viele. Man bewegt sich zwar nur in Schritten von 250, aber wenn man einmal gegen das Netz läuft, kann man plötzlich andere x-Positionen erreichen (dafür die alten nicht mehr). Läuft man dann wieder gegen die "Außenwand", kann man wieder die ursprünglichen Positionen erreichen. Das liegt daran, dass das Netz die Bewegung nicht an einem ganzen Vielfachen von 250 stoppt. Keine Ahnung, ob Helmut das mit Absicht gemacht hat ...

Nein, bis du das sagtest wusste ich das nicht mal . Ich habe mit den Werten einfach so lange gespielt, bis es einigermaßen zum echten Blobby Volley passte. Aber so ist das nun mal in der Programmiererwelt. Nicht alles ist glatt, standardisiert und besteht aus Zweierpotenzen

Zitat von »David Scherfgen«

Was ich stattdessen umgesetzt habe, ist die Wiederverwendung des Suchbaums über mehrere Frames hinweg, so dass nicht alles neu berechnet werden muss. Und die Entscheidungen an den Knoten sind nicht rein zufällig, sondern gehen bevorzugt in die Richtung, wo vorher schon gute Züge gefunden wurden. Das ist angelehnt an Monte Carlo Tree Search (MCTS), eine sehr beliebte Technik für General Game Playing-KIs (KIs spielen Spiele, die sie vorher gar nicht kennen). Darum meinte ich auch, dass man bei so einem Contest sehr viel lernen kann, denn ich habe deswegen einige Paper über MCTS gelesen. Da muss man allerdings aufpassen: Der normale MCTS-Algorithmus ist für sequenzielle Spiele gedacht, wo die Spieler abwechselnd ziehen. Es gibt aber auch eine Variante für gleichzeitige Züge.

Hach was es alles gibt Wie wärs mal mit nem Contest, wo die KI vorgegeben ist und man ein Spiel dazu schreiben muss? Fällt mir so grad als Idee ein.

Zitat von »David Scherfgen«

Übrigens, schau mal, wie stark das Ergebnis bei den zufallsbasierten KIs variiert.
Bei den Spielen zwischen deiner KI und meiner KI haben wir Ergebnisse (ohne CPU-Faktor) zwischen 15:4 und 15:11 - nur weil jeweils ein anderer Random Seed benutzt wurde.
Deine KI ist augenscheinlich noch etwas besser als meine, aber wenn meine jetzt ungefähr auf demselben Niveau wäre, dann müsste man viel weiter als nur bis 15 spielen, um ein aussagekräftiges Ergebnis zu erhalten. Das zu demonstrieren, war auch ein Grund, warum ich 7 KIs abgegeben habe.

Ja, also meine ursprüngliche Idee war, das durch die Tatsache auszugleichen, dass jeder mehrere KIs einsenden kann. Jetzt ist mir da aber auch ne kleine Lücke aufgefallen. Man kann die KIs so programmieren, dass sie absichtlich gegen eine eigene Eingesandte verlieren. So bekäme man Gratispunkte. Von daher werd ich jetzt wohl tatsächlich einfach mal den maximalen Score von 15 verzehnfachen und es zählt nur noch die zu letzt eingesandte KI. Ich muss dann noch mal schaun, dass durch die erhöhte Punktzahl nicht irgendwo Überläufe auftreten.

Zitat von »TGGC«

Irgendwie widersprichst du dir selbst. Wenn die KIs schlechter wären, dann haette sich doch schonmal die Platzierung geaendert.

Naja ich meinte, dass selbst wenn man jetzt die KIs so anpassen würde, dass sie wesentlich weniger Rechenzeit bräuchten, sich wahrscheinlich nichts an der Platzierung ändern würde. Ich sehe auch nicht, dass jetzt KIs mit stumpfem Bruteforce gewonnen hätten.