Du bist nicht angemeldet.

Lieber Besucher, herzlich willkommen bei: DeveloperTalk. Falls dies dein erster Besuch auf dieser Seite ist, lies bitte die Hilfe durch. Dort wird dir die Bedienung dieser Seite näher erläutert. Darüber hinaus solltest du dich registrieren, um alle Funktionen dieser Seite nutzen zu können. Benutze das Registrierungsformular, um dich zu registrieren oder informiere dich ausführlich über den Registrierungsvorgang. Falls du dich bereits zu einem früheren Zeitpunkt registriert hast, kannst du dich hier anmelden.

Erik

Profi

  • »Erik« ist der Autor dieses Themas

Beiträge: 1 274

Registrierungsdatum: 22.06.2011

Wohnort: Deutschland ;)

Danksagungen: 307

  • Private Nachricht senden

1

22.07.2013, 21:54

Sixpack KI

Moin moin.

Es geht um das Spiel Sixpack...

Einfach mal ein bisschen Brainstorming, was denkt ihr, wie man eine KI für so ein Spiel angehen könnte?

Mein Ansatz wär erstmal Minimax. Das Problem ist halt, dass man keine perfekte Information hat... Aber ist imo trotzdem nicht schlecht. Ich dachte auch man könnte, statt das immer in Echtzeit zu rechnen, einfach alle Möglichkeiten durchspielen, die es gibt. Sind ja endlich viele. Und dann hätte man eine Lookup-Tabelle, wodurch man immer den statistisch besten Zug findet. Aber es gibt natürlich extrem viele verschiedene Spielverläufe... Allerdings hätte man auch eine Rechenzeit von mehreren Monaten. Dadurch, dass es auch verschiedene Anfangsstellungen gibt, lässt sich das auch leicht auf viele Computer aufteilen. Ist das realistisch?

Vielleicht noch anderer Ideen? KNNs und GAs finde ich eig geil, könnte man vllt i-wie einbaun...

LG, Erik.
Beste Webite im Internet ( ͡° ͜ʖ ͡°)
xinra.de

Johannes S.

Fortgeschrittener

Beiträge: 444

Registrierungsdatum: 24.06.2011

Wohnort: Lychen

Danksagungen: 71

  • Private Nachricht senden

2

28.07.2013, 01:58

Auf anhirb erscheint es mir etwas unrealistisch alle Möglichkeiten durchzuproboieren, aber ich habe noch nicht genauer drüber nachgedacht.
Signatur ?

Erik

Profi

  • »Erik« ist der Autor dieses Themas

Beiträge: 1 274

Registrierungsdatum: 22.06.2011

Wohnort: Deutschland ;)

Danksagungen: 307

  • Private Nachricht senden

3

28.07.2013, 03:14

Tja... wenn man genauer drüber nachdenkt stimmt das schon. Immerhin geht das nichtmal bei Schach (warum auch immer :D) und ich hab das gefühl, es gibt hier mehr möglichkeiten :D

Realtime-Minimax wäre die andere Option. Das Problem ist halt, dass sehr viel unbekannt ist... Und weit wird man mit schrittweiser rekursion auch net kommen, selbst wenn mans extremst optimiert. Andererseits muss man das auch nicht, es gibt ja nicht so viele Züge... Wobei man allerdings auch fast keine Zeit pro Zug hat. Man müsste in der ZEit des Gegener-Zugs rechnen und seinen eigenen möglichst bis zum Ende hinauszögern (wobei das bei fast jedem Algo so ist, außer man legt es auf eine möglichst schnelle yolo-entscheidung an, um dem gegner eben weniger zeit zu geben, hört sich aber erstmal nach nem schlechten trade-off an...).

Mein KI-Masterplan ist ja immernoch ein KNN, dessen Gewichtung mit einem GA ermittelt wird. Damit würde man den Bruteforce-Charakter von Minimax umgehen, was die Rechenzeit deutlich optimieren würde, mit dem Nachteil, dass man nicht die optimale Lösung finden wird.

Ein KNN würde sich theoretisch anbieten, allerdings sind die 3 inputs (Eigene Steine, Gegener-Steine und Feld) und der Output (Züge) so krank und indirekt miteinander verknüpft, dass ein KNN sehr viele super-komplexe Schichten haben müsste. Auch nur einen Einzigen Validen Zug zu generieren würde ewig dauern.

Ein GA wäre einigermaßen gut, zumal das Punktesystem relativ differenziert ist (viele Abstufungen), allerdings auch nicht zu sehr.

Vielleicht könnte man es auch aus mehreren Modulen aufbauen, und für Teilbereiche verschiedene Algorythmen verwenden. Zum Beispiel das Feld auf bestehende Lines mit einem sehr schnellen KNN scannen (Mustererkennung ist ja eig ein Hauptanwendungsgebiet davon...), einen kleinen Minimax mit wenig Suchtiefe für den Zug und noch eine andere Methode für eventuelles Tauschen dedizieren, vielleicht auch noch ne Lookup-Tabelle, sowas wie das Eröffnungsbuch beim Schach einbauen. So könnte man auch einzelne Teile hardcoden, andere widerrum mit GAs trainieren.
Beste Webite im Internet ( ͡° ͜ʖ ͡°)
xinra.de

JuKu

Profi

Beiträge: 574

Registrierungsdatum: 29.09.2011

Danksagungen: 48

  • Private Nachricht senden

4

03.08.2013, 15:04

@Mehr Möglichkeiten:
Ja, da hast du wohl recht. ^^
Wenn euch mein Beitrag weitergeholfen hat, drückt auf "Bedanken"!
Danke! :D

Erik

Profi

  • »Erik« ist der Autor dieses Themas

Beiträge: 1 274

Registrierungsdatum: 22.06.2011

Wohnort: Deutschland ;)

Danksagungen: 307

  • Private Nachricht senden

5

07.08.2013, 17:36

Ich denke, ich werde mich erstmal daran machen, dass Spiel nachzuprogrammieren, damit wir nen besseren Client zum testen haben...
Beste Webite im Internet ( ͡° ͜ʖ ͡°)
xinra.de