Sprengmeister:

Bei diesem Spiel werden auf einem 6x6 Brett abwechselnd ein Stein auf ein leeres Feld oder eines, das bereits mit Steinen der eigenen Farbe besetzt ist.

Der Wert dieses Feldes wird dadurch um eins erhöht, und der Gegner ist am Zug.

Jedes Feld hat die Eigenschaft zu explodieren. Dies geschieht, wenn der Feldwert genau so groß ist, wie das Feld direkte Nachbarn hat( waagerecht und senkrecht).

Die Steine eines explodierenden Feldes verteilen sich auf die Nachbarfelder.

Diese bekommen die Farbe des explodierenden Feldes, das anschließend wieder leer ist.

Wer keinen Stein mehr auf dem Brett hat, der ist der VERLIERER!

Viel Spaß!!!

Hy,
ich hab das Spiel zwar nicht so ganz verstanden, es ist aber bis jetzt fehlerfrei gelaufen. Noch ein kleine Anmerkung (wie bei www.delphi-forum.de/viewtopic.php?t=78232: Bitte füge ein separates Archiv hinzu, in dem du nur die exe-Datei mit den benötigten Dateien hast. Für die Spieler )

MfG
Regan

Der Computer denkt bei hohen Leveln sehr lange nach ... Ne Progressbar, wie weit er dabei ist, wär nicht schlecht ...

Ferner wäre sicherlich auch noch ein "Schach"-Modus witzig, wo man einstellen kann, wie lange jeder maximal zum Ziehen Zeit hat.

Ach ja: Ich hab die Regeln auch nicht ganz kapiert: Könntest Du die bitte etwas detaillierter erklären?

P.S.: Ggf. kannst Du das Nachdenken ja auch "Multithreaded" schreiben, damit das Denken auf DualCore-Systemen etwas effizienter geschieht.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ich hab mir den Code nicht angeschaut, würde aber meinen, das die Spielstrategie auf Alpha-Beta / MinMax btw. NegaMax beruht. Leider weiss man da nicht, wie lange das Programm noch 'nachdenkt' bzw. durchrechnet. Weiterhin kann man nur bedingt eine maximale Bedenkzeit vorgeben.

@MinMax: Auch für rekursive algorithmen geht das

Angenommen, ich hab den Nachdenk-Vorgang, der ist, 1 Schritt jeweils.
Dabei stell ich fest, dass ich 5 Züge habe.
Also weiß ich, dass ich 1*5 Unterschritte ausführen muss.
Wenn ich 2 dieser ausgeführt habe, und wiederum 7 Unterschritte notwendig sind, ist mein Fortschrit ... (Dieser Text steht nur hier, damit der Leser selber kurz nachdenkt, was die Lösung sein könnte ...) ... 2*7 / 5*7 --> Korrekt 14/35. Am Ende ist man bei 21/35, kann also wieder durch 7 teilen --> 3/5.

Und damit lässt sich auch ne Vorhersage treffen, wie lang das Nachdenken noch brauchen wird ^^

Ach ja: Der denkt WIRKLICH lange ... Auf Level 11 war der mit seinem ersten (nicht-trivialen) Zug nach 14 Stunden immer noch nicht fertig ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Das Programm rechnet rekursiv mit Alpha-Beta.

Die Anzahl der zu untersuchenden Züge ist 36^Level, also 36^11=131621703842267136 Züge, das kann dauern.

Auf Level 3 habe ich noch nie gewonnen. Level 5 müßte auch für Denker schon reichen.

Gruß, Fiete

BenBE hat folgendes geschrieben:

@MinMax: Auch für rekursive algorithmen geht das

Stimmt nur bedingt, und Dein Denkansatz ist falsch: Die Anzahl der möglichen Züge ist ja nicht immer konstant. Bei einigen Spielen mag das so sein, aber bei den meisten eben nicht. Fiete wirft hier mit zahllosen Nullsummen-Spielen um sich, die alle auf seinem Minimax-Algorithmus beruhen. Bei Tic-Tac-Toe weiss man genau, wie viele Züge man in einer bestimmten Stellung durchrechnen muss (n über k), bei Schach, Gobang etc. eben nicht. Gut, hier bei diesem Mienenspiel könnte man das eventuell noch ausrechnen, das ist aber eh Quatsch, weil:

Alpha-Beta beschneidet zudem noch den Spielbaum, sodaß es i.A. wesentlich weniger Züge sind, als angenommen. Eine Progressbar wäre ein sinnloses Instrument, das keinerlei Aussage zulässt, wie lange das Programm denn noch gedenkt, zu rechnen. Es kann sofort fertig sein, auch wenn noch 1000 Züge durchzurechnen sind, es kann aber auch noch ein weilchen dauern.

Und das ein Programm bei einer Spielstufe von 11 doch etwas länger benötigt, sollte einem Kenner der Materie schon klar sein.

Allerdings könnte so ein Programm etwas mehr Action vertragen. Wie wäre es, die Anzahl der durchgerechneten Stellungen anzuzeigen (1x pro Sekunde), sowie mit weiteren mehr oder minder wichtigen Statistiken um sich zu schmeissen, wie z.B. Anzahl der Stellungen pro Sekunde, bester Zug bisher, Alpha-Beta-Schnippelvorgänge etc.

Tipp: Sortierst Du die Züge anhand einer einfachen Heuristik, sodaß Züge, die vermutlich besser sind als andere, zuerst geprüft werden? Das erhöht die Wahrscheinlichkeit, das die A/B-Baumschere ansetzt, gewaltig und man wird dann bei einem Level von 11.

Noch ein Tipp zum Thema 'maximale Nachdenkzeit': Ich hab vor einiger Zeit eine Abhandlung gelesen, bei der jemand vorgeschlagen hat, das Programm einfach mit immer höheren Zugtiefen rechnen zu lassen (Also erstmal bei Level=3 durchrechnen lassen, dann bei 4 usw.). Wenn man dann kein Bock mehr auf warten hat (oder die maximal Denkzeit erreicht ist), bricht das Programm einfach die Suche ab und verwendet den bisherigen besten Zug. Das soll sogar gut funktionieren, da die Durchrechnung bei niedrigen Tiefen sehr schnell geht, das Programm also 'sofort' eine ziemlich gute Antwort parat hätte.

@Alzaimar: Du hast beim Verständnis meines Ansatzes einen Fehler

Mein Ansatz geht nämlich davon aus, dass für jeden Schritt die Anzahl der Unterschritte ermittelt wird (die ja bekannt ist) und daraus der Fortschritt ermittelt wird. Somit würde bei mir die Progressbar "adaptiv" funktionieren Auch das abschneiden von Einzelbäumen geht problemlos.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ok Ben, erklar's mir, ich lerne immer gerne dazu.

Beispiel: In der 1. Ebene haben wir 2 Züge zur Auswahl.
Die erste Variante ermöglicht dem Gegner eine einzige Antwort, die zweite jedoch 1000. Das ist natürlich alles im Vorfeld nicht bekannt.

Also:
Ebene 1: 1.Zug (von 2) ausführen. Wo ist die PB?
Ebene 2: 1.Zug (von 2) ausführen. Wo ist die PB?
Ebene 2: 2.Zug (von 2) ausführen. Wo ist die PB?
Wieder in Ebene 1: 2.Zug (von 2) ausführen. Wo ist die PB?
Ebene 2: 1.Zug (von 1000) ausführen.Wo ist die PB?
...
Ebene 2: 1000.Zug (von 1000) ausführen. Wo ist die PB? Klar, bei 100%

Kannst Du mir die Position der PB (Position, Max) jeweils ausrechnen?

So, und nun
Gleiche Spielstellung, nur wird diesmal die zweite Variante zuerst ausgeführt.
Ebene 1: 1.Zug (von 2) ausführen. Wo ist die PB?
Ebene 2: 1.Zug (von 1000) ausführen. Wo ist die PB?
...
Ebene 2: 1000.Zug (von 1000) ausführen. Wo ist die PB?
Wieder in Ebene 1: 2.Zug (von 2) ausführen. Wo ist die PB?
Ebene 2: 1.Zug (von 2) sführen.Wo ist die PB?
Ebene 2: 2.Zug (von 2) ausführen. Wo ist die PB? Klar, bei 100%

Kannst Du mir die Position der PB (Position, Max) auch diesmal jeweils ausrechnen?

Danke.

alzaimar hat folgendes geschrieben:

Ok Ben, erklar's mir, ich lerne immer gerne dazu. Beispiel: In der 1. Ebene haben wir 2 Züge zur Auswahl. Die erste Variante ermöglicht dem Gegner eine einzige Antwort, die zweite jedoch 1000. Das ist natürlich alles im Vorfeld nicht bekannt. Also: Ebene 1: 1.Zug (von 2) ausführen. Wo ist die PB? 0/2 --> 0/4 Ebene 2: 1.Zug (von 2) ausführen. Wo ist die PB? 0/4 --> 1/4 Ebene 2: 2.Zug (von 2) ausführen. Wo ist die PB? 1/4 --> 2/4 Wieder in Ebene 1: 2.Zug (von 2) ausführen. Wo ist die PB? 2/4 --> 1/2 Ebene 2: 1.Zug (von 1000) ausführen.Wo ist die PB? 1000/2000 --> 1001/2000 Ebene 2: 1.Zug (von 1000) ausführen.Wo ist die PB? 1001/2000 --> 1002/2000 ... Ebene 2: 1000.Zug (von 1000) ausführen. Wo ist die PB? Klar, bei 100%. Jain: 1999/2000 --> 2000/2000 --> 2/2 --> 100% Kannst Du mir die Position der PB (Position, Max) jeweils ausrechnen?

Jup. Steht jeweils dahinter

alzaimar hat folgendes geschrieben:

So, und nun Gleiche Spielstellung, nur wird diesmal die zweite Variante zuerst ausgeführt. Ebene 1: 1.Zug (von 2) ausführen. Wo ist die PB? 0/2 --> 0/2000 Ebene 2: 1.Zug (von 1000) ausführen. Wo ist die PB? 0/2000 --> 1/2000 ... Ebene 2: 1000.Zug (von 1000) ausführen. Wo ist die PB? 999/2000 --> 1000/2000 --> 1/2 Wieder in Ebene 1: 2.Zug (von 2) ausführen. Wo ist die PB? 1/2 --> 2/4 Ebene 2: 1.Zug (von 2) ausführen. Wo ist die PB? 2/4 --> 3/4 Ebene 2: 2.Zug (von 2) ausführen. Wo ist die PB? Klar, bei 100%. Auch wieder nur indirekt: 3/4 --> 4/4 --> 2/2 --> 100% Kannst Du mir die Position der PB (Position, Max) auch diesmal jeweils ausrechnen? Danke.

Ja, kann ich. Wo soll da jetzt das Problem gewesen sein

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ich habs verstanden

Moin,

du hast natürlich recht, war nur als Herausforderung gedacht . Alpha-Beta schneidet viel vom Spielbaum ab, die zu berechnende Anzahl von Stellungen ist bedeutend geringer.

Eine Beschleunigung kann durch einen besseren Zuggenerator, am Besten mit Heuristik, erzielt werden. Bei 3DTTT, Gobang und Reversi habe ich das versucht.

Es war mein Bestreben eine Möglichkeit zu finden, mit möglichst wenig Aufwand ein neues Strategiespiel zu entwickeln, wenn eines schon existiert.

Man muß nur Datentypen für das Spielfeld, die Figuren und die Züge entwickeln, sowie Zuggenerator, Bewertungsfunktion und Zugausführung implementieren.

Da alle Programme z.Zt. nur über Suchtiefe rechnen, bin ich dabei stattdessen über eine einstellbare Rechenzeit rechnen zu lassen - ist noch nicht fertig, die Breitensuche bereitet mir noch Kopfzerbrechen

Gute Idee: (Also erstmal bei Level=3 durchrechnen lassen, dann bei 4 usw.)

In meinen Programmen wird über Service --> Zugbewertung einiges an Infos angezeigt.

Gruß, Fiete

Du könntet die Zugbewertung als Stack implementieren:

- Erster Zug wird gepusht.

Für jeden Zug wird nundurchgerechnet:
- Punktzahl nach AlphaBeta OHNE zusätzliche Tiefe,
- Nicht zu verarbeitende Subzüge entfernen
- Alle zu betrachtenden Züge auf den Stack legen.
- Referenz für Bewertung des Zuges MIT AlphaBeta wird auf Stack für spätere Bewertung verschoben (Alle möglichen Unterzüge). (entfällt IIRC bei AlphaBeta, da das MAximum\Minimum durchgereicht wird).

Wird nun ein besserer Zug gefunden, wird die gefundene Zugfolge und deren Punktwert gespeichert.

Somit kann man effektiv die Spielzugdaue Levelgesteuert bauen, ohne bei jedem Durchlauf alle Berechnungen des vorigen Levels noch mal zu tätigen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.