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
*
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:
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
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.