Come si calcola il numero di Shanten in Mahjong?

Question

Questo è un seguito al mio Domanda precedente sul decidere se una mano è pronta.

La conoscenza delle regole di Mahjong sarebbe eccellente, ma anche un background basato su poker o Romme è sufficiente per comprendere questa domanda.

In Mahjong 14 piastrelle (le piastrelle sono come carte nel poker) sono disposte a 4 set e una coppia. Un dritto ("123") utilizza sempre esattamente 3 piastrelle, non più e non meno. Un insieme dello stesso tipo ("111") è costituito anche da esattamente 3 piastrelle. Questo porta a una somma di 3 * 4 + 2 = 14 tessere.

Ci sono varie eccezioni come Kan o tredici orfani che non sono rilevanti qui. Anche i colori e gli intervalli di valore (1-9) non sono importanti per l'algoritmo.

Una mano è composta da 13 piastrelle, ogni volta che è il nostro turno, possiamo scegliere una nuova piastrella e doverlo scartare qualsiasi piastrella in modo da rimanere su 13 tessere, tranne se possiamo vincere usando le piastrelle appena scelte.

Una mano che può essere organizzata per formare 4 set e una coppia è "pronta". Si dice che una mano che richiede solo 1 piastrella da scambiare sia "Tenpai" o "1 da Ready". Qualsiasi altra mano ha un numero di shanten che esprime quante piastrelle devono essere scambiate per essere a Tenpai. Quindi una mano con un numero shanten di 1 ha bisogno di 1 piastrella per essere tenpai (e 2 piastrelle per essere pronte, di conseguenza). Una mano con un numero shanten di 5 ha bisogno di 5 piastrelle per essere Tenpai e così via.

Sto cercando di calcolare il numero di una mano. Dopo aver cercato su Google per ore e aver letto più articoli e articoli su questo argomento, questo sembra essere un problema irrisolto (ad eccezione dell'approccio della forza bruta). L'algoritmo più vicino che ho potuto trovare affidata al caso, cioè non è stato in grado di rilevare il numero di Shanten corretto al 100% delle volte.

Regole

Spiegherò un po 'le regole effettive (semplificate) e quindi la mia idea su come affrontare questo compito. A Mahjong, ci sono 4 colori, 3 normali come nei giochi di carte (Ace, Heart, ...) che sono chiamati "Man", "Pin" e "Sou". Questi colori vanno da 1 a 9 ciascuno e possono essere usati per formare rettilinei e gruppi dello stesso tipo. Il Forth Color è chiamato "onori" e può essere usato solo per gruppi dello stesso tipo, ma non per rettilinei. I sette onori saranno chiamati "E, S, W, N, R, G, B".

Diamo un'occhiata a un esempio di una mano Tenpai: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E. Successivamente scegliamo un E. Questa è una mano Mahjong completa (pronta) ed è costituita da una strada da 2-4 pin (ricorda, i pin possono essere usati per i rettilinei), una tripla a 3 pin, una tripla da 5 uomini, una tripla W e una coppia E.

Cambiando leggermente la nostra mano originale a 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, abbiamo ottenuto una mano in 1-shenten, cioè richiede che una piastrella aggiuntiva sia Tenpai. In questo caso, lo scambio di un 2p con un 3p ci riporta a Tenpai, quindi disegnando un 3p e un e vinciamo.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W è una mano in 2-shaten. C'è 1 tripletta completata e 5 coppie. Alla fine abbiamo bisogno di una coppia, quindi una volta che scegliamo uno di 1p, 5p, 9p, s o w dobbiamo scartare una delle altre coppie. Esempio: scegliamo un pin e scartiamo un W. La mano è in 1-shaten ora e sembra così: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W. Successivamente, aspettiamo un 5p, 9p o S. supponendo che scegliamo un 5p e scartiamo il rimanente W, otteniamo questo: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S. Questa mano è a Tenpai in può completare su un pin a 9 o un S.

Per evitare di disegnare ancora di più questo testo, puoi leggere più esempio a Wikipedia o utilizzando uno dei vari risultati di ricerca su Google. Tutti sono un po 'più tecnici, quindi spero che la descrizione di cui sopra sia.

Algoritmo

Come affermato, vorrei calcolare il numero di una mano. La mia idea era quella di dividere le piastrelle in 4 gruppi in base al loro colore. Successivamente, tutte le piastrelle vengono ordinate in insiemi all'interno dei rispettivi gruppi per finire con terzine, coppie o piastrelle singole nel gruppo d'onore o, inoltre, Streights nei 3 gruppi normali. I set completati vengono ignorati. Le coppie vengono contate, il numero finale viene decrementato (alla fine abbiamo bisogno di 1 coppia). Le piastrelle singole vengono aggiunte a questo numero. Infine, dividiamo il numero per 2 (poiché ogni volta che scegliamo una buona piastrella che ci avvicina a Tenpai, possiamo sbarazzarci di un'altra piastrella indesiderata).

Tuttavia, non posso dimostrare che questo algoritmo è corretto e ho anche problemi a incorporare rettilinei per gruppi difficili che contengono molte piastrelle a distanza ravvicinata. Ogni tipo di idea è apprezzato. Sto sviluppando in .NET, ma anche il codice pseudo o qualsiasi linguaggio leggibile è il benvenuto.

Answer 1

Ho pensato a questo problema un po 'di più. Per vedere i risultati finali, passa all'ultima sezione.

Prima idea: approccio alla forza bruta

Prima di tutto, ho scritto un approccio alla forza bruta. È stato in grado di identificare 3-shaten in un minuto, ma non era molto affidabile (a volte molto più lungo ed elencare l'intero spazio è impossibile anche per solo 3-shaten).

Miglioramento dell'approccio della forza bruta

Una cosa che mi è venuta in mente è stata quella di aggiungere un po 'di intelligenza all'approccio della forza bruta. Il modo ingenuo è quello di aggiungere una qualsiasi delle tessere rimanenti, vedere se ha prodotto Mahjong e, se non provare il prossimo fino a quando non è stato trovato. Supponendo che ci siano circa 30 piastrelle diverse rimaste e la profondità massima è 6 (non sono sicuro che una mano 7+-shanten sia persino possibile EDIT: Secondo la formula sviluppata in seguito, il numero SHENEN massimo possibile è (13-1)*2/3 = 8), otteniamo (13*30)^6 possibilità, che è grande (10^15 intervallo).

Tuttavia, non è necessario mettere tutte le piastrelle rimanenti in ogni posizione in mano. Poiché ogni colore deve essere completo in sé, possiamo aggiungere piastrelle ai rispettivi gruppi di colori e annotare se il gruppo è completo in sé. I dettagli come avere esattamente 1 coppia complessiva non sono difficili da aggiungere. In questo modo, ci sono Max intorno (13*9)^6 possibilità, ovvero circa 10^12 e più fattibili.

Una soluzione migliore: modifica del controllo Mahjong esistente

La mia prossima idea era quella di usare il codice che ho scritto presto per testare Mahjong e modificarlo in due modi:

• Non fermarti quando viene trovata una mano non valida ma annota una piastrella mancante
• Se ci sono più modi possibili per utilizzare una piastrella, provali tutti

Questa dovrebbe essere l'idea ottimale, e con alcuni euristici aggiunti dovrebbe essere l'algoritmo ottimale. Tuttavia, ho trovato abbastanza difficile da implementare - però è sicuramente possibile. Preferirei prima scrivere e mantenere una soluzione.

Un approccio avanzato che utilizza la conoscenza del dominio

Parlando con un giocatore più esperto, sembra che ci siano alcune leggi che possono essere utilizzate. Ad esempio, un set di 3 piastrelle non deve mai essere rotta, poiché ciò non diminuirebbe mai il numero di Shanten. Tuttavia, può essere usato in diversi modi (diciamo, sia per una combinazione 111 o 123).

Enumera tutti i 3 set possibili e crea una nuova simulazione per ciascuno di essi. Rimuovere il 3 set. Ora crea tutti i 2 set nella mano risultante e simula per ogni piastrella che li migliora in un 3 set. Allo stesso tempo, simula per qualsiasi 1 set rimosso. Continua a farlo fino a quando tutti i 3 e 2 set non saranno spariti. Dovrebbe esserci un 1 set (cioè una singola piastrella) è lasciata alla fine.

Apprendimenti dall'implementazione e algoritmo finale

Ho implementato l'algoritmo di cui sopra. Per una comprensione più facile l'ho scritto in pseudocodice:

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

A proposito, questo è in realtà molto simile all'approccio che adotto durante il calcolo del numero da solo, e ovviamente non produce mai un numero troppo alto.

Funziona molto bene per quasi tutti i casi. Tuttavia, ho scoperto che a volte l'assunzione precedente ("rimuovere i 3 set già completati non è mai una cattiva idea") è sbagliato. Contro-esempi: 23566M 25667P 159S. La parte importante è il 25667. Rimuovendo a 567 3-set finiamo con un rimprovero 6 piastrelle, portando a 5-shenten. Sarebbe meglio usare due delle singole piastrelle per formarsi 56x e 67x, portando a 4-shaten in generale.

Per risolvere, dobbiamo semplicemente rimuovere l'ottimizzazione sbagliata, portando a questo codice:

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

Credo che questo trovi sempre accuratamente il numero più piccolo shanten, ma non so come dimostrarlo. Il tempo impiegato è in un intervallo "ragionevole" (sulla mia macchina 10 secondi massimi, di solito 0 secondi).

Il punto finale sta calcolando lo shanten dal numero di piastrelle singole sinistro. Prima di tutto, è ovvio che il numero è nella forma 3*n+1 (Perché abbiamo iniziato con 14 piastrelle e abbiamo sempre sottratto 3 piastrelle).

Se restano 1 piastrella, siamo già shanten (stiamo solo aspettando la coppia finale). Con 4 piastrelle rimaste, dobbiamo scartarle 2 per formare un 3 set, lasciandoci di nuovo con una singola piastrella. Questo porta a 2 scarti aggiuntivi. Con 7 piastrelle, abbiamo 2 volte 2 scarti, aggiungendo 4. e così via.

Questo porta alla formula semplice shanten_added = (number_of_singles - 1) * (2/3).

L'algoritmo descritto funziona bene e ha superato tutti i miei test, quindi suppongo che sia corretto. Come affermato, non posso provarlo però.

Poiché l'algoritmo rimuove prima le combinazioni di tessere più probabili, ha un'ottimizzazione integrata. Aggiunta di un semplice controllo if (current_depth > best_shanten) then return; Fa molto bene anche per numeri elevati.

Answer 2

La mia ipotesi migliore sarebbe un approccio A* ispirato. Devi trovare un po 'di euristica che non sopravvaluta mai il numero di Shanten e usarlo per cercare sull'albero della forza bruta solo nelle regioni in cui è possibile entrare in uno stato pronto abbastanza rapidamente.

Answer 3

Campione di algoritmo corretto: syanten.cpp

Forme di taglio ricorsive di mano in ordine: set, coppie, forme incomplete, e contalo. In tutte le variazioni. E il risultato è un valore minimo shanten di tutte le varianti: shanten = min (shanten, 8 - * 2 - -)

È possibile trovare il campione C# (riscriverato da C ++) qui (in russo).

Answer 4

Ho fatto un po 'di pensiero e ho trovato una formula leggermente diversa da quella di Mafu. Prima di tutto, considera una mano (una mano molto terribile):

1S 4S 6S 1M 5m 8m 9m 9m 7p 8p Ovest Est North

Usando l'algoritmo di Mafu tutto ciò che possiamo fare è scacciare una coppia (9 m, 9m). Quindi ci restano 11 singoli. Ora, se applichiamo la formula di Mafu, otteniamo (11-1)*2/3 che non è un numero intero e quindi non può essere un numero shanten. Qui è dove mi è venuto in mente questo:

N = ((s + 1) / 3) - 1

N sta per il numero di Shanten e S per la somma del punteggio. Cos'è il punteggio? Sono un numero di tessere che devi completare un set incompleto. Ad esempio, se hai (4,5) in mano, hai bisogno di 3 o 6 per renderlo un 3 set completo, cioè solo una piastrella. Quindi questa coppia incompleta ottiene il punteggio 1. Di conseguenza, (1,1) necessita solo di 1 per diventare un 3 set. Ogni singola piastrella ha ovviamente bisogno di 2 piastrelle per diventare un 3 set e ottiene il punteggio 2. Qualsiasi set completo ovviamente ottiene il punteggio 0. Si noti che ignoriamo la possibilità che i singoli diventino coppie. Ora, se proviamo a trovare tutti i set incompleti nella mano sopra che otteniamo:

(4s, 6s) (8m, 9m) (7p, 8p) 1S 1M 5m 9m Ovest Est North

Quindi contiamo la somma dei suoi punteggi = 1*3+2*7 = 17. Ora se applichiamo questo numero alla formula sopra otteniamo (17+1)/3 - 1 = 5 che significa che questa mano è 5 -shanten . È un po 'più complicato di quello di Alexey e non ho prove, ma finora sembra funzionare per me. Si noti che una tale mano potrebbe essere analizzata dall'altra parte. Per esempio:

(4s, 6s) (9m, 9m) (7p, 8p) 1S 1M 5m 8m Ovest Est North

Tuttavia, ottiene ancora la somma del punteggio 17 e 5-shaten secondo la formula. Inoltre non posso provarlo e questo è un po 'più complicato della formula di Alexey, ma introduce anche punteggi che potrebbero essere applicati (?) A qualcos'altro.

Answer 5

Determinare se la tua mano è già in Tenpai sembra un Problema multi-inganno. Gli algoritmi avidi non funzionano - come ha sottolineato Dialetticus, dovrai considerare l'intero spazio del problema.