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

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

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

// [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];

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

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 миллион предметов. Отныне я m ищет что-то быстрее, чем копирование и сортировка списков .