Das deutsche QBasic- und FreeBASIC-Forum

[Muttonhead]

@nemored:
Wäre denn von meinem Zeugs irgendwas bezüglich Minimax zu gebrauchen? ein einfaches ja würde genügen um mich mal damit intensiver auseinander zu setzen.


Mutton

[nemored]

Ganz ehrlich, ich habe es mir noch nicht angeschaut. Aber prinzipiell ist jede Bewertungsfunktion zunächst einmal für Minimax brauchbar, und wenn sie dann doch nicht so taugt, kann man anschließend an den Bewertungskriterien feilen. Der Minimax-Algorithmus drumherum ist davon dann unabhängig.

Vielleicht komme ich heute noch dazu, mir das anzusehen, dann sage ich Bescheid.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

-----

"Das wissen doch sowieso nur Nerdinauten, die Schlaumeierologie studiert haben." - coldmirror

[Roland Chastain]

Hallo!

Ein hübsch Programm hier:

http://nine-mens-morris.net/

[Muttonhead]

Die letzten vier Tage hab ich mir den Kopf zermartert wie das mit dem Minimax so funktionieren könnte... ich glaube mittlerweile eine Vorstellung zu haben:
Ich mache alle Züge bis zu einer bestimmten Tiefe, bewerte diese und nehme dann den "besten" der mir vom Gegenspieler übrig gelassenen schlechten Züge.

Nur um meine Vorstellung weiter zu strapazieren:
Wenn ein Zug bedeuten würde man könnte dem Gegner ein Stein klauen... Um herauszufinden welcher fehlende Stein den größten Schaden anrichtet, ist dann wohl wieder ein Suchbaum notwendendig, der wie eine zusätzliche Wucherung herauswächst?

Mutton

[ALWIM]

[nemored]

@ALWIM: Ich vermute stark, dass die Daten nicht verschlüsselt sind, sondern einfach nur in einem platzsparenden binären Format gespeichert wurden. Eine Schachdatenbank in für Menschen lesbarer Form zu speichern halte ich für sehr ineffizient.

@Muttonhead und andere Minimax-Interessierte:
Mein Minimax-Gedankengang läuft folgendermaßen: Du machst rekursiv mehrere Züge mit wechselnder Spielerseite (die Tiefe der Suche ergibt dann die Stärke der AI). Auf Ebene 1 führt man alle möglichen Züge nacheinander durch (und macht sie am Ende wieder rückgängig) und lässt dafür eine Antwort des Gegners berechnen (Ebene 2). Ebene 2 macht dasselbe: alle möglichen Züge durchführen und einen Gegenzug dazu anfordern. An unterster Ebene wird dann lediglich das Spielbrett bewertet und an die nächsthöhere Ebene zurückgegeben.

Aus allen Zügen innerhalb einer Ebene sucht sich der Computer denjenigen heraus, bei dem der Gegnerzug am schlechtesten abschneidet. Das sollte dann der beste Zug für ihn sein, und diesen besten Wert gibt er an die nächsthöhere Ebene zurück. 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 natürlich dann wegen der rekursiven Verzeigung sehr sehr häufig); alle anderen Ebenen "bewerten" anhand der Rückgabe der nächsttieferen Ebene.

An einem konkreten Beispiel bedeutet das: Wenn du einen Zug machen kannst, mit dem du den Gegner einsperrst, liefert dir die nächste Rekursionebene einen extrem schlechten Wert (Gegner hat verloren). Das wird dann wohl der schlechteste Wert unter allen anderen möglichen Zügen sein, weshalb du diesen Zug auswählst und negativ zurückgibst (also einen sehr hohen positiven Wert: ich werde gewinnen). Die nächsthöhere 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-Spieleprogrammierbüchlein einen Mini-Minimax-Algorithmus für ein Nim-Spiel drin. Da es hier nur drei mögliche 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 beschäftigt habe ich mich für einen Programmierwettbewerb mit meinem Spiel Major; da habe ich aber schon seit Jahren nicht mehr reingeschaut, und das ist noch für fbc v0.17. Mit -lang deprecated könnte es sich vielleicht copilieren lassen.
(Falls du den Highscore suchst, der funktioniert soweit ich weiß nicht ...)

@Roland: Wirklich ein schönes Programm.
Ich habe schon eine ganze Weile nach einer guten und vielseitiger Mühle-Umsetzung für Linux gesucht und nicht gesehen, dass ich dieses Programm in den Paketquellen habe. Nur die Berechnungstiefe muss ich kräftig nach unten schrauben (oder nach oben? auf jeden Fall in Richtung einfach )


edit: fehlenden Link eingefügt
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

-----

"Das wissen doch sowieso nur Nerdinauten, die Schlaumeierologie studiert haben." - coldmirror

[Muttonhead]

@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.

[nemored]

Ich wurde eben darauf aufmerksam gemacht, dass mein Nim-Spiel-Link gar nicht drin steht; ich habe ihn jetzt oben ergänzt.

Ja, eigentlich arbeitest du nur mit einem Wert; der Minimalwert des Gegners ist der Maximalwert für dich. Die größere Herausforderung besteht (neben einer guten Bewertungsfunktion) darin, die Suche schnell zu machen, indem man die Züge geschickt vorsortiert und die Rekursion frühzeitig abbricht, wenn das Ergebnis nicht mehr besser als das bisher beste werden kann. Das wäre dann aber schon Alpha-Beta.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

-----

"Das wissen doch sowieso nur Nerdinauten, die Schlaumeierologie studiert haben." - coldmirror