@domin:
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 ...
Aber da gibt es noch ein paar Probleme. Manchmal springt deine KI wild drauf los, bevor der Ball im Spiel ist, und trifft ihn dann beim Anstoß so ungünstig, dass sie sich sofort ein Eigentor schießt. Vor allem bei zwei Bällen habe ich das oft beobachtet.
Meine KI macht gegen deine hin und wieder einen dummen Fehler, indem sie hochspringt und deine dann den Ball unter ihr durchschießt. Meine KI springt zu oft. Springen ist eigentlich schlecht, da man für die nächsten 33 Frames keinen Einfluss mehr auf die eigene y-Position hat.
auch wenn eine Brute Force Tiefensuche wahrscheinlich schwer zu schlagen ist
Das glaube ich nicht. Brute Force kommt schnell ans Limit und kann nicht besonders weit voraussehen. Oft werden triviale Lösungen übersehen. Ich glaube, dass Helmut da was ganz Cleveres entwickelt hat, so wie ich ihn kenne. Seine "Profi"-KI spielte ja auch schon ziemlich stark.
Mir schwebte da eine Suche vor, die nicht in Schritten von 1 rechnet, sondern immer so weit, bis es zum nächsten Ballkontakt oder Punkt kommen kann. Das sind oft so um die 30 Frames. Mit ein paar Tabellen kann man dann bestimmen, wohin sich die Spieler in dieser Zeit bewegt haben könnten, und sampelt diese möglichen Positionen. Dabei kann man diejenigen mit höherer Wahrscheinlichkeit samplen, die zu einem Ballkontakt führen. Das ist cleverer als einfach stupide eine Folge von Tastendrücken zu samplen, denn davon führen viele zur selben Situation (z.B. Links, Links, Springen führt zur selben Situation wie Springen, Links, Links - wenn es währenddessen nicht zum Ballkontakt kommt). Man reduziert dadurch den Suchraum und kann in der begrenzen Zeit mehr Züge untersuchen. Ich habe damit angefangen das zu implementieren, aber die Ergebnisse waren eher schlecht. Wahrscheinlich habe ich da noch einen Bug drin. Auch ist es da nicht so trivial, sich am Ende der Suche für den besten Zug zu entscheiden.
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.