Chessball

Hi,

ich hatte mal Lust zwei meiner liebsten Spiele zu verheiraten und dazu eine schöne KI zu basteln.
Wie der Name schon andeutet handelt es sich um einen Mix aus Schach und Fußball.

Aktueller Stand:
Komplett spielbar, aber noch ohne KI. Wollte es erst veröffentlichen, wenn eine KI dabei ist, die nicht „zu doof“ und auch nicht „zu schlau“ ist.

Regeln:
Wenn man an der Reihe ist, kann man seine Figuren wie man es vom Schach kennt bewegen. Steht man in der Nähe vom Ball mit seinen Figuren, kann der Ball so bewegt werden wie die Figuren die drum herum stehen. Steht also eine Dame und ein Pferd um den Ball von der Farbe die gerade dran ist, so kann der Ball von seiner Stelle aus sich bewegen wie ein Pferd und wie eine Dame. Ziel ist es nun ins gegnerische Tor zu treffen.
Aktuell kann man, wenn man dran ist, eine Figur ziehen und danach, wenn möglich, noch drei mal den Ball bewegen (also sozusagen passen und schießen). Danach ist der Gegner dran.
Natürlich kann man auch die Figuren schlagen.
Das Spiel ist vorbei, wenn ein Team drei Punkte hat. Einen Punkt kann man bekommen, indem man entweder ein Tor schießt oder den gegnerischen König Schach matt setzt. Nach einem Tor wird wieder alles normal aufgestellt und das Team, welches ein Tor bekommen hat, darf anfangen.

Download der preAlpha Jar eigentlich nur für den Entwickler, aber wer gerne probieren möchte. Benötigt aber Java8
Derzeit sind die Bauern aber noch zu stark. Sie sind ähnlich wie der König, nur können sie nicht zurück laufen. Das ist der einzige Unterschied zum normalen Schach. Nur ganz „normale“ Bauern wirkten irgendwie zu schwach. Wie gesagt, ich versuche mich gerade aus

aktueller Screenshot
Man sieht, wie die Dame bewegt werden kann

Hier sieht man wie der Ball sich bewegen kann, da das Pferd und die Dame in seiner Nähe stehen.

  1. Nur weil hier manchmal Links in Spamposts durchkommen, die dubiose Substanzen anbieten, heißt das nicht, dass man die alle gleich NEHMEN muss :smiley:
  2. Warum heißt das “Chessball”, und nicht “ApoChessball”
  3. Gibt es eigentlich ein Spiel, das “Calypse” heißt? :smiley:
  4. Einen Link zum Spiel selbst habe ich weder hier, noch auf deiner Seite, noch im Playstore gefunden…!? Also soll das nur ein Teaser sein!? (Man könnte ja auch zwei menchliche Spieler Spielen lassen, wenn es nur darum geht, dass die KI noch fehlt…)

Eine absolut irre Idee! Wie kommst du nur immer auf solch phantastische Spielideen?

Extrem genial :idea:
Als Schachfan muss ich das unbedingt spielen!
Wo kann man das Spiel downloaden? Habe wie Marco im Playstore auch noch nichts gefunden

Hi,

war eigentlich nur als Teaser gedacht, aber ich habe mal eine aktuelle Jar-Version hochgeladen (Benötigt Java 8). Aber sie kann noch nicht viel, außer wenn man gegen sich selber spielen will.
Die KI bastle ich gerade erst. Aber falls es jemand ausprobieren möchte immer gerne, bin mir generell noch nicht sicher, ob

  • 3 Pässe zuviel oder zu wenig sind
  • ob verlorene Figuren schon nach einem Tor wiederkommen sollten oder für das gesamte Spiel weg sind
  • ob eine andere Aufstellung der Figuren besser wäre
  • ob vielleicht das Tor verkleinert werden sollte auf nur 2 Felder
  • derzeit sind die Bauern aber noch zu stark(?). Sie sind ähnlich wie der König, nur können sie nicht zurück laufen. Das ist der einzige Unterschied zum normalen Schach. Nur ganz “normale” Bauern wirkten irgendwie zu schwach. Wie gesagt, ich versuche mich gerade aus

Aber das probiere ich mir gerade aus und hoffe mit meinem Bot mehr Erfahrungen zu sammeln.

Ziel ist es natürlich es mal auf mein Smartphone zu bringen. Aber derzeit ist mein oberstes Ziel eine schöne KI/schönen Bot dafür zu basteln

Kleine Vorschläge:

  • Runde automatisch beenden sobald kein Zug mehr möglich ist
  • Animationen für die Bewegung von Figuren oder Ball?
  • Ich bin es von anderen Schachprogrammen gewohnt, dass ich Figuren nicht am Stück ziehen muss, sondern diese einmal kurz auswähle und mit einem zweiten Klick auf einem anderen Feld platzieren kann. Nicht extrem wichtig, wäre aber eine nette Erleichterung bei der Bedienung
  • Fehler: Wenn ich den Ball anklicke, aber nicht verschiebe, sondern nur innerhalb des eigenen Feldes mit der Maus bewege, wird das als Zug gezählt

Das sieht ja schon mal toll aus, ich bin gespannt. Wenn du mit der KI unsicher bist, kannst du ja auch verschiedene Spielstärken implementieren, wie sie Schachprogramme auch anbieten.

[QUOTE=iFelixxxx]Kleine Vorschläge:

  • Runde automatisch beenden sobald kein Zug mehr möglich ist
  • Animationen für die Bewegung von Figuren oder Ball?
  • Ich bin es von anderen Schachprogrammen gewohnt, dass ich Figuren nicht am Stück ziehen muss, sondern diese einmal kurz auswähle und mit einem zweiten Klick auf einem anderen Feld platzieren kann. Nicht extrem wichtig, wäre aber eine nette Erleichterung bei der Bedienung
  • Fehler: Wenn ich den Ball anklicke, aber nicht verschiebe, sondern nur innerhalb des eigenen Feldes mit der Maus bewege, wird das als Zug gezählt[/QUOTE]

Bis auf die Animationen, die können später kommen, habe ich es mal umgesetzt. Danke für das Feedback. Gleicher Download wie davor.

Jo, ich schlage mich gerade mit dem Alpha Beta Algorithmus rum und versuche es richtig zu gewichten. Mal schauen was raus kommt. Aber es ist richtig, unterschiedlich starke KIs wären sinnvoll, so könnte man ein Turnier veranstalten und zum Schluss kommen halt die echt harten Gegner. :wink:

[QUOTE=Apo]Bis auf die Animationen, die können später kommen, habe ich es mal umgesetzt. Danke für das Feedback. Gleicher Download wie davor.
[/QUOTE]

Funktioniert alles prima, bis auf das Verschieben von Objekten mit zwei Klicks: Wenn ich, beispielsweise, meine Dame auswähle und mit einem zweiten Klick auf ein anderes Feld setzen möchte, bleibt sie einfach stehen und die Aktion wird abgebrochen.

Oh sorry sofort verbessert.

Perfekt :slight_smile:

Von wegen einfach mal ne Ki schreiben …
Durch das Passen gibt es so viele Möglichkeiten, was getan werden kann (allein weiß am Anfang hat 5886 unterschiedliche Zugmöglichkeiten, wären es nur die Züge für die Figuren wären es nur 83; als zweiter Zug wenn der Ball wirklich im Spiel ist und bei einem Turm oder der Dame stehen, sind es ungefähr ~88000 Möglichkeiten).
Jeder kann sich ja vorstellen, wenn man alles ausprobieren will, was das an zeit benötigt. Den aktuellen Zug berechnen und dafür den besten Zug ok, aber halt nur die aktuelle Position wird betrachtet, nicht wie geplant 4 Schritte im vor raus oder so.

Bin gerade etwas überfragt, hat jemand von euch eine Idee wie ich da besser rangehen könnte? Ich hatte halt den MinMax-Algorithmus ausprobiert und wollte es vlt noch auf Alpha Beta Suche erweitern, aber es ist derzeit schon so ineffizient, dass ich glaube ein andere Ansatz wäre praktischer. Ich kann doch nicht einfach Teilbäume weglassen, nur weil die aktuelle nicht so toll wirken … argh
Wie gesagt wenn jemand eine Idee hat, immer her damit.
Danke, ein derzeit etwas frustrierter Apo

Chessball wird es wahrscheinlich noch nicht so oft auf der Welt geben,
aber wenn man sich lang genug das Spielfeld anschaut könnte man es ja auch quadratisch machen,
den Ball wegnehmen und z.B. Chess nennen,

dafür gibt es doch sicherlich KI-Verfahren ohne Ende auf der Welt, bestimmt auch möglichst simple anschauliche dabei, einfach nachlesen?
wenn du das nicht magst oder die zu unverständlich sind, dann ja wenig aussichtsreicher Start

tjaja, KI kann immer ein Knackpunkt sein,
da lob ich mir Dummyspiele wie maximal TowerDefense (oder ManaWars? :wink: ) mit nur anrennenden Gegnern,
nur mathematisch/ zufällig bestimmbare Stärke und Variabilität als Schwierigkeit

Tiefe Neuronale Netze könnten eine Option sein: AlphaGo: Google-KI schlägt menschlichen Profi-Spieler im Go | heise online :smiley:

Mal im Ernst: Dass MinMax zu nichts führt ist ja klar, aber spontan wüßte ich nicht, was man da über Alpha-Beta hinaus noch mit vertretbarem Aufwand implementieren könnte (das muss aber nichts heißen - habe mich nie wirklich “tiefer” damit beschäftigt). Schachprogramme haben da zwar ein paar Tricks, aber sowas wie Eröffnungsbibliotheken sind hier kaum anwendbar, einige der anderen Tricks sind sehr Schach-spezifisch, und ansonsten geht da viel über brutalst-low-levelige Optimierungen (siehe https://chessprogramming.wikispaces.com/ - Kranker shyce…).

Das einzige, was ich als wichtigen Punkt sehe, an dem man “leicht” schrauben und ggf. (mit Alpha-Beta) “viel” rausholen könnte, wäre die Stellungsbewertung. Hast du dir schon eine konkrete Bewertungsfunktion überlegt?

Wenn du mit dem Minimax Algorithmus arbeitest, aber die Anzahl möglicher Züge stark einschränkst, könnte das schon machbar sein. Dann beherrscht die KI natürlich kaum fiese Tricks, die über viele Züge durchdacht sind.

Das sind jetzt nur ein paar spontane Ideen und Anreize: wahrscheinlich hast du mehr Erfahrung in dem Themenbereich, als ich. Bisher habe ich selbst nur sehr simple künstliche Intelligenz für ManaWars geschrieben.

Du könntest, jede Runde, unmittelbare Spielzüge in mehrere Kategorien unterteilen: z.B. Schlecht, Neutral, Gut (die Züge werden bisher noch nicht in die Tiefe gedacht)
Im Folgenden könntest du dich ausschließlich auf die Spielzüge der “Gut” Kategorie konzentrieren, und deren Folgezüge betrachten. Kommst du hier zu einem zufriedenstellenden Ergebnis, bleibst du dabei. Ansonsten (oder wenn es von Anfang an keine Züge in der Kategorie “Gut” gibt) betrachtest du die Möglichkeiten in der nächsttieferen Kategorie. Im Endeffekt wird der, von allen bisher berechneten Optionen, beste Zug ausgewählt.

Bei der Bewegung einer Figur (noch das einfachste)

  • Alle Züge, in denen deine Figur geschlagen werden kann, werden sofort als schlecht bewertet
  • Züge, in denen du eine Figur schlagen kannst, sind gut
  • Die Spielsituation ist allgemein gut, wenn deine Figuren sich verteilt haben, und möglichst viele Felder “angreifen” können
  • usw.

Bei dem Passen

  • Sobald bei dem letzten Pass ein Gegner den Ball berührt, ist der Zug schlecht
  • Sobald der Ball von keiner deiner Figuren mehr erreichbar ist, ist der Zug schlecht
  • Wenn der Ball bei dem letzten Pass nicht von dem Gegner erreichbar ist, außer dieser bewegt sich auf ein Feld, auf dem er geschlagen werden kann, ist der Zug gut
  • Allgemein bei dem ersten und zweiten Pass: Nur Züge betrachten, bei denen weitere Pässe möglich sind & möglichst auf Pässe konzentrieren, bei denen der Ball in Richtung Tor des Gegenspielers kommt

Das ist jetzt sehr simpel dargestellt und natürlich viel komplexer umzusetzen, aber ich hoffe das ist ein kleiner Anreiz für dich :slight_smile:
Ich bin nämlich überzeugt, dass der Minimax Algorithmus hier auch anwendbar ist, wenn man die Züge effektiv genug einschränkt.

Das Thema finde ich sehr interessant, deswegen informiere ich mich auch ein bisschen über alternative Algorithmen.

Grüße
Felix

Das ist natürlich eine Wissenschaft für sich, aber - solche Greedy-Ansätze…

… können leicht dazu führen, dass menschliche Spieler sie durchschauen. Sie könnten dann, z.B. für Schach, und etwas vereinfacht formuliert, die Dame als “Köder” irgendwo hinschicken, wenn sie wissen, das die KI sie sich holen wird, egal, ob die KI im nächsten Zug dann Schachmatt gesetzt werden kann…

[QUOTE=Marco13]Das ist natürlich eine Wissenschaft für sich, aber - solche Greedy-Ansätze…

… können leicht dazu führen, dass menschliche Spieler sie durchschauen. Sie könnten dann, z.B. für Schach, und etwas vereinfacht formuliert, die Dame als “Köder” irgendwo hinschicken, wenn sie wissen, das die KI sie sich holen wird, egal, ob die KI im nächsten Zug dann Schachmatt gesetzt werden kann…[/QUOTE]

Klar, ist jetzt auch stark vereinfacht dargestellt :stuck_out_tongue:

Wobei in diesem Beispiel die KI nicht so extrem leicht ausgetrickst werden kann:
Wenn man versucht, sie mit einer Figur zu ködern, welche die KI schlagen kann, dann würde der Zug zwar anfangs in die Kategorie “Gut” fallen und würde zu den Optionen gehören, die genauer berechnet werden. Allerdings werden gerade diese -augenscheinlich - guten Züge ausgewählt und nach typischem Minimax Algorithmus in die Tiefe berechnet und es würde sich schnell herausstellen, dass der Zug eine Falle ist.

Ich denke, wenn es so viele Zugmöglichkeiten gibt, musst du irgendwie versuchen, nur “sinnvolle” Züge weiterzuverfolgen. Dieses “sinnvoll” muss dann durch eine Heuristik gegeben sein, der man einige andere zufällige Spielzüge noch beifügen könnte, um nicht zu berechenbar zu werden. Sprich, auch diese zufälligen Züge berechnet man dann entsprechend tief.

Bis in welche Tiefe der Berechnung dann noch zufällige Züge hinzugenommen werden, oder ob man irgendwann nur noch “plausible” Züge verwendet, muss man wohl austesten.

Erst einmal vielen Dank für das Feedback!

Versuche mich nun seit drei Tagen an der KI. Ich sage wird … noch nicht :smiley:
Passe immer meine Heuristik an, aber sie liefert noch nicht das was sie in der Theorie soll. Ich versuche die Negamax-Implementierung der Alpha Beta Suche ( siehe Wikipedia z.B. )
Ich versuche dabei zu bedenken, dass
1.) Ist der Ball im Tor oder der König des Gegners geschlagen, dann gibt es “unendlich” Punkte
2.) Wert der Spieler wie beim Schach, eigene geben plus, Gegner geben minus
3.) Nähe zum Ball. Wenn ein eigener Spieler näher zum Ball steht gibt es Punkte. Stehen die Gegner näher zum Ball gibt es Minuspunkte
4.) Ist in der aktuellen Position ein Spieler bedroht, dann gibt es Minuspunkte
5.) Wenn der Ball näher zum gegnerischen Tor ist, gibt es Pluspunkte, ansonsten kleine Minuspunkte.

Außerdem nehme ich von allen Möglichkeiten nur die 100 Besten derzeit, damit ich überhaupt eine gewisse Tiefe erlangen kann. Das Problem ist trotzdem, dass es Züge gibt, da gibt es 650000 Möglichkeiten wie man ziehen und passen/schießen kann. Und die ermittle ich erst, um sie dann zu sortieren (mit Hilfe der Heuristik).

Wie gesagt versuche mich daran. Auch wenn es komisch klingt, tut echt mal wieder nicht nur ein Simpelspiel zu machen, sondern sich in einem Gebiet zu versuchen, wo ich noch nicht zu viel Erfahrung habe. Deshalb bin ich noch voll motiviert. =)

Habe außerdem das Spiel etwas “gepimpt”. Nun kann man auswählen gegen wen man kämpfen will (KI oder Mensch), außerdem zieht die KI automatisch, wenn sie fertig ist mit nachdenken und das ganze etwas “gepolisht”, aber ist noch nicht fertig.
Ich lade es hoch, wenn die KI MINIMAL brauchbar ist. Kann also noch etwas dauern =)

So ich habe mal eine Version mit einer KI hochgeladen.

Sie ist schon einfach besiegbar, aber wenn man unbedachte Züge macht, nutzt sie es eiskalt aus. Habe mit ihr gemerkt, wie sehr man auspassen muss, sein Tor nicht zu offen zu haben. Ansonsten ist man voll im Angriff und kurz vor einem Tor und dann ein "mega"Konter und Tor für den Gegner. Die KI macht auch nicht immer die gleichen Züge, sondern hat etwas Zufall drin, damit nicht jedes Spiel gleich abläuft. So kann es aber auch vorkommen, da manche Züge zufällig ausgewählt werden, dass es nicht der perfekte Zug ist. (Außer ein Tor oder das Schlagen des Königs … das macht er immer) =)
Die derzeitige KI denkt aber nur zwei Züge voraus und ist somit relativ leicht ausrechenbar. Ich versuche es noch zu optimieren, damit ich eine Tiefe von 3 oder sogar 4 hinbekomme.

Nächster Plan:

  • Demomodus, wo gespeicherte Spiele gezeigt werden (perfekt zur Entspannung und zum Lernen wie das Spiel fkt) und auch Spiele, die gespielt wurden, automatisch hochladen, damit ich vlt doch noch eine selbst lernende KI schreiben kann (war schon immer mal ein Ziel)
  • Es ermögichen, dass jeder seine KI bauen und laden kann
  • Das Tutorial “interaktiv” machen
  • Eure möglichen Wünsche einbauen :smiley: