tictactoe - bewertungsfunktion für ki

F34r0fTh3D4rk · Verfasst: Mo 24.04.06 16:37

hi, ich habe gerade eine kleinigkeit vor, bei der ich berechnen muss, wie oft ein spieler bei tictactoe 2 in einer reihe hat und da hakts, denn ich möchte nicht werweißwieviele abfragen machen, meine siegbedingung sieht schon so aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

function TForm1.gwinner: TSpieler;
begin
  result := keiner;
  if ((felder[1] = rot) and (felder[2] = rot) and (felder[3] = rot)) or
     ((felder[4] = rot) and (felder[5] = rot) and (felder[6] = rot)) or
     ((felder[7] = rot) and (felder[8] = rot) and (felder[9] = rot)) or
     ((felder[1] = rot) and (felder[4] = rot) and (felder[7] = rot)) or
     ((felder[2] = rot) and (felder[5] = rot) and (felder[8] = rot)) or
     ((felder[3] = rot) and (felder[6] = rot) and (felder[9] = rot)) or
     ((felder[1] = rot) and (felder[5] = rot) and (felder[9] = rot)) or
     ((felder[3] = rot) and (felder[5] = rot) and (felder[7] = rot)) then
       result := mensch;
  if ((felder[1] = blau) and (felder[2] = blau) and (felder[3] = blau)) or
     ((felder[4] = blau) and (felder[5] = blau) and (felder[6] = blau)) or
     ((felder[7] = blau) and (felder[8] = blau) and (felder[9] = blau)) or
     ((felder[1] = blau) and (felder[4] = blau) and (felder[7] = blau)) or
     ((felder[2] = blau) and (felder[5] = blau) and (felder[8] = blau)) or
     ((felder[3] = blau) and (felder[6] = blau) and (felder[9] = blau)) or
     ((felder[1] = blau) and (felder[5] = blau) and (felder[9] = blau)) or
     ((felder[3] = blau) and (felder[5] = blau) and (felder[7] = blau)) then
       result := maschine;
end;

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

type
  TSpieler = (keiner, mensch, maschine);
  TFeld = (nix, rot, blau);
{...}
var
  spieler: TSpieler;
  felder: array[1..9] of TFeld;

wie kann ich das abkürzen und wie bekomme ich möglichst kurz die anzahl der 2 in einer reihe befindenlichen heraus ?

das ziel ist eine bewertungsfunktion für einen minimax algo

danke schonmal

Sy- · Beiträge: 177

Wieso machst du das nicht 2 dimensional?
Dann hast es kürzer, übersichtlicher und einfacher

F34r0fTh3D4rk · Verfasst: Mo 24.04.06 17:00

viel bringen tut mir das auch nicht, ich muss sämtlicher 1er und 2er reihen der beiden spieler zählen, und das möglichst kurz und performant, mit nem 2d array wäre das auch möglich, aber ich weiß selbst dann nicht wie :lol:

Spaceguide · Beiträge: 552 (D3/D7/D8) Prof.

Ist jetzt auch nicht kürzer, sieht aber nicht ganz so amateurhaft aus ;-)

(ungetestet)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

type
 TTicTacToeState = (leer,rot,blau);
 TTicTacToeField = array [1..9] of TTicTacToeState;

function IsWin(const aField : TTicTacToeField; aCheckFor : TTicTacToeState) : boolean;
 {111 000 000 100 010 001 100 001
  000 111 000 100 010 001 010 010
  000 000 111 100 010 001 001 100
 }
 const mask : array [0..7] of integer = (7,56,448,73,146,292,273,84);
 var i : integer;
     value : integer;
begin
 Result := false;

 //feld in bit-codierten integer umwandeln
 value:=0;
 for i:=1 to 9 do Inc(value,Ord(aField[i]=aCheckFor) shl (i-1));

 //auf maske prüfen
 for i:=0 to 7 do
 if (value and mask[i])<>0 then
 begin
  Result:=true;
  exit;
 end;
end;

F34r0fTh3D4rk · Verfasst: Mo 24.04.06 18:26

das problem ist ja, dass ich eine bewertungsfunktion für den Suche in Wikipedia

MINIMAX-ALGORITHMUS schreiben muss, deshalb dachte ich daran, die plättchen zu bewerten, also

markieren

Quelltext

1:
2:
3:

1 plättchen alleinstehend = +1
2 plättchen nebeneinander = +2
3 (also gewonnen)         = +3

naja so richtig funzen tut das net, vielleicht hat hier jemand schonmal etwas in der richtung mit der ki (minimax oder alphabeta) gemacht, das wäre natürlich hilfreich, google hab ich schon mehrmals durch.

Yamato · Hält's aus hier Beiträge: 3

Was mich wundert, ist die Frage nach der Bewertungsfunktion. Bei einem Spiel wie TicTacToe expandiert der MiniMax-Algorithmus den gesamten Suchbaum im Bruchteil einer Sekunde (es kann ja eigentlich höchstens 9! = 362880 Spielverläufe geben). D. h. in den Endstellungen kann man direkt mit Gewinn/Verlust/Remis bewerten.
Eine heuristische Bewertungsfunktion braucht man nur bei Spielen, bei denen man nicht bis zur maximalen Tiefe (= Endposition) rechnen kann (z. B. Schach etc.), da der Suchbaum zu groß ist.

alzaimar · Verfasst: Mi 26.04.06 08:31

Eine Bewertungsfunktion soll doch die Stellung numerisch so darstellen, das eine Gewinnsituation eindeutig erkannt wird.
Allgemein würde ich es so definieren:

Stellung (Brett, Spieler, Gegner) = (BS - BG)
Wobei BS die Bewertung der Stellung für den Spieler, und BG die Bewertung für den Gegner darstellt. In der klassischen Spieleprogrammierung wird aus Uniformitätsgründen vorgeschlagen, die Stellung so zu definieren:
S = (BS - BG) / (BS + BG)
Damit liegt der Wertebereich der Funktion zwischen -1 und 1: Stellungen sind dann direkt vergleichbar. Ich hab das nie gebraucht.

Nehmen wir an, Dein Brett sieht so aus:
X X -
X X O
O O -

Wenn man einfach die 2er zählt, dann könnte man für den ersten 2er einen Punkt vergeben und für jeden weiteren 1000, denn wer 2 offene 2er hat, der hat ja gewonnen, oder? Nee:
- X X
X O -
X O -

'X' hat zwei offene zweier, aber nicht automatisch gewonnen. 'O' setzt einen Stein in die linke obere Ecke und -patt-. Also könnte man es so versuchen:
Ein Punkt für den ersten 2er, 1000 Punkte für jeden weiteren 2er, *dessen offenes Ende nicht mit einem bereits gefundenen 2er identisch ist*.

Wie yamato schon bemekrt hat, reicht es jedoch, die Stellungsfunktion auf das 'Gewinnen' zu reduzieren, denn der Spielbaum wird vollständig durchsucht.

Stellung (Brett, Spieler, Gegner) = Wenn Spieler-gewonnen dann '1' Wenn Gegner-gewonnen dann '-1' sonst '0'

Die maximale Vorschautiefe ist dann 9.

Klar ist Tic-Tac-Toe nicht geeignet, eine gute Stellungsfunktion zu implementieren: Der Aufwand ist recht hoch. Dafür eignet es sich jedoch sehr für die Analyse des Minimax- und/oder Alpha-Beta-Pruning. Diese Algorithmen sind für alle Nullsummenspiele identisch und wer es mit Tic-Tac-Toe hinbekommt, der schafft es auch mit Schach. A-B-Pruning reduziert die Anzahl der zu durchsuchenden Spielstellungen drastisch (von X^n auf log (X^n)).

Das Problem reduziert sich dann darauf, eine gute Stellungsfunktion zu finden: Sie repräsentiert ja das Wissen über die Taktik.

_________________
Na denn, dann. Bis dann, denn.

F34r0fTh3D4rk · Verfasst: Mi 26.04.06 15:37

dann hab ich das mit dem minimax algo nicht verstanden, denn der funktioniert bei mir nur optimal, wenn der spieler auch optimal spielt, alternativ habe ich den hier:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

  procedure nextbest;
  var
    i, curr, mini: integer;
  begin
    mini := maxint;
    for i := 1 to 9 do
      if felder[i] = nix then
      begin
        felder[i] := blau;
        curr := bewertung;
        if curr < mini then
        begin
          mini := curr;
          nextone := i;
        end;
        felder[i] := nix;
      end;
  end;

der aber auch leicht zu schlagen ist.

wie mache ich eine perfekte ki für XXO ?

meine bewertung macht schon sinn, denn der algo soll ja in der nächsten runde eine möglichst hohe punktzahl erreichen, das wäre bei gewonnen (maxint) ansonsten funzt das recht gut, ich hab das mit einigen beispielen durchgerechnet und eigentlich muss es funzen, aber ich gebe nicht auf

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme