Tanhinmin (jap. 単貧民; dt. Einzelne*r Arme*r) ist eine vereinfachte Abwandlung des populären[1] japanischen Kartenspieles Daihinmin (jap. 大貧民; dt. Gewaltige*r Arme*r) manchmal auch Daifugō (jap. 大富豪; dt. Gewaltige*r Superreiche*r). Bei diesen Spielen handelt es sich um Ablegespiele.
Tanhinmin wurde von Junji Nishino zum ersten Mal 2007 auf dem 12. Spieleentwicklungsworkshop (jap. ゲームプログラミングワークショップ) der Information Processing Society of Japan vorgestellt. Das Ziel ist mittels Tanhinmin Daihinmin zu erforschen[2].
Tanhinmin wird mit Karten mit strenger Halbordnung gespielt. Es benötigt mindestens 2 Personen, kann aber in beliebig großen Gruppen gespielt werden. Alle Karten werden an die Spielenden ausgeteilt. Dies muss nicht gleichmäßig sein.
Das Spiel ist in Züge unterteilt, die reihum gehen. Wer den ersten Zug spielt, ist nicht durch die Regeln definiert und muss entsprechend anderweitig festgelegt werden.[3]
Ein Spielzug besteht darin eine Karte zu spielen oder auszusetzen. In jedem Zug kann ausgesetzt werden. Spielt man eine Karte, wird genau eine gespielt. Dabei muss diese einen größeren Wert haben als die zuletzt gespielte Karte auf dem Tisch. Liegt keine Karte auf dem Tisch, kann eine beliebige Karte gespielt werden.
Hat seit dem letzten eigenen Zug kein Mitspielender eine Karte gelegt, so wird der Tisch geleert und man kann eine beliebe Karte auf den nun leeren Tisch spielen.[2:1]
Die Spieler*in, die zuerst ihre letzte Karte ablegt, gewinnt das Spiel.[2:2]
Aufgrund der weiten Verbreitung von Daihinmin gibt es viele Varianten. Der UECda-Wettbewerb, der seit 2006[4] abgehalten wird und bei dem Computer gegeneinander antreten, hat ein Regelwerk, welches die Version von Daihinmin definiert, auf der Tanhinmin basiert.
Es wird mit einem 52-Karten-Deck und einer Jokerkarte gespielt. Im Wettbewerb wird mit 5 Spieler*innen gespielt.
In Daihinmin besteht keine Einschränkung auf eine Karte pro Zug. Es dürfen beliebig viele gleiche Karten oder beliebig lange Straßen gelegt werden. Die Länge der Straße oder Größe des Paares muss der auf dem Tisch gelegten entsprechen, falls bereits auf ihn gelegt wurde.[5]
Es gibt noch viele weitere Regeln, vor allem ein Rangsystem, das nach jeder Runde die Nächste beeinflusst[5:1].
Jedes Spiel von Tanhinmin hat eine Gewinner*in[2:3]. Dies liegt darin begründet, dass jede Karte irgendwann legbar wird, da der Tisch geleert wird, wenn nichts gelegt wird, und dass irgendwann eine Person als erste ihre letzte Karte legt, da das Legen vorher nicht endet. Insbesondere kann es kein Unentschieden geben, da keine zwei Spieler*innen gleichzeitig Karten legen können.
Die Menge aller Karten ist allen Spieler*innen bekannt. Folglich kann man die Karten der Gegenspieler*in ermitteln, wenn es nur zwei Spieler*innen gibt[2:4].
Da für zwei Spieler*innen Tanhinmin zu einem Spiel mit vollständiger Information wird, kann hier eine eindeutige Gewinner*in ermittelt werden[2:5].
Der Algorithmus benutzt dafür einen Algorithmus zum Ermitteln maximaler Matchings in bipartiten Graphen, die der Algorithmus für die Spielsituation konstruiert.
Spieler*in hat eine Gewinnstrategie genau dann, wenn der Spielgraph von ein größeres Matching als der Spielgraph von hat.[2:6]
Der zu konstruierende Graph ist ungerichtet und bipartit. Die Knoten bilden die Spielkarten auf den Händen der Spieler*innen mit Ausnahme der schwächsten Karte der Gegenspieler*in. Für Spieler*in , die zuerst ihren Zug ausführt, wird zudem noch die Karte auf dem Tisch als Knoten behandelt. Liegt keine Karte auf dem Tisch, wird eine 0 repräsentativ für eine Karte, die schwächer als alle anderen Karten ist, für diese Rolle genutzt.
Kanten werden nach dem Prinzip 'Mögliche Antworten' gebildet: Kanten werden zwischen den stärkeren Karten der Spieler*in und schwächeren Karten der Gegenspieler*in oder der gegebenenfalls schwächeren Karte auf dem Tisch gebildet.
Da mit den Graphen mögliche Antworten modelliert werden, ist eine Antwort auf die letzte Karte der Gegenspieler*in uninteressant. Deshalb ignorieren wir eine ihrer Karten, was durch das Entfernen der schwächsten ihrer Karten geschehen ist. Es wird keine andere stattdessen entfernt, da das Blatt der Gegenspieler*in sonst künstlich schlechter dargestellt würde, als es ist, wodurch der Algorithmus ein falsches Ergebnis liefern würde.
Sei ein ungerichteter bipartiter Graph für eine Spieler*in. ist folgendermaßen definiert:
Seien und Mengen und die Kartendecks der Spieler*innen und , wobei das Kartendeck der Spieler*in sei, die den nächsten Zug macht. Sei weiter die Karte auf dem Tisch oder 0, falls dort keine ist. Zuletzt sei die Stärkerelation der Karten. Dann ist der Spielgraph der Spieler*innen
:
: [2:8]
Da die Regeln von Tanhinmin denen von Daihinmin nicht widersprechen, können Spiele von Daihinmin als Tanhinmin betrachtet werden, wenn keine Züge mit mehreren Karten möglich sind oder andere Sonderregeln andere Züge erlauben.
In einigen Fällen kann dieser Algorithmus also auch bei Daihinmin zum Bestimmen der Gewinner*in genutzt werden. Allerdings auch nur bei 2 Personen, da die volle Information benötigt wird.[2:9]
"UECda about the contest," (in Japanisch), UECda-2023. http://www.tnlab.inf.uec.ac.jp/daihinmin/2023/intro.html (Zugriff: 6.2.2024) ↩︎
H. Kiya, K. Ohto, H. Ono, "Computing the Winner of 2-Player TANHINMIN," (in Englisch), IEICE TRANS. FUNDAMENTALS, Bd. E104-A, Nr. 9, S. 1134-1141, Sep., 2021, doi: 10.1587/transfun.2020DMP0026 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
H. Kiya, H. Ono, "2人単貧民の必勝判定とその拡張," (in Japanisch), 講究録, Nr. 2088, S. 23-26, Feb. 2018. [Online]. Verfügbar: https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2088-04.pdf ↩︎
"UECda frequently asked questions," (in Japanisch), UECda-2023. http://www.tnlab.inf.uec.ac.jp/daihinmin/2023/faq.html (Zugriff: 6.2.2024) ↩︎
"UECda the UEC standard rule," (in Japanisch), UECda-2023. http://www.tnlab.inf.uec.ac.jp/daihinmin/2023/document_rules.html (Zugriff: 6.2.2024) ↩︎ ↩︎