Spielvorstellung (plus KI frage): Connect Four – Extreme

[M.F.G.]

Hey Leute,
seit längerer Zeit arbeite ich zusammen mit meinem Kommilitonen „haering“ zusammen an einem kleinem Spiel. Die Idee stammt noch aus Zeiten in denen ich meine langweilige Vorlesung nicht durch den Gebrauch eines Laptops aufpuschen konnte, sondern auf analoge Art und Weiß mit einem Blatt Papier und Stift den Unterricht erträglicher machen wollte:

Jeder kennt wahrscheinlich das Spiel „Vier Gewinnt“ ( engl. 'Connect Four' ). lame denkt sich jetzt jeder, im Netz gibt’s tausende Implementierungen dieses Spiels, nun haben wir aber dieses Konzept aufgegriffen und erweitert. Statt in ein starres 6x7 Spielfeld seinen von der Gravitation nach unten gezogenen Steine zu setzen, ist das Spielfeld bei uns unendlich groß. Gesetzt werden darf aber nur neben bereits liegenden Steine, gewonnen hat selbstverständlich derjenige, der als erstes vier Steine seiner Farbe in Reihe (horizontal, vertikal, quer) legen kann.
Und wer es auch immer gehasst hat, nur zu verlieren weil er als zweiter angefangen hat (der Anfänger wechselt natürlich zu beginn jeder runde), der sollte den „Expertmode“ testen: Hat Spieler A (welcher das Spiel begonnen hat) seine Reihe fertig, darf Spieler B noch einmal setzen. Sollte B es schaffen auch eine Reihe zu bauen, geht das Spiel für beide Spieler weiter.

Zudem haben wir das Spiel optisch aufgemöbelt und auf die Höhe der Zeit gebracht, man kann an dem selben PC zusammen spielen („Partymodus“), sich über Matchmaking mit einem fremden verbinden lassen und spielen (auch chatten durch Enter ist möglich) oder über eine direkt Verbindung einen Bekannten über TCP oder UDP (durch Eingabe der selben 'Connect ID') herausfordern. Vielspieler können versuchen alle Achievements zu erlangen und später folgt noch die Integration in Facebook (FB wir aber nicht erforderlich sein um es zu spielen) und die Portierung auf Android.
Uns und unseren Freunden hat es schon viel Knobel Spaß beschert, wer „Vier Gewinnt“ mochte, wird „Connect Four -Extreme“ lieben.
Sowohl Kritik als auch Lobe sind erwünscht


-Applet
-Webstarter
-jar-Datei


Und nun zu unserem Problem:
Wir wollen auch einen Singelplayer haben, dazu brauchen wir aber ein KI. Tja und da haben wir so unsere Probleme, per backtracking (also alle möglichen nächsten n Züge ausprobieren und dann schauen welcher Zug im Nachhinein die meisten wins und wenigsten loses mit sich bringt) haben wir es schon versucht (ne Zufall KI is genauso gescheit), ich glaub aber das es so nicht zu lösen ist: 1. Backtracking kostet viel Rechenpower ( bei tiefe 7-8 dauerts schon ne sec, bei fast leerem Spielfeld) und 2. sind die Kriterien die wir gewählt haben nicht ausreichen um sagen zu können ob ein Zug gut sein wird oder nicht.
Dh. Brauchen wir eure Hilfe für die KI, was ist der Ansatz den wir verfolgen sollten.

Viel Spass beim spielen und schon mal danke für alles was ihr hier so schreibt
Matze

 

[Marco13]

Krasse Fancy Grafik :toll:

Zur KI kann ich leider nicht viel mehr als die Standardwantwort Alpha-Beta-Suche ? Wikipedia geben... eine "sinnvolle" Bewertungsfunktion wüßte ich auch nicht (man müßte irgendwie das "Hinarbeiten auf eine Zwickmühle" damit abbilden können) aber selbst mit einer "trivialen" (also nur gewonnen/verloren) sollte es für einen Menschen bei einer Suchtiefe von mehr als 3 schon schwierig werden?!

 

[Network]

Ok, die Idee ist mal genialwitzig und die Umsetzung super. Aber entweder sind wir hier zu dämlich das Spiel zu spielen, oder es ist tatsächlich immer in ein paar Zügen fertig.
Mit ein paar TicTacToe Strategien war es relativ schnell vorbei. Wobei das eig. sehr charmant ist auf der anderen Seite.
Schön wäre eine Anzeige, welcher Spieler gerade an der Reihe ist, sowie, dass die ersten beiden Blöcke bereits gesetzt sind. Die ersten 2 Züge sind im Grund genommen ja immer die selben.
Wie dem auch sei...

Zur KI... naja KI ist immer schwer und (für viele) nervig zu entwerfen.
Mein persöhnlicher Tipp, wobei der wahrscheinlich nicht perfekt ist, aber ein Ansatz (Ich kenne eure Spielmechanik ja nicht)
=> Raten würde ich zu einem 2 Teiler, also 2 KIs, wobei die eine Aggressiv handelt, die andere Defensiv, also versucht den Spieler zu hindern. Dabei wird dann ausgewertet welche KI in der jeweiligen Situation mehr Gewichtung bekommt.
Mit Backtracing sehe ich hier (wie ja auch erwähnt) keinen Erfolg. Vielmehr wäre eine art "Zug-Katalog" eventuell vielversprechender.
Solange der Spieler seine Steine nicht in eine gewisse Anordnung bringt, wie sie die verteidigende KI beobachtet, agiert die aggressive KI nach einem speziellen (zufälligen/berechneten) "Angriffsmuster" auf die sie reagiert bei Unterbechungen reagieren kann.
Eine eventuelle 3. KI muss in entsprechenden Fällen herausfinden/berechnen nach welcher Strategie weiter gehandelt werden soll.

 

[Apo]

Gefällt mir auch echt gut. Ist super schick geworden.
Grafik ist nice und auch der Sound (wenn auch leicht nervig imho) passt zum Style!

Würde auch Alpha-Beta Algo nutzen zur Erstellung der KI.

 

[Illuvatar]

Also erstens mal: alles was die anderen schon gesagt haben Die Grafik gefällt mir auch gut, und das Ganze sieht - sofern man das bei so etwas sagen kann - recht professionell aus.

Ich frage mich nur, ob hier "5 gewinnt" vielleicht sinnvoller wäre? So wie ich das sehe, ist es doch so: Sobald Spieler 1 zwei Steine nebeneinander hat (und in beide Richtungen Platz), was eigentlich immer leicht zu erreichen ist, muss Spieler 2 handeln. Sonst kommt der dritte Stein, und das ist schon die Zwickmühle.
Ich hab grade gegen mich selbst gespielt und hatte mit Spieler 2 nie die Wahl zwischen mehr als 2 Plätzen, bis mein Spieler 1 irgendwann geschafft hat, sich diagonal etwas zu bauen... Das Problem wird vielleicht durch den Expertmode etwas relativiert, könnte für Spieler 2 aber potentiell frustrierend sein...
Naja, just my 2 cents, ihr habt ja offensichtlich auch schon mehr Erfahrungen mit dem Spiel und vielleicht übersehe ich ja irgendwelche offensichtlichen Strategien?

Aber auf jeden Fall noch mal ein :toll::toll::toll:

 

[xehpuk]

Sieht sehr schick aus! Da ich bei sowas aber immer auf Fehlersuche bin, folgen jetzt auch nur negative Anmerkungen. :bae:

Applet geht bei mir nicht:

This occurred while 'Checking version'
For input string: "04-ea"
java.lang.NumberFormatException: For input string: "04-ea"
	at java.lang.NumberFormatException.forInputString(Unknown Source)
	at java.lang.Integer.parseInt(Unknown Source)
	at java.lang.Integer.parseInt(Unknown Source)
	at org.lwjgl.util.applet.AppletLoader.isMinJREVersionAvailable(AppletLoader.java:961)
	at org.lwjgl.util.applet.AppletLoader.run(AppletLoader.java:836)
	at java.lang.Thread.run(Unknown Source)

Tjoa, ich hab Version 1.7.0_04-ea.

Credits öffnen (JAR):

java.lang.NullPointerException
	at org.nova6.Connect4Extreme.MainMenu$7.run(MainMenu.java:261)
	at org.nova6.Connect4Extreme.Button.mouseClicked(Button.java:96)
	at org.nova6.Connect4Extreme.ExtendedGameState.mouseClicked(ExtendedGameState.java:143)
	at org.newdawn.slick.state.StateBasedGame.mouseClicked(StateBasedGame.java:490)
	at org.newdawn.slick.Input.fireMouseClicked(Input.java:1516)
	at org.newdawn.slick.Input.considerDoubleClick(Input.java:1111)
	at org.newdawn.slick.Input.poll(Input.java:1223)
	at org.newdawn.slick.GameContainer.updateAndRender(GameContainer.java:635)
	at org.newdawn.slick.AppGameContainer.gameLoop(AppGameContainer.java:408)
	at org.newdawn.slick.AppGameContainer.start(AppGameContainer.java:318)
	at org.nova6.Connect4Extreme.Application.main(Application.java:71)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:601)
	at org.eclipse.jdt.internal.jarinjarloader.JarRsrcLoader.main(JarRsrcLoader.java:58)

Danach ging auch nichts mehr außer Ton an/aus.

Der Credits-Link ist auch merkwürdig. Soll der nur "aktiv" sein, wenn man mit der Maus genau über dem Inneren eines Buchstabens ist? Beim Lautsprecher wirkt das ja noch ganz nett, da aber eher weniger.

"Find Match" schließt sich manchmal direkt von selbst mit

Finished Loading!

auf der Konsole.

Beim Klick aufs X schließt sich das Fenster, die Anwendung bleibt (manchmal) aber am Leben. Immer reproduzierbar, wenn man mindestens einmal in "Find Match" war.

Close Requested!!!
AL lib: FreeContext: (090909F0) Deleting 64 Source(s)

Zur Screenreihe im Anhang: Der erste ist die Ausgangsposition, von da aus von Screen zu Screen eine Zoomstufe raus.

1. Hintergrund fehlt
2. Hintergrund weit unten
3. Hintergrund weit oben
4. Hintergrund fehlt
5. Alles fehlt

Von der letzten Situation aus habe ich eine Weile "Scrolling" gebraucht, um das Spielfeld wiederzufinden.

Und ein kleiner Fehler in deinem Beitrag: Links von Webstarter und JAR sind vertauscht.

 

[M.F.G.]

Danke für die positive Resonanz,

Hab mich gleich mal dran gemacht, aber erst mal nur wenig geschafft:
-credits sind leichter aufzurufen
[EDIT]-zum ausprobieren ne 5 gewinnt version[/EDIT]
-diesen ellenlangen Text geschrieben^^

Über die KI denk ich weiter nach und schau mir nochmal den Alpa-Beta-Algo an, diese we ist aber haering nich da, weshalb es nur langsam vorwärts geht.

@xehpuk:
die erste Exzerption is anscheinen ja deiner vorab Java Version zuzuschreiben, darum werden wir uns wohl nich kümmern^^
die 2. beschriebene exception is für mich leider nich reproduzierbar, bekommst du die immer oder wie bist du da vorgegangen?
Fehler bei „find match“ sind uns schon bekannt, momentan läuft das ganze über eine php zusammen mit der Datenbank auf unsere hp. Also eine sher unschöne lösung, aber was soll man machen wenn man keinen (V-)Server hat? Da wir auch bei einem kostenlosen anbieter sind werden anscheinen manche aufrufe von der php datei strikt ignoriert. Unsere momentane idee ist es eines der heiß begehrten Raspberry Pi zu bekommen und den dann über DynDNS als kleinen server bei jemanden privat aufzustellen, aber das wir wohl noch ein wenich dauern.
Das schließen Problem: bei uns is es momentan immer so das sich die applikation in eclips sofort beendet, die jar Version braucht dagegen meist ne halbe minute oder so (beendet sichs bei dir nich nach ner weile im taskmanager?), wir wohl einer der threads noch was werkeln und dh. lässt sich die VM nicht beenden, werd ich mir später nochmal anschauen.
Dachte echt nich des jemand die verschiedenen kleinen Problemchen bemerkt die mit raus-zoomen (Mausrad) oder verschieben (Rechtsklick-Dragg) auftreten so früh bemerkt. An dieser stelle vielen dank für das ausführliche Testen) Hab sie mal auf die ToDo liste geschrieben. Übrigens kann man per Rechtsklick auf nen Stein diesen markieren, is für mp ganz nützlich.

@Network:
also wir brauchen oft schon länger, konnten haben aber bei 2-3 Anfänge feststellen (also beim ziehen des 3. Steins) kann immer der Anfänger gewinnen (normaler Modus). Deswegen haben wir wenn wir gegeneinander spielen diese Anfänge verboten. Dann dauern die spiele auch länger, ich denk auch allgemein dauern die spiele mit steigender Erfahrung länger (sowohl zeitlich wie auch Anzahl der gesetzten Steine).
Unten links wir doch schon bereits angezeigt wer dran ist, is die anzeige noch zu unauffällig? Soll sie vll nich textuell oder mehr visuelle sein?
Die Idee die ersten beiden Züge automatisch zu setzen hat ich auch schon, nur meine mein Kumpel (in dessen Bereich des Projekts dieser Code gehören würde) das sei unnötig. Ich denke man könnte durch setzen von mehr als 3 Steinen ( zufällig aber ohne oben erwähnte Immergewinnmöglichkeit) zwei fliegen mit einer klappe schlagen, aber dann muss erst wieder viel gespielt werden um sagen zu können ob das sinnvoll ist.
An dieser stelle möchte ich noch erwähnen das wir alle spielergebnise übrigens per php in eine Datenbank auf unserer Webseite eintragen, ich hoffe niemand hat angst das wir ihn ausspionieren, es werden nur Informationen zum Spiel (auch der genau verlauf) gespeichert einzig „persönlich“ is ein hash aus OS, Benutzername, (aber duchs hashen unerkennbar für uns), den wir brauchen um die Spiele miteinander in Verbindung zu bringen, um später mal ne Rangliste zu machen und ähnliches. besonders um Analysen drüber laufen zu lassen.


@Illuvatar
über ein 5 gewinnt haben wir während der Entwicklung auch mal nachgedacht aber auf später verschoben und wieder vergessen, sollten wir unbedingt mal ausprobieren.
Du hast schon recht mit den zwei Steinen nebeneinander und nach beiden Seiten offen bedeutet Sieg wenn nicht eingegriffen wird, das muss man halt als Gegenspieler versuchen zu vermieden, natürlich is Spieler B anfangs fast nur dabei Spieler A den Sieg nicht zu ermöglichen, aber irgendwann macht A nen Fehler und dann wechseln die rollen dieses Katze-Maus-Spiels

[EDIT]Download (nur als .jar, weil keine lust auf signieren usw.):
- Normal
- 5 Gewinnt Edition[/EDIT]

 

[mymaksimus]

WOOW Hammer Grafik :idea:
Ich wusste gar nicht das sowas mit java möglich ist?
Habt ihr externe libs benutzt oder native java?
und womit die ganzenAnimationen? Nur pur Java?

 

[Ikaron]

Esrt mal: Echt schöne Grafik, hier und da ein paar Pixelfehler (z.B. beim sich drehenden Kreis, eine schräge Linie im Hintergrund) aber alles in allem echt gelungen. Naja, der Multiplayer will bei mir gar nicht - Sagt sofort "Found opponent", wartet dann 30s oder so, und springt dann ins Menü zurück. Außerdem, zum Multiplayer: Ich würde definitiv die Methode wählen, dass ein 3x3 Feld oder so bereits gesetzt ist.

WOOW Hammer Grafik :idea:
Ich wusste gar nicht das sowas mit java möglich ist?
Habt ihr externe libs benutzt oder native java?
und womit die ganzenAnimationen? Nur pur Java?

LWJGL (OpenGL java bindings) und Slick zum Texturen laden, etc

 

[Network]

Das Thema ist über ein Jahr alt.
Das sich der Threadstarter oder irgendwer dazu nochmals meldet ist unwahrscheinlich, jetzt sowieso nachdem ganzen Vorfall mit diesem Forum was lange brauchen wird um sich wieder zum alten Zustand zu erholen.

Und mit OpenGL hat die "hammer" Grafik erstmal so nichts zu tun. OpenGL ist nur eine platformunabhängige Programmbibliothek zur Darstellung von 3D-Szenen in Echtzeit. Durch die damit häufig verbundene Hardwarebeschleunigung durch die Grafikkarte bietet sich das auch für 2D-Projekte an, um den Zeichenvorgang immens zu beschleunigen.
In diesem Falle wurde mit OpenGL gearbeitet, wobei man sich bei der größe des Projektes auch hätte fragen können ob es in diesem Fall sinnvoll eingesetzt ist. Da OpenGL reichlich komplizierter ist zum implementieren ist, später kann man jedoch viele Effekte viel einfacher erreichen - wenn gut umgesetzt.

Wenn man (auch heutzutage noch) bei Google "Java Applet Games" oder ähnliches eintippt, findet man nur diese hässlichen pixeligen uralten langsamen Dinger, bei denen man verstehen kann, das Adobe die Applets damals relativ schnell abgezogen hatte.
Von daher ist die Überraschung wahrscheinlich etwas größer für andere.

Gruß
Net

 

[mymaksimus]

Ich hatte gedacht alle Beiträge wären gelöscht gewesen? So stands in der email...

 

[M.F.G.]

Hätte echt nicht gedacht das hier nochmal wer was schreibt^^

So also zu deinen Fragen, wir hatten das ganze Projekt mit der Grafik Engine Slick2D (welches auf JOGL und damit auf OpenGL basiert) umgesetzt. Die würde ich aber mittlerweile nur noch begrenzt weiter empfehlen, da Slick nicht mehr weiterentwickelt wird und die Homepage mehrmals tagelang down war, ohne online Javadoc und Forum macht proggen doch kein spass. Ich würde jetzt ehr auf libGDX (Cross-Platform, aktive Entwicklung) setzen, aber da kommt man nich so leicht rein wie in Slick2D, da ist deutlich mehr "overhead" den man am Anfang wahrscheinlich für unnötig hält.
Die „Animationen“ sind größtenteils sog. Partikeleffeckte (ganz viele kleine bilderchen die nach irgendeiner Physik herumschwirren), dazu haben slick2d und viele andere engines extra Klassen ( und auch nen Editor wo man in echtzeit sieht was Veränderungen an den Parameter bewirken), da hab ich halt ein bisschen herumgespielt und dabei ist dann das raus gekommen. Btw mittlerweile finde ich persönlich das ganze ein bisschen zu bunt^^.


Zu guter Letzt: Wir haben das ganze Spiel Anfang des Jahres auf Android portiert (samt engine wechsel auf AndEngine (AndroidOnly) )





Hier sollten auch weniger Bugs vorhanden sein, leider spielen das so wenige das man beim Matchmaking nie jmd antrifft. Wir arbeiten deswegen schon an einem Spielmodus, bei dem nicht beide Spieler gleichzeitig online sein müssen.
Naja, ich würde mich freuen wenn ihr euch das mal da anschaut und hier oder dort einen Kommentar hinterlasst

beste Grüße
Matze