Como calculo o número Shanten no Mahjong?

Question

Esta é uma continuação do meu pergunta anterior sobre decidir se uma mão está pronta.

O conhecimento das regras do mahjong seria excelente, mas uma experiência baseada no pôquer ou no romme também é suficiente para entender esta questão.

Em Mahjong 14 telhas (telhas são como cartas no Poker) são organizadas em 4 conjuntos e um par.Uma reta ("123") sempre usa exatamente 3 blocos, não mais e não menos.Um conjunto do mesmo tipo ("111") consiste em exatamente 3 telhas, também.Este leva a uma soma de 3 * 4 + 2 = 14 Telhas.

Há várias exceções como Kan ou Treze Órfãos que não são relevante aqui.Cores e intervalos de valores (1-9) também não são importantes para o algoritmo.

Uma mão consiste em 13 peças, cada vez que é a nossa vez, escolhemos uma nova peça e temos que descartar qualquer peça, então ficamos com 13 peças - exceto se pudermos ganhar usando a peça recém-escolhida.

Uma mão que pode ser organizada para formar 4 conjuntos e um par está “pronta”.Uma mão que requer apenas a troca de 1 peça é chamada de "tenpai" ou "1 de pronto".Qualquer outra mão tem um número shanten que expressa quantas peças precisam ser trocadas para estar em tenpai.Portanto, uma mão com número shanten 1 precisa de 1 peça para ser tenpai (e 2 peças para estar pronta, respectivamente).Uma mão com um número shanten de 5 precisa de 5 peças para ser tenpai e assim por diante.

Estou tentando calcular o número Shanten de uma mão.Depois de pesquisar por horas e ler vários artigos e artigos sobre esse assunto, este parece ser um problema não resolvido (exceto pela abordagem de força bruta).O algoritmo mais próximo que consegui encontrar dependia do acaso, ou seja,não foi possível detectar o número Shanten correto em 100% das vezes.

Regras

Explicarei um pouco sobre as regras reais (simplificadas) e depois minha ideia de como realizar essa tarefa.No mahjong existem 4 cores, 3 normais como nos jogos de cartas (ás, copas, ...) que se chamam "man", "pin" e "sou".Essas cores vão de 1 a 9 cada e podem ser usadas para formar retas e também grupos do mesmo tipo.A quarta cor é chamada de "honras" e pode ser usada apenas para grupos do mesmo tipo, mas não para retas.As sete homenagens serão chamadas de "E, S, W, N, R, G, B".

Vejamos um exemplo de mão tenpai: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E.A seguir escolhemos um E.Esta é uma mão de mahjong completa (pronta) e consiste em uma rua de 2 a 4 pinos (lembre-se, os pinos podem ser usados ​​para sequências), um triplo de 3 pinos, um triplo de 5 homens, um triplo W e um par E.

Mudando ligeiramente a nossa mão original para 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, temos uma mão em 1-shanten, ou seja,requer uma peça adicional para ser tenpai.Neste caso, trocar um 2p por um 3p nos traz de volta ao tenpai, então comprando um 3p e um E ganhamos.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W é uma mão em 2-shanten.Há 1 trigêmeo completo e 5 pares.Precisamos de um par no final, então, depois de escolhermos um de 1p, 5p, 9p, S ou W, precisamos descartar um dos outros pares.Exemplo:Escolhemos um pino 1 e descartamos um W.A mão está em 1-shanten agora e tem esta aparência: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W.Em seguida, esperamos por 5p, 9p ou S.Supondo que escolhemos um 5p e descartamos o W restante, obtemos isto: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S.Esta mão está em tenpai e pode ser completada em 9 pinos ou S.

Para evitar prolongar ainda mais este texto, você pode ler mais exemplos em Wikipédia ou usando um dos vários resultados de pesquisa no Google.Todos eles são um pouco mais técnicos, então espero que a descrição acima seja suficiente.

Algoritmo

Conforme declarado, gostaria de calcular o número Shanten de uma mão.Minha ideia era dividir as peças em 4 grupos de acordo com a cor.Em seguida, todas as peças são classificadas em conjuntos dentro de seus respectivos grupos para terminarmos com trigêmeos, pares ou peças individuais no grupo de honra ou, adicionalmente, sequências nos 3 grupos normais.Conjuntos concluídos são ignorados.Os pares são contados, o número final é decrementado (precisamos de 1 par no final).Ladrilhos únicos são adicionados a este número.Por fim, dividimos o número por 2 (pois cada vez que escolhemos uma peça boa que nos aproxima do tenpai, podemos nos livrar de outra peça indesejada).

No entanto, não posso provar que este algoritmo está correto e também tenho dificuldade em incorporar sequências para grupos difíceis que contêm muitas peças próximas.Todo tipo de ideia é apreciado.Estou desenvolvendo em .NET, mas pseudocódigo ou qualquer linguagem legível também é bem-vindo.

Answer 1

Já pensei um pouco mais sobre esse problema.Para ver os resultados finais, pule para a última seção.

Primeira ideia:Abordagem de Força Bruta

Em primeiro lugar, escrevi uma abordagem de força bruta.Ele foi capaz de identificar 3-shanten em um minuto, mas não era muito confiável (às vezes muito mais tempo, e enumerar todo o espaço é impossível mesmo para apenas 3-shanten).

Melhoria da abordagem de força bruta

Uma coisa que me veio à mente foi adicionar um pouco de inteligência à abordagem da força bruta.A maneira ingênua é adicionar qualquer uma das peças restantes, ver se produziu Mahjong e, se não, tentar a próxima recursivamente até que seja encontrada.Supondo que restem cerca de 30 peças diferentes e a profundidade máxima seja 6 (não tenho certeza se uma mão 7+-shanten é possível [Editar:de acordo com a fórmula desenvolvida posteriormente, o número Shanten máximo possível é (13-1)*2/3 = 8]), obtemos (13*30)^6 possibilidades, o que é grande (intervalo de 10^15).

No entanto, não há necessidade de colocar todas as peças restantes em todas as posições da sua mão.Como cada cor deve ser completa por si só, podemos adicionar peças aos respectivos grupos de cores e anotar se o grupo está completo por si só.Detalhes como ter exatamente 1 par no total não são difíceis de adicionar.Dessa forma, existem no máximo (13*9)^6 possibilidades, ou seja, cerca de 10^12 e mais viáveis.

Uma solução melhor:Modificação do Mahjong Checker existente

Minha próxima ideia foi usar o código que escrevi anteriormente para testar o Mahjong e modificá-lo de duas maneiras:

• não pare quando uma mão inválida for encontrada, mas anote uma peça faltante
• se houver várias maneiras possíveis de usar um bloco, experimente todas elas

Esta deve ser a ideia ideal e, com alguma heurística adicionada, deve ser o algoritmo ideal.No entanto, achei muito difícil de implementar - embora seja definitivamente possível.Eu preferiria primeiro uma solução mais fácil de escrever e manter.

Uma abordagem avançada usando conhecimento de domínio

Conversando com um jogador mais experiente, parece que existem algumas leis que podem ser utilizadas.Por exemplo, um conjunto de 3 peças nunca precisa ser quebrado, pois isso nunca diminuiria o número de shanten.Pode, no entanto, ser utilizado de diferentes maneiras (por exemplo, para uma combinação 111 ou 123).

Enumere todos os 3 conjuntos possíveis e crie uma nova simulação para cada um deles.Remova o conjunto de 3.Agora crie todos os 2 conjuntos na mão resultante e simule para cada peça que os melhore para um conjunto de 3.Ao mesmo tempo, simule para qualquer um dos conjuntos 1 sendo removidos.Continue fazendo isso até que todos os conjuntos de 3 e 2 acabem.Deve haver um conjunto 1 (ou seja, uma única peça) no final.

Aprendizados da implementação e algoritmo final

Eu implementei o algoritmo acima.Para facilitar a compreensão, anotei em 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

A propósito, isso é na verdade muito semelhante à abordagem que utilizo ao calcular o número sozinho e, obviamente, nunca resulta em um número muito alto.

Isso funciona muito bem para quase todos os casos.No entanto, descobri que às vezes a suposição anterior (“remover 3 séries já concluídas NUNCA é uma má ideia”) está errada.Contra-exemplo: 23566M 25667P 159S.A parte importante é a 25667.Ao remover um 567 3 conjuntos acabamos com uma sobra 6 telha, levando a 5-shanten.Seria melhor usar duas peças individuais para formar 56x e 67x, levando a 4-shanten no geral.

Para corrigir, precisamos simplesmente remover a otimização errada, levando 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

Acredito que isso sempre encontra com precisão o menor número Shanten, mas não sei como provar isso.O tempo gasto está em uma faixa "razoável" (na minha máquina, no máximo 10 segundos, geralmente 0 segundos).

O ponto final é calcular o shanten a partir do número de peças únicas que sobraram.Em primeiro lugar, é óbvio que o número está na forma 3*n+1 (porque começamos com 14 peças e sempre subtraímos 3 peças).

Se sobrar 1 peça, já estamos shanten (estamos apenas esperando o par final).Com 4 peças restantes, temos que descartar 2 delas para formar um conjunto de 3, ficando novamente com uma única peça.Isso leva a 2 descartes adicionais.Com 7 peças, temos 2 vezes 2 descartes, somando 4.E assim por diante.

Isso leva à fórmula simples shanten_added = (number_of_singles - 1) * (2/3).

O algoritmo descrito funciona bem e passou em todos os meus testes, então presumo que esteja correto.Como afirmado, não posso provar isso.

Como o algoritmo remove primeiro as combinações de peças mais prováveis, ele tem uma otimização integrada.Adicionando uma verificação simples if (current_depth > best_shanten) then return; funciona muito bem mesmo para números elevados de shanten.

Answer 2

Meu melhor palpite seria uma abordagem inspirada em A*.Você precisa encontrar alguma heurística que nunca superestime o número de Shanten e usá-la para pesquisar a árvore de força bruta apenas nas regiões onde é possível entrar em estado de prontidão com rapidez suficiente.

Answer 3

Amostra de algoritmo correta: syanten.cpp

Corte recursivo de formas manuais em ordem:conjuntos, pares, formas incompletas - e conte-os.Em todas as variações.E o resultado é o valor mínimo de Shanten de todas as variantes:Shanten = Min(Shanten, 8 - * 2 - - )

Amostra C# (reescrita de c++) pode ser encontrada aqui (em russo).

Answer 4

Pensei um pouco e descobri uma fórmula um pouco diferente da de mafu.Primeiro de tudo, considere uma mão (uma mão muito terrível):

1s 4s 6s 1m 5m 8m 9m 9m 7p 8p Oeste Leste Norte

Usando o algoritmo do mafu, tudo o que podemos fazer é lançar um par (9m,9m).Então ficamos com 11 singles.Agora, se aplicarmos a fórmula de mafu, obteremos (11-1)*2/3 que não é um número inteiro e, portanto, não pode ser um número Shanten.Foi aqui que eu descobri isso:

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

N significa número Shanten e S significa soma de pontuação.O que é pontuação?É uma série de peças que você precisa para completar um conjunto incompleto.Por exemplo, se você tem (4,5) em sua mão, você precisa de 3 ou 6 para formar um conjunto completo de 3, ou seja, apenas uma peça.Portanto, este par incompleto recebe pontuação 1.Conseqüentemente, (1,1) precisa apenas de 1 para se tornar um conjunto de 3.Qualquer peça única obviamente precisa de 2 peças para se tornar um conjunto de 3 e obter pontuação 2.Qualquer conjunto completo, é claro, recebe pontuação 0.Observe que ignoramos a possibilidade de os solteiros se tornarem pares.Agora, se tentarmos encontrar todos os conjuntos incompletos na mão acima, obteremos:

(4s,6s) (8m,9m) (7p,8p) 1s 1m 5m 9m Oeste Leste Norte

Então contamos a soma de suas pontuações = 1*3+2*7 = 17.Agora, se aplicarmos este número à fórmula acima, obteremos (17+1)/3 - 1 = 5, o que significa que esta mão é 5-shanten.É um pouco mais complicado que o de Alexey e não tenho provas, mas até agora parece funcionar para mim.Observe que tal mão poderia ser analisada de outra maneira.Por exemplo:

(4s,6s) (9m,9m) (7p,8p) 1s 1m 5m 8m Oeste Leste Norte

No entanto, ainda obtém pontuação soma 17 e 5-shanten de acordo com a fórmula.Também não posso provar isso e é um pouco mais complicado do que a fórmula de Alexey, mas também apresenta pontuações que podem ser aplicadas (?) a outra coisa.

Answer 5

Determinar se sua mão já está em tenpai soa como um problema de múltiplas mochilas.Algoritmos gananciosos não funcionarão – como apontou Dialecticus, você precisará considerar todo o espaço do problema.