Entwickler-Ecke
Sonstiges (Delphi) - tictactoe - bewertungsfunktion für ki
F34r0fTh3D4rk - Mo 24.04.06 16:37
Titel: tictactoe - bewertungsfunktion für ki
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:
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; |
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- - Mo 24.04.06 16:40
Wieso machst du das nicht 2 dimensional?
Dann hast es kürzer, übersichtlicher und einfacher
F34r0fTh3D4rk - 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 - Mo 24.04.06 17:24
Ist jetzt auch nicht kürzer, sieht aber nicht ganz so amateurhaft aus ;-) (ungetestet)
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;
const mask : array [0..7] of integer = (7,56,448,73,146,292,273,84);
var i : integer;
value : integer;
begin
Result := false;
value:=0;
for i:=1 to 9 do Inc(value,Ord(aField[i]=aCheckFor) shl (i-1));
for i:=0 to 7 do
if (value and mask[i])<>0 then
begin
Result:=true;
exit;
end;
end; |
F34r0fTh3D4rk - Mo 24.04.06 18:26
das problem ist ja, dass ich eine bewertungsfunktion für den
MINIMAX-ALGORITHMUS schreiben muss, deshalb dachte ich daran, die plättchen zu bewerten, also
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 - Mi 26.04.06 00:21
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 - 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.
F34r0fTh3D4rk - 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:
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 ;)
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!