Расчёт числа шантен

[teplofizik]

Данное число показывает минимальное число замен, необходимое, чтобы рука стала темпай (один тайл до победы).

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

Для начала можно рассмотреть вторые два как более простые. Шантен до читойцу считается просто. В темпае в руке 6 пар и один левый тайл. Соответственно, надо посчитать число пар и вычесть это из шести. Повторяющиеся пары не считаются.
ShantenChiitoi = 6 - (Paircount);

Шантен до Кокуши считается аналогично, только считаются уже отдельные тайлы. Все терминалы, все ветра, все драконы.
Максимальный шантен: 13. За каждый нужный неповторяющийся тайл отнимаем единицу. И один раз отнимаем за повтор нужного тайла (нужна одна пара). Все остальные повторы не уменьшают число шантен.

Самый сложный алгоритм, конечно, относится к обычной руке, так как там могут быть различные и пересекающиеся формы. Суть алгоритма всё же не такая и мудрёная: вырезать все пары, сеты и таацу (незаконченные формы) всеми возможными способами, — и тем самым найти минимальное значение числа шантен. Максимальное значение шантен для обычной руки: 8. То есть как бы имеем зайчатки для 4 сетов и одной пары, но только по одному тайлу от каждого (итого 13 - 5 = 8). Соответственно, пара будет уменьшать число шантен на единицу (как пара или как незаконченный ankou в дальнейшем), два (изолированных от остальных) соседних тайла будут уменьшать число шантен на единицу, образуя таацу, законченный сет же (3 одинаковых или 3 последовательных тайла) уменьшает число шантен на 2, так как к изолированному тайлу пришло два подходящих тайла. Итого, число шантен для текущего разложения считается: Temp = 8 - Mentsu * 2 - Kouho - Toitsu;

Mentsu в данном случае обозначает число сетов (чи, пон).
Toitsu — голова, пара тайлов, или 0 или 1.
Kouhou — все таацу и остальные пары (кантян, пентян, рянмен, пара).

Выделяя из руки форму, убираем тайлы в неё входящие, чтобы можно было посмотреть, что же осталось.

Например: имеем часть руки .

Проходим первый раз без выделения пары, начиная с 2х:
1. Убирается сет ;
2. Убирается сет ;
Остался в руке лишний тайл: . Посчитали Mentsu = 2. Если остальные сеты открыты (Mentsu += 2), то это темпай. (8 - 2 * 4) = 0.

Проходим в другой раз, но сначала убирая пару:
1. Убирается пара .
2. Убирается сет .
3. Убирается кантян: .
В руке ничего не осталось. Mentsu = 1. Toitsu = 1. Kouho = 1. Это тоже темпай: (8 - 3*2 - 1 - 1) = 0.

Ещё раз проходим, начиная с 4х:
1. Убирается сет ;
2. Убирается пара: ;
3. Убирается рянмен: ;
В руке ничего не осталось. Mentsu = 1. Toitsu = 1. Kouho = 1. Расчёт такой же: (8 - 3*2 - 1 - 1) = 0.

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

Для удобства расчётов руку удобно представлять в виде массива, где индекс обозначает конкретный тайл, а содержимое — количество оных тайлов в руке.
uint8_t Tehai[38];

Всего тайлов 34, но для удобства хорошо бы отделить все неблагородные тайлы разных мастей друг от друга и выровнять относительно какого-либо числа, например:

0: разделитель;
1-9: тайлы ман;
10: разделитель;
11-19: тайлы пин;
20: разделитель;
21-29: тайлы соу;
30: разделитель;
31: 東 (восток)
32: 南 (юг)
33: 西 (запад)
34: 北 (север)
35: 白 (белый дракон)
36: 発 (зелёный дракон)
37: 中 (красный дракон)

Для примера выше массив будет инициализирован так:

Tehai[22] = 2; // 2 2s
Tehai[23] = 1; // 1 3s
Tehai[24] = 2; // 2 4s
Tehai[25] = 1; // 1 5s
Tehai[26] = 1; // 1 6s

Теперь остаток от деления на 10 будет давать номер тайла в данной масти. И алгоритмы нахождения последовательностей будут проще из-за того, что все масти в массиве расположены симметрично и разделены нулями.
Чтобы полностью обойти все возможные варианты разбиения руки надо использовать рекурсивный алгоритм. Перед запуском назначаем руке шантен 8, число всех сетов, пар и форм 0. Когда вырезаем форму, убираем используемые тайлы и увеличиваем счётчик форм, вызываем ту же функцию, пусть она ищет дальше. Когда ничего полезного не останется, считаем по формуле шантен и сравниваем с записанным где-то. Если получился меньше, то обновим его. По выходе из функции возвращаем тайлы на место, уменьшаем счётчик форм (чтоб потом попробовать тайлы скомбинировать по-иному) и идём дальше.
Так же, не стоит забывать, что сетов нам надо всего четыре, потому лишние формы нам с шантеном не помогут, их надо пропускать.
Очерёдность вырезания тоже понятна: сначала сеты, потом из того, что осталось, вычленяем незавершённые формы. Единственное исключение: голову вырезать пробуем первой (она всё же отличается от сетов).
Что здорово, нет ограничения на число тайлов. Если есть открытые сеты, то просто запишем в Mentsu их количество.

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

Вот кусок кода на C#, который считает шантен по данному алгоритму:

{
	private uint Mentsu; // Количество сетов
	private uint Kouho;  // Количество форм
	private uint Toitsu; // Количество пар

	private uint[] Tehai = new uint[38]; // Для анализа руки

	private uint ShantenChiitoi; // Шантен до 7 пар
	private uint ShantenKokushi; // Шантен до Кокуши
	private uint ShantenNormal;  // Шантен до обычной руки

	private uint TempShantenNormal;

	private uint Shanten;

	private void Test()
	{
		// Когда рука сформирована
		Shanten = GetShanten();
	}

	private uint GetShanten()
        {
		// Шантен — минимальное из трёх

		// Шантен до обычной руки
		ShantenNormal = CalcShantenNormal();
		// Шантен до 7 пар
		ShantenChiitoi = CalcShantenChiitoi();
		// Шантен до кокуши
		ShantenKokushi = CalcShantenKokushi();

		return Math.Min(ShantenChiitoi, Math.Min(ShantenKokushi, ShantenNormal));
	}


	// Шантен до читойцу
	private uint CalcShantenChiitoi()
	{
		int i;
		uint Types = 0;

		// Считаем пары
		Pair = 0;
		for (i = 0; i < 38; i++)
		{
			if (Tehai[i] >= 2) Pair++;
		}

		// Посчитаем количество типов тайлов
		for (i = 0; i < 38; i++)
		{
			if (Tehai[i] > 0) Types++;
		}

		// Шантен равен 6 - количество имеющихся пар
		uint shanten = 6 - Pair;

		// Единственное ограничение: пары не должны повторяться, повторы (4 одинаковых тайла) увеличивают шантен
		// Иначе может получиться так, что там какое-нибудь сууанко собирается: 111 222 333 44 55
		// А это ещё 3-шантен до читойцу.
		if (Types < 7) shanten += 7 - Types;

		return shanten;
	}

	// Шантен до Кокуши
	private uint CalcShantenKokushi()
	{
		uint KokushiPair = 0;
		uint shanten = 13;
		int i;

		// посмотрим терминалы
		// Для кокуши нужны все единицы и девятки
		for (i = 1; i < 30; i++)
		{
			if ((i % 10 == 1)|| (i % 10 == 9))
			{
				if (Tehai[i] > 0) shanten--;
				if ((Tehai[i] >= 2) && (KokushiPair == 0)) KokushiPair = 1;
			}
		}

		// Посмотрим благородные тайлы
		for (i = 31; i < 38; i++)
		{
			if (Tehai[i] > 0)
			{
				shanten--;
				if ((Tehai[i] >= 2) && (KokushiPair == 0)) KokushiPair = 1;
			}
		}

		// Если есть одна необходимая пара - уменьшим шантен
		shanten -= KokushiPair;

		return shanten;
	}

	// Шантен до обычной руки
	private uint CalcShantenNormal()
	{
		int i;

		// Шантен максимален
		TempShantenNormal = 8;

		// Сетов пока не считали
		Mentsu = 0; // Если есть открытые сеты, то запишем сюда их количество
		Toitsu = 0;
		Kouho = 0;

		// Нам нужна одна пара, попробуем все тайлы в качестве её.
		for (i = 1; i < 38; i++)
		{
			// Если тайлов этой масти более одного, то от него можно попробовать отчекрыжить пару и посмотреть,
			// что из этого выйдет
			if (Tehai[i] >= 2)
			{
				Toitsu++;
				Tehai[i] -= 2;
				CutMentsu(1);
				Tehai[i] += 2;
				Toitsu--;
			}
		}

		// Что ж, попробуем и без пары оценить строение руки
		CutMentsu(1);

		return TempShantenNormal;
	}

	// По очереди вырезаем сеты из руки и смотрим, что там остаётся
	private void CutMentsu(int StartTile)
	{
		int i = StartTile;

		// Ищем первый попавшийся тайл
		if(i < 38) for(; (i < 38) && (Tehai[i] == 0); i++);

		// Сеты кончились, смотрим с начала незаконченные формы
		if(i >= 38) { CutTaatsu(1); return; }

		// если таких тайлов 3, то можно их рассмотреть как пон
		if(Tehai[i] >= 3)
		{
			Mentsu++;
			Tehai[i] -= 3;
			CutMentsu(i);
			Tehai[i] += 3;
			Mentsu--;
		}

		// Если есть следующий и ещё послеследующий тайл, то это можно рассмотреть как чи
		// Только для числовых тайлов (i < 30)
		// Благодаря разделителям (0, 10, 20, 30) не надо беспокоиться о пересечениях с чужой мастью
	        if((i < 30) && (Tehai[i + 1] > 0) && (Tehai[i + 2] > 0))
	        {
		        Mentsu++;
		        Tehai[i]--;
			Tehai[i+1]--;
			Tehai[i+2]--;

			CutMentsu(i);

			Tehai[i]++;
			Tehai[i + 1]++;
			Tehai[i + 2]++;
			Mentsu--;
	        }

		// Отрезали, смотрим дальше
		CutMentsu(i + 1);
	}

	private void CutTaatsu(int Start)
	{
		int i = Start;

		// Ищем первый попавшийся тайл
		if (i < 38) for (; (i < 38) && (Tehai[i] == 0); i++) ;

		// Если закончили и с формами, то посмотрим, что получилось
		if(i >= 38)
		{
			// Если шантен данного разложения меньше, чем насчитанный в других
			// вариантах, запишем его.
			uint Temp = 8 - Mentsu * 2 - Kouho - Toitsu;
			if (Temp < TempShantenNormal) { TempShantenNormal = Temp; }
                	return;
		}

		// Если форм ещё недостаточно, считаем
		// Лилшние формы шантен не уменьшают
		if (Mentsu + Kouho < 4)
		{
			// Пары
			if (Tehai[i] == 2)
			{
				Kouho++;
				Tehai[i] -= 2;
				CutTaatsu(i);
				Tehai[i] += 2;
				Kouho--;
			}

			// Пентян и рянмен
			if((i < 30) && (Tehai[i + 1] > 0))
			{
				Kouho++;
				Tehai[i]--; Tehai[i + 1]--;
				CutTaatsu(i);
				Tehai[i]++; Tehai[i + 1]++;
				Kouho--;
			}

			// Кантян
			if((i < 30) && ((i % 10) <= 8) && (Tehai[i + 2] > 0))
			{
				Kouho++;
				Tehai[i]--; Tehai[i + 2]--;
				CutTaatsu(i);
				Tehai[i]++; Tehai[i + 2]++;
				Kouho--;
			}
		}
		CutTaatsu(i + 1);
	}
}

А имея алгоритм расчёта шантен, можно уже посчитать уке-ире и иные параметры руки. То есть круто.
Данный алгоритм подсмотрен на упоминавшемся мной ранее сайте: 麻雀C言語プログラム集 (Collection of C language mahjong program).