|
Das deutsche QBasic- und FreeBASIC-Forum Fr euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
Vorheriges Thema anzeigen :: Nchstes Thema anzeigen |
Autor |
Nachricht |
Muttonhead
Anmeldungsdatum: 26.08.2008 Beitrge: 563 Wohnort: Jterbog
|
Verfasst am: 09.09.2015, 09:34 Titel: |
|
|
@nemored:
Wre denn von meinem Zeugs irgendwas bezglich Minimax zu gebrauchen? ein einfaches ja wrde gengen um mich mal damit intensiver auseinander zu setzen.
Mutton |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beitrge: 4599 Wohnort: ~/
|
Verfasst am: 09.09.2015, 12:25 Titel: |
|
|
Ganz ehrlich, ich habe es mir noch nicht angeschaut. Aber prinzipiell ist jede Bewertungsfunktion zunchst einmal fr Minimax brauchbar, und wenn sie dann doch nicht so taugt, kann man anschlieend an den Bewertungskriterien feilen. Der Minimax-Algorithmus drumherum ist davon dann unabhngig.
Vielleicht komme ich heute noch dazu, mir das anzusehen, dann sage ich Bescheid. _________________ Deine Chance betrgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Roland Chastain
Anmeldungsdatum: 05.12.2011 Beitrge: 192 Wohnort: Frankreich
|
|
Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008 Beitrge: 563 Wohnort: Jterbog
|
Verfasst am: 12.09.2015, 10:11 Titel: |
|
|
Die letzten vier Tage hab ich mir den Kopf zermartert wie das mit dem Minimax so funktionieren knnte... ich glaube mittlerweile eine Vorstellung zu haben:
Ich mache alle Zge bis zu einer bestimmten Tiefe, bewerte diese und nehme dann den "besten" der mir vom Gegenspieler brig gelassenen schlechten Zge.
Nur um meine Vorstellung weiter zu strapazieren:
Wenn ein Zug bedeuten wrde man knnte dem Gegner ein Stein klauen... Um herauszufinden welcher fehlende Stein den grten Schaden anrichtet, ist dann wohl wieder ein Suchbaum notwendendig, der wie eine zustzliche Wucherung herauswchst?
Mutton |
|
Nach oben |
|
|
ALWIM
Anmeldungsdatum: 08.08.2006 Beitrge: 1040 Wohnort: Niederbayern
|
Verfasst am: 12.09.2015, 13:49 Titel: |
|
|
Muttonhead hat Folgendes geschrieben: | Die letzten vier Tage hab ich mir den Kopf zermartert wie das mit dem Minimax so funktionieren knnte... ich glaube mittlerweile eine Vorstellung zu haben:
Ich mache alle Zge bis zu einer bestimmten Tiefe, bewerte diese und nehme dann den "besten" der mir vom Gegenspieler brig gelassenen schlechten Zge.
Nur um meine Vorstellung weiter zu strapazieren:
Wenn ein Zug bedeuten wrde man knnte dem Gegner ein Stein klauen... Um herauszufinden welcher fehlende Stein den grten Schaden anrichtet, ist dann wohl wieder ein Suchbaum notwendendig, der wie eine zustzliche Wucherung herauswchst?
Mutton |
Ich habe selber noch keine Idee, wie man das am besten machen knnte?
Mhle ist doch nicht so einfach wie ich gedacht habe. Habe mich aber die letzten paar Tage nicht mehr damit beschftigt. Muss mir das nochmal genauer ansehen. Was mir eben noch einfiel: Man knnte jeden mglichen Zug prfen ob dieser die Partie beendet. Sei es durch Zugunfhigkeit oder durch wegnehmen des drittletzten Steines.
Also fiktiv Zug ausfhren und Stellung auf Zugunfhigkeit prfen.
Zugunfhigkeit ist bei meinem Testprogramm ja bereits drin!
Letztens habe ich eine Schachdatenbankdatei mit dem Texteditor geffnet und so was hnliches wie das hier gesehen:
Welche Verschlselung steckt da dahinter? Man sieht lauter Vierecke! Und auch Leerzeichen sind in groer Menge vorhandenZuerst habe ich gedacht, was ist denn das? Nun wei ich aber, dass das verschlsselt wurde? Vielleicht hat das von euch schon einer mal irgendwo gesehen?
Edit:
Man sieht hier gar nichts? Ich habe leider kein Bild von der Textdatei!
Edit2: https://www.freebasic-portal.de/porticula/verschluesselung-txt-1811.html
Einfach die Datei downloaden und Inhalt als .txt speichern, dann sieht man was.
Gru
Alwim _________________ SHELL SHUTDOWN -s -t 05 |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beitrge: 4599 Wohnort: ~/
|
Verfasst am: 12.09.2015, 15:21 Titel: |
|
|
@ALWIM: Ich vermute stark, dass die Daten nicht verschlsselt sind, sondern einfach nur in einem platzsparenden binren Format gespeichert wurden. Eine Schachdatenbank in fr Menschen lesbarer Form zu speichern halte ich fr sehr ineffizient.
@Muttonhead und andere Minimax-Interessierte:
Mein Minimax-Gedankengang luft folgendermaen: Du machst rekursiv mehrere Zge mit wechselnder Spielerseite (die Tiefe der Suche ergibt dann die Strke der AI). Auf Ebene 1 fhrt man alle mglichen Zge nacheinander durch (und macht sie am Ende wieder rckgngig) und lsst dafr eine Antwort des Gegners berechnen (Ebene 2). Ebene 2 macht dasselbe: alle mglichen Zge durchfhren und einen Gegenzug dazu anfordern. An unterster Ebene wird dann lediglich das Spielbrett bewertet und an die nchsthhere Ebene zurckgegeben.
Aus allen Zgen innerhalb einer Ebene sucht sich der Computer denjenigen heraus, bei dem der Gegnerzug am schlechtesten abschneidet. Das sollte dann der beste Zug fr ihn sein, und diesen besten Wert gibt er an die nchsthhere Ebene zurck. Diese sucht sich auch wieder unter all diesen besten Werten denjenigen heraus, welcher der schlechteste ist; usw. Die Bewertungsfunktion selbst wird also nur auf unterster Ebene aufgerufen (da natrlich dann wegen der rekursiven Verzeigung sehr sehr hufig); alle anderen Ebenen "bewerten" anhand der Rckgabe der nchsttieferen Ebene.
An einem konkreten Beispiel bedeutet das: Wenn du einen Zug machen kannst, mit dem du den Gegner einsperrst, liefert dir die nchste Rekursionebene einen extrem schlechten Wert (Gegner hat verloren). Das wird dann wohl der schlechteste Wert unter allen anderen mglichen Zgen sein, weshalb du diesen Zug auswhlst und negativ zurckgibst (also einen sehr hohen positiven Wert: ich werde gewinnen). Die nchsthhere Ebene wird nun versuchen, diesen Zug, mit dem die tiefere Ebene einen so hohen Wert erreichen konnte, zu vermeiden, sprich: dort wird versucht, einen Zug zu machen, mit dem der Gegner nicht sofort gewinnen kann.
Ich habe im 2D-Spieleprogrammierbchlein einen Mini-Minimax-Algorithmus fr ein Nim-Spiel drin. Da es hier nur drei mgliche Bewertungssituationen gibt (gewonnen, verloren, ungewiss), ist die Bewertungsfunktion extrem einfach und wurde gleich in die Minimax-Prozedur eingebaut (wird aber trotzdem nur auf unterster Ebene verwendet). Das erste Mal mit Minimax beschftigt habe ich mich fr einen Programmierwettbewerb mit meinem Spiel Major; da habe ich aber schon seit Jahren nicht mehr reingeschaut, und das ist noch fr fbc v0.17. Mit -lang deprecated knnte es sich vielleicht copilieren lassen.
(Falls du den Highscore suchst, der funktioniert soweit ich wei nicht ...)
@Roland: Wirklich ein schnes Programm.
Ich habe schon eine ganze Weile nach einer guten und vielseitiger Mhle-Umsetzung fr Linux gesucht und nicht gesehen, dass ich dieses Programm in den Paketquellen habe. Nur die Berechnungstiefe muss ich krftig nach unten schrauben (oder nach oben? auf jeden Fall in Richtung einfach )
edit: fehlenden Link eingefgt _________________ Deine Chance betrgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.
Zuletzt bearbeitet von nemored am 12.09.2015, 19:48, insgesamt einmal bearbeitet |
|
Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008 Beitrge: 563 Wohnort: Jterbog
|
Verfasst am: 12.09.2015, 19:45 Titel: |
|
|
@nemored: weisst du wie verzweifelt man ist wenn man denkt man operiert mit
zwei Werten, einem Minimal und einem MaximalWert...
man bekommt es nicht zusammen
http://www.trinimon.de/Chess/ChessGame/Develop/chs_min.htm
der kleine Suchbaum und die Darstellung als Funktion min(,) und max(,) da hatte ich eine Eingebung.
|
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beitrge: 4599 Wohnort: ~/
|
Verfasst am: 12.09.2015, 19:55 Titel: |
|
|
Ich wurde eben darauf aufmerksam gemacht, dass mein Nim-Spiel-Link gar nicht drin steht; ich habe ihn jetzt oben ergnzt.
Ja, eigentlich arbeitest du nur mit einem Wert; der Minimalwert des Gegners ist der Maximalwert fr dich. Die grere Herausforderung besteht (neben einer guten Bewertungsfunktion) darin, die Suche schnell zu machen, indem man die Zge geschickt vorsortiert und die Rekursion frhzeitig abbricht, wenn das Ergebnis nicht mehr besser als das bisher beste werden kann. Das wre dann aber schon Alpha-Beta. _________________ Deine Chance betrgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
|
|
Du kannst keine Beitrge in dieses Forum schreiben. Du kannst auf Beitrge in diesem Forum nicht antworten. Du kannst deine Beitrge in diesem Forum nicht bearbeiten. Du kannst deine Beitrge in diesem Forum nicht lschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|