Как рассчитать число шантенов в маджонге?

Question

Это продолжение моего предыдущего вопроса о решении, готова ли рука .

Знание правил маджонга было бы превосходным, но для понимания этого вопроса также достаточно знаний о покере или роме.

В Маджонг 14 плиток (плитки как карты в покер) расставлены по 4 сетам и пара. Стрит ("123") всегда использует ровно 3 плитки, не больше и не Меньше. Набор того же вида («111») тоже состоит ровно из 3 плиток. это приводит к сумме 3 * 4 + 2 = 14 плитка.

Существуют различные исключения, такие как Кан или тринадцать сирот, которые не являются здесь актуально. Цвета и диапазоны значений (1-9) также не важны для Алгоритм.

Рука состоит из 13 фишек, каждый раз, когда наступает наш ход, мы выбираем новую фишку и вынуждены сбрасывать любую фишку, поэтому мы остаемся на 13 фишках - кроме случаев, когда мы можем выиграть, используя вновь выбранную фишку.

Рука, которая может быть организована в 4 набора, и пара «готова». Рука, для которой требуется обмен только 1 плитки, называется «тенпай» или «1 с готового». Любая другая рука имеет число shanten, которое выражает, сколько плиток нужно обменять, чтобы быть в тенпай. Таким образом, рука с shanten числом 1 нуждается в 1 плитке, чтобы быть tenpai (и 2 плитки, чтобы быть готовыми, соответственно). Рука с числом shanten 5 нуждается в 5 тайлах, чтобы быть tenpai и так далее.

Я пытаюсь подсчитать число рук в руке. После нескольких часов поиска в Google и прочтения нескольких статей и статей на эту тему, эта проблема, похоже, остается нерешенной (за исключением подхода грубой силы). Самый близкий алгоритм, который я мог найти, основывался на случайности, то есть он не мог определить правильное число Шента в 100% случаев.

Правила

Я немного объясню действительные правила (упрощенно), а затем свою идею, как решить эту задачу. В маджонге есть 4 цвета, 3 нормальных, как в карточных играх (туз, сердце, ...), которые называются «человек», «булавка» и «су». Эти цвета варьируются от 1 до 9 каждый и могут использоваться для формирования прямых, а также групп одного и того же вида. Четвертый цвет называется «отличием» и может использоваться только для групп одного типа, но не для прямых. Семь почестей будут называться "E, S, W, N, R, G, B".

Давайте рассмотрим пример руки тенпая: 2p, 3p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E. Далее мы выбираем E. Это полная рука маджонга (готовая), состоящая из улицы с 2-4 булавками (помните, булавки можно использовать для стритов), тройки с 3 булавками, тройки с 5 игроками, тройки W и пары E.

Немного изменив нашу исходную руку на 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, мы получили 1-shanten, т. Е. Для получения тенпая требуется дополнительная плитка. В этом случае обмен 2p на 3p возвращает нас к тенпаю, поэтому, выиграв 3p и E, мы выигрываем.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W - это рука в 2 шанте. Есть 1 законченный триплет и 5 пар. В конце концов нам нужна одна пара, поэтому, как только мы выберем одну из 1p, 5p, 9p, S или W, нам нужно сбросить одну из других пар. Пример: мы выбираем 1 булавку и сбрасываем букву W. Рука теперь 1-shanten и выглядит следующим образом: 1p, 1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W. Затем мы ждем 5p, 9p или S. Предполагая, что мы выберем 5p и отбросим остаток W, мы получим следующее: 1p, 1p, 1p, 5p, 5p, 5p, 9p, 9p, E, E, E, S, S. Эта рука в тенпай может быть завершена на 9 булавках или на S.

Чтобы не рисовать этот текст еще длиннее, вы можете прочитать больше примеров на википедии или использовать один из различных результатов поиска в Google. Все они немного более техничны, поэтому я надеюсь, что приведенного выше описания достаточно.

Алгоритм

Как уже говорилось, я хотел бы подсчитать число рук в руке. Моя идея состояла в том, чтобы разбить плитки на 4 группы в соответствии с их цветом. Далее, все тайлы сортируются в наборы в соответствующих группах, и в итоге мы получаем либо тройки, пары или отдельные тайлы в группе чести, либо, дополнительно, стриты в 3 нормальных группах. Завершенные наборы игнорируются. Пары подсчитываются, окончательное число уменьшается (нам нужна 1 пара в конце). К этому номеру добавляются отдельные плитки. Наконец, мы делим число на 2 (так как каждый раз, когда мы выбираем хорошую плитку, которая приближает нас к тенпаю, мы можем избавиться от другой нежелательной плитки).

Однако я не могу доказать, что этот алгоритм корректен, и у меня также возникают проблемы с включением прямых для сложных групп, которые содержат много плиток с близкого расстояния. Любая идея приветствуется. Я занимаюсь разработкой в ​​.NET, но также приветствуется псевдокод или любой читаемый язык.

Answer 1

Я думал об этой проблеме немного больше.Чтобы увидеть окончательные результаты, перейдите к последнему разделу.

Первая идея: метод грубой силы

Прежде всего, я написал метод грубой силы.Он мог идентифицировать 3-shanten в течение минуты, но он был не очень надежным (иногда слишком длинным, и перечисление всего пространства невозможно даже для 3-shanten).

Улучшение грубой силыПодход

Одна вещь, которая пришла в голову, это добавить некоторый интеллект к подходу грубой силы.Наивный способ - добавить любую из оставшихся плиток, посмотреть, произвел ли он Маджонг, и если нет, попробовать следующую рекурсивную процедуру, пока она не была найдена.Предполагая, что осталось около 30 различных плиток, а максимальная глубина равна 6 (я не уверен, возможна ли даже комбинация с 7 + шантами [Редактировать: в соответствии с формулой, разработанной позже, максимально возможное число шантов составляет (13-1) * 2/3 = 8] ), мы получаем (13 * 30) ^ 6 возможностей, что является большим (диапазон 10 ^ 15).

Однако нет необходимостиположить каждую оставшуюся плитку в каждой позиции в вашей руке.Поскольку каждый цвет должен быть завершен сам по себе, мы можем добавить плитки в соответствующие цветовые группы и записать, является ли группа завершенной сама по себе.Такие детали, как наличие ровно 1 пары в целом, добавить несложно.Таким образом, существует максимум около (13 * 9) ^ 6 возможностей, то есть около 10 ^ 12 и более выполнимых.

Лучшее решение: модификация существующей проверки Маджонга

Мой следующийИдея заключалась в том, чтобы использовать код, который я написал ранее, для проверки Маджонга и изменить его двумя способами:

• не останавливаться при обнаружении недействительной руки, а записывать недостающую плитку
• если есть несколько возможных способов использования тайла, попробуйте все из них

Это должно быть оптимальной идеей, а с добавленной эвристикой - оптимальным алгоритмом.Тем не менее, я нашел, что это довольно сложно реализовать - хотя, безусловно, возможно.Я предпочел бы, чтобы сначала было проще написать и поддерживать решение.

Продвинутый подход, использующий знание предметной области

Говоря с более опытным игроком, кажется, есть некоторые законы, которые можно использовать.Например, набор из 3 плиток никогда не нужно разбивать, так как это никогда не уменьшит число шантов.Однако его можно использовать по-разному (скажем, для комбинации 111 или 123).

Перечислите все возможные 3-множества и создайте новую симуляцию для каждого из них.Снимите 3 набора.Теперь создайте все 2 набора в получившейся руке и смоделируйте для каждой плитки, которая улучшает их до 3 набора.В то же время, симулируйте для любого из 1 удаляемых наборов.Продолжайте делать это, пока не исчезнут все 3- и 2-сеты.В конце должен быть оставлен 1 набор (то есть одна плитка).

Извлечения из реализации и окончательного алгоритма

Я реализовал вышеупомянутый алгоритм.Для облегчения понимания я записал это в псевдокоде:

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

Кстати, это на самом деле очень похоже на подход, который я использую при вычислении числа самостоятельно, и, очевидно, никогда не приводит к получению слишком большого числа.

Это работает очень хорошо почти во всех случаях.Однако я обнаружил, что иногда более раннее предположение («удаление уже завершенных 3-сетов НИКОГДА не плохая идея») неверно.Контрпример: 23566M 25667P 159S.Важной частью является 25667.Удаляя набор 567 3, мы получаем оставшуюся плитку 6, ведущую к 5-шанту.Было бы лучше использовать две отдельные плитки для формирования 56x и 67x, что приведет к 4-кратному увеличению.

Чтобы исправить, нам просто нужно удалить неправильную оптимизацию, что привело к этому коду:

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

Я полагаю, что это всегда точно находит наименьшее число Шантана, но я не знаю, как это доказать.Требуемое время находится в «разумном» диапазоне (на моей машине максимум 10 секунд, обычно 0 секунд).

Финальной точкой является вычисление вычитания из числа оставшихся одиночных плиток. Прежде всего, очевидно, что число имеет вид 3*n+1 (потому что мы начинали с 14 плиток и всегда вычитали 3 плитки).

Если осталось 1 тайл, мы уже сдвинулись (мы просто ждем финальную пару). Оставив 4 плитки, мы должны отбросить 2 из них, чтобы сформировать 3 сета, и мы снова останемся с одной плиткой. Это приводит к 2 дополнительным сбросам. С 7 тайлами у нас есть 2 раза 2 сброса, добавляя 4. И так далее.

Это приводит к простой формуле shanten_added = (number_of_singles - 1) * (2/3).

Описанный алгоритм работает хорошо и прошел все мои тесты, поэтому я предполагаю, что он правильный. Как уже говорилось, я не могу доказать это, хотя.

Поскольку алгоритм сначала удаляет наиболее вероятные комбинации тайлов, он как бы имеет встроенную оптимизацию. Добавив простой чек if (current_depth > best_shanten) then return;, он очень хорошо справляется даже с большими числами.

Answer 2

Моим лучшим предположением будет * вдохновленный подход *.Вам нужно найти эвристику, которая никогда не переоценивает число Шантена, и использовать его для поиска дерева грубой силы только в тех областях, где можно достаточно быстро войти в готовое состояние.

Answer 3

Пример правильного алгоритма: syanten.cpp

Рекурсивные формы вырезать из руки по порядку: наборы, пары, неполные формы, - и считать это. Во всех вариациях. И результатом является минимальное значение Шантена всех вариантов: Шантен = Мин (Шантен, 8 - * 2 - -)

Пример C # (переписан с c ++) можно найти здесь (на русском языке).

Answer 4

Я немного подумал и придумал формулу, немного отличающуюся от мафу. Прежде всего, рассмотрим руку (очень ужасная рука):

1с 4с 6с 1м 5м 8м 9м 9м 7п 8п Запад Восток Север

Используя алгоритм Мафу, все, что мы можем сделать, это изгнать пару (9м, 9м). Тогда у нас осталось 11 синглов. Теперь, если мы применим формулу Мафу, мы получим (11-1) * 2/3, которое не является целым числом и, следовательно, не может быть числом с шунтом. Вот где я придумал это:

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

N обозначает число shanten, а S - сумму очков. Что такое оценка? Это количество плиток, которое необходимо для завершения неполного набора. Например, если у вас в руке (4,5), вам нужно 3 или 6, чтобы сделать из него полный набор из 3, то есть только одну плитку. Таким образом, эта неполная пара получает 1 балл. Соответственно, (1,1) нужно только 1, чтобы стать 3-сетом. Очевидно, что любой отдельной плитке нужно 2 плитки, чтобы стать 3-сетом, и она получает 2 балла. Любой полный набор, конечно, получает 0 баллов. Обратите внимание, что мы игнорируем возможность превращения одиночных пар в пары. Теперь, если мы попытаемся найти все неполные множества в приведенной выше раздаче, мы получим:

(4 с, 6 с) (8 м, 9 м) (7 с 8 с) 1 с 1 м 5 м 9 м запад восток север

Тогда мы посчитаем сумму его баллов = 1 * 3 + 2 * 7 = 17. Теперь, если мы применим это число к формуле выше, мы получим (17 + 1) / 3 - 1 = 5, что означает, что эта рука 5-шантовая. Это несколько сложнее, чем у Алексея, и у меня нет доказательств, но пока мне кажется, что это работает. Обратите внимание, что такая рука может быть проанализирована другим способом. Например:

(4 с, 6 с) (9 м, 9 м) (7 с, 8 с) 1 с 1 м 5 м 8 м запад восток север

Тем не менее, он по-прежнему получает сумму очков 17 и 5-кратную в соответствии с формулой. Я также не могу доказать это, и это немного сложнее, чем формула Алексея, но также вводит оценки, которые могут быть применены (?) К чему-то еще.

Answer 5

Определение того, находится ли ваша рука уже в тенпай, звучит как проблема с несколькими ранцами . Жадные алгоритмы не будут работать - как указал Диалектик, вам нужно рассмотреть все проблемное пространство.