Dies ist eine Fortsetzung meiner früheren Frage zu Entscheiden, ob eine Hand bereit ist .
Die Kenntnis der Mahjong-Regeln wäre hervorragend, aber ein poker- oder romme-basierter Hintergrund reicht auch aus, um diese Frage zu verstehen.
In Mahjong 14 Fliesen (Fliesen sind wie Karten im Poker) sind zu 4 Sets angeordnet und ein Paar. Eine Gerade ("123") immer verwendet genau 3 Kacheln, nicht mehr und nicht Weniger. Ein Satz der gleichen Art ("111") besteht aus genau 3 Kacheln. Dies führt zu einer Summe von 3 * 4 + 2 = 14 Fliesen.
Es gibt verschiedene Ausnahmen wie Kan oder Dreizehn Waisen, die nicht sind relevant hier. Farben und Wertebereiche (1-9) sind auch nicht wichtig für die Algorithmus.
Eine Hand besteht aus 13 Kärtchen, jedes Mal, wenn wir an der Reihe sind, müssen wir ein neues Kärtchen nehmen und jedes Kärtchen ablegen, damit wir auf 13 Kärtchen bleiben - außer wir können mit dem neu gewählten Kärtchen gewinnen.
Eine Hand, die angeordnet werden kann, um vier Sätze und ein Paar zu bilden, ist "bereit". Eine Hand, die nur 1 zu tauscht, wird als "tenpai" oder "1 von bereit" bezeichnet. Jede andere Hand hat eine Shanten-Nummer, die angibt, wie viele Kärtchen ausgetauscht werden müssen, um in Tenpai zu sein. Eine Hand mit einer Shantenanzahl von 1 benötigt also 1 Fliese, um Tenpai zu sein (und dementsprechend 2 Fliese). Eine Hand mit einer Shantenanzahl von 5 benötigt 5 Kacheln, um Tenpai und so weiter zu sein.
Ich versuche die Shanten-Nummer einer Hand zu berechnen. Nachdem ich stundenlang geforscht und mehrere Artikel und Artikel zu diesem Thema gelesen habe, scheint dies ein ungelöstes Problem zu sein (mit Ausnahme des Brute-Force-Ansatzes). Der nächste Algorithmus, den ich finden konnte, beruhte auf Zufall, d. H. Er war nicht in der Lage, die korrekte Shanten-Nummer zu 100% der Zeit zu erkennen.
Ich werde ein wenig über die tatsächlichen Regeln (vereinfacht) und dann meine Idee, wie man diese Aufgabe angehen. In Mahjong gibt es 4 Farben, 3 normale wie in Kartenspielen (Ass, Herz, ...), die man "Man", "Pin" und "Sou" nennt. Diese Farben laufen von 1 bis 9 und können sowohl Straights als auch Gruppen gleicher Art bilden. Die vierte Farbe wird "Honours" genannt und kann nur für Gruppen gleicher Art verwendet werden, jedoch nicht für Straights. Die sieben Auszeichnungen werden "E, S, W, N, R, G, B" heißen.
Sehen wir uns ein Beispiel für einen Tenpai-Hand an: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E . Als nächstes wählen wir ein E . Dies ist eine komplette Mahjong-Hand (fertig) und besteht aus einer 2-4-Pin-Straße (denken Sie daran, Pins können für Straights verwendet werden), einem 3-Pin-Triple, einem 5-Mann-Triple, einem W-Triple und einem E-Paar >
Wenn wir unsere ursprüngliche Hand leicht in 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E geändert haben, haben wir eine Hand in 1-shanten, d. h. es erfordert eine zusätzliche Kachel, um tenpai zu sein. In diesem Fall bringt uns das Tauschen einer 2p für eine 3p zurück zu tenpai, also gewinnen wir, indem wir eine 3p und ein E ziehen.
1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W ist eine Hand in 2-Shanten. Es gibt 1 vollendetes Triplet und 5 Paare. Wir brauchen ein Paar am Ende, also wenn wir eins von 1p, 5p, 9p, S oder W wählen, müssen wir eines der anderen Paare verwerfen. Beispiel: Wir wählen einen 1 Pin und verwerfen ein W. Die Hand ist jetzt in 1-Shanten und sieht so aus: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W . Als nächstes warten wir entweder auf 5p, 9p oder S. Wenn wir eine 5p wählen und den übrig gebliebenen W verwerfen, erhalten wir: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S . Diese Hand ist in Tenpai und kann entweder auf einem 9 Pin oder einem S enden.
Um zu vermeiden, dass dieser Text noch länger gezeichnet wird, können Sie sich ein Beispiel an wikipedia ansehen oder eines davon verwenden die verschiedenen Suchergebnisse bei Google. Alle von ihnen sind ein bisschen technischer, also hoffe ich, dass die obige Beschreibung genügt.
Wie gesagt, möchte ich die Shanten-Nummer einer Hand berechnen. Meine Idee war, die Fliesen in 4 Gruppen nach ihrer Farbe aufzuteilen. Als nächstes werden alle Kacheln in Mengen innerhalb ihrer jeweiligen Gruppen sortiert, so dass wir entweder Dreiergruppen, Paare oder einzelne Kacheln in der Ehrengruppe oder zusätzlich noch Streicher in den 3 normalen Gruppen erhalten. Abgeschlossene Sets werden ignoriert. Paare werden gezählt, die endgültige Zahl wird dekrementiert (am Ende benötigen wir 1 Paar). Zu dieser Nummer werden einzelne Kacheln hinzugefügt. Schließlich teilen wir die Zahl durch 2 (da jedes Mal, wenn wir ein gutes Plättchen auswählen, das uns näher zu tenpai bringt, können wir ein weiteres unerwünschtes Plättchen loswerden).
Allerdings kann ich nicht beweisen, dass dieser Algorithmus korrekt ist, und ich habe auch Schwierigkeiten, Straights für schwierige Gruppen einzubauen, die viele Kacheln in naher Umgebung enthalten. Jede Art von Idee wird geschätzt. Ich entwickle in .NET, aber auch Pseudocode oder irgendeine lesbare Sprache ist willkommen.
Ich habe über dieses Problem ein bisschen mehr nachgedacht. Um die endgültigen Ergebnisse anzuzeigen, gehen Sie zum letzten Abschnitt über.
Zuerst schrieb ich einen Brute-Force-Ansatz. Es war in der Lage, 3-Shanten innerhalb einer Minute zu identifizieren, aber es war nicht sehr zuverlässig (manchmal zu viel länger, und das Aufzählen des gesamten Raums ist unmöglich, sogar für nur 3-Shanten).
Eine Sache, die mir in den Sinn kam, war, dem Brute-Force-Ansatz etwas Intelligenz hinzuzufügen. Die naive Art besteht darin, irgendwelche der verbleibenden Kacheln hinzuzufügen, zu sehen, ob sie Mahjong erzeugt haben, und falls nicht, die nächste rekursiv zu versuchen, bis sie gefunden wurde. Angenommen, es sind ungefähr 30 verschiedene Kacheln übrig und die maximale Tiefe ist 6 (Ich bin mir nicht sicher, ob eine 7 + -händige Hand überhaupt möglich ist [Edit: entsprechend der später entwickelten Formel ist die maximal mögliche Shanten-Nummer ( 13-1) * 2/3 = 8] ), erhalten wir (13 * 30) ^ 6 Möglichkeiten, die groß sind (10 ^ 15 Bereich).
Es ist jedoch nicht notwendig, jedes übrig gebliebene Plättchen an jeder Position in der Hand zu platzieren. Da jede Farbe in sich abgeschlossen sein muss, können wir den jeweiligen Farbgruppen Kacheln hinzufügen und notieren, wenn die Gruppe in sich abgeschlossen ist. Details wie genau 1 Paar insgesamt sind nicht schwer hinzuzufügen. Auf diese Weise gibt es maximal ungefähr (13 * 9) ^ 6 Möglichkeiten, das sind ungefähr 10 ^ 12 und mehr möglich.
Meine nächste Idee war, den Code zu verwenden, den ich früh geschrieben habe, um auf Mahjong zu testen und ihn auf zwei Arten zu modifizieren:
Dies sollte die optimale Idee sein, und mit einigen hinzugefügten Heuristiken sollte es der optimale Algorithmus sein. Ich fand es jedoch ziemlich schwierig zu implementieren - es ist aber durchaus möglich. Ich würde eine Lösung bevorzugen, die einfacher geschrieben und gewartet werden kann.
Im Gespräch mit einem erfahrenen Spieler scheint es, dass es einige Gesetze gibt, die verwendet werden können. Zum Beispiel braucht ein Satz von 3 Kacheln niemals aufgebrochen zu werden, da dies niemals die Shanten-Zahl verringern würde. Es kann jedoch auf verschiedene Arten verwendet werden (zum Beispiel für eine Kombination aus 111 oder 123).
Zählen Sie alle möglichen 3er-Sätze auf und erstellen Sie für jede eine neue Simulation. Entferne das 3-er Set. Erstelle nun alle 2 Sätze in der resultierenden Hand und simuliere für jede Kachel, die sie zu einem 3-Satz verbessert. Gleichzeitig simulieren Sie für jedes der 1 Sätze, die entfernt werden. Mach so weiter, bis alle 3- und 2-Sätze weg sind. Es sollte ein 1-Satz (dh eine einzelne Kachel) am Ende übrig sein.
Ich habe den obigen Algorithmus implementiert. Zum leichteren Verständnis habe ich es im Pseudocode aufgeschrieben:
%Vor%Das ist übrigens sehr ähnlich dem Ansatz, den ich bei der Berechnung der Zahl selbst anwende, und natürlich niemals zu hohe Zahlen.
Das funktioniert in fast allen Fällen sehr gut. Allerdings stellte ich fest, dass manchmal die frühere Annahme ("das Entfernen von bereits fertiggestellten 3-Sätzen ist NIE eine schlechte Idee") falsch ist. Gegenbeispiel: 23566M 25667P 159S . Der wichtige Teil ist der 25667 . Wenn wir eine 567 3-Menge entfernen, endet die verbleibende 6 -Kachel, was zu 5-Shanten führt. Es wäre besser, zwei der einzelnen Kacheln zu verwenden, um 56x und 67x zu bilden, was insgesamt zu 4-shanten führt.
Um zu beheben, müssen wir einfach die falsche Optimierung entfernen, die zu diesem Code führt:
%Vor%Ich glaube, das findet immer genau die kleinste Shanten-Nummer, aber ich weiß nicht, wie ich das beweisen soll. Die Zeit ist in einem "vernünftigen" Bereich (auf meiner Maschine maximal 10 Sekunden, normalerweise 0 Sekunden).
Der letzte Punkt ist die Berechnung der Shanten aus der Anzahl der übrig gebliebenen Einzelkacheln. Zuerst ist es offensichtlich, dass die Zahl in der Form 3*n+1 ist (weil wir mit 14 Kärtchen angefangen haben und immer 3 Kacheln abgezogen haben).
Wenn noch 1 Plättchen übrig ist, werden wir bereits abgeschlagen (wir warten nur auf das letzte Paar). Mit 4 übrig gebliebenen Plättchen müssen wir 2 von ihnen abwerfen, um ein 3-Set zu bilden, und uns wieder mit einem einzelnen Plättchen verlassen. Dies führt zu 2 zusätzlichen Rückwürfen. Mit 7 Kacheln haben wir 2 mal 2 Rückwürfe und fügen 4 hinzu. Und so weiter.
Dies führt zur einfachen Formel shanten_added = (number_of_singles - 1) * (2/3) .
Der beschriebene Algorithmus funktioniert gut und hat alle meine Tests bestanden, also gehe ich davon aus, dass er korrekt ist. Wie gesagt, ich kann es aber nicht beweisen.
Da der Algorithmus die wahrscheinlichsten Kachelkombinationen zuerst entfernt, hat er eine eingebaute Optimierung. Wenn Sie einen einfachen Check if (current_depth > best_shanten) then return; hinzufügen, ist das sogar für hohe Shanten-Nummern sehr gut.
Meine beste Vermutung wäre ein A * inspirierter Ansatz. Sie müssen eine Heuristik finden, die die Shanten-Nummer niemals überschätzt und sie verwendet, um den Brute-Force-Baum nur in den Regionen zu suchen, in denen es möglich ist, schnell genug in einen Bereitschaftszustand zu gelangen.
Korrektes Algorithmus-Beispiel: syanten.cpp
Rekursive Schnitte von Hand in Reihenfolge: Mengen, Paare, unvollständige Formen, - und zählen. In allen Variationen. Und das Ergebnis ist minimaler Shanten-Wert aller Varianten: Shanten = Min (Shanten, 8 - * 2 -)
C # Beispiel (neu geschrieben von C ++) kann hier (auf Russisch) gefunden werden.
Das Bestimmen, ob Ihre Hand bereits in Tenpai ist, klingt wie ein Problem mit mehreren Rucksäcken . Gierige Algorithmen werden nicht funktionieren - wie Dialecticus darauf hingewiesen hat, müssen Sie den gesamten Problemraum berücksichtigen.
Ich habe ein wenig nachgedacht und mir eine etwas andere Formel als Mafu ausgedacht. Betrachten Sie zuerst eine Hand (eine sehr schreckliche Hand):
1s 4s 6s 1m 5m 8m 9m 9m 7p 8p Westen Osten Norden
Indem wir Mafus Algorithmus verwenden, können wir nur ein Paar (9m, 9m) auswerfen. Dann sind wir mit 11 Singles übrig. Wenn wir nun die Formel von mafu anwenden, erhalten wir (11-1) * 2/3, was keine Ganzzahl ist und daher keine Shanten-Nummer sein kann. Hier kam ich auf:
N = ((S + 1) / 3) - 1
N steht für die Shanten-Nummer und S für die Score-Summe. Was ist ein Score? Es ist eine Anzahl von Kacheln, die Sie benötigen, um ein unvollständiges Set fertigzustellen. Wenn du zum Beispiel (4,5) in deiner Hand hast, brauchst du entweder 3 oder 6, um es zu einem vollständigen 3-Satz zu machen, das heißt, nur eine Kachel. Also erhält dieses unvollständige Paar die Punktzahl 1. Dementsprechend braucht (1,1) nur 1, um eine 3-Satz zu werden. Jede einzelne Kachel benötigt offensichtlich 2 Kacheln, um ein 3-Set zu werden und erhält die Punktzahl 2. Jeder komplette Satz erhält natürlich die Punktzahl 0. Beachten Sie, dass wir die Möglichkeit ignorieren, dass Singles zu Paaren werden. Wenn wir nun versuchen, alle unvollständigen Mengen in der obigen Hand zu finden, erhalten wir:
(4s, 6s) (8m, 9m) (7p, 8p) 1s 1m 5m 9m westlicher Osten Norden
Dann zählen wir die Summe seiner Punkte = 1 * 3 + 2 * 7 = 17. Wenn wir nun diese Zahl auf die obige Formel anwenden, erhalten wir (17 + 1) / 3 - 1 = 5, was bedeutet, dass diese Hand 5-Shanten ist. Es ist etwas komplizierter als Alexeys und ich habe keinen Beweis, aber bisher scheint es für mich zu funktionieren. Beachten Sie, dass eine solche Hand auf die andere Art geparst werden könnte. Zum Beispiel:
(4s, 6s) (9m, 9m) (7p, 8p) 1s 1m 5m 8m westlicher Osten Norden
Allerdings erhält es nach Formel immer noch Score-Summe 17 und 5-Shanten. Ich kann das auch nicht beweisen, und das ist ein wenig komplizierter als Alexeys Formel, aber führt auch Punkte ein, die man auf etwas anderes anwenden kann.