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.

Anstelle die Wahrscheinlichkeit nur um eins zu erhöhen kann man diese auch um die Punkte des Stiches erhöhen.

Eine weitere sinnvolle aber nicht faire Variante, wäre es nur die Stiche zu betrachten die überhaupt möglich sind, d.h. die Stiche in denen auf eine eigene Handkarte eine Handkarte eines nachfolgenden Spielers folgt.

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:

            

Möglichkeiten des



Größe des Waldes bis zu diesem Stich

1. Stiches

(12*36*35*34) *

514.080

2.Stiches:

(11*33*32*31) *

185.118.151.680

3.Stiches:

(10*30*29*28) *

45.094.781.749.248.000

4.Stiches:

(9*27*26*25) *

7.122.720.777.293.721.600.000

5.Stiches:

(8*24*23*22) *

691.986.568.955.639.640.883.200.000

6.Stiches:

(7*21*20*19) *

38.654.369.741.862.039.339.735.552.000.000

7.Stiches:

(6*18*17*16) *

...

8.Stiches:

(5*15*14*13) *



9.Stiches:

(4*12*11*10) *



10.Stiches:

(3*9*8*7) *



11.Stiches:

(2*6*5*4) *



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 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

Stand 17. Oktober 2001