4 gewinnt: finden v. 2er-/3er-/4er-reihen u. bewertung einer spielfeldsituation
-
hallo,
ich weiss, dass ueber das thema 4 gewinnt, minimax, alpha-beta-suche usw. usf. einiges hier im forum und auch via google zu finden ist, allerdings tu ich mich wirklich schwer damit, eine gegebene konstellation von spielsteinen auf dem feld zu "erfassen" (wieviele 2er-/3er-/4er-reihen?) und bewerten, und dazu habe ich noch nichts wirklich hilfreiches gefunden.
wenn ich von jedem stein aus alle moeglichen reihen, in denen er liegen koennte, checke, werden u.u. reihen mehrfach gezaehlt.
wenn ich nur bis max. 4 steine in einer reihe pruefe, werden, auch wenn ich pruefe, ob eine erkannte reihe schon einmal erkannt wurde, bspw. 5er-reihen ggf. als mehrere 4er-reihen erkannt.
ist es also wirklich noetig, fuer jeden stein die horizontale und vertikale, sowie 1 oder 2 diagonale reihen komplett zu pruefen?
oder gibt es einen ganz anderen, sinnvolleren und evtl. performanteren ansatz?ich denke, wenn ich alle 2er- und 3er-reihen haette, koennte ich daraus schon etwas mehr machen, hinsichtlich der bewertung ...
danke im voraus fuer jede hilfe!
mfg,
julian
-
ok, ich habe es jetzt einmal so gemacht:
- alle 2er- bis 7er-reihen erkennen/speichern (damit keine reihe mehrfach gezaehlt wird)
- dann alle 4er- bis 7er-reihen zusammenfassen ("gewinnreihen")
- (das alles geordet nach spieler 1/2)zur bewertung eines spielfelds:
- wert jeder reihe: anzahl d. steine + anzahl d. "offenen enden" (hier koennte angebaut werden" + anzahl d. "offenen enden", an denen direkt im nexten zug angebaut werden koennte (sprich, eine reihe drunter liegt schon ein stein)
- fuer jeden spieler dann die werte aller reihen addiert
- wert fuer einen best. spieler: eigenerWert - gegnerischerWertdas ganze habe ich dann in einem minimax-algorithmus verwendet, und das ergebnis ueberzeugt nicht wirklich ...
macht diese bewertung ueberhaupt sinn? langsam verzweifle ich daran ...
mfg,
julian
-
Ich habs so gemacht dass ist alle Reihen durchgehe, und schaue ob es 3er Kombinationen gibt, wenn ja Bewertung um einen gewissen Wert rauf/runter, je nachdem wer der beiden Spieler der Besitzer der 3er Kombination ist. Bei 4er Kombinationen ist das Spiel eh gelaufen und ich setze die Bewertung entweder auf SPIEL_GEWONNEN bzw. SPIEL_VERLOREN.
Ich glaub der Ansatz ist klar, oder?Nun kannst du das gleiche mit den Spalten und mit den Diagonalen machen.
Damit hat man eine durchaus vernünftige KI bereits bei Baumtiefe 3, ich mein, verbesserbar ist sie natürlich immer noch.
Wenn gewünscht kann ich natürlich auch den entsprechenden Codeteil posten.
-
hi,
das sollte von der bewertung her ja in etwa mein ansatz sein.
ich pruefe halt alle reihen von 2, 3 oder 4 und mehr steinen und je die bewertung wird halt hoch-/runtergesetzt um die anzahl der steine (2 bis 4), addiert mit der anzahl der offenen enden (0 bis 2) und der anzahl derjenigen enden, an denen direkt im nexten zug angebaut werden kann (0 bis 2).mfg,
julian
-
Gibts hier vielleicht noch was hilfreiches: http://www.developia.de/forum/viewtopic.php?t=125274 ? f'`8k
Gruß, TGGC (Der neue Game Star)
-
vielen dank TGGC.
ich werds morgen gruendlich lesen, bin jetzt zu muede.
soweit ich das eben gesehen hab, geht es da um die optimierung der spielfeldchecks, aber das waere die nexte massnahme, wenn denn erstmal die doofe zugbewertung funktioniert ...mfg,
julian
-
http://www.ke.informatik.tu-darmstadt.de/lehre/bachelorarbeiten/2006/Baier_Hendrik.pdf
In diesem Artikel solltest du unter Evaluierung etwas interessantes finden. Ist zwar nicht sooo elegant, aber damit kriegt man schon eine ganz gute Bewertung hin...
EDIT: Vorrausgesetzt dein Programm kann tief genug Rechnen 16 Halbzüge+
-
Noch was: Bei der Bewertung kommt es sehr stark auf die Konstellation der Drohungen an. Ein Tutorial von Martin Fierz beschreibt das sehr gut:
http://www.fierz.ch/4tutorial.htm
