| |
| Autor |
 Wer gewinnt beim Spiel Isola? |
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 2312
 |  Themenstart: 2018-08-23
|
Hallo Leute!
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_isola.gif
( Bild von http://www.superfred.de/isola.html )
Ich habe vor Jahren das Spiel Isola gespielt.
"Isola ist ein strategisches Brettspiel für zwei Spieler. Es wurde 1972 und 1980 vom Ravensburger-Verlag herausgegeben.
Es wird auf einem 8×6 Felder großen Spielfeld gespielt. Jeder Spieler hat eine Spielfigur, außerdem benötigt man noch 46 Plättchen, um die erlaubten Felder zu markieren. Zur Vorbereitung werden die beiden Spielfiguren auf die Felder A3 und H4 gestellt. Alle anderen Felder werden mit den Plättchen belegt. Ein Spielzug besteht aus zwei Schritten: Zuerst bewegt der Spieler seine Spielfigur auf eines der (maximal acht) umliegenden Plättchen, wobei er nicht auf das Feld mit dem Gegner ziehen darf. Dann entfernt er ein beliebiges Plättchen, das von keinem der beiden Spieler belegt ist. Wer zuerst nicht mehr ziehen kann, hat das Spiel verloren." ( https://de.wikipedia.org/wiki/Isola_(Spiel) )
Mich würde interessieren ob jemand weiß, wer bei optimalem Spiel beider Spieler gewinnt.
Viele Grüße
Ronald
|
 Profil
|
Ex_Senior
 | Beitrag No.1, eingetragen 2018-08-24
|
Nur eine kurze Überlegung zur Spielkomplexität:
Wenn man $46-k$ leere Felder hat, bei denen also die Plättchen schon entfernt wurden, so bleiben für die übrigen $k$ Plättchen also $\binom{46}{k}$ mögliche Positionen. Inklusive der beiden Startfelder können die beiden Spielfiguren auf $k+2$ möglichen Positionen stehen, sodass es dafür also für jede entsprechende Plättchenverteilung $\binom{k+2}{2}$ Positionen für die beiden Spielfiguren gibt. Offenbar läuft $k$ von 46 bis 0, sodass man durch Summation der Produkte dieser beiden Binomialkoeffizienten die Anzahl möglicher Stellungen in diesem Spiel nach oben abschätzen kann. Das wären dann ca. $2 \cdot 10^{16}$ Stück, wobei nicht alle davon aus der Startposition erreichbar sein dürften.
Das klingt nach einer angreifbaren Größenordnung.
Cyrix
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.2, vom Themenstarter, eingetragen 2018-08-25
|
Hallo,
zur Zeit als ich Isola spielte gab es auch 4-gewinnt. Darüber wurde schon vor langer Zeit eine Arbeit geschrieben, mit dem Ergebnis Spieler 1 (weiß) gewinnt bei richtigem Spiel.
(siehe auch https://de.wikipedia.org/wiki/Gelöste_Spiele )
Bei Isola gibt es Spielsituationen, die häufiger auftreten. Ein Endspiel kann sein, dass ein Spieler auf einem 3x3 Feld mit 9 Feldern steht. Falls der Spieler nicht in der Mitte steht kann man im nächsten Zug das mittlere Feld durchdrücken (entfernen). Ich glaube, dies schränkt die Bewegungsfreiheit des Spielers am meisten ein.
Ein Sonderfall tritt ein, wenn beide Spieler direkt nebeneinander stehen und sich dieselben Restfelder teilen.
Ich kann mir vorstellen, dass Isola auch mal von jemandem vollständig gelöst wurde.
Viele Grüße
Ronald
|
Profil
|
gonz
Senior 
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
 | Beitrag No.3, eingetragen 2018-08-25
|
Hallo Delastelle,
wenn eine mögliche Gewinntaktik für den weißen Spieler bekannt ist, wäre es natürlich einfacher, diese zu verifizieren als, wie von Kitaktus angegeben, die gesamten Möglichkeiten der Züge für beide Spieler durchzugehen. Ich würde anfangen, das erst einmal mit einem kleineren Spielfeld durchzuprobieren, um auch ggf. programmierte Algorithmen testen zu können...
Grüsse
gonz
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2795
 | Beitrag No.4, eingetragen 2018-08-26
|
Hier mal ein paar er-bruteforce-te Ergebnisse für verschiedene Brettgrößen. Startfelder sind ganz links und ganz rechts, vertikal so nah an der Mitte, wie's geht (im Fall ungerader Höhe des Spielfeldes sind die Startfelder also in derselben Zeile).
\sourceon
1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4
---------------------------
1 - 0 0 1 1 1 1 1 1 1 1 1 1 1
2 0 1 0 1 1 1 1 1 1 1 1
3 - 0 0 1 1 1 1
4 1 1 0 0 1
5 - 0 0 0
6 1 0 0 x
7 - 1 1
8 1 0
9 - 1
10 1 1
11 - 1
12 1 1
13 -
14 1
\sourceoff
Bei Spielfeldbreite 1 und ungerader Höhe würden die Startpositionen der Spielfiguren aufeinandertreffen müssen. Daher steht an den entsprechenden Stellen in der Tabelle ein -.
Ein 1-Eintrag heißt: der Anspielende gewinnt garantiert bei perfektem Spiel. 0 heißt: der Anspielende verliert garantiert bei perfektem Spiel des Gegners.
Gefragt ist der Eintrag, der an der Stelle steht, die mit x markiert ist. Wer bietet eine vollere Füllung der Tabelle?
Da die Einträge, die sich grob entlang der Diagonale befinden, empfindlich von den tatsächlich gegebenen Dimensionen abzuhängen scheinen, glaube ich nicht, dass es eine einfach beschreibbare (falls überhaupt vorhandene) Gewinnstrategie für den Anziehenden im Fall von Breite 8, Höhe 6 gibt.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.5, eingetragen 2018-08-26
|
tactac,
klasse :) Magst du mitteilen, mit welchen Mitteln und mit welcher Rechenzeit du die Werte ermittelt hast? Damit man mal so ein Gefühl bekommt wie man vorgehen müsste...
Grüsse und einen schönen Sonntag
Gonz
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.6, eingetragen 2018-08-26
|
Nachtrag:
Erstmal nur gedanklich beschäftige ich mich mit diesbezüglichen Endspielen, und dabei ist mir aufgefallen, dass man Steine, die keiner der Spieler mehr erreichen kann, zwar nicht ganz wegnehmen kann, aber nur noch deren Anzahl wissen muss ( da man als Spieler ggf. einen von dort nehmen kann als "Tempozug" ). Es ergeben sich dann ein oder zwei "Inseln", auf denen die Spielfiguren sich aufhalten, und deren Gestalt zählt - unabhängig davon, wie sie zueinander oder zum Rand liegen. Das sollte es ggf. vereinfachen, in einer gewissen Tiefe vom Ende her zurückzurechnen und eine Datenbank Stellungen und deren Gewinner anzulegen ( ob das für eine Gesamtlösung hilfreich ist, sei erstmal dahingestellt ).
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.7, vom Themenstarter, eingetragen 2018-08-26
|
Hallo,
jetzt muss tactac vielleicht nur noch 20 Jahre seinen Rechner arbeiten lassen - dann ist die Lösung da.
Ich hatte auch schon überlegt, wie man auf eine Antwort auf die Frage "wer gewinnt?" bekommen kann. Ich dachte dabei an eine Lösung vom Endspiel an Rückwärts. Und wenn dann eine größere Datenbank mit Endspielzügen vorhanden ist, kann man versuchen vom Start mittels Suchbaumtechniken zu den Endspielen vorzudringen. Es kann aber sein, dass dies noch zu aufwändig ist.
Eine Frage bleibt noch bei den Lösungen für kleinere Brettgrößen: sind die Inseln der Spieler am Ende immer isoliert oder können die Spielfiguren (rot und blau im Original) auf mal Nebeneinander stehen am Ende?
Viele Grüße
Ronald
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.8, eingetragen 2018-08-29
|
Eine Vereinfachung könnte es noch geben: sind die Bereiche, in denen sich die Spielsteine befinden, getrennt, so kann man die Bereiche unabhängig voneinander betrachten ( der Spieler zieht immer mit seiner Figur so, dass er seine Chancen dort maximal verbessert, und nimmt aus der Fläche seines Spielpartners einen Stein derart, dass dessen Situation sich dort verschlechtert). Damit muss man für beide Teilbereiche nur noch wissen, in wievielen Zügen sie zur Entscheidung zu bringen sind, sie beeinflussen sich nicht mehr.
Wenn, ja wenn man sicher sein könnte, dass es niemals sinnvoll ist, in einem Bereich, in dem sich nur noch der eigene Spielstein befindet, selber einen Stein zu entfernen, sei es, um dort die eigenen Chancen zu verbessern, sei es, um den Gegner in seinem Bereich in "Zugzwang" zu bringen...
Ich bin am schwanken, ob es lohnt, sich hier zu engagieren. Das 8x6 Brett anzugreifen wäre, wie Cyrix schon schreibt, denkbar, aber sicher mit sehr viel Aufwand verbunden ( so man nicht Jahrzehnte an Rechenzeit investieren mag und einfach zuwartet ). Man könnte versucht sein, in dem Diagramm von Tactac Lücken zu füllen die am Rand des Bereichs mit den bereits ausgefüllten Werten liegen. Man könnte sich um die "Endspiele" kümmern. Oder man könnte Programme schreiben, die gegeneinander antreten.
Wollen wir?
Grüsse aus dem Harz
Gerhard/Gonz
|
Profil
|
Ex_Senior
| Beitrag No.9, eingetragen 2018-08-29
|
Moin zusammen,
ich schwanke auch, ob ich mich hier mal mit heransetze. Bei dem Spiel scheint Alpha-Beta-Suche gefühlt nicht so zielführend zu sein, da der Spielbaum doch recht schnell deutlich auffächert. Aber MCTS (Monte-Carlo-Tree-Search) wäre mal auszuprobieren. Und wenn man Bock hat, kann man dann noch ein kleines Neuronales Netz dafür trainieren. Das müsste recht gut funktionieren.
Wenn man dann herausbekommt, dass in der Startstellung häufig eine Spielpartei gewinnt, dann wäre das ein starker Hinweis, dass das Spiel für den An- bzw. Nachziehenden bei perfektem Spiel gewonnen ist.
Cyrix
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.10, vom Themenstarter, eingetragen 2018-08-30
|
Hallo,
bei Zillions-of-Games gibt es zum Download auch 2 Isola-Versionen.
Bei mir lief nur die Isola.zip Version.
Es ist ein Isola, wo auch die beiden Startfelder weggedrückt werden dürfen.
Ein kleiner Spielverlauf
Delastelle vs. schlechten Brute-Force-Computer
Notation hier a1 ist links unten, h6 ist rechts oben
move King, drop a Soldier
1. King a4-b4, Soldier f3, King h3-g4, Soldier a1
2. b4-c4, f4, g4-g5, g1
3. c4-d4, f5, g5-h6, a3
4. d4-c4, f6, h6-h5, b3
5. c4-d4, g3, h5-g4, g2
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_Zillions_Isola1.jpg
6. d4-d3, h3, g4-g5, c6
7. d3-c4, h5, g5-g6, c5
8. c4-d4, g5, g6-h6, e1
9. d4-e4, g6 Gewinn
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_Zillions_Isola2.jpg
Falls man einen Isola-Suchbaum generieren möchte muss man eventuell nur ein paar schlaue Suchkriterien finden. Ein Zug der Figur ist gut, falls man sich noch viele Züge lang bewegen kann. Ein Wegdrücken eines Steines ist gut, falls die Zugmöglichkeiten des Gegners kleiner werden - im Idealfall halbiert man den Bereich des Gegners.
Der Computer im obigen Zillions-of-Games erinnert an frühe Schach-Computer, die falls sie nicht mehr weiter wußten einfach Turm a8-b8 gezogen haben. (Der 1.mögliche Zug auf dem Brett von Schwarz, wenn der Springer b8 schon gezogen hat.)
@gonz: Du kannst auch 2 verschiedene Algorithmes ("engines") gegeneinander antreten lassen, z.B. 16 oder 100 Spiele lang. Und schauen welcher Algorithmus besser ist!
Strategie 1: z.B. rot oder Spieler 1 - halbiere das Feld indem ich Spalte 5 von 8 wegdrücke. Beginne bei Zeile 4 (von oben) gegenüber vom Spielstein blau, falls die Genze fertig ist, halbiere das gegnerische Feld. usw.
Strategie 2: z.B. blau oder Spieler 2 - wenn rot halbiert, muss ich das nicht tun. Ich drücke eine Zeile weg. Z.B. Zeile 3 (von oben), dort wo rot nicht steht. Falls sich rot für den oberen oder unteren Bereich des Feldes entscheidet, mache die Grenze dicht (Zeile 3 entfernen). Dann halbiere den Bereich von rot. usw.
Viele Grüße
Ronald
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.11, eingetragen 2018-08-31
|
Hi Roland,
ja das werd ich auch so mal angehen ( etwas bauen bei dem zwei Engines gegeneinander antreten können ) und dann könnte man daran auch gleich eine GUI anbinden ( quasi auch als "engine" ), sodass damit auch Mensch-Maschine und Spiele unter Menschen ermöglicht werden :)
Ist ja bald Wochenende * schmunzel
Grüsse aus dem Harz
Gerhard/Gonz
PS.: Ich glaube, ich muss dass auch erst nen paarmal wirklich gespielt haben, um eine Idee zu bekommen, wie eine gute Strategie aussehen könnte :)
|
Profil
|
Ex_Senior
| Beitrag No.12, eingetragen 2018-08-31
|
Falls jemand eine Schnittstelle, wo man nur noch die jeweilige Stellung abgreift und den eigenen Zug einspeist, zur Verfügung stellen würde, könnten wir tatsächlich verschiedene Algorithmen gegeneinander antreten lassen.
Cyrix
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.13, eingetragen 2018-08-31
|
das klingt gut :) ich hätte da als Ansätze entweder eine TPC/IP Schnittstelle mit Übertragung der Daten als ASCII String, oder HTTP/POST mit angehängtem XML? Dann könnten wir das Ganze im Web online stellen und jeder der mag damit rumspielen.
|
Profil
|
Ex_Senior
| Beitrag No.14, eingetragen 2018-08-31
|
Ich meine, ich bin ja auch nur zu faul, ggf. alles selbst zu basteln. Insofern dies bitte nicht als Anforderung o.Ä. verstehen, sondern bestenfalls als Wunsch: Ich würde gern auch lokal auf meinem Rechner zwei Strategien - etwa zur Optimierung - gegeneinander spielen lassen können, ohne dafür einen Webserver zu belasten. (Es erscheint mir aus meiner naiven Sicht auch erst einmal einfacher, sich dafür nicht mit Übertragungswegen übers Netz auseinander setzen zu müssen. Aber damit kenne ich mich auch einfach nicht aus, kann also die potentiellen Schwierigkeiten dabei nicht gut einschätzen.)
Cyrix
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.15, eingetragen 2018-08-31
|
Naja, wenn man etwas für den lokalen Rechner baut, könnte man auch entweder die "engines" per lokaler IP Schiene einbinden, also via "localhost" kommunizieren, oder am einfachsten natürlich sich auf eine Sprache einigen und einen Programmrahmen schreiben, in den die Engines eingebunden werden.
Dazu wäre dann eben zu klären, welche Sprache etc. Was da aktuell so zeitgemäß wäre ist mir leider unklar... ich bin aber für Vorschläge immer offen ( und mag es, wenn man sich die Mühe nur einmal macht und andere eben profitieren können ). Sollte es fürs Web tauglich sein, müsste noch ein minimales Userhandling dazu, damit klar ist, wer welche Partien spielt/gespielt hat bzw. berechtigt ist Züge abzugeben...
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.16, eingetragen 2018-08-31
|
Ich hab mal nen bissl gebastelt - Datenbank und ein paar Routinen für den Zugriff, das Testen von gültigen Zügen etc. Mit einer rudimentären Oberfläche... guckst du:
[aktuell nicht mehr erreichbar]
Eine vollständige Beschreibung einer Stellung liefert hier einfach die Belegung der Felder, die ich als ASCII String speichere ( zB "-" für Leer, "x" für verdeckt, "S" und "W" für die beiden Spielsteine )… Damit ist eigentlich auch klar, wer am Zug ist ( bei einer geraden Anzahl von belegten Feldern der Weisse ).
Die Angabe eines Zuges mache ich in der Form zB "A3 B4" : ziehe nach A3 und decke das Feld B4 auf. A1 unten links, H6 oben rechts.
Ich könnte jetzt eine beliebige Schnittstelle für den Zugriff vom Computer aus einbauen, oder erstmal eine minimale Oberfläche, um dort wirklich mit ein bissl GUI spielen zu können ( oder beides... ).
Alternativ könnte ich "engines" direkt in das Programm einbinden ( es ist in PHP geschrieben ). Auch eine kleine Userverwaltung wäre nicht schlecht.
Mal gucken. Anmerkungen / Wünsche / Anregungen immer willkommen :)
Grüsse
gonz
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2795
| Beitrag No.17, eingetragen 2018-08-31
|
\quoteon(2018-08-26 11:36 - gonz in Beitrag No. 5)
tactac,
klasse :) Magst du mitteilen, mit welchen Mitteln und mit welcher Rechenzeit du die Werte ermittelt hast? Damit man mal so ein Gefühl bekommt wie man vorgehen müsste...
\quoteoff
Pure stundenlange Gewalt, mit einem generischen rekursiv vorgehenden Algorithmus, der aber die Ergebnisse für Stellungen, die er schon gesehen hat, sich merkt.
Die einzige Optimierungsmöglichkeit ist in der Beschreibung des Spiels: Eine Stellung ist Gewinnstellung gdw. irgendeine Spiegelung oder Drehung oder Translation der Stellung (und Kompositionen davon) eine Gewinnstellung ist. Daher kann die Zugausführung ja von allen sich durch Symmetrien ergebende Stellungen die zurückgeben, die bzgl. irgendeiner totalen Ordnung minimal ist -- so trifft man vielleicht öfter auf schonmal gesehenes. Desweiteren ist natürlich unerheblich, *wo* sich Plättchen befinden, die niemand mehr betreten kann.
\quoteon(2018-08-26 20:45 - Delastelle in Beitrag No. 7)
jetzt muss tactac vielleicht nur noch 20 Jahre seinen Rechner arbeiten lassen - dann ist die Lösung da.
\quoteoff
:-D Könnte sein, dass 20 Jahre nicht reichen. Es wird auch viel zu viel Speicher benötigt.
Die Ergebnisse, da durch ein mehr oder weniger offensichtlich korrektes aber ineffizientes Programm erzeugt, sind eher dazu gedacht, cleverere Programme mit Bugs identifizeren zu können.
Zwei weitere Ergebnisse sind übrigens: (3,7) ist eine Gewinnstellung, (2,12) auch :-P .
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.18, eingetragen 2018-09-01
|
ein bissl weitergebaut. man kann die züge jetzt zusammenklicken. Als "Probierbrett" um einen ersten Eindruck zu gewinnen mag es durchgehen. Wir spielen das hier nebenbei immer mal, es macht Spass. Vielleicht kommt mir dann auch eine Idee für eine Strategie :)
[aktuell nicht mehr erreichbar]
|
Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 3279
 | Beitrag No.19, eingetragen 2018-09-02
|
Zur effizienten Implementierung eine Idee:
Die gesamte Spielsituation passt in eine 64-bit Variable.
- 48 Bits für die Plättchenbelegung.
- Je 6 Bits für die Position der Spielsteine
- 4 Bits für sonstige Infos (bspw. Partei am Zug oder Ergebnis, falls bereits bekannt)
Diese Darstellung erlaubt es auch, recht flott die Zugmöglichkeiten einer Seite zu finden.
Als Eingabe für neuronale Netzwerke ist sie natürlich nicht so gut geeignet.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.20, eingetragen 2018-09-02
|
Yep, das ist gut für den Rechner :) Wer am Zug ist ergibt sich eigentlich daraus, ob die Anzahl der verdeckten Felder gerade oder ungerade ist, das muss man aber nicht immer neu auszählen.
Ich bin am überlegen, ob ich aus meinem Probierbrett mal etwas baue, mit dem übers Internet zwei Personen gegeneinander spielen können. Wer hätte denn Lust dazu mal ein paar Probepartien zu spielen? Mich würde dabei zB auch die Statistik der Anfangszüge interessieren und ggf. können wir dann ein bissl über Eröffnungen etc fachsimpeln?
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.21, vom Themenstarter, eingetragen 2018-09-05
|
Hallo,
wer noch Strategien zum Programmieren sucht, hier sind 2:
(1) gehe zufällig auf ein Nachbarfeld, drücke zufällig einen Stein
(2) gehe auf ein Nachbarfeld, das möglichst viele Nachbarfelder hat. Dann drücke ein Nachbarfeld vom Gegner weg.
Ich selbst möchte mir Strategien für Endspiele anschauen.
Beispielsweise nur 1 Stein, der möglichst lange ziehen soll, bevor er nicht mehr kann.
1.Aufgabe: rot steht auf einem 3x3 Feld links oben. Wie lange kann er ziehen, wenn der Gegner blau immer 1 Feld seiner Wahl wegdrückt.
(Das läuft auf eine rekursive Funktion heraus, eventuell mit alpha-beta-Suche)
Viele Grüße
Ronald
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.22, eingetragen 2018-09-05
|
Ich bin aktuell hier angelangt:
bisher ist es noch eine Art von Probierbrett und nicht geeignet, Partien gegeneinander oder gegen Algorithmen zu spielen. Nur ein Zwischenstand sozusagen. Anregungen werden gerne angenommen :)
Einen schönen Tag wünscht
Gerhard/Gonz
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.23, vom Themenstarter, eingetragen 2018-09-06
|
Hallo,
ich habe mit Scilab mal 2 Strategien probiert:
(1) gehe zufällig auf ein Nachbarfeld, drücke zufällig einen Stein
und
(2) gehe auf ein Nachbarfeld, das möglichst viele Nachbarfelder hat.
Dann drücke ein Nachbarfeld vom Gegner weg. Falls dies nicht geht drücke ein beliebiges Feld weg.
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_Isola_Spielverlauf_Strategien_2_und_2_neu.jpg
Ein Endbild Strategie 2 gegen Strategie 2.
Ein paar Ergebnisse der Strategien gegeneinander:
\
array(Spiele,Strategie a,Strategie b,Siege von a,Zuglänge bei Sieg a,Siege von b,Zuglänge bei Sieg b,Zeit;1000,1,1,493,39.764706,507,40.037475,16.2;1000,2,1,969,21.684211,31,38.096774,55.1;1000,1,2,33,35.090909,967,22.247156,54.0;1000,2,2,486,28.777778,514,28.817121,90.8)
Im Programm sind wahrscheinlich nur noch endlich viele Fehler. Deshalb diese Zahlen unter Vorbehalt.
Viele Grüße
Ronald
Edit:
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_Isola_Spielverlauf_Strategien_3_und_2.jpg
Bild Endstand Strategie 3 rot und Strategie 2 blau: rot drückt die 5.Spalte, dann den Rest der 3.Zeile weg
Ich habe noch eine neue Strategie implementiert:
(3) gehe auf ein Nachbarfeld, das möglichst viele Nachbarfelder hat.
Wegdrücken für rot (Spieler 1), drücke Feld 29, falls blau im oberen Bereich ist, drücke weg: 21,13,5 dann 37 und 45,
falls blau im unteren Breich ist drücke weg 37,45 dann 21,13,5 // (A) 5.Spalte
jetzt versuche wegzudrücken 23,22,24 // (B) 3.Zeile rechte Seite des Feldes
falls blau jetzt im unteren Bereich ist drücke 39,31,47 // (C) Teilung unten rechts
falls blau jetzt im oberen Bereich ist drücke 15 und 7 // (D) Teilung oben rechts
nach der selben Logik drücke 38,30,46 bzw. 40,48 bzw. 14,6 bzw. 16,8
Wegdrücken für blauen Spieler (Spieler 2) analog nur gespiegelte Felder.
\
array(Spiele,Strategie a,Strategie b,Siege von a,Zuglänge bei Sieg a,Siege von b,Zuglänge bei Sieg b,Zeit;1000,1,3,18,41.555556,982,23.969450,78.3;1000,2,3,384,24.296875,616,27.542208,120.9;1000,3,1,994,23.338028,6,44.000000,79.5;1000,3,2,943,23.972428,57,21.175439,110.1;1000,3,3,1000,24.000000,0,0.000000,141.3)
Es fällt auf das Strategie 1 am schlechtesten ist, 2 ist besser und 3 für rot am besten.
Falls Strategie 3 (rot) gegen Strategie 3(blau) spielt, verliert blau (zumindest bei meinen Testläufen).
Ich habe auch schon mal eines Testlauf gesehen bei dem blau mit Strategie 3 gegen rot mit Strategie 2 sich auf die linke Hälfte des Feldes verlaufen hat. Dies ist eher ungünstig.
Edit: 9.9.2018
Für Spieler 2 (blau) habe ich auch einmal eine Antistrategie gegen Strategie (3) gestestet:
(4 blau) gehe auf ein Nachbarfeld, das möglichst viele Nachbarfelder hat.
Drücke im Breich von rot die 4.Zeile weg, dann die 2.Spalte oben oder unten je nachdem wo
sich rot aufhält. Drücke danach noch einen Teil einer Zeile weg. Im Fall von rot ist
rechts oben den Rest der 2.Zeile.
https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/15578_4_Isola_Spielverlauf_Strategien_3_und_4.jpg
Beispiellauf Strategie 3 (rot) gegen Strategie 4 (blau)
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.24, vom Themenstarter, eingetragen 2018-09-24
|
Hallo,
ich habe mal etwas zum Thema Endspiele getestet.
Z.B. 3x1, 3x2 und 3x3 Felder mit dem roten Stein (Spieler 1) links oben.
So richtig gut funktioniert es aber noch nicht.
Zu klären wären dabei:
(a) wie sieht gutes Spiel von rot (Spieler 1) aus. Welche Züge sind gut?
(b) wie sieht gutes Spiel von blau (Spieler 2) aus. Welches Wegdrücken von Feldern ist gut?
Für (a) und (b) habe ich Probleme sofern noch viele Steine da sind und entsprechend viele Zugmöglichkeiten.
Viele Grüße
Ronald
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1437
Wohnort: Koblenz (früher: Berlin)
 | Beitrag No.25, eingetragen 2018-09-28
|
Eine andere Möglichkeit, einen Zug zu finden besteht darin, eine Spielstellung nach geeigneten Kriterien zu bewerten und dann den Zug auszuführen, der zu der Position mit der besten Bewertung führt.
Eine solche Bewertungsfunktion lässt sich theoretisch auch mit einer Suche kombinieren.
Viele Grüße,
Kay
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1437
Wohnort: Koblenz (früher: Berlin)
| Beitrag No.26, eingetragen 2018-09-30
|
Hier mal meine Browserumsetzung: Isola
Für jedes Feld wird ein Score berechnet, in den die Zahl der Nachbarn, aber auch die Zahlen der Nachbarn der Nachbarn usw. einfließen. Es wird dann so gezogen bzw. entfernt, dass das Scoreverhältnis eigenes/gegnerisches Feld maximal wird.
Die KI scheint augenscheinlich vernünftig zu agieren, wenngleich taktisch vielleicht noch etwas anfällig...
Viele Grüße,
Kay
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.27, vom Themenstarter, eingetragen 2018-09-30
|
Hallo Kay!
Mir stellt sich dann die Frage, wer gewinnt wenn Computer gegen Computer spielt.
Falls es (fast) immer eine Seite ist, wäre das schon interessant!
Viele Grüße
Ronald
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.28, eingetragen 2018-09-30
|
Hi Kay, interessante Umsetzung. sag bescheid, wenn du die KI etwas aufpoliert hast. Habe das erste spiel gewonnen. Bei dem Programm von Gonz mit seiner KI habe ich es leider nicht hinbekommen die KI spielen zu lassen. Gibt es da einen Trick? Ich denke ich werde mich auch mal an einer Umsetzung versuchen.
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1437
Wohnort: Koblenz (früher: Berlin)
| Beitrag No.29, eingetragen 2018-10-01
|
\quoteon(2018-09-30 20:57 - Delastelle in Beitrag No. 27)
Hallo Kay!
Mir stellt sich dann die Frage, wer gewinnt wenn Computer gegen Computer spielt.
Falls es (fast) immer eine Seite ist, wäre das schon interessant!
Viele Grüße
Ronald
\quoteoff
Das Ergebnis hängt dann vermutlich vom Zufall ab. Die Frage ist auch die nach dem Erkenntnisgewinn, denn beide Seiten sind ja auf demselben Auge blind.
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1437
Wohnort: Koblenz (früher: Berlin)
| Beitrag No.30, eingetragen 2018-10-03
|
\quoteon(2018-09-30 23:46 - Scynja in Beitrag No. 28)
Hi Kay, interessante Umsetzung. sag bescheid, wenn du die KI etwas aufpoliert hast.
\quoteoff
Die KI rechnet nun zwei Züge im Voraus (eigener + gegnerischer Zug), wobei nur Felder entfernt werden, die vom Gegner in ein oder zwei Zügen erreicht werden können.
Danach wird der Feldscore ermittelt und angenommen, dass man im nächsten Zug auf das Nachbarfeld mit dem höchsten und danach der Gegner auf das mit dem zweithöchsten (da eins beseitigt wird) zieht. Das Verhältnis der beiden Scores ist dann die Bewertung der Position.
Bei der Bewertung muss man immer den Fall beachten, dass bei zwei Nachbarfeldern der Gegner evtl. auf das eine ziehen und danach das andere beseitigen könnte, was eine Verluststellung bedeutet.
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 2312
| Beitrag No.31, vom Themenstarter, eingetragen 2018-10-05
|
Hallo,
im Schach gab es mal einen Computer, der auf spezieller Hardware rechnete.
Ich meine das Schachprogramm/den Computer "Belle" ( https://de.wikipedia.org/wiki/Belle_(Schach) ).
Mit diesem Computer startete Ken Thompson mal ein Experiment:
er ließ "Belle" mit Suchtiefe n gegen Suchtiefe n+1 spielen. Und das mit n = 3, 4, 5, ..., 8
Wenn Kay zu viel Zeit hat, kann er ja auch seine KI mit Tiefe 1 gegen Tiefe 2 spielen lassen! Und falls die KI auch größere Suchtiefen hinbekommt, n gegen n+1 als Suchtiefe.
Viele Grüße
Ronald
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.32, eingetragen 2018-10-05
|
\quoteon(2018-09-30 23:46 - Scynja in Beitrag No. 28)
Bei dem Programm von Gonz mit seiner KI habe ich es leider nicht hinbekommen die KI spielen zu lassen. Gibt es da einen Trick?
\quoteoff
Nee, das Ganze funktioniert (noch) nicht so wie es soll... Ich muss da nochmal dran * schmunzel
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.33, eingetragen 2018-10-14
|
So, nach zahlreichen Hilfsfunktionen und Linterproblemen ist es endlich soweit. Das Board ist fertig und die leichte KI implementiert.
http://sigmanek.net/features/isolaAi
Mal sehen, wie ich die tweaken kann. Habt ihr inzwischen eine Möglichkeit gefunden, wie man die KIs gegeneinander antreten lassen kann? (ohne dass man die eine Seite händisch spielt)
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.34, eingetragen 2018-10-15
|
Huhu Scynja!
Das funktioniert prima, allerdings ist es (noch?) mit intuitivem Spiel ohne grösseres Nachdenken zu schlagen. Prima! Eine witzige Sache, eher ein Schönheitsdingens: Wenn das Spiel beendet ist, zeigt es an "Rot ist am Zug"... Jedenfalls macht es Spass. Werden die Partien geloggt? Dann wäre es klasse mal zu gucken wie "Menschen" so spielen * schmunzel
Zum Thema vernetzen... Ich hätte folgende Vorschläge, die ich halbwegs einfach realisieren könnte:
a) per HTTP POST, wir definieren eine API, die Züge werden dann entweder einfach in festgelegten Variablen übertragen, sowas wie
www.gonzens.de/isola_api?id=121233&myzug=A3&aufdecken=B5
(bisher ein Beispiel ohne jegliche Funktion)
a1) wie a), aber es wird im Anhang eine XML Datei transportiert
b) Eine TCP/IP Verbindung, über die wir irgendein Format definieren, irgendwas ASCII definiertes...
c) SOAP
d) per EMail, dann könnte man es so bauen, dass auch Menschen es benutzen können, um Fernschach-mäßig Partien langsam, aber mit Überlegung gegeneinander zu spielen...
Ich wäre aber auch für andere Vorschläge offen!
Wir könnten im Vorlauf schon einmal vereinbaren, wie komplette Stellungen oder die Zugfolge einer Partie codiert werden könnte.
Grüsse aus dem Harz
und immer noch bannig interessiert
Gerhard/Gonz
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1437
Wohnort: Koblenz (früher: Berlin)
| Beitrag No.35, eingetragen 2018-10-15
|
Benötigt man bei all diesen Lösungen einen Webserver (der die Züge entgegennimmt, weiterleitet und die Regeln überprüft, also quasi die 'Turnierleitung') oder geht es auch ohne?
Man müsste auch noch beachten:
- Zeitbeschränkung pro Zug, da man mit viel Rechenzeit sein Programm natürlich prinzipiell stärker spielen lassen kann
- Zufallskomponente (z.B. zufällige Wahl der Startfelder), da bei rein deterministischen Kontrahenten nur zwei verschiedene Partien produziert werden, sonst nur Dubletten
Kay
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.36, eingetragen 2018-10-15
|
Ich hatte es erst so gedacht dass es "peer-to-peer" geht, und man ggf. den Clients beibringen kann, Listen der ihnen bekannten Gegner auszutauschen, sodass nach und nach ein Netzwerk entsteht. Das Logging von Partien könnte dann der Client übernehmen, und wir könnten die Daten von gespielten Partien dann manuell hier hochladen und posten...
Aber ein zentraler Server wäre auch gar nicht so schlecht, bzw. wäre ja eher notwendig, wenn man eine Zeitbegrenzung pro Zug einführen würde ( was ich wiederum auch sehr sinnvoll finde ).
Natürlich könnte ein Server dann auch
- Listen der möglichen Spielpartner zur Verfügung stellen,
- die Spielzüge weiterleiten, ggf. gar "multiprotokollfähig" sein wenn wir das wollen,
- Partien loggen,
- Statistiken über Ergebnisse führen,
- Züge auf Gültigkeit überprüfen,
- über ein Web-Interface diese Informationen zur Verfügung stellen
[ja, das alles und mehr...]
Und natürlich gäbe es eine zwischenversion, einen Server, der Clientadressen und Spielwünsche verwaltet und zur Verfügung stellt, und die Ergebnisse für die Statistik mitgeteilt bekommt, während die eigentlichen Partien dann eben peer-peer ausgetragen werden ( man könnte trotzdem natürlich eine Zeitüberwachung einführen, eben auf Client Seite, und wir würden ja sowieso sehen, dass wir das alles "good-will" machen, wenn jemand den eindruck hat, sein programm bekommt ungültige Züge mitgeteilt oder es wurde ungültig auf "Zeitüberschreitung" plädiert, dann muss eben der jeweilige Programmautor benachrichtigt werden und gucken, was Sache ist...
(letzteres Modell würde mir persönlich am besten gefallen)
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.37, eingetragen 2018-10-15
|
Vielleicht könnten wir uns auf folgende Darstellung für den Verlauf einer Partie einigen, wie oben von Delastele benutzt:
Notation hier a1 ist links unten, h6 ist rechts oben
move King, drop a Soldier
1. King a4-b4, Soldier f3, King h3-g4, Soldier a1
2. b4-c4, f4, g4-g5, g1
3. c4-d4, f5, g5-h6, a3
4. d4-c4, f6, h6-h5, b3
5. c4-d4, g3, h5-g4, g2
und dazu ggf. ähnlich wie im PGN Format einen Header voransetzen, sowas wie
[Event "Uebungspartie"]
[Runde "1"]
[Datum "15.04.2018"]
[Weiss "Gonz"]
[Schwarz "Der_Gruselmonster_Algo"]
[Ergebnis "offen"]
1. a4-b4, f3, h3-g4, a1
2. b4-c4, f4, g4-g5, g1
3. c4-d4, f5, g5-h6, a3
4. d4-c4, f6, h6-h5, b3
5. c4-d4, g3, h5-g4, g2
Einen konkreten Spielstand könnte man dann einfach durch Zeilenweises angeben von W ( White King ), R ( Red Queen ), X nicht aufgedeckt, - offen darstellen:
XXXXXRXX
XXXXX-XX
XXX-X-XX
XXW-XXXX
XXXXXXXX
XXXXXXXX
Ggf. wären noch Daten zum Abgleichen der Zeitkontrolle mit zu übermitteln, und bei einer Position die Angabe, wer am Zug ist
( wobei die ja eigentlich redundant ist, da man es aus der Anzahl
der aufgedeckten Felder ermitteln kann).
Eigentlich bräuchte man dann gar kein Protokoll, sondern könnte sich einfach Spielstände "zuwerfen", wobei eben eine leere Partie eine Herausforderung darstellt.
Nachtrag:
Ich glaube inzwischen, dass eine komplette Berechnung des Spiels "mit Bordmitteln" nicht möglich ist, aber natürlich könnte ein Programm eine recht umfangreiche Datenbank benutzen. Das wäre aber ja alles kein Problem, solange wir mit offenen Karten spielen und dokumentieren, wie da was gemacht ist.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4728
Wohnort: Harz
| Beitrag No.38, eingetragen 2018-10-15
|
Und noch ein Nachtrag...
da ja die meisten mit ihrem heimischen Rechner eine dynamische IP Adresse haben, dürften wir einen zentralen Server schon alleine zum Herstellen der Verbindung benötigen?
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.39, eingetragen 2018-10-15
|
Meine interne Implementierung sieht ein Doppelarray y*x vor. In diesem ist dann jeweils ein enum mit empty, blocked, p1 oder p2. Ich weiß gar nicht, ob er das mit strings oder number abbildet. Beim Restservice muss man wieder Corsheader beachten, was das ganze verkompliziert. Also sind WebSockets wohl die Lösung. Ich hatte eher gehofft, dass man ähnlich wie bei codinggame seinen Algorithmus eintippt und dann testet.
@gonz, gut gesehen mit dem rot statt grün. Ich muss die Farben eh noch auf die Webseitenfarben abstimmen. Die KI prüft derzeit nur einen Zug im voraus. Da sollte man eigentlich gut gewinnen können.
[Die Antwort wurde nach Beitrag No.37 begonnen.]
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
