KI-Ansätze für FreeDoko

KI-Heuristiken *

Ansatz 1: Die Stichdatenbank *

Ansatz 2: Ein fairer Spielwald *

Ansatz 3: Der unfaire Spielwald *

Implementationsstand der KI-Heuristiken *

Implementation *

Die Stichdatenbank *

 

KI-Heuristiken

Was ist eine Heuristik? Einfach gesagt eine Regel die meistens aber nicht immer gilt. Im folgenden einige Heuristiken für Doppelkopf mit absteigender Anwendungsbedeutung, d.h., es ist sinnvoller die erste Regel zuerst anzuwenden, als die zweite:

  1. Spiele als erste Karte eines Stiches ein As
  2. Als letzte Karte eines Farbstich, dessen Farbe man nicht hat, spiel ein Karo As, eine Karo Zehn, einen Karo König, einen Buben, eine Karo Neun oder Dame, wenn in diesem Stich nicht bereits eine Trumpfkarte ist.
  3. Wenn den Stich gewinnt, spiele als letzte Karte Karo Ass, Karo Zehn, Farb Zehn, Farb Ass oder Farb König, sofern erlaubt
  4. Wenn ich mit einem As oder einer Zehn den Stich nicht gewinne, versuch ich doch lieber einen König oder eine Neun der entsprechenden Farbe zu spielen.
  5. Wenn ich mit meinem Trumpf diesem Stich nicht gewinne, spiel einen niedrigen Trumpf oder Fehl, wenn erlaubt, Trumpfreihenfolge hierbei zuerst Karo Neun, dann Karo König, Bube, Karo Zehn, Karo As, Dame.
  6. Spiel kein As oder keine Dame, die bereits im Stich liegen

 

Ansatz 1: Die Stichdatenbank

Ein einfacher Ansatz ist das Anlegen einer Stichdatenbank aller überhaupt möglicher Stiche, aus der die KI dann berechnet mit welcher Karte sie wohl am ehesten diesen Stich gewinnt.

Grundlegende einfache Idee:

Ein Doppelkopfblatt hat 24 verschiedene Karten, ein Stich besteht aus 4 Karten:

Also lässt sich dies in 24*24*24*24=331776 Datensätzen speichern. Diese Anzahl lässt sich noch reduzieren, wenn man davon ausgeht das jede Karte nur zweimal vorkommt. Dies führt dann zu einer geringfügig kleineren Größe allerdings ermöglicht die obige Kodierung einen direkten und einfachen Zugriff auf die Datensätze der Datenbank.

Bekommt die KI jetzt einen Stich sucht sie aus der Datenbank alle zu ihren Handkarten passenden Stiche raus, d.h. wo eine ihre Handkarten an der Stelle der aktuell geforderten Karte des Stiches erscheint, und ermittelt ob sie den so gefundenen Stich gewinnen würde, ist dies der Fall erhöht sie die Anzahl der mit dieser Handkarte gewonnen Stiche um eins und findet so am Ende die Handkarte mit der höchsten Wahrscheinlichkeit diesen Stich zu gewinnen. Berücksichtigt werden sollte dabei noch, dass die Handkarte überhaupt zu spielen erlaubt war.

Wenn diese Datenbank mit obigen Heuristiken kombiniert wird, kann es dazu kommen, dass die KI auf das spielen einer bestimmten Karte verzichten möchte, für diesen Fall ist es durchaus sinnvoll auch noch die zweit beste zu ermitteln und vielleicht sogar eine komplette Rangreihenfolge der Handkarten zu erstellen.

 

Ansatz 2: Ein fairer Spielwald

Ein Spielwald gibt ausgehenden von der aktuellen Situation alle möglichen Spielverläufe an. Mit fair ist hier gemeint, dass die KI keinen Einblick in die Handkarten anderer Spieler nimmt.

Ein naiver Ansatz führt dann zu folgender Komplexität eines Spielbaumes für den ersten Stich:

   

Größe des Waldes bis zu diesem Stich

Möglichkeiten des

(12*36*35*34) *

514.080

Möglichkeiten des 2.Stiches:

(11*33*32*31) *

185.118.151.680

Möglichkeiten des 3.Stiches:

(10*30*29*28) *

45.094.781.749.248.000

Möglichkeiten des 4.Stiches:

(9*27*26*25) *

7.122.720.777.293.721.600.000

Möglichkeiten des 5.Stiches:

(8*24*23*22) *

691.986.568.955.639.640.883.200.000

Möglichkeiten des 6.Stiches:

(7*21*20*19) *

38.654.369.741.862.039.339.735.552.000.000

Möglichkeiten des 7.Stiches:

(6*18*17*16) *

...

Möglichkeiten des 8.Stiches:

(5*15*14*13) *

 

Möglichkeiten des 9.Stiches:

(4*12*11*10) *

 

Möglichkeiten des 10.Stiches:

(3*9*8*7) *

 

Möglichkeiten des 11.Stiches:

(2*6*5*4) *

 

Möglichkeiten des 12.Stiches:

(1*3*2*1)

 

Wie man hier sieht explodiert die Größe des Spielbaumes fast sofort. Zum Glück kann man hier die Komplexität wie bei der Datenbank direkt auf für alle Zahlen größer 24 auf 24 reduzieren.

   

Größe dieses Stich

Größe des Waldes

1.Stich

(12*24*24*24)

165888

165.888

2. Stich:

(11*24*24*24) *

152064

25.225.592.832

3. Stich:

(10*24*24*24) *

138240

3.487.185.953.095.680

4. Stich:

(9*24*24*24) *

124416

433.861.727.540.352.122.880

5. Stich:

(8*24*23*22) *

85008

36.881.717.734.750.253.261.783.040

6. Stich:

(7*21*20*19) *

55860

2.060.212.752.663.149.147.203.200.614.400

7. Stich:

(6*18*17*16) *

29376

...

8. Stich:

(5*15*14*13) *

13650

 

9. Stich:

(4*12*11*10) *

5280

 

10. Stich:

(3*9*8*7) *

1512

 

11. Stich:

(2*6*5*4) *

240

 

12. Stich:

(1*3*2*1)

6

 

Auch diese Lösung führt noch zu einem viel zu großen Spielbaum, selbst wenn man noch dreifach vorkommende Karten eliminiert, wird die Datenmenge nicht wesentlich weiter reduziert. Es bleibt also nur noch die Möglichkeit die Tiefe des Baumes einzuschränken, d.h. es werden nicht alle Stiche im voraus berechnet sondern nur ein kleiner Teil:

   

Größe dieses Stich

Stiche voraus berechnen

Größe des Waldes

1.Stich

(12*24*24*24)

165888

1

165888

2. Stich:

(11*24*24*24) *

152064

1

152064

3. Stich:

(10*24*24*24) *

138240

1

138240

4. Stich:

(9*24*24*24) *

124416

1

124416

5. Stich:

(8*24*23*22) *

85008

1

85008

6. Stich:

(7*21*20*19) *

55860

1

55860

7. Stich:

(6*18*17*16) *

29376

1

29376

8. Stich:

(5*15*14*13) *

13650

1

13650

9. Stich:

(4*12*11*10) *

5280

1

5280

10. Stich:

(3*9*8*7) *

1512

2

362.880

11. Stich:

(2*6*5*4) *

240

2

1440

12. Stich:

(1*3*2*1)

6

1

6

Leider ist diese Ergebnis aber auch sehr unbefriedigend, denn eine Vorausschau nur in den Stichen 10 und 11 ist zuwenig und das Berechnen eine Spielwaldes mit mehr als 300.000 Blättern ist nicht akzeptabel, da schon das erstellen der obigen Datenbank auf einem Rechner mit 700MHz und 128MB ca. 5 Sekunden dauerte.

In wieweit obige Heuristiken zur Einschränkung des Baumes verwendet werden können, muss erst noch untersucht werden.

 

Ansatz 3: Der unfaire Spielwald

Als unfair wird hier der Einblick in die Handkarten der anderen Spieler angesehen. Allerdings führt dieses zu einen deutlich kleineren Wald:

   

Größe dieses Stich

Stiche voraus berechnen

Größe des Waldes

1.Stich:

(12*12*12*12) *

20736

1

20.736

2. Stich:

(11*11*11*11) *

14641

1

14.641

3. Stich:

(10*10*10*10) *

10000

1

10.000

4. Stich:

(9*9*9*9) *

6561

1

6.561

5. Stich:

(8*8*8*8) *

4096

1

4.096

6. Stich:

(7*7*7*7) *

2401

1

2.401

7. Stich:

(6*6*6*6) *

1296

1

1.296

8. Stich:

(5*5*5*5) *

625

2

160.000

9. Stich:

(4*4*4*4) *

256

4

331.776

10. Stich:

(3*3*3*3) *

81

3

1.296

11. Stich:

(2*2*2*2) *

16

2

16

12. Stich:

(1*1*1*1)

1

1

1

Auch diese Lösung führt leider zu keinem wirklich zufriedenstellenden Ergebnis, ist aber doch deutlich besser als die Lösung des Ansatzes 2.

Wünschenswert wäre eine Lösung mit folgender Vorausberechnungskette:

 

Stiche voraus berechnen sinnvoll/ optimal

1.Stich:

1 / 1

2. Stich:

1 / 2

3. Stich:

2 / 3

4. Stich:

2 / 4

5. Stich:

3 / 5

6. Stich:

3 / 6

7. Stich:

4 / 6

8. Stich:

4 / 5

9. Stich:

4 / 4

10. Stich:

3 / 3

11. Stich:

2 / 2

12. Stich:

1 / 1

 

Implementationsstand der KI-Heuristiken

  1. Komplett implementiert
  2. Wird auch angewendet, wenn Partner bereits abgestochen hat
  3. Noch nicht vorhanden
  4. Komplett implementiert
  5. Das spielen von Fehl ist noch nicht implementiert
  6. Komplett implementiert

 

Implementation

Die Stichdatenbank

Die Datensätze werden in einem Feld gespeichert.

Erzeugung der Datenbank:

TCard c[4];

for(int w=0;w<24;w++)

for (int x=0;x<24;x++)

for (int y=0;y<24;y++)

for (int z=0;z<24;z++)

{

c[0]=TCard(InttoCardColor(w/6),InttoCardValue(2*(w%6)));

c[1]=TCard(InttoCardColor(x/6),InttoCardValue(2*(x%6)));

c[2]=TCard(InttoCardColor(y/6),InttoCardValue(2*(y%6)));

c[3]=TCard(InttoCardColor(z/6),InttoCardValue(2*(z%6)));

Tricks[w*24*24*24+x*24*24+y*24+z]=TTrick(c);

}

Hierbei sind die Kartenfarbe von 0=Karo bis 3=Kreuz codiert und Die KartenWerte sind 0=Neun, 2=Zehn, 4=As, 6=Bube, 8=Dame und 10=König

Ein Zugriff erfolgt dann wie folgt:

int mod=24*24*24;

// computation of startposition for Database

for(i = 0; i < CardsInTrick; i++)

{

startpos+=mod*(6*T.GetCard(i).GetColor()+CardValuetoInt(T.GetCard(i).GetValue())/2);

mod=mod/24;

}

Wobei CardValueToInt genau obige Zahlen zu den entsprechenden Kartenwerten liefert.