Ход конём по битам. Шахматный Bitboard

    Добрый день. Эту статью я написал специально для студентов курса «Алгоритмы для разработчиков» в OTUS и сегодня хочу поделиться ею со всеми читателями нашего блога.

    Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль.
    Сколько разных ходов он может сделать?

    image

    Хвала изобретателю шахмат, на доске 64 клетки.
    Хвала архитектору компьютеров — у типа ulong тоже 64 бита.
    Это же надо было случиться такому совпадению!
    Напрашивается гениальная идея — хранить всю доску в одном целом числе! Для этого решения существует даже специальный термин — Bitboard — битовая доска.

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

    Дано: knightNr — номер клетки доски, где стоит конь (от 0 до 63).
    Надо: movesCount — количество полей, куда он может пойти (от 2 до 8).

    Алгоритм.


    1.Конвертировать номер клетки коня в ulong-значение битовой доски
    knightNr -> knightBits

    2.Установить биты для всех возможных ходов коня
    knightBits -> movesBits

    3.Подсчитать количество единичных битов
    movesBits -> movesCount

    image

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

    	ulong knightBits = 1 << knightNr;

    Второй шаг немножко сложнее. Конь может пойти в 8 разных сторон. Мы будем считать эти смещения не «по горизонтали/вертикали», а по битовым позициям. То есть, считаем, на сколько позиций нужно сместить стартовый бит для каждого хода. Потом всё «складываем» операцией логического «или».

    Начнём перечислять ходы от левой стороны доски к правой:

      movesBits = knightBits <<  6 | knightBits >> 10 // на b5 и b3
                | knightBits << 15 | knightBits >> 17 // на c6 и c2
                | knightBits << 17 | knightBits >> 15 // на e6 и e2
                | knightBits << 10 | knightBits >>  6 // на f5 и f3; 
    

    Правда, классно!?


    К сожалению, по краям доски есть «чёрные дыры». Например, по этому алгоритму из клетки a4 (бит #24) можно попасть на клетку g2 (бит #14 = 24 — 10), этот прыжок является телепортацией сферического шахматного коня в вакууме на доске сквозь чёрную дыру крайние вертикали

    Чтобы исключить квантовый скачок коня через край доски, необходимо «отключать» крайние полосы после перемещения. Например, для ходов +6 и -10 (влево на две клетки) необходимо аннулировать полученные значения на вертикалях g и h, так как на этих вертикалях нельзя оказаться после перемещения «влево» на два хода.

    Для этого нам понадобится 4 константы битовых сеток, в которых все биты установлены в 1, кроме указанных вертикалей. А именно:

            ulong nA  = 0xFeFeFeFeFeFeFeFe;
            ulong nAB = 0xFcFcFcFcFcFcFcFc;
            ulong  nH = 0x7f7f7f7f7f7f7f7f;
            ulong nGH = 0x3f3f3f3f3f3f3f3f;
    

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

    Теперь алгоритм генерации допустимых ходов коня выглядит так:

       movesBits = nGH & (knightBits <<  6 | knightBits >> 10)
                 |  nH & (knightBits << 15 | knightBits >> 17)
                 | nA  & (knightBits << 17 | knightBits >> 15)
                 | nAB & (knightBits << 10 | knightBits >>  6);
    

    Это работает очень (!) быстро.

    Несколько тиков — и у нас битовая карта всех возможных похождений коня. Самое удивительное, что этот алгоритм отлично работает, даже если на доске расположено несколько коней. Он за один раз генерирует все возможные ходы для всех коней! Правда, здорово!?

    Осталось подсчитать количество бит


    Самый простой способ — сдвигать число на 1 бит вправо и считать единички. Сложность — 64 операции. Память — 64 бита.

    Самый быстрый способ — создать кэш/массив на 65536 элементов, в котором записано количество битов для каждого индекса от 0 до 65535. И сложить 4 элемента из этого массива, которые соответствуют очередным 16-битовым сегментам числа.
    Сложность — 4 операции. Память — 64 килобайта.

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

    Для начала заметим, что вычитая единицу из числа, мы превращаем все «правые» нули в единицы, а самую крайнюю единицу в нуль:

    1001010100010000 - 1 =
    1001010100001111
    

    Далее применим операцию логического «и» для этих чисел:

    1001010100010000 &
    1001010100001111 =
    1001010100000000
    

    Как видите, таким хитрым способом мы сбросили в нуль самую правую единицу. Повторяем эту операцию, пока не получим в результате нуль. Сколько итераций, столько и единичных битов. Правда, здорово!?

    Вот как записывается этот алгоритм полностью:

            int movesCount = 0;
            while (movesBits != 0)
            {
                movesBits &= (movesBits - 1);
                movesCount ++;
            }
    

    Задача решена!


    У этой задачи есть другое, очень простое, чисто логическое решение: определить удалённость коня от края шахматной доски (в углу 2 хода, возле края от 3 до 6 ходов, в центре 8 ходов). Но если бы мы решали задачу «в лоб» таким образом, то не узнали бы про битовую доску, про вертикальные битовые маски, про алгоритм быстрого подсчёта единичных битов и про чёрные дыры для сферических коней в вакууме…

    Теперь мы про это всё знаем. Жизнь шахматного программиста стала более богатой и осмысленной, ура!

    Самостоятельное задание: сделайте то же самое для Шахматного короля.
    OTUS. Онлайн-образование
    699,77
    Цифровые навыки от ведущих экспертов
    Поделиться публикацией

    Комментарии 19

      +4
      Дано: knightNr — номер клетки доски, где стоит конь (от 0 до 63).
      Надо: movesCount — количество полей, куда он может пойти (от 2 до 8).

      Почему бы не завести массив из 64 элементов по ~3 бита, чтобы извлекать из него цифры непосредственно? Или даже из 16 элементов, если учитывать симметрии доски?
      Более того, близость коня к краю доски отсекает некоторые из его 8ми ходов, и, наверно, можно написать несложную функцию из if-ов для решения этой задачи.

        +1
        В конце статьи я даю ответ на этот вопрос. По поводу 3 битов — спасибо, отличная мысль.
        Ещё одна причина — на практике часто нужно знать не только количество, но и сами ходы.
        +7
        Самый быстрый способ

        POPCNT?
        0
        POPCNT?

        Такая штука не на всех процессорах есть :-)
          –4
          Процессор без SSE4.2 в 2019 году?
          Можно при отсутствии этого флага выводить ругательное сообщение с предложением таки поагредить систему. Или перейти к варианту Б.
            0

            ARM?

              0
              В ARM есть CNT.
              На самом деле, мой первоначальный комментарий был к двоякости фразы «самый быстрый способ».
                0
                Может быть мелкий микроконтроллер, там тоже подобных инструкций может не быть.
          +3
          Приведённый алгоритм хорош для малозаполненных битбордов. Наличие в нём цикла и проверки условия не слишком дружественно к предсказателю ветвлений в процессоре. Поэтому, если важна скорость, обычно используют или ассемблерные вставки с POPCNT, или алгоритм без циклов. Пример из моей шахматной программы:

          int CountBits(U64 b)
          {
          	if (b == 0)
          		return 0;
          
          	static const U64 mask_1 = LL(0x5555555555555555);   // 0101 0101 0101 0101 ...
          	static const U64 mask_2 = LL(0x3333333333333333);   // 0011 0011 0011 0011 ...
          	static const U64 mask_4 = LL(0x0f0f0f0f0f0f0f0f);   // 0000 1111 0000 1111 ...
          	static const U64 mask_8 = LL(0x00ff00ff00ff00ff);   // 0000 0000 1111 1111 ...
          
          	U64 x = (b & mask_1) + ((b >> 1) & mask_1);
          	x = (x & mask_2) + ((x >> 2) & mask_2);
          	x = (x & mask_4) + ((x >> 4) & mask_4);
          	x = (x & mask_8) + ((x >> 8) & mask_8);
          
          	U32 y = U32(x) + U32(x >> 32);
          	return (y + (y >> 16)) & 0x3f;
          }
          
            0
            Спасибо, очень красивое, элегантное решение!
              –1

              А есть какой-то резон кроме эстетического делать статические переменные в функции?
              Вы на какой архитектуре профилировали своё решение?

                +1
                Это быстрее работает при многократных вызовах функции. Так заполнение переменных происходит один раз при старте.
                  –1

                  я в курсе, вопрос — зачем внутри это делать, а не вне функции.

                    +2
                    Чтобы не засорять глобальную область видимости.
                    А вообще всем современным компиляторам данный static по фигу, поскольку «переменная» mask — константа.
                      –1

                      есть анонимные namespaces, и ф-ия на 30% меньше строк станет

                        0
                        С чего вы решили, что это именно ++?
                +3
                обычно используют или ассемблерные вставки с POPCNT, или алгоритм без циклов.

                Или даже метод из стандартной библиотеки. И в реализации этого метода на java 8 лишь 17 арифметических и битовых операций, а не 21, как у вас.


                код java.lang.Long#bitCount(Long)
                public static int bitCount(long i) {
                        i = i - ((i >>> 1) & 0x5555555555555555L);
                        i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
                        i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
                        i = i + (i >>> 8);
                        i = i + (i >>> 16);
                        i = i + (i >>> 32);
                        return (int)i & 0x7f;
                     }

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

              Самое читаемое