Маджонг (пасьянс)

Маджонг — компьютерная игра-пасьянс с использованием изображений фишек от китайской настольной игры маджонг.

Пасьянс изобретён американским программистом Броди Локардом, впервые реализовавшим маджонг в 1981 году в системе программированного обучения PLATO.

В 1986 году, при участии Локарда, компания Activision выпустила первую коммерческую версию маджонга под названием Shanghai (Шанхай)^[1]. Игра стала очень популярной и в дальнейшем появилось множество других реализаций этого пасьянса.

В 1990 году был издан маджонг Taipei (Тайбэй) в составе набора игр Microsoft Entertainment Pack 1^[2].

Позже появились и свободно распространяемые версии маджонга. Например для Linux — Mahjongg из набора игр GNOME Games и KMahjongg KDE Games.

Принцип нахождения парных элементов также используется в компьютерных играх типа Memory, впервые появившихся в 1983 году^[3].

Используется стандартный набор из 144 фишек.

Три масти — Медяки (銅 тун), Бамбуки (索 со), Тьмы (萬 вань), нумерованные от одного до девяти. 27 мастей по 4 фишки каждой, всего 108 фишек:

Благородные кости

Четыре Ветра — Восточный, Южный, Западный, Северный. По 4 шт. каждого вида, всего 16:

Три Дракона — Красный, Зелёный и Белый (в японском наборе белый дракон имеет вид фишки без изображения). По 4 шт., всего 12:

Цветы

Цветы — слива, орхидея, хризантема, бамбук. По 1 шт., всего 4, Считаются одинаковыми фишками:

Времена года — весна, лето, зима, осень. По 1 шт., всего 4. Считаются одинаковыми:

Таким образом, набор фишек сводится к 36 различным предметам (как в карточной колоде), повторяющимся 4 раза — 27 мастей + 4 ветра + 3 дракона + 1 цветы + 1 сезоны.

• Фишки перемешиваются и случайным образом складываются в многослойную фигуру определённой формы.
• Цель игры — разобрать построенную фигуру, удаляя за один ход две одинаковые незаблокированные фишки.
• Фишка считается незаблокированной, если на ней не лежит никакая фишка, и свободна левая либо правая сторона.
• Одинаковыми считаются фишки с одинаковым изображением, кроме считающихся одинаковыми, но внешне отличающихся фишек цветов и сезонов.

Если при построении формы строго следовать случайному порядку расположения фишек, то некоторые из комбинаций получатся нерешаемыми; в компьютерных вариантах пасьянса маджонг часто применяют специальные алгоритмы генерации пирамиды, которые приводят исключительно к разрешимым раскладам. Самый простой алгоритм — постепенное наращивание пирамиды добавлением пар фишек. Такая раскладка однозначно имеет хотя бы одно решение — убрать эти же пары в обратном порядке.

Задача минимизации вероятности застревания с учётом того, что нижние фишки не видны, PSPACE-полная. Задача решения головоломки, когда известны фишки в нижних слоях, NP-полная. Методом Монте-Карло для стандартной пирамиды-«черепахи» получена оценка: 2,95…2,96 % раскладов неразрешимы^[4].

Shisen-Sho — вариант маджонга, разработанный японской компанией Tamtex (Irem) в 1989 году^[5].

Одинаковые фишки убираются, если их можно соединить одной, или соединяющимися под прямым углом двумя—тремя воображаемыми линиями. На пути линий не должно быть других фишек. Классическая фигура Shisen-Sho представляет собой прямоугольник 8×18 фишек.