Не понимая, как работает техника битборда для шахматных досок

Question

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

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘ 

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

Теперь представьте, что пользователь перемещает треугольник в последнюю позицию, например так:

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ ● │   │ ▲ │
└───┴───┴───┴───┴───┴───┴───┴───┘

Для этого примера битборд движения треугольника

1 1 0 1 1 1 1 1

и маска положения круга

0 0 0 0 0 1 0 0

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

Answer 1

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

Шахматный кейс

Самые последние шахматные движки используют технику, известную как Magic Bitboards.

Реализации различаются, но основной принцип всегда один и тот же:

1. Выделите квадраты, которые данная фигура может достичь из данной позиции, не принимая во внимание занятость доски. Это дает нам 64-битную битовую маску потенциальных целевых квадратов. Давайте назовем это T (для цели).

2. Выполните побитовое И Т с битовой маской из занятых квадратов на доске. Давайте назовем последний O (для Занятых).

3. Умножьте результат на магическое значение M и сдвиньте результат вправо на магическое количество S. Это дает нам I (для индекса).

4. Используйте I в качестве индекса в таблице поиска, чтобы получить битовую маску квадратов, которая может быть фактически достигнута с помощью этой конфигурации.

Подвести итог:

I = ((T & O) * M) >> S
reachable_squares = lookup[I]

T, M, S и поиск все предварительно рассчитаны и зависят от положения фигуры (P = 0... 63). Итак, более точная формула будет:

I = ((T[P] & O) * M[P]) >> S[P]
reachable_squares = lookup[P][I]

Цель шага № 3 - преобразовать 64-битное значение T & O в гораздо меньший, так что можно использовать таблицу разумного размера. Что мы получаем, вычисляя ((T & O) * M) >> S по сути случайная последовательность битов, и мы хотим отобразить каждую из этих последовательностей в уникальную битовую маску достижимых целевых квадратов.

"Волшебная" часть в этом алгоритме состоит в том, чтобы определить значения M и S, которые будут создавать таблицу поиска без столкновений как можно меньше. Как заметил Бо Перссон в комментариях, это проблема Perfect Hash Function. Однако до сих пор не было найдено идеального хэширования для магических битовых досок, что означает, что используемые таблицы поиска обычно содержат много неиспользуемых "дырок". Большую часть времени они создаются с помощью обширного перебора.

Ваш тестовый кейс

Теперь вернемся к вашему примеру:

┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ ▲ │   │   │ ● │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘ 
  7   6   5   4   3   2   1   0

Здесь положение фигуры в [0 ... 7] и битовая маска занятости находится в [0x00 ... 0xFF] (так как это 8-битная ширина).

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

У нас будет:

reachable_squares = lookup[P][board]

Это приведет к поиску таблицы, содержащей:

8 * 2^8 = 2048 entries

Очевидно, что мы не можем сделать это для шахмат, поскольку они будут содержать:

64 * 2^64 = 1,180,591,620,717,411,303,424 entries

Отсюда необходимость магических операций умножения и сдвига для хранения данных в более компактной форме.

Ниже приведен фрагмент JS, иллюстрирующий этот метод. Нажмите на доску, чтобы переключать фигуры противника.

var xPos = 5,          // position of the 'X' piece
    board = 1 << xPos, // initial board
    lookup = [];       // lookup table

function buildLookup() {
  var i, pos, msk;

  // iterate on all possible positions
  for(pos = 0; pos < 8; pos++) {
    // iterate on all possible occupancy masks
    for(lookup[pos] = [], msk = 0; msk < 0x100; msk++) {
      lookup[pos][msk] = 0;

      // compute valid moves to the left
      for(i = pos + 1; i < 8 && !(msk & (1 << i)); i++) {
        lookup[pos][msk] |= 1 << i;
      }
      // compute valid moves to the right
      for(i = pos - 1; i >= 0 && !(msk & (1 << i)); i--) {
        lookup[pos][msk] |= 1 << i;
      }
    }
  }
}

function update() {
  // get valid target squares from the lookup table
  var target = lookup[xPos][board];

  // redraw board
  for(var n = 0; n < 8; n++) {
    if(n != xPos) {
      $('td').eq(7 - n)
        .html(board & (1 << n) ? 'O' : '')
        .toggleClass('reachable', !!(target & (1 << n)));
    }
  }
}

$('td').eq(7 - xPos).html('X');

$('td').click(function() {
  var n = 7 - $('td').index($(this));
  n != xPos && (board ^= 1 << n);
  update();
});

buildLookup();
update();

td { width:16px;border:1px solid #777;text-align:center;cursor:pointer }
.reachable { background-color:#8f8 }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
  <tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</table>