Работа с симметрией шахматной доски

Question

В шахматной доске 8X8 мне было интересно, как реализовать симметрию платы.

Много позиций просто зеркал или вращения друг от друга (без пешек или рокировка возможности влево направления неразличимы).

С помощью комбинации вертикальное, горизонтальное и диагональное зеркалирование платы всегда можно зафиксировать положение куска внутри треугольника a1-d1-d4.

Как реализовать эти симметрии на шахматной доске? Это зависит от выбора выбора доски (Биты, 0x88, массив 8x8 и т. Д.)?

Редактировать 1: Цель состоит в том, чтобы реализовать генерацию таблиц эндшпилей и их сжатие.

Answer 1

Если вы хотите сжать доски, вы можете создать каноническое представление каждой доски. older answer по @DocBrown выражает это хорошо:

Чтобы сделать это более эффективным, вы можете работать с «канонической» каждой платы, определяется следующим образом. Генерируйте все симметричные платы заданного, упаковывайте каждый из них в массив байтов, и среди этих массивов сохраняется массив, который интерпретируется как большое число, имеет минимальное значение.Это упакованное представление является уникальным идентификатором класса симметрии каждой платы и может быть легко помещено в таблицу словаря/хэша, что делает тестирование, если этот класс симметрии уже оказался очень эффективным.

Этот вопрос относится к N-queens problem, где много симметрии можно найти, поскольку каждая королева неразличима. Для плат для конечных игр это (редко) случай, поэтому я не уверен, сколько сбережений вы получите.

Answer 2

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

Кроме того, это не помогает локализовать каждую отдельную деталь в треугольнике a1-d1-d4. Вам нужно беспокоиться обо всех частях на доске сразу и как они соотносятся друг с другом. Не имеет смысла рассматривать две ладьи на a1 и h1, поскольку на самом деле оба находятся на a1.

Что вы можете сделать, так это «нормализовать» все доски по отношению к симметрии. Вам нужен алгоритм для определения нормальной формы. Например, вы можете сначала преобразовать белого короля в этот треугольник, затем выполнить любые оставшиеся преобразования, которые удерживают белого короля там, и переместить черного короля в стандартное место (я выбрал королей, потому что они, несомненно, будут на борту и быть уникальным). Как вы заметили, многие преобразования будут действительны только в том случае, если нет пешек слева, а рокировка недействительна, что в любом случае существенно ограничивает возможности.

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

Эта нормализация тогда применима в сочетании с любой существующей базой данных, которую вы создаете. Если вы знаете какое-либо свойство (например, выигрышные ходы) платы X, а плата Y нормализуется до платы X, то вы также знаете это свойство платы Y, при условии отмены необходимых преобразований. При добавлении позиций в базу данных вы должны делать это на основе нормализованной платы.

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