¿Cómo puedo calcular el shanten número de mahjong?

Question

Esta es una continuación de mi pregunta anterior acerca de cómo decidir si una mano es listo.

Conocimiento de reglas de mahjong sería excelente, pero un poker o romme de fondo también es suficiente para entender esta pregunta.

En Mahjong 14 azulejos (azulejos son como las cartas en el Poker) están dispuestos a 4 juegos y un par.Una recta ("123") siempre utiliza exactamente 3 fichas, no más y no menos.Un conjunto de la misma clase ("111") consiste de exactamente 3 azulejos, demasiado.Este conduce a una suma de 3 * 4 + 2 = 14 las baldosas.

Hay varias excepciones, como el Kan o Trece Huérfanos que no son es pertinente aquí.Colores y rangos de valor (1-9) no son también importantes para la el algoritmo.

Una mano se compone de 13 de baldosas, cada vez es nuestro turno nos toca elegir un azulejo nuevo y tener que descartar cualquier azulejo así que nos quedamos en 13 de los azulejos - excepto si podemos ganar usando el recién elegido azulejo.

Una mano que se pueden organizar para formar 4 juegos y un par de "listo".Una mano que requiere sólo 1 de baldosas para ser intercambiados se dice que es "tenpai", o "1 de listo".Cualquier otro lado, tiene una shanten-número que expresa cuántas baldosas deben ser intercambiados a ser en tenpai.Entonces una mano con un shanten número 1 de necesidades 1 baldosas se tenpai (y 2 azulejos para estar listo, en consecuencia).Una mano con un shanten número de 5 de necesidades 5 baldosas tenpai y así sucesivamente.

Estoy tratando de calcular la shanten número de una mano.Después de googlear alrededor por horas y la lectura de varios artículos y documentos sobre este tema, este parece ser un problema sin resolver (excepto para el acercamiento de fuerza bruta).El más cercano algoritmo podía encontrar invocado oportunidad, es decir,no fue capaz de detectar la correcta shanten número de 100% del tiempo.

Reglas

Voy a explicar un poco sobre las reglas (simplificado) y, a continuación, mi idea de cómo abordar esta tarea.En mahjong, hay 4 colores, 3 normal, como en los juegos de cartas (as, corazón, ...) que se llama "hombre", "pin" y "sou".Estos colores de ejecución del 1 al 9 cada uno y pueden ser utilizados para formar las escaleras así como de los grupos de la misma especie.El cuarto color es llamado "honores" y puede ser utilizado por grupos de la misma especie, pero no por escalera.El siete de honores se llama "E, S, W, N, R, G, B".

Veamos un ejemplo de una mano tenpai: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E.A continuación podemos elegir una E.Este es un completo mahjong mano (listo) y consiste en un 2-4 pin de la calle (recuerde que el pin puede ser utilizado para escaleras), un 3 pin triple, un hombre 5 triples, un triple W y una dirección de E par.

El cambio de nuestro original un poco la mano, para 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, nos llegó una mano en 1-shanten, es decir,se requiere un adicional de baldosas se tenpai.En este caso, el intercambio de una 2p para una 3p nos trae de vuelta a tenpai por el dibujo de un 3p y un Correo ganamos.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W es una mano en 2-shanten.Hay 1 completado el triplete y 5 pares.Tenemos un par en el final, así que una vez que elija a uno de 1p, 5p, 9p, S o W tenemos que descartar a uno de los otros pares.Ejemplo:Escoger un 1 pin y descartar una W.La mano está en 1-shanten ahora y se parece a esto: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W.A continuación, vamos a esperar para que sea un 5p, 9p o S.Suponiendo que elegir un 5p y deseche el sobrante W, obtenemos esto: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S.Esta mano es en tenpai puede completar en un 9 pin o una S.

Para evitar el consumo de este texto en longitud, incluso más, puede leer más ejemplo en wikipedia o utilizando uno de los varios resultados de la búsqueda en google.Todos ellos son un poco más técnico, aunque, así que espero que la descripción anterior es suficiente.

Algoritmo

Como se ha dicho, me gustaría calcular el shanten número de una mano.Mi idea era dividir los azulejos en 4 grupos de acuerdo a su color.Siguiente, todas las fichas se ordenan en grupos, dentro de sus respectivos grupos para terminamos con cualquiera de los tríos, parejas o azulejos solo en el honor del grupo o, además, streights en los 3 grupos normales.Completado conjuntos son ignorados.Los pares son contadas, el número final se decrementa (tenemos 1 par en el extremo).Azulejos solo se agregan a este número.Finalmente, se divide el número por 2 (ya que cada vez que elija un buen mosaico que nos acerca a tenpai, podemos deshacernos de otro no deseados de la baldosa).

Sin embargo, no puedo demostrar que este algoritmo es correcto, y también tengo problemas para la incorporación de las escaleras de difícil grupos que contienen muchos azulejos en un rango cercano.Cada tipo de idea se agradece.Estoy desarrollando en .NET, pero en pseudo-código, o cualquier legible lenguaje es agradable, también.

Answer 1

He pensado acerca de este problema un poco más.Para ver los resultados finales, saltar a la última sección.

Primera idea:Aproximación De Fuerza Bruta

Primero de todo, me escribió una aproximación de fuerza bruta.Fue capaz de identificar 3-shanten dentro de un minuto, pero no era muy fiable (a veces mucho más, y la enumeración de todo el espacio es imposible, incluso para sólo 3 shanten).

Mejora de la Fuerza Bruta Enfoque

Una cosa que me vino a la mente fue a añadir algo de inteligencia para la aproximación de fuerza bruta.El ingenuo manera es añadir el resto de los azulejos, a ver si se produce Mahjong, y si no, intente la siguiente forma recursiva hasta que fue encontrado.Asumiendo que existen alrededor de 30 diferentes baldosas de la izquierda y la profundidad máxima es de 6 personas (no estoy seguro de si 7+-shanten mano, incluso, es posible [Editar:de acuerdo a la fórmula desarrollada más tarde, el máximo posible shanten número es (13-1)*2/3 = 8]), obtenemos (13*30)^6 posibilidades, que es grande (10^15 rango).

Sin embargo, no es necesario poner todos los restos de baldosas en cada posición en la mano.Ya que cada color tiene que ser completo en sí mismo, podemos añadir los azulejos a los respectivos grupos de color y anotar si el grupo está completo en sí mismo.Detalles como tener exactamente 1 par en general no son difíciles de agregar.De esta manera, existen max alrededor de (13*9)^6 posibilidades, que es de alrededor de 10^12 y más factible.

Una solución mejor:Modificación de la existente Mahjong Corrector

Mi siguiente idea fue utilizar el código que escribí a principios para la prueba de Mahjong y modificar de dos maneras:

• no se detienen cuando un inválido de la mano se encuentra, pero nota que falta una baldosa
• si hay varias formas posibles de utilizar un azulejo, probar todos ellos

Esta debe de ser la óptima idea, y con alguna heurística agregado debe ser la óptima algoritmo.Sin embargo, me pareció muy difícil de implementar - en definitiva, es posible sin embargo.Prefiero una más fácil de escribir y mantener la solución en primer lugar.

Un enfoque avanzado, utilizando el conocimiento de un dominio

Hablando con un jugador más experimentado, parece que hay algunas leyes que pueden ser utilizadas.Por ejemplo, un conjunto de 3 baldosas nunca necesita ser roto, como que nunca iba a disminuir la shanten número.Puede, sin embargo, ser utilizado de diferentes maneras (por ejemplo, para un 111 o un 123 combinación).

Enumerar todos los posibles 3-configurar y crear una nueva simulación para cada uno de ellos.Quite los 3-set.Ahora hay que crear todos los 2 en la mano resultante y simular para cada azulejo que mejora a un 3-set.Al mismo tiempo, para simular cualquiera de los 1-conjuntos de ser eliminado.Siga haciendo esto hasta que todos los 3 - y 2-conjuntos se han ido.Debe haber un 1-establecido (es decir, de una sola pieza) ser a la izquierda en la final.

Los aprendizajes de la implementación y el final del algoritmo

He implementado el algoritmo anterior.Para facilitar la comprensión de la escribí en pseudocódigo:

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

Por cierto, esto es en realidad muy similar a la de enfoque a la hora de calcular el número de mi mismo, y, obviamente, nunca a los rendimientos de un número excesivamente alto.

Esto funciona muy bien para casi todos los casos.Sin embargo, he encontrado que a veces la anterior suposición ("extracción ya completado 3-configura NUNCA es una mala idea") es incorrecta.Contra-ejemplo: 23566M 25667P 159S.La parte importante es el 25667.Mediante la eliminación de una 567 3-conjunto nos encontramos con una izquierda más 6 azulejo, que conduce a la 5-shanten.Sería mejor utilizar a dos de los azulejos solo para formar 56x y 67x, conduce a 4-shanten en general.

Para solucionarlo, solo tienes que quitar el mal de optimización, que conduce a este código:

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

Creo que este siempre con precisión encuentra el más pequeño shanten número, pero no sé cómo probar que.El tiempo está en un "razonable" de la gama (en mi máquina 10 segundos max, generalmente de 0 segundos).

El punto final es el cálculo de la shanten el número de la izquierda sobre una sola de las baldosas.Primero de todo, es evidente que el número está en la forma 3*n+1 (ya empezamos con 14 fichas y siempre se resta 3 fichas).

Si hay 1 cuadrado de la izquierda, estamos shanten ya (estamos a la espera de la final de la pareja).Con 4 fichas a la izquierda, tenemos que descartar 2 de ellos para formar una 3-set, lo que nos deja con una sola baldosa de nuevo.Esto conduce a 2 adicionales de descartes.Con 7 azulejos, tenemos 2 veces 2 descartes, la adición de 4.Y así sucesivamente.

Esto conduce a la simple fórmula de shanten_added = (number_of_singles - 1) * (2/3).

El algoritmo descrito funciona bien y aprobado todos mis exámenes, así que estoy asumiendo que es correcto.Como se ha dicho, yo no puedo probarlo, aunque.

Dado que el algoritmo elimina la mayoría de las probabilidades de combinaciones de azulejos de primera, en cierto modo tiene un built-in de optimización.La adición de una simple comprobación if (current_depth > best_shanten) then return; lo hace muy bien, incluso para la alta shanten números.

Answer 2

Mi mejor suposición sería un enfoque inspirado*. Debe encontrar algo de heurística que nunca sobreestima el número de Shanten y usarlo para buscar en el árbol de fuerza bruta solo en las regiones donde es posible entrar en un estado listo lo suficientemente rápido.

Answer 3

Muestra de algoritmo correcta: syanten.cpp

Formas de corte recursivo de la mano en orden: conjuntos, pares, formas incompletas, y cuéntelo. En todas las variaciones. Y el resultado es un valor mínimo de Shanten de todas las variantes: shanten = min (shanten, 8 - * 2 - -)

Se puede encontrar una muestra de C# (reescribida de C ++) aquí (en ruso).

Answer 4

He pensado un poco y se me ocurrió una fórmula ligeramente diferente a la de MAFU. En primer lugar, considere una mano (una mano muy terrible):

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p West East North

Al usar el algoritmo de MAFU, todo lo que podemos hacer es expulsar un par (9m, 9m). Entonces nos quedamos con 11 singles. Ahora, si aplicamos la fórmula de MAFU, obtenemos (11-1)*2/3, que no es un entero y, por lo tanto, no puede ser un número de Shanten. Aquí es donde se me ocurrió esto:

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

N significa SHANTEN Number y S para la suma de puntaje. ¿Qué es el puntaje? Es una serie de mosaicos que necesita para completar un conjunto incompleto. Por ejemplo, si tiene (4,5) en su mano, necesita 3 o 6 para que sea un 3-set completo, es decir, solo un mosaico. Entonces, este par incompleto obtiene puntaje 1. En consecuencia, (1,1) necesita solo 1 para convertirse en un 3-set. Cualquier mosaico obviamente necesita 2 mosaicos para convertirse en un 3-set y obtiene puntaje 2. Cualquier conjunto completo, por supuesto, obtenga puntaje 0. Tenga en cuenta que ignoramos la posibilidad de que los solteros se conviertan en parejas. Ahora, si intentamos encontrar todos los conjuntos incompletos en la mano anterior, obtenemos:

(4s, 6s) (8m, 9m) (7p, 8p) 1s 1m 5m 9m West East North

Luego contamos la suma de sus puntajes = 1*3+2*7 = 17. Ahora, si aplicamos este número a la fórmula anterior, obtenemos (17+1)/3 - 1 = 5, lo que significa que esta mano es 5 -Shanten . Es algo más complicado que el de Alexey y no tengo pruebas, pero hasta ahora parece funcionar para mí. Tenga en cuenta que tal mano podría analizarse de la otra manera. Por ejemplo:

(4s, 6s) (9m, 9m) (7p, 8p) 1s 1m 5m 8m West East North

Sin embargo, todavía obtiene la suma de puntaje 17 y 5-Shanten según la fórmula. Tampoco puedo probar esto y esto es un poco más complicado que la fórmula de Alexey, pero también introduce puntajes que podrían aplicarse (?) A otra cosa.

Answer 5

Determinar si su mano ya está en tenpai suena como un Problema de múltiples mocas. Los algoritmos codiciosos no funcionarán, como señaló Dialecticus, deberá considerar todo el espacio de problemas.