Определить, равны ли две шахматные позиции

Question

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

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

// [Piece List]
// 
// Contents: The location of the pieces.
//           Values 0-63 are board indexes; -2 is dead; -1 is placeable
// Structure: Black pieces are at indexes 0-15
//            White pieces are at indexes 16-31
//            Within each set of colors the pieces are arranged as following:
//            8 Pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 Queen, 1 King
// Example: piece[15] = 6 means the black king is on board index 6
//          piece[29] = -2 means the white rook is dead
char piece[32];

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

1) first rook on A1; second rook on D7
2) first rook on D7; second rook on A1

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

for each color:
    for each piece type:
        are all pieces in the same position, disregarding transpositions?

Следующее сравнение НЕ работает из-за транспонирования . Мне нужен способ определить транспонирование как равное и сообщать только о фактически разных позициях.

bool operator==(const Position &b)
{
    for (int i = 0; i < 32; i++)
        if (piece[i] != b.piece[i])
            return false;
    return true;
}

Производительность / память - это вопрос , потому что таблица получает более 100 тыс. Обращений (где ключи равны) за ход, а типичная таблица содержит 1 миллион элементов. Отныне я ищу что-то на быстрее, чем копировать и сортировать списки .

Answer 1

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

Что вам нужно сделать, это использовать Zobrist Hashing , чтобы создать уникальный (не совсем уникальный, но мы увидим позже, почему это не проблема на практике) ключ для каждой позиции. Алгоритм , применяемый к шахматам, объясняется здесь .

Когда вы запускаете свою программу, вы создаете то, что мы называем ключами зобриста. Это 64-битные случайные целые числа для каждой пары кусок / квадрат. В C вы бы имели двухмерный массив, подобный этому:

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

Каждый из этих ключей инициализируется хорошим генератором случайных чисел (Предупреждение: генератор случайных чисел, предоставляемый с gcc или VC ++, недостаточно хорош, используйте реализацию Mersenne Twister ).

Когда доска пуста, вы произвольно устанавливаете ее хеш-ключ на 0, затем, когда вы добавляете фигуру на доску, скажем, «Ладья» на А1, вы также обновляете хеш-ключ, делая XOR клавишу «Зобрист» для ладьи на А1 с хеш-ключ доски. Как это (в C):

boardHash = boardHash ^ zobKeys[ROOK][A1];

Если вы позже удалите ладью из этого квадрата, вам нужно будет повернуть вспять то, что вы только что сделали, поскольку XOR можно повернуть вспять, применив его снова, вы можете просто использовать ту же команду еще раз, когда удаляете фигуру:

boardHash = boardHash ^ zobKeys[ROOK][A1];

Если вы перемещаете фигуру, скажем, ладью на турнире A1, в B1, вам нужно сделать два XOR, один для удаления ладьи на A1 и один для добавления ладьи на B2.

boardHash = boardHash ^ zobKeys[ROOK][A1] ^ boardHash ^ zobKeys[ROOK][B1];

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

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

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

unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE];

Если у вас есть 2 лапы с доски и вы положили одну из этих пешек на a2, вам придется сделать 2 операции:

// remove one pawn from the off-the-board
boardHash = boardHash ^ offTheBoardZobKeys[WHITE_PAWN][numberOfWhitePawsOffTheBoard];

// Put a pawn on a2
boardHash = boardHash ^ zobKeys[WHITE_PAWN][A2];

Answer 2

Почему бы не сохранить в вашей базе данных 64-байтовую строку, соответствующую разметке шахматной доски? Каждый тип фигуры, включая «нет фигуры», представляет букву (разные заглавные буквы для обоих цветов, например ABC для черного, abc для белого) Сравнение досок сводится к простому сравнению строк.

В общем, сравнение с точки зрения шахматной доски, а не с точки зрения фигуры, избавит вас от проблемы переноса!

Answer 3

«не предлагайте мне хранить по центру платы, а не по частям».

Вы настолько сосредоточены на том, чтобы не делать этого, что упускаете очевидное решение. Сравнить для платы.Чтобы сравнить два списка позиций L1 и L2, поместите все элементы L1 на (временную) доску.Затем для каждого элемента L2 проверьте, присутствует ли он на временной доске.Если элемент L2 отсутствует на плате (и, следовательно, в L1), вернуть неравный.

Если после удаления всех элементов L2 на доске остались еще фигуры, то L1 должен иметь элементы, которых нет в L2, и списки равны.L1 и L2 равны только тогда, когда временная доска пуста.

Оптимизация заключается в том, чтобы сначала проверить длины L1 и L2.Это не только быстро улавливает множество расхождений, но также устраняет необходимость в удалении элементов L2 из баорда и проверки «пустой доски» в конце.Это необходимо только для того, чтобы поймать случай, когда L1 является истинным расширенным набором L2.Если L1 и L2 имеют одинаковый размер, а L2 является подмножеством L1, то L1 и L2 должны быть равны.

Answer 4

Ваше основное возражение против хранения штатов по доскам - наличие у вас пакета без позиции. Почему бы не поддерживать доску + вектор фигур? Это будет соответствовать вашим требованиям и имеет то преимущество, что это каноническое представление для ваших штатов. Следовательно, вам не нужна сортировка, и вы либо используете это представление внутренне, либо конвертируете в него, когда вам нужно сравнить:

Piece-type in A1
... 63 more squares
Number of white pawns off-board
Number of black pawns off-board
... other piece types

Answer 5

Учитывая ваш выбор игрового состояния, вы должны сортировать индексы черных пешек, индексы белых пешек и т. Д., Так или иначе.Если вы не сделаете это в процессе создания нового игрового состояния, вам придется сделать это после сравнения.Поскольку вам нужно только отсортировать не более 8 элементов, это можно сделать довольно быстро.

Существует несколько альтернатив для представления состояний вашей игры:

• Представляет каждый тип фигурыкак битовое поле.Первые 64 бита означают, что на координате этой доски есть фрагмент этого типа;тогда есть n битов "размещаемых" и n битов "мертвых" слотов, которые должны быть заполнены с одной стороны ( n - это числофигуры этого типа).

или

• Дайте каждому типу фигуры уникальный идентификатор, например, белые пешки могут быть 0x01.Состояние игры состоит из массива из 64 фигур (доска) и двух упорядоченных списков «размещаемых» и «мертвых» фигур.Поддержание порядка этих списков может быть сделано достаточно эффективно после вставки и удаления.

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

Answer 6

И третий вариант (я действительно надеюсь, что опубликовать 3 ответа на один вопрос - нормально, в стеке;)):

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

Теперь, сравнивая позиции, вы можете быть уверены, что проблем с транспозицией нет, и вы можете просто использовать предложенный цикл for.

Answer 7

С точки зрения фигуры вы можете сделать это:

for each color:
    for each piece type:
        start new list for board A
        for each piece of this piece type on board A
            add piece position to the list
        start new list for board B
        for each piece of this piece type on board B
            add piece position to the list
        order both lists and compare them

Оптимизация может происходить по-разному. Ваше преимущество: как только вы заметите разницу: вы сделали!

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

Если суммы равны, вы можете быстро сравнить позиции уникальных фигур (Король и Королева). Тогда вы могли бы записать (в несколько сложных операторах if) сравнения для частей, которые находятся в парах. Все, что вам нужно сделать, это сравнить пешки, используя вышеуказанный метод.