Die Mathe-Redaktion - 16.11.2018 21:56 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt3 im Schwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 435 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo matph
Informatik » Angewandte Informatik » Wer gewinnt beim Spiel Isola
Thema eröffnet 2018-08-23 22:12 von
Delastelle
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich Wer gewinnt beim Spiel Isola
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2018-10-15


2018-10-15 17:52 - Scynja in Beitrag No. 39 schreibt:
Ich hatte eher gehofft, dass man ähnlich wie bei codinggame seinen Algorithmus eintippt und dann testet.
[Die Antwort wurde nach Beitrag No.37 begonnen.]


Hm, du meinst, wir bauen eine Art Scriptsprache ein mit der man verschiedene Algorithmen implementieren kann? Oder einigen uns auf eine Programmiersprache und binden dann die jeweils beigestellten Programmteile in einen Rahmen ein, der sie gegeneinander spielen lässt?


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2018-10-15


Genau. Dort kann man sogar zwischen jeder beliebigen Sprache wählen. Aber in unserem Fall würde sich JavaScript anbieten, da wir ja eh alle im Web unterwegs sind. Ich weiß nur nicht, wie das mit der Sicherheit ist. Deshalb habe ich noch nicht probiert soetwas auf meiner Webseite einzubauen. Man kann ja Quasi jeden Code dann schreiben. Beginnend mit Format C bist zu drop table user. Oder irgendwelche DOS Attacken. Es gibt zwar die same-origin policy, aber hundertprozentig wohl fühle ich mich noch nicht dabei so eine Schnittstelle einzubauen.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, eingetragen 2018-10-15


Ah das zu lernen wie es da mit Sicherheitsaspekten ist würde mich aber auch interessieren. Man müsste die Scripte zB irgendwie in einer Art Box laufen lassen können, von der aus keine Zugriffe auf das restliche System möglich sind? Wir könnten natürlich auch so vorgehen, dass wir beigestellen Code vorher irgendwie reviewen, bevor "jemand" ihn dann einbindet. Eine offene Schnittstelle nach draussen zum Upload "irgendwelchen" Codes würde mir auf meinem Server sicher auch nicht gefallen ...


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2018-10-15


Ich habe gerade mal auf google.de geguckt. Man kann ja ohne weiteres in der Konsole auf der Seite Bibliotheken wie axios einbinden und dann Requests ausführen. Wahrscheinlich ist es also wirklich sicher, da der Code nur im Client ausgeführt wird. Also es tun sich wahrscheinlich keine zusätzlichen Sicherheitsrisiken auf.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2018-10-16


Scynja:

Und wie wäre es andersherum? Die Überlegung, dass sich die Programme via Socket Verbindung jeweils den aktuellen Partiestand "zuwerfen"? Das wäre vielleicht auch eine nette Erweiterung der Sache :)


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2018-10-16


Hallo Gonz, das hätte zur Folge, dass die Spieler jedes mal den anderen Zug validieren müssen. Zumindest im web wüsste ich nicht, wie ich zwei Clients ohne Server miteinander reden lassen soll. Mit einer app oder desktop Applikation ist das kein Problem.
Mir ging es in erster Linie darum meine KI gegen eine andere antreten lassen zu können. Wenn ich mir also einen Server aufsetze, welchen ich wegen des Quiz auf meiner Seite eh brauche, dann kann zwar jeder gegen meine KI spielen, ich habe aber keine Möglichkeit meine KI gegen andere antreten zu lassen.
Die Vision ist, dass man eine BasisKI hat. Dann kann man code gegen die KI spielen lassen. Wenn der Code 3 mal gewinnt, kann er im Server abgelegt und validiert werden. Wenn es keine Schadsoftware ist, kann die KI integriert werden und ab sofort kann jeder gegen die BasisKI oder die erste eigene KI spielen. Kannst du so einen Service bereitstellen?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2018-10-17


Ja das klingt machbar :)


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, eingetragen 2018-10-17


Nachtrag:

Ich baue mal nen Prototypen. Die Vorstellung wäre also:

Es gibt irgendwo einen Server im Internet, sozusagen "Die Zentrale", im folgenden kurz "der Server" genannt. Hier kann man per Browserzugriff spielen, zB gegen verschiedene dort schon hinterlegte Algorithmen. Man kann ausserdem Algorithmen gegeneinander spielen lassen.

Das Spiel an sich läuft dann jeweils lokal auf dem Rechner des Users, indem dort eine (zB per PHP erzeugte) Seite im Browser angezeigt wird, die javascripte beinhaltet, die die eigentliche Spielabwicklung entweder user-algo oder algo-algo abwickeln. Nur die Ergebnisse werden dann zur späteren Statistik etc. wieder auf den Server hochgeladen.

Wenn man einen neuen Algo hat, dann stellt man hierzu ein Codesnipplet zur Verfügung, zB in Javascript, und lädt dieses auf den Server hoch. Der Server bietet von da ab an, dass man gegen diesen neuen algo spielen kann, oder ihn auch gegen andere schon etablierte algos antreten lassen kann.

Wenn der algo gut ist ( also zB Erfolge gegen bereits bestehende Algos oder menschliche Spieler aufzuweisen hat), dann erfolgt ein Review ( zB durch uns hier im Forum oder so... ) und wenn alles gut geht wird er "kanonisiert", das heisst vom Server von da ab offiziell angeboten.

Der Server kann dabei auch eine Art "Ranking" durchführen, oder jeweils den ( für die Situation? ) bisher am geeignetesten erscheinenden Algo benutzen ( es könnte ja zB sein, dass ein Algo genau für Enspiele gut ist oder so ).

Wäre das so richtig verstanden?




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5521
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2018-10-17


Ich möchte an der Stelle erwähnen, dass das Spiel von den Regeln her viel Ähnlichkeit mit dem "Spiel der Amazonen" (kurz: "Amazons") hat. Dieses Spiel wurde 1988 vom Argentinier Walter Zamkauskas erfunden.

Während bei Isola die Figuren wie Schachkönige ziehen, ziehen die Amazonen wie Schachdamen [wie im Schach müssen alle zwischen Start und Ziel liegenden Felder frei sein]. Dafür dürfen sie anschließend nicht beliebige Felder blockieren, sondern nur solche, die sie mit einem weiteren Damenzug erreichen könnten.
Ein weiterer Unterschied ist die Brettgröße (10x10) und die Zahl der Amazonen auf jeder Seite (je 4).

Eine umfangreiche Arbeit über Endspielanalysen für das "Spiel der Amazonen" findet man
hier.

Außerdem hier noch ein Link zur Erklärung des Konzepts der kombinatorischen Spieltheorie. Bei einem Stein pro Spieler bringt die noch nicht sehr viel, aber wenn beide Spieler mehrere Steine haben, kommt sie dann voll zum Tragen.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2832
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.49, eingetragen 2018-10-17


Wenn es eine Spezifikation für Eingabe der Züge usw. gibt, würde ich mich -- sofern ich Zeit finde -- auch wieder mit einklinken und was basteln.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.50, eingetragen 2018-10-17


Hallo Gonz, ich hatte gerade einen längeren Text zusammengefasst und bin dann auf die Maustaste "zurück" gekommen. Damit war alles weg-.-
Dieses mal ohne erweiterten Vorschlag:
Mache erst einmal nur die Basisversion: Man kann mit einer eigenen KI gegen eine auf dem Server spielen und die Integration einer weiteren KI geht nur über Umwege wie Forum Mail oder PN.
Ansonsten steigt die Wahrscheinlichkeit, dass es nicht fertig wird. (Lässt sich nur empirisch beweisen, wenn überhaupt.)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.51, eingetragen 2018-10-18


Gekauft :)

Was das Timing bestrifft… Spätestens am Wochenende sollte das stehen.

*5

Gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.52, eingetragen 2018-10-21 11:50


Dummerweise habe ich gedacht, ich baue etwas, das beides kann, und hab erstmal die "falsche" Schnittstelle fertig gemacht. Nun gibt es ihn also - den "Isolator", und man kann über eine Socket/TCPIP Schnittstelle mit ihm sprechen, via 85.214-67.3 Port 8081 und TCPIP raw ( man nehme bspw. putty, um das Ganze zu erkunden ). Die Verbindung wird über die gesamte Partie ( und ggf. auch weitere Partien ) aufrecht erhalten.

Die Ausgaben sind eher lyrisch umwölkt, man kann triggern auf "OK" ( habs verstanden ), "HUCH" ( hier ist was schiefgegangen ) und "MEIN ZUG".

Die Kommandos, die verstanden werden, sind:

GO      Der Isolator soll als Weisser beginnen
A3 D4   Ziehe nach A3 und entferne den Stein auf D4
NEW     Neue Partie beginnen ( und damit ggf. aktuelle aufgegeben)
BYE     Verbindung beenden ( und damit ggf. aktuelle aufgegeben)

Wünsche für Änderungen am Protokoll etc. gerne gehört. Es soll dann auch eine Web-Schnittstelle geben, über die man Statistiken, gespielte Partien etc. ansehen kann :)

Vielleicht mag ja jemand... Ansonsten ist der nächste Plan ein Frontend zu bauen, in das man eigene Algorithmen in javascript einbinden kann.

Falls jemand Algorithmen in C schreiben will, kann ich die Maschinerie gerne multi-algorithmenfähig machen und diese mit einbinden/anbieten.

Auch auf den Algorithmus, nach dem der Isolator spielt, sollte ich noch was an Hirnschmalz verwenden, bisher ist es eher ein Dummy, der wenigstens nach den Regeln spielt * grins

Ich wünsche einen schönen Sonntag
Gerhard/Gonz







-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.53, eingetragen 2018-10-21 15:51


Hallo Gonz, ich habe damals in Netzwerktechnik leider nie hundertprozentig den Durchblick gehabt. Wenn ich das richtig verstanden habe, kann man mit seinem Browser keine tcpip Verbindung aufbauen. Also müsste man einen Umweg über einen Rest-Service o. ä. gehen. Hast du einen fertiges JavaEEprogramm, wo man sich das einmal ansehen kann? Oder bist du eher im .net Feld unterwegs und hast einen c# Service?
Oder hast du jetzt nur eine Consolenanwendung von Isola geschrieben?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.54, eingetragen 2018-10-21 15:56


Nein, ich habe auf einem Linux System in C einen Server geschrieben, der einen TCP Port aufmacht. Ein passendes Frontend fehlt noch. Dh ich bin gegenüber meiner aussage "am Wochenende schaff ich was weg" erstmal zurcückgeblieben. Das, was wir beiden an Schnittstellen angedacht haben, gibt es da (noch!) nicht.

Ich dachte aber ich geb schonmal nen Status, und ggf. will ja auch jemand auf diesen Zugang direkt aufspringen...


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.55, eingetragen 2018-10-25 11:29


Hallo tactac,

ich versuche deine Tabelle aus dem obigen Post #4 nachzuvollziehen. Irgendwie stimmt das nicht mit meinen Ergebnissen überein, schon bei 2x2 nicht.

Bei 2x2 müsste m.E. der Anziehende verlieren. Auf dem Feld gibt es für ihn zwei Zugmöglichkeiten, und danach muss er eines der Felder aufdecken. Damit verbleiben drei Felder, von denen auf je einem der weisse bzw. rote Spielstein steht. Der Spieler im Nachzug zieht nun auf das verbleibende  freie Feld und deckt das Feld, von dem er kommt, auf - der Anziehende hat keinen Zug mehr und verliert. In deiner Tabelle steht dort aber eine "1".

Ich lasse sonst mal mein Programm rechnen, ich kann ( wegen der Begrenzung des Speichers ) ziemlich genau dieselben Parameterwerte für die Spielfeldgrösse berechnen wie du in deiner Tabelle angegeben hast, also bis max. 7x3=21 Felder Grösse...


Beste Grüsse

Gerhard/Gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.56, eingetragen 2018-10-28 08:40


Guten Morgen liebe Freunde des Isola-Spiels :)

Eine Schnittstelle ( ausser eben einem Terminal ) habe ich immer noch nicht, aber ich habe jetzt einen recht guten Endspielhelfer implementiert. Und mit diesem gelingt es mir regelmäßig, gegen das Script von Kay zu gewinnen. Dabei muss ich allerdings (noch) die ersten Züge händisch spielen ( allerdings nach einem gewissen Algo ) und werfe dann im rechten Augenblick den "Nachbrenner" an. Ich möchte jetzt fast behaupten, dass man damit sogar zeigen könnte, dass ein Algorithmus zum weissen Gewinn auf dem normierten Brett existiert ( 8x6 mit den bekannten Startpositionen ).

Es bleibt spannend!

Jetzt, an diesem Sonntagmorgen, an dem ich vielleicht zum letzten Mal die Uhren umgestellt habe, ruft dann erstmal die Realwelt. Ich freue mich jedenfalls, hier endlich mal etwas neues mitteilen zu können!

Grüsse aus dem Oberharz (nass, kalt, wie immer)
Gerhard/gonz






-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.57, eingetragen 2018-10-28 09:00


Schön, dass du noch am Ball bleibst. Wie sieht dein Endspielhelfer aus? Hast du eine Datenbank mit "Sieg in 3 Zügen" hinterlegt und dein Programm versucht diese Stellung zu erreichen?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.58, eingetragen 2018-10-28 09:25


Das Programm kann für alle Positionen auf (Korrektur!) 5x4 oder 7x3 Ausschnitten den Gewinnweg ( wenn vorhanden ) in unter einer Minute wenigen Sekunden berechnen (*).

Ich versuche den Gegenspieler einzuschränken, um auf eine dieser berechenbaren Ausschnitte zu kommen, ja. Wobei ich das noch nicht auscodiert habe. Das Programm ist in C und hat aktuell eine eher rudimentäre Schnittstelle zur Eingabe der Stellung, die berechnet werden soll. Ich könnte das zB auch per URL Aufruf erreichbar machen, dann könnte man den Rest in Javascript herumbauen...


(*) Das könnte man natürlich auch abspeichern, es sind aktuell maximal

2^21 * 21^2

Positionen, für die jeweils der Zug gespeichert werden muss.


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1309
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.59, eingetragen 2018-10-28 22:00


Interessante Ergebnisse... smile
Ich werde in den nächsten Tagen mal versuchen, das Skript zu verbessern, ein paar Ideen habe ich ja noch. smile Momentan basiert es auf einer einfachen Suche mit statischer Bewertung. Weiterhin interessant ist auch, wie viel eine Alpha/Beta-Suche hier bringt (theoretisch die doppelte Tiefe, praktisch wohl deutlich weniger).

Kay



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.60, eingetragen 2018-10-30 08:32


Wir haben da gestern im Chat drüber gesprochen und es kam die Frage auf, ob es Sinn macht, für die Speicherung der berechneten Stellungen hash codes zu verwenden ( und damit die pro Stellung zu speichernde Datenmenge zu erhöhen, da ja dann die komplette Stellung gespeichert werden muss, aber die Anzahl der vorzuhaltenden Indices zu verringern ).

Ich habe deshalb mein Programm mal mitzählen lassen. Ich reserviere aktuelle einen Indexraum von 2^Feldzahl * Feldzahl^2 und speichere pro Index dann aber nur 8 Bit ( um unsigned char verwenden zu können, also auf Bytegrenze zu kommen, in Wirklichkeit brauche ich nur 3 Werte, nämlich "noch nicht bekannt", "gewonnen" oder "verloren".


Von diesen Indices wird beim Start auf einem ( bis auf die Majestäten ) leeren Spielfeld der Grösse 7x3 ca. 1/160 benutzt, wenn ich drei Felder bereits aufgedeckt habe, nur noch ca. 1/800.

Da ich eine Stellung ( für diesen Fall von 7x3) in einem 30 Bit breiten Wert unterbekomme, und dann noch eine Zeigerverkettung auf den nächsten Wert brauche, komme ich zB mit 16 Byte pro Tabelleneintrag aus. Das heisst der Speicherbedarf würde bei einem leeren Feld, also maximaler zu erwartenden Belegung der Tabelle, um den Faktor 10 sinken, bei einem etwas belegten Feld wie oben angesehen um den Faktor 50. Das lohnt sicherlich, allerdings ist damit nichts erreicht im Hinblick auf den Abstand, den wir noch zu einem 8x6 Feld haben.

Wobei ich noch einen kleinen Ansatz habe: Wenn man davon ausgeht, dass sich der König am Anfang in Richtung auf die Brettmitte bewegt, dh die Felder in dieser Richtung zuerst auf Gewinnmöglichkeiten prüft, und genauso mit dem Wegnehmen zuerst Felder in Richtung zur gegnerischen Majestät beginnt, spart man ca. noch einmal Faktor 10 ein ( da man früher auf einen Gewinnweg stößt )

Soweit... Was jetzt immer noch ansteht wäre mal ein Frontend für mein Programm zu bauen.

Grüsse
Gerhard/Gonz




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.61, eingetragen 2018-10-30 10:13


Ich habe mal eine mittlere KI hinzugefügt. Sie bewertet die Felder jetzt etwas anders und gewinnt zu ca. 66% gegen die leichte KI. Ich gehe davon aus, dass sie der KI von Kay_S noch unterlegen ist, aber manuelles Testen ist zu aufwendig. Man braucht ja mindestens 20 Matches, um halbwegs aussagekräftige Ergebnisse zu bekommen.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.62, eingetragen 2018-10-30 10:57


ja.. allerdings hat sie mein Programm dazu gebracht aufzugeben, weil irgendein teilalgorithmus meinte keinen zug mehr zu finden der gewinnen können... da muss ich nochmal ran :)

rein händisch kann ich gegen deine KI noch ganz gut gewinnen.


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.63, eingetragen 2018-10-31 20:54


Stimmt es, dass es fed-Code einblenden
fed-Code einblenden
gb an Speicher braucht, um alle Möglichen Stellungen abzuspeichern? Wenn eine Stellung genau ein zehntel kb Speicher in Anspruch nimmt.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.64, eingetragen 2018-10-31 22:16


Ja ich denke, aber ich habe ein bissl gemogelt. Benutzt man die Codierung die bei dir dahinter steht, also zB die durch die Majestäten belegten Felder in der Bitmap nicht vorhanden sind, braucht man für die Codierung des Index natürlich einen etwas aufwendigeren algo. Auch dass es nur 47 Positionen für die rote Queen gibt, da ja eine schon von der weissen belegt wird, habe ich nicht berücksichtigt. Deshalb komme ich vereinfacht eben auf

fed-Code einblenden

Da ich dann pro Spielstellung nur 2 Bit speichere ( um die Fälle unbekannt, gewonnen oder verloren zu unterscheiden ) brauche ich für ein Spielfeld von 25 Feldern 5 Gigabyte.

Leider steigt der Rechenaufwand dann erheblich an, sodass das Programm einige Tage an dem kompletten Baum rumrechnen wird.

Welcher Zug dann konkret der Gewinnzug ist kann man sich aus einem solchen Baum ja dann relativ leicht regenerieren.






-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.65, eingetragen 2018-10-31 23:06


Naja, man kann das Board natürlich auch mit 40 Booleans (belegt, nicht belegt) und zwei bytes für die Spielerpositionen kodieren.

Ich weiß nicht, wie du dann auf 5GB bei 25 Feldern kommst. Wenn ich richtig gerechnet habe, dann komme ich mit 96 bit für die gesamte Spielstellung aus. Bei den möglichen Kombinationen bezogen auf 25 Felder (5*5) sind das nach meiner Formel 5 033 164 800 Möglichkeiten. Auf MB gerechnet also *96/8/1024/1024 = 57600 mb = 56,25gb. Wo habe ich den Rechenfehler?

Edit: außer, dass ich mit 2 Bit für 1 Boolean gerechnet habe. Aber auch wenn ich die 56 gb halbiere komme ich nicht auf 5gb.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.66, eingetragen 2018-11-01 06:41


Ja der Beitrag war etwas verwirrend ( ich sollte nicht mehr abends grad noch vor dem zu-Bett gehen was posten lacht ).

Ausserdem ist mir jetzt natürlich klargeworden, dass es durchaus lohnt, den Faktor 4 einzusparen, indem man die beiden durch die Majestäten belegten Felder, die ja getrennt gespeichert sind, in der Bitmap einfach weglässt. Aber dazu unten mehr. Also ich rechne so, sei einfach mal n die Anzahl der Felder des Brettes, zB n=48 für unser Standardbrett.

fed-Code einblenden









-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.67, eingetragen 2018-11-01 18:28


Aber musst du nicht speichern, wie der nächste Zug aussehen soll? Mir ist jetzt klar geworden, dass ein Speichern des Spiels überflüssig ist, weil man einen Index in jedes beliebige Spielfeld transformieren kann. Welchen Nutzen hat ansonsten die Vorberechnung?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.68, eingetragen 2018-11-01 18:30


Wenn ich von jeder Stellung weiss, ob sie gewonnen ist oder nicht, dann brauche ich doch nur alle möglichen Züge durchgehen und gucken, ob die Stellung, auf die sie führen, für den Gegner eine Verluststellung ist. Den ersten Zug, der auf eine Verluststellung des Gegners führt, nehme ich dann halt. Das geht relativ schnell und erspart mir halt den Speicherplatz, den ich für einen kompletten zug gebraucht hätte.

Was ich damit nicht weiss (zugeb ) ist, wie schnell eine bestimmte Variante gewinnt, dh ich bekomme nicht die optimale gewinnstrategie, sondern nur "irgendeine". Andernfalls müsste ich die Zugzahl bis zum Gewinn ebenfalls noch abspeichern.


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 134
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.69, eingetragen 2018-11-01 18:48


Ok, dafür ich habe immer eine Funktion, die einen Zug bewertet genutzt. (Bewegungsfreiraum man selbst und Gegner) Du wertest den Zug also nicht aus, sondern machst "stupides" Backtracking. In Anführungszeichen, weil die Implementierung nicht trivial ist. Ich habe immer noch Probleme mir vorzustellen, wie das geht. Auch wenn ich weiß, dass ein Weg zur Lösung führt, dann kann ich den Weg doch nur beschreiten, wenn ab da alle Wege zum Sieg führen. Und man kann sich schlimmstenfalls selbst game over setzen.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2934
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.70, eingetragen 2018-11-02 09:03


Ja klar. ich glaube ich muss  meinem krams erstmal ne browserfähige Oberfläche verpassen, und dann sehen wir mal. ggf. können wir die algos ja dann gegeneinander spielen lassen, indem wir sie in iframes in einem fenster laufen lassen und dann per JavaScript die züge von einer seite auf die andere schaufeln. aber ich glaube das ist dann besser konkret zu besprechen wenns soweit ist :)


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle hat die Antworten auf ihre/seine Frage gesehen.
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]