Распознавание шахматной фигуры с битбордами
Когда шахматная доска хранится в различных битбордах, как современные шахматные движки распознают, какой тип / боковая фигура расположены в конкретной ячейке? У меня проблемы с этим, так как, чтобы узнать, какой тип / боковая часть есть конкретный бит, я должен всегда делать:
if((bit_check & occupied) == 0ULL) ... // empty
else if((bit_check & white) != 0ULL) // white
if((bit_check & white_pawns) != 0ULL) ... // white pawns
else if((bit_check & white_rooks) != 0ULL) ... // white rooks
....
else if((bit_check & white_kings) != 0ULL) ... // white kings
else if((bit_check & black) != 0ULL) // black
if((bit_check & black_pawns) != 0ULL) ... // black pawns
....
else if((bit_check) & black_kings) != 0ULL) ... // black kings
Это довольно утомительный процесс, и его нужно делать довольно много раз (например, во время генерации хода, чтобы увидеть, что захватывается). Я не уверен, должен ли я просто пойти с этим или было бы быстрее просто создать массив типа 64 Piece[64], который по сути будет хранить тип куска.
Что было бы лучше, учитывая, что это должно быть миллионы раз, для анализа захвата в функциях поиска. Я делаю это неправильно?
Решение
Сам бит проверяется быстро; Я бы беспокоился в основном о ветвлении.
Вместо этого рассмотрим uint64_t bitboards[12] как массив из 12 битбордов для всех частей. Это теперь непрерывно в памяти и может быть отсканировано в цикле:
for (int i = 0; i != 12; ++i)
{
if (bitboards[i] && bit_check) return i;
}
return -1; // empty.
Предсказатель ветвления проще только для двух ветвей (цикл и проверка), а непрерывная память оптимизирует предварительный выборщик.
Очевидные изменения — проверка битбордов с [0] по [5] только для белых фигур и с [6] по [11] только для черных.
Более тонкий вариант:
uint64_t bitboards[13];
bitboards[12] = ~uint64_t(0);
for (int i = 0; /* NO TEST*/ ; ++i)
{
if (bitboards[i] && bit_check) return i;
}
Вместо того, чтобы возвращать -1 для пустого, это возвратит 12 (значение дозорного). Однако это заменяет условную ветвь цикла более быстрой безусловной ветвью. Это также означает, что возвращаемое значение всегда int i,
Другая несвязанная оптимизация заключается в том, чтобы признать, что пешки являются наиболее распространенными фигурами, поэтому их использование более эффективно. bitboards[0] для белых пешек или bitboards[1] или же bitboards[6] для черных пешек, в зависимости от того, чередуете ли вы чёрные или белые фигуры.
colorВам тогда не понадобятся две битборды для белых и черных пешек. Вместо этого есть один битборд для пешек. Чтобы проверить на черную пешку, И два значения. (bit_check & color & bitboard[0]). Чтобы проверить на белую пешку, инвертируйте цвет (bit_check & ~color & bitboard[0])
Другие решения
Это самая медленная операция для битборда. Однако вам редко приходится это делать.
Я вижу, что вы поддерживаете побитовые ‘или’ всех белых фигур, white и побитовые или все черные фигуры, black, Используя их, вы можете быстро отклонять ходы на свои части и легко обнаруживать захват.
В несколько маловероятном случае захвата вы должны проверить до 5 из 6 битовых досок противника, потому что захват короля уже должен был быть исключен. Кроме того, это не так утомительно, как вы себе представляете; в 64-битной системе каждая маска — это только 1 операция на одну битовую доску и затем сравнение, то есть 10 целочисленных операций. And/Or некоторые из самых легких операций на процессоре. Поддержание Piece[64] одно стоит больше времени, чем это.
Я считаю, что нет другого случая (в коде двигателя), где вам нужно получить кусочек ID из данного квадрата.
Основным преимуществом битбордов является генерация хода и позиционный анализ. Ничто не может сравниться, поэтому вы будете поддерживать эту структуру, несмотря ни на что.