Wie berechnet ich die Shanten -Zahl in Mahjong?
https://stackoverflow.com/questions/4239028
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Dies ist eine Follow -up zu meinem Frühere Frage zur Entscheidung, ob eine Hand fertig ist.
Das Wissen über Mahjong-Regeln wäre ausgezeichnet, aber ein poker- oder romme-basierter Hintergrund reicht auch aus, um diese Frage zu verstehen.
In Mahjong sind 14 Fliesen (Fliesen sind wie Karten im Poker) zu 4 Sätzen und einem Paar angeordnet. Ein gerade ("123") verwendet immer genau 3 Fliesen, nicht mehr und nicht weniger. Ein Satz der gleichen Art ("111") besteht auch aus genau 3 Kacheln. Dies führt zu einer Summe von 3 * 4 + 2 = 14 Kacheln.
Es gibt verschiedene Ausnahmen wie Kan oder dreizehn Waisen, die hier nicht relevant sind. Farben und Wertebereiche (1-9) sind auch für den Algorithmus nicht wichtig.
Eine Hand besteht aus 13 Fliesen. Jedes Mal, wenn wir an der Reihe sind, können wir eine neue Fliese auswählen und müssen jede Fliese verwerfen, damit wir auf 13 Kacheln bleiben - außer wenn wir mit dem neu ausgewählten Fliesen gewinnen können.
Eine Hand, die auf 4 -Sets angeordnet werden kann und ein Paar "bereit" ist. Eine Hand, für die nur 1 Fliese ausgetauscht werden muss, soll "zehnpai" oder "1 von bereit" sein. Jede andere Hand hat eine Shantennummer, die ausdrückt, wie viele Fliesen ausgetauscht werden müssen, um in Tenpai zu sein. Eine Hand mit einer Shantenzahl von 1 benötigt also 1 Fliese, um zehnpai zu sein (und 2 Fliesen, um entsprechend fertig zu sein). Eine Hand mit einer Shantenzahl von 5 5 Kacheln benötigt zehnpai und so weiter.
Ich versuche, die Shantenzahl einer Hand zu berechnen. Nachdem sie stundenlang herumgegossen und mehrere Artikel und Papiere zu diesem Thema gelesen haben, scheint dies ein ungelöstes Problem zu sein (mit Ausnahme des Brute -Force -Ansatzes). Der nächstgelegene Algorithmus, den ich finden konnte, stützte sich auf den Zufall.
Regeln
Ich werde die tatsächlichen Regeln (vereinfacht) ein wenig erklären und dann meine Idee, wie man diese Aufgabe angeht. In Mahjong gibt es 4 Farben, 3 normale wie in Kartenspielen (Ace, Herz, ...), die "Mann", "Pin" und "Sou" genannt werden. Diese Farben laufen von jeweils 1 bis 9 und können verwendet werden, um Geraden sowie Gruppen derselben Art zu bilden. Die vierte Farbe wird als "Ehrungen" bezeichnet und kann nur für Gruppen derselben Art verwendet werden, aber nicht für Geraden. Die sieben Ehrungen werden "E, S, W, N, R, G, B" genannt.
Schauen wir uns ein Beispiel einer Tenpai -Hand an: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E. Als nächstes wählen wir eine E. Dies ist eine komplette Mahjong-Hand (bereit) und besteht aus einer 2-4-Pin-Straße (denken Sie daran, Stifte können für Geraden verwendet werden), ein 3-Pin-Triple, ein 5-Mann-Triple, ein W-Triple und ein E-Paar.
Ändern unserer ursprünglichen Hand leicht nach 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, Wir haben eine Hand in 1-Shanten, dh es erfordert eine zusätzliche Fliese, um zehnpai zu sein. In diesem Fall bringt uns der Austausch eines 2p gegen 3p zurück zu Tenpai, indem wir einen 3p und ein e gewinnen.
1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W ist eine Hand in 2-Shanten. Es gibt 1 abgeschlossene Triplet und 5 Paare. Wir brauchen am Ende ein Paar. Sobald wir eines von 1p, 5p, 9p, S oder W auswä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. unter der Annahme, dass wir einen 5p auswählen und den übrig gebliebenen W verwerfen, wir bekommen Folgendes: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S. Diese Hand ist in Tenpai in CAN entweder auf einem 9 -Pin oder einem S. abgeschlossen.
Um zu vermeiden, dass dieser Text noch mehr in Länge zeichnet, können Sie mehr Beispiele unter nachlesen Wikipedia oder verwenden Sie eines der verschiedenen Suchergebnisse bei Google. Alle von ihnen sind jedoch etwas technischer, daher hoffe ich, dass die obige Beschreibung ausreicht.
Algorithmus
Wie bereits erwähnt, möchte ich die Shantenzahl einer Hand berechnen. Meine Idee war es, die Fliesen nach ihrer Farbe in 4 Gruppen aufzuteilen. Als nächstes werden alle Kacheln in Sets in ihren jeweiligen Gruppen sortiert, um entweder Tripletts, Paare oder einzelne Fliesen in der Ehrengruppe oder zusätzlich Stacheln in den drei normalen Gruppen zu erhalten. Fertige Sets werden ignoriert. Paare werden gezählt, die endgültige Zahl wird abgeschlossen (wir brauchen am Ende 1 Paar). Zu dieser Nummer werden einzelne Kacheln hinzugefügt. Schließlich teilen wir die Zahl um 2 (da wir jedes Mal, wenn wir eine gute Fliese auswählen, die uns näher an Tenpai bringt, eine weitere unerwünschte Fliese loswerden können).
Ich kann jedoch nicht beweisen, dass dieser Algorithmus korrekt ist, und ich habe auch Probleme, Geraden für schwierige Gruppen einzubeziehen, die viele Kacheln im engen Bereich enthalten. Jede Art von Idee wird geschätzt. Ich entwickle in .NET, aber Pseudocode oder eine lesbare Sprache ist auch willkommen.
Lösung
Ich habe ein bisschen mehr über dieses Problem nachgedacht. Um die endgültigen Ergebnisse zu sehen, überspringen Sie den letzten Abschnitt.
Erste Idee: Brute Force -Ansatz
Zunächst schrieb ich einen brutalen 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 die Aufzählung des gesamten Raums ist selbst für nur 3-Shanten unmöglich).
Verbesserung des Brute -Force -Ansatzes
Eine Sache, die mir in den Sinn kam, war, dem brutalen Kraftansatz etwas Intelligenz zu verleihen. Der naive Weg besteht darin, eine der verbleibenden Kacheln hinzuzufügen, zu sehen, ob es Mahjong erzeugt hat, und versuchen Sie es, wenn nicht die nächste rekursiv versuchen, bis es gefunden wurde. Angenommen, es sind noch etwa 30 verschiedene Fliesen und die maximale Tiefe beträgt 6 Bearbeiten: Nach der später entwickelten Formel beträgt die maximal mögliche Shanten-Zahl (13-1)*2/3 = 8), wir bekommen (13*30)^6 Möglichkeiten, was groß ist (10^15 Reichweite).
Es ist jedoch nicht erforderlich, jede übrig gebliebene Fliese in jede Position in der Hand zu setzen. Da jede Farbe an sich abgeschlossen sein muss, können wir den jeweiligen Farbgruppen Fliesen hinzufügen und feststellen, ob die Gruppe an sich vollständig ist. Details wie genau 1 Paar insgesamt sind nicht schwer hinzuzufügen. Auf diese Weise gibt es max.
Eine bessere Lösung: Modifikation des vorhandenen Mahjong -Checker
Meine nächste Idee war es, den Code zu verwenden, den ich früh geschrieben habe, um für Mahjong zu testen und ihn auf zwei Arten zu ändern:
- Halten Sie nicht an, wenn eine ungültige Hand gefunden wird, aber notieren Sie eine fehlende Kachel
- Wenn es mehrere mögliche Möglichkeiten gibt, eine Fliese zu verwenden, probieren Sie alle aus
Dies sollte die optimale Idee sein, und mit einigen heuristischen Hinzufügen sollte es der optimale Algorithmus sein. Ich fand es jedoch ziemlich schwierig zu implementieren - es ist jedoch definitiv möglich. Ich würde es vorziehen, zuerst eine Lösung zu schreiben und zu pflegen.
Ein fortgeschrittener Ansatz mit Domänenkenntnissen
Wenn man mit einem erfahrenen Spieler gesprochen hat, gibt es anscheinend einige Gesetze, die verwendet werden können. Zum Beispiel muss ein Satz von 3 Kacheln niemals aufgelöst werden, da dies die Shantenzahl niemals verringern würde. Es kann jedoch auf unterschiedliche Weise verwendet werden (z. B. entweder für eine Kombination von 111 oder 123).
Zählen Sie alle möglichen 3-Sets auf und erstellen Sie für jede von ihnen eine neue Simulation. Entfernen Sie den 3-Set. Erstellen Sie nun alle 2-set in der resultierenden Hand und simulieren Sie für jede Fliese, die sie zu einem 3-Set-Set verbessert. Gleichzeitig simulieren Sie für jeden der 1-Sets entfernt. Machen Sie dies weiter, bis alle 3- und 2-Sets verschwunden sind. Am Ende sollte ein 1-Satz (dh eine einzelne Fliese) vorhanden sein.
Erkenntnisse aus der Implementierung und dem endgültigen Algorithmus
Ich habe den obigen Algorithmus implementiert. Für einfacheres Verständnis habe ich es in Pseudocode geschrieben:
Remove completed 3-sets
If removed, return (i.e. do not simulate NOT taking the 3-set later)
Remove 2-set by looping through discarding any other tile (this creates a number of branches in the simulation)
If removed, return (same as earlier)
Use the number of left-over single tiles to calculate the shanten number
Übrigens ist dies tatsächlich sehr ähnlich wie bei der Berechnung der Zahl selbst und offensichtlich niemals zu hohen zu hohen Zahl.
Dies funktioniert in fast allen Fällen sehr gut. Ich stellte jedoch fest, dass manchmal die frühere Annahme ("bereits abgeschlossenes 3-Sets entfernen" nie eine schlechte Idee ist) falsch. Gegenbeispiel: 23566M 25667P 159S. Der wichtige Teil ist der 25667. Durch Entfernen a 567 3-set wir haben links 6 Fliese, die zu 5-Shanten führt. Es wäre besser, zwei der einzelnen Fliesen zu verwenden, um sich zu formen 56x und 67x, insgesamt zu 4-Shanten.
Um zu beheben, müssen wir einfach die falsche Optimierung entfernen und zu diesem Code führen:
Remove completed 3-sets
Remove 2-set by looping through discarding any other tile
Use the number of left-over single tiles to calculate the shanten number
Ich glaube, das findet immer genau die kleinste Shanten -Zahl, aber ich weiß nicht, wie ich das beweisen soll. Die Zeit ist in einem "vernünftigen" Bereich (auf meiner Maschine 10 Sekunden max, normalerweise 0 Sekunden).
Der letzte Punkt ist die Berechnung des Shanten aus der Anzahl der linken Einfliesen. Zunächst ist es offensichtlich, dass die Zahl in der Form ist 3*n+1 (Weil wir mit 14 Kacheln angefangen und immer 3 Fliesen abgezogen haben).
Wenn noch 1 Fliesen übrig sind, sind wir schon Shanten (wir warten nur auf das letzte Paar). Mit 4 Kacheln müssen wir 2 davon verwerfen, um einen 3-Satz zu bilden und uns wieder mit einer einzelnen Fliese zu lassen. Dies führt zu 2 zusätzlichen Abzügen. Mit 7 Kacheln haben wir 2 Mal 2 Ablagerungen, um 4. und so weiter hinzuzufügen.
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, daher gehe ich davon aus, dass er richtig ist. Wie bereits erwähnt, kann ich es aber nicht beweisen.
Da der Algorithmus zuerst die wahrscheinlichsten Fliesenkombinationen entfernt, hat er eine integrierte Optimierung. Hinzufügen einer einfachen Prüfung if (current_depth > best_shanten) then return; Es eignet sich auch für hohe Shanten -Zahlen sehr gut.
Andere Tipps
Meine beste Vermutung wäre ein A* inspirierter Ansatz. Sie müssen eine Heuristik finden, die die Shantennummer niemals überschätzt und sie verwenden, um den Brute-Force-Baum nur in den Regionen zu durchsuchen, in denen es möglich ist, schnell genug in einen fertigen Zustand zu gelangen.
Richtige Algorithmus -Probe: syanten.cpp
Rekursive Schnittformulare von Hand in Reihenfolge: Sets, Paare, unvollständige Formen, - und zählen Sie es. In allen Variationen. Und Ergebnis ist minimaler Shantenwert aller Varianten: shanten = min (Shanten, 8 - * 2 - -)
C# Probe (von C ++ umgestellt) kann gefunden werden hier (auf Russisch).
Ich habe ein bisschen nachgedacht und eine etwas andere Formel als Mafu ausgedacht. Betrachten Sie zunächst eine Hand (eine sehr schreckliche Hand):
1s 4s 6s 1m 5m 8m 9m 9m 7p 8p West East North
Durch die Verwendung von Mafu -Algorithmus können wir nur ein Paar (9m, 9m) auswerfen. Dann bleiben wir mit 11 Singles. Wenn wir nun die MAFU-Formel anwenden, erhalten wir (11-1)*2/3, was keine Ganzzahl ist und daher keine Shanten-Zahl sein kann. Hier habe ich das ausgedacht:
N = ((s + 1) / 3) - 1
N steht für Shanten Number und s für die Score -Summe. Was ist Punktzahl? Es sind eine Reihe von Fliesen, die Sie benötigen, um ein unvollständiges Set vollständig zu machen. Wenn Sie beispielsweise (4,5) in Ihrer Hand haben, benötigen Sie entweder 3 oder 6, um es zu einem vollständigen 3-Set zu machen, das heißt nur eine Fliese. Dieses unvollständige Paar erhält also eine Punktzahl 1. Dementsprechend benötigt (1,1) nur 1, um ein 3-Set zu werden. Jede einzelne Fliese benötigt offensichtlich 2 Kacheln, um ein 3-Set zu werden, und erhält eine Punktzahl. Jede vollständige Set erhalten natürlich eine Punktzahl 0. Beachten Sie, dass wir die Möglichkeit ignorieren, dass Singles Paare werden. Wenn wir nun versuchen, alle unvollständigen Sätze in der obigen Hand zu finden, die wir erhalten:
(4s, 6s) (8m, 9m) (7p, 8p) 1s 1m 5m 9 m West East North
Dann zählen wir die Summe ihrer Bewertungen = 1*3+2*7 = 17. Wenn wir diese Zahl jetzt 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 in die andere Weise analysiert werden könnte. Zum Beispiel:
(4s, 6s) (9m, 9m) (7p, 8p) 1s 1m 5m 8 m Westost Norden
Es wird jedoch immer noch die Punktzahl 17 und 5-Shantinen gemäß der Formel erhalten. Ich kann dies auch nicht beweisen und das ist ein bisschen komplizierter als die Formel von Alexeys, aber auch Werte einführt, die auf etwas anderes angewendet werden könnten.
Festzustellen, ob Ihre Hand bereits in Tenpai ist, klingt wie a Multi-Knapsack-Problem. Gierige Algorithmen funktionieren nicht - wie Dialecticus betonte, müssen Sie den gesamten Problemraum berücksichtigen.
