Как я могу рассчитать номер Shanten в Маджонг?

Question

Это последующий соблюдатель более ранний вопрос о решении, если рука готова.

Знание правил Mahjong было бы превосходным, но фон на основе покера или Romme также достаточно, чтобы понять этот вопрос.

В Mahjong 14 плиток (плитка похожи на карты в покере), расположены до 4 наборов и пары. Прямой («123») всегда использует ровно 3 плитки, не более и не меньше. Набор того же рода («111») состоит из ровно 3 плиток тоже. Это приводит к сумме 3 * 4 + 2 = 14 плиток.

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

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

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

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

Правила

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

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

Изменение нашей оригинальной руки слегка на 2p, 2p, 3p, 3p, 3p, 4p, 5m, 5m, 5m, W, W, W, E, Мы получили руку в 1-шантене, т.е. это требует дополнительной плитки, чтобы быть Tenpai. В этом случае обменение 2P для 3P возвращает нас в Tenpai, так что рисуя 3P и мы выигрываем.

1p, 1p, 5p, 5p, 9p, 9p, E, E, E, S, S, W, W это рука в 2-шантене. Есть 1 завершенные триплеты и 5 пар. Нам нужна одна пара в конце, поэтому, как только мы выберем один из 1P, 5P, 9P, S или W, нам нужно отменить одну из других пар. Пример: мы выбираем 1 контакт и выбросьте W. Рука в 1-шантене сейчас и выглядит так: 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. Отказ Эта рука находится в Tenpai, может завершить на 9 PIN или S.

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

Алгоритм

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

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

Answer 1

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

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

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

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

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

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

Лучшее решение: модификация существующих шатер Mahjong

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

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

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

Усовершенствованный подход с использованием знаний домена

Разговор с более опытным игроком, окажется, что есть некоторые законы, которые могут быть использованы. Например, набор из 3 плиток никогда не нужно разбить, так как это никогда не уменьшит число Shanten. Это, однако, может использоваться по-разному (сказать, либо для комбинации 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-SET Мы в конечном итоге с левой 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

Я считаю, что это всегда точно находит самый маленький чисел Shanten, но я не знаю, как доказать это. Время взят в «разумном» диапазоне (на моей машине 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; Это очень хорошо даже для высоких чисел Shanten.

Answer 2

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

Answer 3

Правильный алгоритм образец: Syanten.cpp.

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

C # образец (переписан из C ++) можно найти здесь (на русском).

Answer 4

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

1S 4S 6S 1M 5M 8M 9M 9M 7P 8P West East North

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

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

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

(4s, 6s) (8 м, 9 м) (7p, 8p) 1s 1 м 5 м 9 м западный восточный север

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

(4s, 6s) (9 м, 9 м) (7p, 8p) 1s 1 м 5 м 8 м западный восточный север

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

Answer 5

Определение ли ваша рука уже в Tenpai звучит как Multi-knaxack проблема. Отказ Жадные алгоритмы не будут работать - как указал dalecticus, вам нужно будет рассмотреть все проблемное пространство.