Entwickler-Ecke

Algorithmen, Optimierung und Assembler - vier gewinnt KI


feuerodem - Di 16.12.08 14:37
Titel: vier gewinnt KI
Hi Leute

habe mich grade angemeldet, denn sonst habe ich alles immer über die Suchfunktion gefunden ! - Alles Top hier -

zu meinem Problem:

Ich habe mich an ein Vier Gewinnt gesetzt. Es war recht einfach Mensch gegen Mensch zu programmieren, für die Kästchen habe ich einen Stringgrid genommen.
Doch nun habe ich versucht eine KI zu schreiben, doch die ist wohl noch etwas zu schwierig für mich (bin erst seit 2 Jahren am Programmieren ^^).
Ich habe von dem MinMaxverfahren gehört, ist das mit Backtracking zu vergleichen? Jedoch habe ich keine Ahnung wie ich das Umsetzen soll...
Ich habe wir Luckie's Quelltext angeschaut (danke dafür, dass du ihn zugägnlich gemacht hast !!!) doch irgendwie kann ich nirgens eine procedure für seine w3ssek KI finden.

Ich hätte jetzt meinen Computerzug so programmiert, dass er schaut ob er sofort gewinnen könnte und dann noch einen Zug im Vorraus, so das er meinen Sieg abwenden kann. Doch eine bessere Rechentiefe kann ich mir kaum vorstellen selber programmieren zu können.
Dann hätte ich dem PC ein System gegeben, so das er bevorzugt in die Mitte setzt.
Doch diese Vorgehensweise ist ja wohl weeeeeit von einer annehmbarer KI entfernt...

Kann mir jmnd durch Tipps oder Quelltext helfen ?
Benutze Delphi 3

Vielen Dank
feuerodem


Horst_H - Di 16.12.08 15:52

Hallo

einfach mal nach vier gewinnt suchen
Bei der Suche kommt auch dieses:
http://www.delphi-forum.de/viewtopic.php?t=77741&start=0&postorder=asc&highlight=vier+gewinnt

Gruß Horst


nagel - Di 16.12.08 16:22

Bei genug Zeit und Interesse:
http://www.connectfour.net/Files/connect4.pdf


Jann1k - Di 16.12.08 16:44

Hab mir die verlinkten Sachen nicht angeschaut, aber Kollegen von mir haben sowas mal gemacht:

Deine KI schaut sich den Effekt an, den ein gelegtes Steinchen in jeder Spalte hat (sind ja nur 9), je nachdem was passiert ist wird ein Prioritätswert für die Spalte aufaddiert, dabei gibts verschiedene Kategorien z.B. eigenen Vierer setzen = 1000 Punkte, gegnerischen vierer verhindern = 250 Punkte, eigenen dreier setzen =50 Punkte (Punkte sind nur Beispielhaft über den genauen wert kann man streiten). So addiert die KI also für jede Spalte einen Wert auf und nimmt am Ende die Spalte die den höchsten Wert hat.


jfheins - Do 18.12.08 01:01

Ich ab sowas auch mal gemacht ...

Die "schwere KI" sah folgendermaßen aus.

Dabei steht "Player" für "Ich" im Sinne des Spielers für den die KI spielt.

"3 - Player" ist der Gegegenspieler gegen den gespielt wird

fsCanDo heißt "In das Feld kann gesetzt werden" (= Darunter sind Steine sodass ein Zug reicht, um einen Stein dort zu platzieren)

fsOpen heißt "Offenes Feld, hier kann erstmal kein Stein hin.

erst werrden alle Möglicheiten definiert, dann wird geschaut ob eine von denen auf dem Spielfeld vorkomt. sollte das der Fall sein, wir die erte genommen, die vorkommt. Wenn nicht ==> Zufall


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:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
// Wenn möglich ==> eigenen vierer machen
  CheckFieldStatesArr[0] := SetFieldStates(Player, Player, Player, fsCanDo);
  CheckFieldStatesArr[1] := SetFieldStates(Player, Player, fsCanDo, Player);
  CheckFieldStatesArr[2] := SetFieldStates(Player, fsCanDo, Player, Player);
  CheckFieldStatesArr[3] := SetFieldStates(fsCanDo, Player, Player, Player);

// Wenn der Gegner im nächsten Zug einen viere machen könnte ==> Stein hin
  CheckFieldStatesArr[4] := SetFieldStates(3 - Player, 3 - Player, 3 - Player, fsCanDo);
  CheckFieldStatesArr[5] := SetFieldStates(3 - Player, 3 - Player, fsCanDo, 3 - Player);
  CheckFieldStatesArr[6] := SetFieldStates(3 - Player, fsCanDo, 3 - Player, 3 - Player);
  CheckFieldStatesArr[7] := SetFieldStates(fsCanDo, 3 - Player, 3 - Player, 3 - Player);

// geg. Dreier verhindern
  CheckFieldStatesArr[8] := SetFieldStates(fsCanDo, fsCanDo, 3 - Player, 3 - Player);
  CheckFieldStatesArr[9] := SetFieldStates(fsCanDo, 3 - Player, fsCanDo, 3 - Player);
  CheckFieldStatesArr[10] := SetFieldStates(fsCanDo, 3 - Player, 3 - Player, fsCanDo);

  CheckFieldStatesArr[11] := SetFieldStates(fsCanDo, fsCanDo, 3 - Player, 3 - Player);
  CheckFieldStatesArr[12] := SetFieldStates(3 - Player, fsCanDo, fsCanDo, 3 - Player);
  CheckFieldStatesArr[13] := SetFieldStates(3 - Player, fsCanDo, 3 - Player, fsCanDo);

  CheckFieldStatesArr[14] := SetFieldStates(fsCanDo, 3 - Player, fsCanDo, 3 - Player);
  CheckFieldStatesArr[15] := SetFieldStates(3 - Player, fsCanDo, fsCanDo, 3 - Player);
  CheckFieldStatesArr[16] := SetFieldStates(3 - Player, 3 - Player, fsCanDo, fsCanDo);

  CheckFieldStatesArr[17] := SetFieldStates(fsCanDo, 3 - Player, 3 - Player, fsCanDo);
  CheckFieldStatesArr[18] := SetFieldStates(3 - Player, fsCanDo, 3 - Player, fsCanDo);
  CheckFieldStatesArr[19] := SetFieldStates(3 - Player, 3 - Player, fsCanDo, fsCanDo);


// Wenn möglich Falle stellen
  CheckFieldStatesArr[20] := SetFieldStates(fsCanDo, fsOpen, Player, Player);
  CheckFieldStatesArr[21] := SetFieldStates(fsCanDo, Player, fsOpen, Player);
  CheckFieldStatesArr[22] := SetFieldStates(fsCanDo, Player, Player, fsOpen);

  CheckFieldStatesArr[23] := SetFieldStates(fsOpen, fsCanDo, Player, Player);
  CheckFieldStatesArr[24] := SetFieldStates(Player, fsCanDo, fsOpen, Player);
  CheckFieldStatesArr[25] := SetFieldStates(Player, fsCanDo, Player, fsOpen);

  CheckFieldStatesArr[26] := SetFieldStates(fsOpen, Player, fsCanDo, Player);
  CheckFieldStatesArr[27] := SetFieldStates(Player, fsOpen, fsCanDo, Player);
  CheckFieldStatesArr[28] := SetFieldStates(Player, Player, fsCanDo, fsOpen);

  CheckFieldStatesArr[29] := SetFieldStates(fsOpen, Player, Player, fsCanDo);
  CheckFieldStatesArr[30] := SetFieldStates(Player, fsOpen, Player, fsCanDo);
  CheckFieldStatesArr[31] := SetFieldStates(Player, Player, fsOpen, fsCanDo);

// Falle verhindern
  CheckFieldStatesArr[32] := SetFieldStates(fsCanDo, fsOpen, 3 - Player, 3 - Player);
  CheckFieldStatesArr[33] := SetFieldStates(fsCanDo, 3 - Player, fsOpen, 3 - Player);
  CheckFieldStatesArr[34] := SetFieldStates(fsCanDo, 3 - Player, 3 - Player, fsOpen);

  CheckFieldStatesArr[35] := SetFieldStates(fsOpen, fsCanDo, 3 - Player, 3 - Player);
  CheckFieldStatesArr[36] := SetFieldStates(3 - Player, fsCanDo, fsOpen, 3 - Player);
  CheckFieldStatesArr[37] := SetFieldStates(3 - Player, fsCanDo, 3 - Player, fsOpen);

  CheckFieldStatesArr[38] := SetFieldStates(fsOpen, 3 - Player, fsCanDo, 3 - Player);
  CheckFieldStatesArr[39] := SetFieldStates(3 - Player, fsOpen, fsCanDo, 3 - Player);
  CheckFieldStatesArr[40] := SetFieldStates(3 - Player, 3 - Player, fsCanDo, fsOpen);

  CheckFieldStatesArr[41] := SetFieldStates(fsOpen, 3 - Player, 3 - Player, fsCanDo);
  CheckFieldStatesArr[42] := SetFieldStates(3 - Player, fsOpen, 3 - Player, fsCanDo);
  CheckFieldStatesArr[43] := SetFieldStates(3 - Player, 3 - Player, fsOpen, fsCanDo);

// Zweier erstellen
  CheckFieldStatesArr[44] := SetFieldStates(fsCanDo, Player, fsOpen, fsOpen);
  CheckFieldStatesArr[45] := SetFieldStates(fsCanDo, fsOpen, Player, fsOpen);
  CheckFieldStatesArr[46] := SetFieldStates(fsCanDo, fsOpen, fsOpen, Player);

  CheckFieldStatesArr[47] := SetFieldStates(Player, fsCanDo, fsOpen, fsOpen);
  CheckFieldStatesArr[48] := SetFieldStates(fsOpen, fsCanDo, Player, fsOpen);
  CheckFieldStatesArr[49] := SetFieldStates(fsOpen, fsCanDo, fsOpen, Player);

  CheckFieldStatesArr[50] := SetFieldStates(Player, fsOpen, fsCanDo, fsOpen);
  CheckFieldStatesArr[51] := SetFieldStates(fsOpen, Player, fsCanDo, fsOpen);
  CheckFieldStatesArr[52] := SetFieldStates(fsOpen, fsOpen, fsCanDo, Player);

  CheckFieldStatesArr[53] := SetFieldStates(Player, fsOpen, fsOpen, fsCanDo);
  CheckFieldStatesArr[54] := SetFieldStates(fsOpen, Player, fsOpen, fsCanDo);
  CheckFieldStatesArr[55] := SetFieldStates(fsOpen, fsOpen, Player, fsCanDo);

// Zweier verhindern
  CheckFieldStatesArr[56] := SetFieldStates(fsCanDo, 3 - Player, fsOpen, fsOpen);
  CheckFieldStatesArr[57] := SetFieldStates(fsCanDo, fsOpen, 3 - Player, fsOpen);
  CheckFieldStatesArr[58] := SetFieldStates(fsCanDo, fsOpen, fsOpen, 3 - Player);

  CheckFieldStatesArr[59] := SetFieldStates(3 - Player, fsCanDo, fsOpen, fsOpen);
  CheckFieldStatesArr[60] := SetFieldStates(fsOpen, fsCanDo, 3 - Player, fsOpen);
  CheckFieldStatesArr[61] := SetFieldStates(fsOpen, fsCanDo, fsOpen, 3 - Player);

  CheckFieldStatesArr[62] := SetFieldStates(3 - Player, fsOpen, fsCanDo, fsOpen);
  CheckFieldStatesArr[63] := SetFieldStates(fsOpen, 3 - Player, fsCanDo, fsOpen);
  CheckFieldStatesArr[64] := SetFieldStates(fsOpen, fsOpen, fsCanDo, 3 - Player);

  CheckFieldStatesArr[65] := SetFieldStates(3 - Player, fsOpen, fsOpen, fsCanDo);
  CheckFieldStatesArr[66] := SetFieldStates(fsOpen, 3 - Player, fsOpen, fsCanDo);
  CheckFieldStatesArr[67] := SetFieldStates(fsOpen, fsOpen, 3 - Player, fsCanDo);

// Erste Situation die Vorkommt suchen und auf der "CanDo"-Position den Stein legen


Grüße,
Julius


Fiete - Fr 19.12.08 11:33
Titel: Re: vier gewinnt KI
Moin feuerodem,
schau mal hier rein http://www.delphi-forum.de/topic_Programmierung+von+Strategiespielen_77741.html.

Es sind Theoriematerial und Beispiele
Gruß
Fiete


GTA-Place - Fr 19.12.08 12:42

@Fiete: Das selbe wie horst schon gepostet hat, nur jetzt 3x :mrgreen:

Der beste Thread, wenns um Informationen zu KI in Delphi geht, ist echt dieser hier von galagher und alzaimar:
http://www.delphi-forum.de/topic_StrategieSpiel++wie+dazu+eine+KI+programmieren_59658,0.html

Soviel wie in dem Thread habe ich nirgends gelernt.


Horst_H - Fr 19.12.08 14:16

Hallo,

ich finde
[url=http://www.ke.informatik.tu-darmstadt.de/lehre/bachelorarbeiten/2006/Baier_Hendrik.pdf]Der Alpha-Beta-Algorithmus und Erweiterungen bei Vier Gewinnt[/url]

von Hendrik Baier aber schöner zu lesen ;-)

Gruß Horst
EDIT:
Nichts von Feueratem ?


GTA-Place - Fr 19.12.08 15:25

Kenn ich ja auch, ist aber halt nicht auf Delphi zugeschnitten und ohne Delphi-Source :-P


feuerodem - Di 23.12.08 14:43

vielen dank für die massigen ratschläge, ich werde mich jetzt durch die durchackern ^^
Doch im Moment bin ich im ABI Stress - schreibe in 20 Tagen die Prüfungen -.-
Ich werde mich bei Problemen dann wieder hier melden / oder wenn es geklappt hat :p

Vielen dank nochmal !!!