Identifizieren und Sammeln von Schlüsseldaten
Ich habe mehrere Algorithmen untersucht, um den Suchraum für alle möglichen Kombinationen zu optimieren und zu reduzieren. Allerdings erhöht die Tatsache, dass jede Karte zweimal erscheinen kann, die Anzahl möglicher Kombinationen, was es schwierig macht, jede einzelne zu verfolgen und zu validieren. Als ich an Codeforces teilnahm, stieß ich auf ein Drawback, das mich an „Inselproblem,‘ was mir neue Einblicke in die Herangehensweise an das Handbewertungssystem gab.
Wir können die Hand als 2D-Gitter der Größe 4×13 darstellen, wobei jede Spalte die Ränge 1 bis 13 darstellt und jede Zeile den 4 Farben entspricht. Jede Zelle in diesem Raster enthält die Anzahl der Karten in der Hand, in unserem Fall entweder 1, 2 oder 0. Dadurch können wir die Hand in „Inseln“ unterteilen, die als Gruppen verbundener Landzellen mit einer Anzahl von 1 oder 2 definiert sind, basierend auf den folgenden Konnektivitätsregeln:
1. Zwei Zellen gelten als verbunden, wenn sie im Raster eine gemeinsame Seite (hyperlinks, rechts, oben oder unten) haben.
2. Alle Zellen innerhalb derselben Spalte sind auch dann verbunden, wenn sie beide mindestens Einsen enthalten, auch wenn sie nicht benachbart sind (oben oder unten).
EXP von „Hand A“: 11C 3H 4H 11D 3D 5H 9D 2H 6H 3C 4H 3D 4D 5H 12D 3C
Unsere erste Aufgabe besteht darin, alle einzelnen Inseln zu identifizieren und zu kennzeichnen. Da jede Insel unabhängig von den anderen ist, können wir uns das Leben erleichtern, indem wir jede Insel einem Klassentyp zuordnen, nennen wir ihn _cardGraph. Diese Klasse ist für diese Insel in Bezug auf Extraktions-, Änderungs- oder Löschvorgänge verantwortlich.
Aus Gründen der Übersichtlichkeit isolieren wir in den nächsten Abschnitten eine Insel und bearbeiten sie, damit Sie sie leichter nachvollziehen können. Wenn es hilft, können Sie sich jede Insel als zusammenhängenden Graphen vorstellen, wie in der folgenden Abbildung dargestellt:
Wenn Sie nun mehrere Inselbeispiele nehmen und versuchen, die möglichen Kombinationen zu extrahieren, werden Sie feststellen, dass einige Karten bei der Verzweigung zu möglichen Kombinationen eine einzigartige Rolle spielen. Wir nennen diese Artwork von Karten a Kontrollpunkte oder Cpts Kurz gesagt, denn sie spielen eine wesentliche Rolle, indem sie den Suchraum erheblich reduzieren, wie Sie in den folgenden Schritten sehen werden.
Cpts: Damit eine Karte als Cpts gilt, muss sie sich an einer Place befinden, an der wir eine Entscheidung treffen müssen, an welche Meldung (Lauf oder Satz) wir sie anhängen möchten. Wenn eine Karte auf natürliche Weise in mehrere Meldungen passt, ohne eine Auswahl zu erzwingen (zum Beispiel wird eine doppelte Karte mit zwei Optionen für Meldungen, bei denen jede Karte an eine Meldung angehängt wird), nicht als Cpts betrachtet.
Im Fall unseres Inselbeispiels wird die 3 des Herzens als Cpts identifiziert. Nachfolgend finden Sie nacheinander alle Meldungen, an die sich die Herz-3 anschließen könnte.
Unser nächster Schritt besteht darin, jede Karte zu markieren, die als Cpts qualifiziert ist. Dazu erstellen wir eine 4×13-Tabelle (im Byte-Typ) und nennen sie _flagMap . Aus Gründen der Speichereffizienz können Sie diese Tabelle nun zu einer gemeinsam genutzten Tabelle machen. Jede aus der Hand erstellte _cardGraph-Instanz kann darauf verweisen und sie verwenden. In dieser Tabelle wird jeder Karte in einer Insel ein Bitstrom am entsprechenden Index in _flagMap zugewiesen. Dieses Byte stellt ihre möglichen Platzierungen in verschiedenen Läufen oder Sätzen dar. Wenn eine Karte als Cpts qualifiziert ist, wird sie in einem Stapel gespeichert (wir werden ihn später benötigen), den wir _cptsStack nennen. Hier ist eine Aufschlüsselung der Bytestruktur: Das erste Bit gibt an, ob die Karte zu einem Lauf gehört, das zweite Bit zeigt ihre Platzierung in einem zusätzlichen Lauf an, das dritte Bit gibt an, ob sie zu einem Satz gehört, und das vierte Bit gibt an, ob sie dazugehört zu mehreren Sätzen.
Hier ist ein Beispiel für einen Bitstrom: 00000111 Hier haben wir:
• Das erste Bit (1) bedeutet, dass die Karte zu einem Lauf gehören kann.
• Das zweite Bit (1) bedeutet, dass die Karte zu einem zweiten Lauf gehören kann.
• Das dritte Bit (1) bedeutet, dass die Karte zu einem Satz gehört.
• Das vierte Bit (0) bedeutet, dass die Karte nicht zu einem zweiten Satz gehört.
Dies könnte der Fall sein, dass die Konfiguration für eine Karte 00000101 ist (keine Kopie), was bedeutet, dass die Karte zu einem Lauf oder einem Satz gehört. Oder eine andere Konfiguration könnte 00000011 sein, was bedeutet, dass die Karte zu zwei verschiedenen Läufen gehört.
Um einen CPT zu identifizieren, zählen Sie einfach die Einsen in seiner Bitdarstellung. Wenn dieser Wert die Gesamtzahl dieser Karte in der Hand übersteigt, gilt dies als CPT. Wenn beispielsweise eine Karte zweimal vorkommt (dh zwei Kopien hat) und ihre Bitdarstellung 00000101 ist, handelt es sich nicht um einen CPT. Wenn die Bitdarstellung jedoch wie im Beispiel 00000111 ist, gilt sie als cpts.
In unserem Inselbeispiel würde die _flagMap-Tabelle so aussehen:
Sobald wir die _flagMap gefüllt und die CPTs identifiziert haben, besteht die nächste Aufgabe darin, die Insel in horizontale und vertikale Linien zu zerlegen. Aber warum? Die Aufteilung des Kartendiagramms in diese Zeilen vereinfacht die Identifizierung von Läufen und Sätzen, da wir uns so auf zusammenhängende Kartensequenzen konzentrieren können, die effizienter verarbeitet werden können. Wie Sie sich vorstellen können, stellen die vertikalen Linien die Sätze dar, während die horizontalen Linien die Läufe darstellen.
Wir speichern jede horizontale Zeile in einer Liste vom Typ Tupel, wobei das erste Factor den Startindex der Zeile und das letzte Factor den Endindex (einschließlich) darstellt. Für die vertikalen Linien reicht es aus, den Spaltenindex einfach in einer Liste zu speichern.
Tipp: Wir können diese Aufgabe zusammen mit dem Bitdarstellungsschritt in einer einzigen Schleife erledigen und so eine O(n)-Komplexität erreichen.
Combos generieren
Machen wir nun eine Pause und rekapitulieren: Wir haben die Kontrollpunkte (CPTs) identifiziert und im _cptsStack gespeichert. Wir haben die Insel auch in vertikale und horizontale Linien zerlegt und die _flagMap mit der Kartenbitdarstellung gefüllt.
Wenn unsere Daten vorhanden sind, müssen wir sie nur noch verwenden, um alle möglichen gültigen Kombinationen der Insel zu generieren. Aber wie machen wir das? Hier ist ein vereinfachter Ansatz:
1. Weisen Sie den Kontrollpunkten (Cpts) gültige Platzierungen zu:
Wir übernehmen die Bitdarstellung eines Cpts aus _flagMap, die alle möglichen Platzierungen für diesen Cpts angibt. Dann schauen wir uns die Anzahl der Kopien der cpts im _cardGraph an und passen seine Bitdarstellung an eine aktuell gültige Konfiguration an. Wenn der cpts beispielsweise eine Bitdarstellung von 00001111 und 2 Kopien hat, können wir alle gültigen Platzierungen dafür generieren, additionally C(4,2)=6C(4,2) = 6C(4,2)=6. Mögliche Kombinationen wären 0011, 0101, 1100, 1010, 1001 und 0110.
2. Verwenden von DFS zum Konfigurieren aller möglichen Kombinationen für jeden Cpts:
Wir verwenden eine Tiefensuche (DFS), um die gültigen Platzierungen für jeden CPT zu durchlaufen, wie in Schritt 1 gezeigt. Jeder Knoten im DFS-Baum stellt eine mögliche Platzierung für einen bestimmten CPT dar, sodass jeder eindeutige DFS-Pfad einen gültigen darstellt Combo-Konfiguration. Für jeden „Blatt“-Knoten (Ende des DFS-Pfads) fahren wir mit dem nächsten Schritt fort.
3. Combos generieren:
In diesem Schritt durchlaufen wir die horizontalen und vertikalen Linien in der Insel, um Läufe, Sätze und eine Dump-Liste zu identifizieren. Dies erfolgt in zwei Durchgängen für jede Zeile wie folgt:
- Durchgang 1: Bei einer horizontalen Linie hängen wir beispielsweise kontinuierlich Karten von (Zeilenanfang bis Zeilenende) an eine Liste an, um einen Lauf zu bilden. Wir hören auf, if (card_bit_representation | 00000001 == 0) hinzuzufügen. Wenn die Länge des Laufs größer oder gleich 3 ist, fügen wir sie der Laufkombination hinzu; andernfalls geht jede Karte in die Dump-Liste und wir versuchen weiter, einen weiteren Lauf zu bilden, bis wir das Ende der Zeile erreichen.
- Durchgang 2: Wiederholen Sie den Vorgang und suchen Sie dieses Mal nach Karten, die einem anderen Bitmuster mit der Operation or (00000010) entsprechen. Dies ermöglicht es uns, mögliche Zweitläufe zu identifizieren.
Der gleiche Ansatz gilt für das Extrahieren von Mengen, wir verwenden jedoch Bitoperationen mit 00000100 und 00001000.
4. Registrieren Sie die gültige Kombination und wechseln Sie zur nächsten DFS-Konfiguration:
Nachdem wir alle Läufe, Sätze und Dumps für die aktuelle Kombination abgeschlossen haben, speichern wir die Kombination und fahren dann mit der nächsten DFS-Konfiguration fort, um den Vorgang zu wiederholen. Auf diese Weise untersuchen wir systematisch alle möglichen Konfigurationen für gültige Kombinationen.
Wenn Sie alles richtig codiert und unser Inselbeispiel eingegeben haben: „2H3H4H5H4H5H6H3C3C3D3D4D“, sollte es wie unten gezeigt zerlegt werden. Beachten Sie, dass ich jeder generierten Combo eine Berechnung hinzugefügt habe, damit wir ein Gefühl dafür bekommen, wie sich die KI verhalten wird.
Im nächsten Artikel werde ich auf den Relaxation des Techniques eingehen und mich dabei auf die dynamische Modifikation der Hand und die KI-Strategie konzentrieren. Wenn Sie bisher mitgelesen haben, wird es nicht schwer sein, zu erkennen, wie wir das Hinzufügen und Entfernen von Karten optimieren und die beiden Regeln, die wir zu Beginn beiseite gelegt haben, integrieren können. Bleiben Sie dran und bis zum nächsten Mal! „hoffentlich 😉“.
Sofern nicht anders angegeben, wurden alle Bilder vom Autor mit Lucidchart, Gimp und Python erstellt