4 gewinnt

[mrhappiness]

servus,

bin grade dabei ein wunderhübsches 4 gewinnt Spiel zu prorammieren und hab mir die vorgehensweise so gedacht:

1. array mit spielfeld
   $board[spalte][zeile] spalte geht von 1 - 7 und zeile von 1 - 6
2. gewinnen, falls im nächsten zug möglich
3. prüfen, ob der gegner im nächsten zug gewinnen könnte

punkt 1 klappt
punkt 3 auch
punkt 2 auch (teilweise)
was mir noch sorgen bereitet ist ein schicker algorithmus, der berechnet wie ich gewinne *g*

was ich habe:
prüfen ob im nächsten zug gewonnen wird, und zwar horizontal, vertikal und diagonal (alle richtungen)

was ich noch bräuchte:
ein zeitschonender weg zwickmühlen oder ganz allgemein gewinnchancen u. ä. aufzubauen
momentan wird nämlich, so ich nicht im nächsten zug gewinne oder den sieg des gegners verhindern muss, einfach per zufall ein stein platziert und das ist ja nicht immer die optimale lösung

[Wurzel]

ich hab keine wirkliche idee (nur ne vision )

momentan hast du ein array => $board[spalte][zeile]

kannst du dies nicht erweitern auf
$board[spieler1][spalte][zeile]
$board[spieler2][spalte][zeile]
u.Umständen:
$board[gesamt][spalte][zeile]

und diese zwei/drei in relation bringen?

du hättest
- deine felder
- die felder des gegners
- alle belegten felder

array_diff liefert die freien felder
und 1-5 counts (unter berücksichtigung der freien) liefert dir den
höchsten wert deiner spielsteine. dazu kommt der nächste.

aber vielleicht ists auch zu spät für sowas (bei mir )

btw: hast du eigentlich nix besseres zu tun

[mrhappiness]

Original geschrieben von Wurzel
ich hab keine wirkliche idee (nur ne vision )

mir fehlt momentan sogar die

und 1-5 counts (unter berücksichtigung der freien) liefert dir den
höchsten wert deiner spielsteine. dazu kommt der nächste.

bitte was?

und das wäre dann meine strategie?

ich suche irgendwas, was bspw. die spalten 3, 4 und 5 belegt, dann hab ich ja nämlich gewonnen, falls in spalte 2 und spalte 6 noch nix is
und diese strategie(n) und das eruieren von möglichkeiten und das auswählenaus diesen is das, was mir momentan kopfzerbrechen bereitet

btw: hast du eigentlich nix besseres zu tun

freiwillig mach ich das bestimmt nicht...

[derHund]

naja,

vielleicht hilft das ja

Alpha-Abbruch

Sobald der provisorische Wert eines Min-Knotens kleiner oder gleich dem seines Max-Vorgängers wird, kann die Suche unterhalb dieses Min-Knotens beendet werden.

Beta-Abbruch

Sobald der provisorische Wert eines Max-Knotens größer oder gleich dem seines Min-Vorgängers wird, kann die Suche unterhalb dieses Max-Knotens beendet werden.

quelle: http://www.mathematik.de/spurenderma...ege/vorberger/

klingt sehr interessant, ist aber eher für ki-einsteiger, und auch nicht auf 4 gewinnt bezogen.

[MelloPie]

einen algorithmus zu finden wird schwer sein du solltest die verschiedenen felder mit prioritäten für die jeweilige farbe versehen.
Es gibt bestimmte felder, die sind für gelb wertvoll und manche für rot.
Das ganze könnte noch in abhängigkeit der Eröffnung stehen.

[derHund]

also,

ansatz für die ki:

- für alle besetzbaren felder 'wertigkeit' bestimmen

wertigkeit ist dabei ein wert, der angibt, wie hoch die change ist, einen sieg zu erringen, wenn dieses feld im nächsten zug besetzt wird

- auf das feld mit der höchsten wertigkeit setzen
- das wars schon

berechnung der wertigkeit:

positive werte für
- 2 gleiche steine und 2 mögliche +0.3
- 3 gleiche steine und 1 mögliche +0.7
- 4 gleiche steine +1.2
- etc ... zb. zwickmühlen ...

negative werte für den gegner
- 2 gleiche steine und 2 mögliche -0.3
- 3 gleiche steine und 1 mögliche -0.7
- 4 gleiche steine -1.2
- etc ...

von diesen regeln wird wohl viel abhängen ...

die wertigkeit ergibt sich dann aus der vorausberechnung aller nächsten züge, wobei jeweils die max/min-werte werte zurück bis zum ausgangsfeld gereicht werden und damit seinen wert bestimmen.

der rest hängt an der suchtiefe und an den regeln.

so hab ichs zumindest verstanden.

vielleicht ließe sich noch ein algorhytmus finden, der bei bestimmten vorbedingungen die suchtiefe variiert. durch das alpha/beta-pruning spart man vielleicht nochmal ein wenig rechenzeit ...

so wird ich rangehn. ich glaub, ich werd das demnächst mal umsetzen.

als overkill könnte man den algorhytmus noch so erweitern, daß er mit der zeit lernt, wie er bestimmte stellungen zu bewerten hat ...

usw

[mrhappiness]

mein algorithmus sieht momentan so aus, aber es tut nicht so wie ich es gern hätte. sieht da jemand spontan meinen großen dummen fehler oder muss ich mir evaluate() vornehmen?

function best_move($board=NULL, $player=SELF, $depth=5)
{
  if (!isset($board))
    $board=$this->board;
  if ($depth>0)
    for ($col=1; $col<=COLUMNS; $col++)
      if ($this->move_allowed($col, $board))
      {
        $this->move($col, $player, $board);
        $value=$this->best_move($board, ((PLAYER==SELF) ? OPPONENT : SELF), --$depth);
        if ($player==SELF and $value > $this->eval['value'])
        {
          $this->eval['value']=$value;
          $this->eval['col']=$col;
        }
        if ($player==OPPONENT and $value < $this->eval['value'])
        {
          $this->eval['value']=$value;
          $this->eval['col']=$col;
        }
      }
  else
    return $this->evaluate($board, $player);
} 

[derHund]

aber es tut nicht so wie ich es gern hätte. sieht da jemand spontan meinen großen dummen fehler

        if ($player==SELF and $value > $this->eval['value'])
        {
          $this->eval['value']=$value;
          $this->eval['col']=$col;
        }
        if ($player==OPPONENT and $value < $this->eval['value'])
        {
          $this->eval['value']=$value;
          $this->eval['col']=$col;
        }
      } 

so wie ich den code verstehe, bestimmst du das feld/den wert, der in allen rekursionsebenen der größste/kleinste ist, speicherst dann spalte und wert?

du müßtest afaik aber vielmehr pro rekusionsebene den min/max-wert bestimmen, den zurückgeben, in der nächsten ebene wieder den max/min-wert usw. so daß du dann in der ersten ebene die spalte bestimmen kannst, ... dh. für mich auch, daß in den inneren ebenen die spalte irrelevant ist, da sie sich ja auf die späteren züge bezieht. einzig der wert sollte zurückgegeben werden und nach beendigung der rek. sollte dann gesetzt werden.

ich weis aber nicht, ob ich richtig verstanden habe, was du mit $this->eval bezweckst ... und ob ich das prinzip überhaupt richtig kapiert hab.

du kannst gern mal die auswertungs-routine zeigen, es würde mich interessieren, welche sttellungen du wie bewertest ...

OffTopic:

---

ich bastel auch grad anner ki, 'nur' fürs tictactoe, läuft aber ähnlich, ... ahh, rekusion bringt mich um, dabei ists so einfach

---

[mrhappiness]

Original geschrieben von derHund
so wie ich den code verstehe, bestimmst du das feld/den wert, der in allen rekursionsebenen der größste/kleinste ist, speicherst dann spalte und wert?

so hatte ich das vor

du müßtest afaik aber vielmehr pro rekusionsebene den min/max-wert bestimmen, den zurückgeben, in der nächsten ebene wieder den max/min-wert usw. so daß du dann in der ersten ebene die spalte bestimmen kannst

also noch ein return $value; ?

dh. für mich auch, daß in den inneren ebenen die spalte irrelevant ist,

und woher weiß ich, dass ich in einer inneren ebene bin (die tiefe soll ja variabel sein)?

einzig der wert sollte zurückgegeben werden und nach beendigung der rek. sollte dann gesetzt werden.

und woher weiß ich nach beendigung der rekursion zu welcher spalte das gehört?

ich weis aber nicht, ob ich richtig verstanden habe, was du mit $this->eval bezweckst

ich speichere den momentan gefundenen besten wert und die dazugehörige spalte

du kannst gern mal die auswertungs-routine zeigen, es würde mich interessieren, welche sttellungen du wie bewertest

ich zähle einfach nur, wieviel 4er, 3er und 2er der gegenspieler bzw. ich habe und multipliziere das mit (-)900, (-)300 und (-)100 (negativ wenn $player == OPPONENT)

[derHund]

also,

und woher weiß ich, dass ich in einer inneren ebene bin (die tiefe soll ja variabel sein)?

ja, du hast recht. die spalte muß gespeichert werden. (ups, falsches zitat)

also noch ein return $value; ?

ja, weil die splate nur im letzten zug für dich wichtig ist, der wert aber in jeder ebene zurückgegeben werden muß

wie behandelst du folgende problematik: angenommen, die zweite spalte führt nach 7 zügen zum gewinn, die vierte nach 1 zug. beide spalten würden also in der ersten ebene den höchsten wert liefern. da man aber nicht weiß, welcher sieg schneller zu erreichen ist, würde man nur manchmal den richtigen wählen. man müßte also die tiefe irgendwie in die bewertung einfließen lassen, ... oder nicht?

ein weiteres problem ist dann, sicherzustellen, daß ein sieg in 10 zügen mehr wiegt als drei steine nebeneinander, aber ohne möglichkeit auf einen vierten in 4 zügen. usw.

ich muß es mal niederschreiben:

best_move() {
// bei erreichen eines sieges, eines unentschieden oder 
// der rekursionstiefe wird die stellung bewertet und zurückgegeben
//sonst wird die beste stelle für den nächsten stein bestimmt.
  if (setzen_möglich && ebene > 0 && !gewonnen()) {
    für alle möglichen spalten {
      stein_setzen();
      array_push($array, best_move(-player))
      board_reset; // !wichtig! imho
    }
    beste_spalte_global_speichern();
    return max($array);
  }
  sonst return stellung_bewerten ();
}

ich glaub, so gehts. ich werds gleich mal testen.

ich zähle einfach nur, wieviel 4er, 3er und 2er der gegenspieler bzw. ich habe und multipliziere das mit (-)900, (-)300 und (-)100 (negativ wenn $player == OPPONENT)

ok, sollte ja für den anfang reichen, läßt sich sicher drüber diskutieren, ob man mehr regeln benutzt, und zur zeitersparnis eine rek-ebene wegläßt, oder nur wenig regeln, und damit mehr tiefe. vielleicht sollte man auch nur die 2er und 3er werten, die erstens die möglichkeit bieten, 4er zu werden und das zweitens in relations zur anzahl der züge, die benötigt werden.

wie lange rechnest du bei tiefe 5?

meine tictactoe-ki braucht für den ersten zug mehr als 30sec. auf nem 500mhz rechner. darum wird auch erst ab dem dritten zug gerechnet.

ich werd mal schauen, ob mein gedankenmodell von oben funktioniert.

[derHund]

also,

function best_move($board=NULL, $player=SELF, $depth=5)
{
    $value=$this->best_move($board, ((PLAYER==SELF) ? OPPONENT : SELF), --$depth);
} 

da ist der fehler! wenn du --$depth übergibst, hast du im nächsten schleifendurchlauf die falsche ebene, du mußt $depth - 1 übergeben.

[derHund]

also,

der algorithmus, so wie ich ihn skizziert habe, funktioneirt (scheinbar) bei mir jetzt. zumindest hab ich noch nicht gewonnen.
er ließe sich eigentlich ohne umbauten auch für das 4 gewinnt einsetzen.

zwickmühlen erkennst du u.a. folgendermaßen:

sollte bei den max/min-werten mehr als einmal der wert für sieg auftauchen, hast du ne zwickmühle, oder? wenn man jetzt die anzahl der zwickmühlen mit dem wert für sieg multipliziert, und das zurückgibt, kann man das dem algo auch klarmachen. da tritt nur wieder das problem auf, daß gleiche stellungen eigentlich auf unterschiedlichen leveln unterschiedliche bewertungen erhalten sollten.

man sollte daß dann auch so erweitern, daß generell bei mehreren gleichen max-werten ein höherer wert zurückgegeben wird, ...

damit sollte der algo zumindest mehr in richtung zwickmühle als einfache reihe tendieren.

naja, ich bastel mir jetzt erstmal nen 4-gewinnt-board und teste mal.

wie gesagt, die bewertungen sind wohl das wichtigste an der sache - und dafür braucht man spiel-erfahrung.

[mrhappiness]

ich häng einfach mal meine komplette klasse an, da hast du meine kleine bewertungsfunktion und siehst eventuell noch den denkfehler den ich mache

die bewertungsfunktion erkennt 4er, zwickmühlen, 3er mit freiem platz links oder rechts oder mittendrin, 2er mit 3 freien plätzen und einfach jeden stein

[derHund]

also,

ich häng einfach mal meine komplette klasse an, da hast du meine kleine bewertungsfunktion und siehst eventuell noch den denkfehler den ich mache

puh, das muß ich erstmal verdauen.. du hast ja sogar den alpha/beta-abbruch mit drin ... und phpdoc.

ähm, was geht denn eigentlich nicht? ich nehme an, du hast die bewertungsroutine an verschiedenen situationen getestet und die hat dann auch so reagiert, wie sie sollte?

oder nicht?

[mrhappiness]

Original geschrieben von derHund
puh, das muß ich erstmal verdauen

ein klarer zum magen aufräumen? *g*

du hast ja sogar den alpha/beta-abbruch mit drin ... und phpdoc.

wenn schon, denn schon

ich nehme an, du hast die bewertungsroutine an verschiedenen situationen getestet und die hat dann auch so reagiert, wie sie sollte?

naja, nicht ganz, teilweise hat sie ganz komisch gezogen, aber da ich bei dem spiel immer verloren hab, kann das auch an mir liegen

naja, hab das mal "kurz" umgekrempelt und hardcore-objektorientiert mit klase game klasse board, klasse player (unterklassen computer, opponent [relevant für meinen speziellen zweck], klasse humanplayer kommt noch) und es geht einigermaßen vernünftig, wenn da die lange berechnungsdauer nicht wäre...