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

Ответ 1

"не предполагают, что я должен хранить по центру, а не по частям".

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

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

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

Ответ 2

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

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

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

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

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

Когда плата пуста, вы произвольно устанавливаете хеш-ключ на 0, а затем, когда вы добавляете кусок на доске, скажем, ладья на A1, вы также обновляете хэш-ключ, используя XORing ключ zobrist для ладьи на A1 с хэш-ключ платы. Как это (в 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 каждый раз, xoring zobKeys, соответствующий всем частям на доске. Вам также понадобится XOR позиция пешки, которая может быть принята en passant, и статус возможностей соединения с обеих сторон. Вы делаете это точно так же, создавая ключи звёзд для всех возможных значений.

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

edit: Я просто краснею, что вы пытаетесь реализовать это для варианта шахмат, у которого есть доски. 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];

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

С точки зрения куска можно сделать следующее:

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

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

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

Если суммы равны, вы можете быстро сравнить позиции уникальных предметов (King and Queen). Затем вы можете выписать (в несколько усложненных операциях) сравнения для частей, находящихся в парах. Все, что вам нужно сделать, это сравнить пешек с использованием вышеуказанного метода.

Ответ 6

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

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

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

Ответ 7

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

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

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

или

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

Эти две альтернативы не будут иметь проблему транспонирования.

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