3. Canasta KI - Wie Karten verwalten?

Canasta KI - Wie Karten verwalten?

  • 3

    Guten Abend,

    Ich möchte eine KI für das Kartenspiel 'Canasta' schreiben. Bei diesem Spiel geht es hauptsächlich darum, möglichst viele gleiche Karten (Zahl, nicht Farbe) zu bekommen und zu stapeln. Gespielt wird mit 2 Stapeln Karten mit 2 Jokern.

    Ein Spieler bekommt - beim Spiel zu zweit - 15 Karten. Je höher die Zahl, desto wertvoller ist eine Karte. Farben spielen keine Rolle, eine Herz 8 ist gleich viel wert wie eine Karo 8.

    Ich habe mir schon einmal Gedanken darüber gemacht, wie ich die Karten verwalte.
    Ich würde die eine Klasse "CardStack" schreiben, die den operator < implementiert. Diese Klasse kann mehrere Karten einer Zahl speichern.

    Welchen Container sollte ich jedoch für das speichern der einzelnen CardStacks verwenden? Meine Überlegung war, dass immer der "oberste" CardStack die nächste Karte enthält, die von der KI gespielt wird. Welchen der folgenden Container sollte ich verwenden:

    - priority_queue (Auf welchen Cotainer, deque, vector, list, ...?)
    - set

    Wenn die KI eine Karte zieht, brauche ich Zugriff auf den entsprechenden CardStack um die Anzahl der Karten um 1 zu erhöhen, gleichzeitig sollte der Container aber immer so sortiert bleiben, dass die nächste Karte im "vordersten" CardStack liegt.

    0
  • C

    314159265358979 schrieb:

    Wenn die KI eine Karte zieht, brauche ich Zugriff auf den entsprechenden CardStack um die Anzahl der Karten um 1 zu erhöhen, gleichzeitig sollte der Container aber immer so sortiert bleiben, dass die nächste Karte im "vordersten" CardStack liegt.

    Mein spontaner Vorschlag dafür wäre: std::map<> (Schlüssel ist die jeweilige Karte, Wert die Anzahl auf der Hand).

    Bei priority_queue kommst du nur schlecht auf die einzelnen Elemente (außer dem Kopf), bei set<> kannst du die Elemente nicht direkt ändern.
    (btw, priority_queue<> mit einer list<> dürfte nicht einmal durch den Compiler kommen ;))

    0
  • 3

    Und wie bekomme ich aus der map dann die nächste Karte? Ich müsste die doch jedes mal neu heraussuchen, oder hab ich in meiner Müdigkeit etwas übersehen?

    0
  • C

    Die map<> ist auch sortiert, also dürfte die nächste Karte (je nach Sortierrichtung) entweder das erste oder das letzte Element sein. Du mußt nur darauf achten, daß du leere Stapel gleich aus der map löschst.

    Edit:
    Oder spielt die Anzahl der Karten eines Wertes auch eine Rolle bei der Bewertung des Kartenstapels?

    0
  • 3

    Das verstehe ich nicht. Meine CardStack Klasse sähe in etwa so aus:

    class CardStack
{
    Type type; // enum
    unsigned count; // Anzahl
};

    Oder war das anders gemeint? Wie sollte die map dann aussehen?

    0
  • 3

    Zu deinem Edit: Ja, es gibt 2 Sortierkriterien. Das erste Kriterium ist die Anzahl der gleichen Karten. Das zweite Kriterium ist dann die Höhe. Ist also die Anzahl gleich, so zählt die Höhe der Karte(n).

    0
  • C

    Ich kenne die Regeln nicht so gut wie du, deshalb nochmal: Ist es für den Wert des Stapels wichtig, wieviele Karten der selben Sorte man hat? Sprich: Ist ein Stapel aus 4 Neunern mehr wert als ein einzelner Bube?

    Wenn ja, vergiss was ich gesagt habe - da würde ich doch eher ein set<CardStack> (beim Karte ziehen mußt du den alten Stapel aus der Menge löschen und einen neuen mit der aktualisierten Anzahl einfügen) oder eine manuell sortierte list<CardStack> verwenden.

    Wenn nein: Ich hatte an eine map<Type,unsigned> gedacht (ohne einen eigenen Datentyp für den Kartenstapel).

    0
  • 3

    Wie würdest du diese list sortieren? Welche der beiden Varianten ist in welchen Fällen besser geeignet, und wieso?

    0
  • C

    314159265358979 schrieb:

    Wie würdest du diese list sortieren?

    Einmal vorsortieren per list::sort() und danach immer die richtige Position gemäß Sortierreihenfolge bestimmen und den Eintrag dort einfügen (bzw. per splice() verschieben, wenn sich der Wert eines Stapels geändert hat).

    Was besser ist, kann ich auf Anhieb nicht sagen, das müsstest du im Zweifelsfall nebeneinanderhalten und vergleichen.

    Edit: Wobei - bei maximal 13 Kartenstapeln, die du verwalten müsstest, spielen die Unterschiede zwischen O(n) und O(log n) noch nicht so die Rolle - da könnte es sogar ausreichen, über ein Array konstanter Größe per max_element() drüberzulaufen.

    0
  • 3

    Habe es hier mal mit std::set geschrieben: http://ideone.com/YKA4p
    Besonders schön finde ich es nicht, dafür ist es einfacher.

    0
  • ?

    Ihr kennt die Canasta-Spielregeln? Ich weiss es gibt da viele Varianten, aber gewisse Basics sind in der Regel gleich.

    Die Farben spielen keine Rolle mit Ausnahme bei den 3er.

    Gespielt wird meist mit 2 * 52er Karten + 2 bis 6 Joker.
    Ich würde den Karten 106 bis 110 Werte zuordnen und dann mathematisch durch Division "gruppieren".
    z.B. Karten/8 -> Anzahl des Rest: für (min.2 + wilde Karte) oder 3 Karten zum Auslegen -> oder 7 Karten zum Canasta.

    Wenn ihr das übersichtlich in Container hinein bekommt, ...

    MfG f.-th.

    0
  • 3

    Natürlich ist mir bewusst, dass 3er eine Sonderrolle einnehmen (so auch die 2er und Joker, die falsch eingeordnet sind) aber ich wollte den Sachverhalt vereinfachen 😉

    Deine Idee habe ich jetzt nicht so ganz verstanden, kannst du mir das nochmal genauer erklären?

    0
  • ?

    Es gibt sicher noch andere Lösungen:

    Beispiel:Karten in Array
    D[0] = Herz Ass Spielsatz 1
    D[1] = Herz Ass Spielsatz 2
    D[2] = Karo Ass S1 <= S=Spielsatz=Kartensatz
    D[3] = Karo ...
    D[4] = Kreuz Ass S1
    ...
    D[8] = Herz 2 S1
    ...
    D[12] = Herz 3 S1
    ...
    D[103] = Pik König S2
    D[104] = Joker ??
    ...

    Wenn du die Indices durch 8 dividierst, gruppierst du die Karten nach ihren Werten. Bei der 3 muss da noch ein wenig mehr.
    Die ersten 8 Karten haben den Zählwert 20
    die nächsten 4 => 100
    die weiteren 36 => 5
    der Rest ohne Joker => 10
    die Joker => 50

    Die 2 hat auch noch "Jokerfunktionen", d.h. sie kann beim Auslegen oder Bildung eines "unechten" Canastas einen anderen Wert vertreten.

    Okay das hätte man auch schon früher so geschrieben.
    Vielleicht kann das ja jemand elegante aktuelle C++ Mittel empfehlen.
    Für das mischen eventuell mal in der STL nachsehen.

    Jetzt muss halt noch die Kartenverwaltung der Spieler folgen.

    Bei den Containern bin ich nicht fit genug.
    Eventuell als Datensatz:
    laufende Nr. - Farbe - Wert - Kartensatz - Zählwert - Spieler
    in einen Container packen. Aber da werden Andere sicher bessere Infos haben.

    MfG f.-th.

    0
Anmelden zum Antworten