Как я могу преобразовать возможные ходы фигур в реальный ход на битовой доске?

Jan 09 2021

Если у меня есть битборд (например, для квадратов коня, на которые он может перейти), например:

00000000
00000000
00000000
00000000
00000000
01000000
00100000
N0000000

Как я могу «преобразовать» его в ход или «применить» этот ход?

Ответы

2 AryanParekh Jan 09 2021 at 19:28

На самом деле в вашем посте есть два вопроса

  • Как преобразовать атаки в битбордах в список ходов?

  • Как изобразить эти ходы?


  • Как изобразить эти ходы?

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

  • Откуда (где была движущаяся часть)
  • Куда (где будет движущаяся часть)
  • Флаг особого движения (был ли этот ход особым, т. Е. Enpassant, кастинг, повышение)
  • Повышенная фигура (если ход был повышением, то в какую фигуру она продвинулась)

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

Итак, учитывая вышесказанное, мы можем представить ход следующим образом

struct Move {
    char from; 
    char to;   
    char spMoveFlag;
    char promotedPiece;
};

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

Как только мы узнаем, что такое ход, мы сможем ответить на следующий вопрос.


  • Как преобразовать атаки в битбордах в список ходов?

Предположим, у нас есть конь на поле d4 . У нас также есть функция, которая возвращает атаки коня с учетом квадрата.

. . . . . . . . 
. . . . . . . . 
. . 1 . 1 . . . 
. 1 . . . 1 . . 
. . . n . . . .   =  knightattacks(SQ_D4)
. 1 . . . 1 . . 
. . 1 . 1 . . . 
. . . . . . . . 

Итак, давайте сохраним это внутри переменной knightAttacks

uint64_t knightAttacks = getKnightAttacksBB(SQ_D4);

Если вы внимательно заметили, у нас уже есть 1 из 4 атрибутов, которые нам нужны для представления хода, а именно Fromквадрат - D4. Теперь все, что нам нужно сделать, это каким-то образом получить Toквадрат, чтобы завершить это, поскольку конь не может выполнять никаких специальных ходов.

Очень распространенным методом является поп - младший значащий бит , пока ваш knightAttacksне осталось ничего , т.е. 0.

0000011100001000 
            ^
            Least significant bit (lsb)

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

Вам просто нужно создать функцию, которая очищает LSB битовой доски и возвращает ее индекс. Назовем это poplsb().

В целом ваш код может выглядеть так

int from = SQ_D4;
uint16_t knightAttacks = getknightAttacks(from);

while (knightAttacks)  {
     int to = poplsb(knightAttacks);
     MyMoveList.Add( NewMove(from, to, 0, 0) ); // The last two 0's denote that there is no special move
}

Это работает, потому что каждый раз, когда вы открываете lsb, бит очищается, пока число не станет == 0. Вот когда цикл останавливается, и у вас есть отличный список ходов. Та же идея применима к любым движениям, которые вы создали с помощью Bitboard.