Этюд для программистов: разбиение гобана

Вот родился такой этюд

Есть доска 19x19. Для этой используется некоторая битовая маска (массив из 361 бит). Этот массив логично представить в виде шести 64-битных числа (всего 384 бита), в дальнейшем эти 64-битные числа мы будем называть блоками.

Битовая маска называется сокращенной, если все у нее все блоки, кроме одного, нулевые. Битовая маска называется слабо сокращенной, если у нее по не более чем два ненулевых блока.

Если каждому пункту доски поставлен в соответствие одн из шести блоков, то будем говорить о разбиении доски. Разбиение называется правильным, если для каждому блоку соответствует не более 64 пунктов доски.

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

Задача:
1. Найти правильное разбиение с максимальным количеством сокращенных битовых маск
2. То же самое, что и пункт (1), но в разбиении допустимы только сокращенные и слабо сокращенные битовые маски.

 

Если это нужно для алгоритма закраски - то лучше делать иначе.
Закраску вести сразу по всей поверхности.

 

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

 

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

 

Доска представляется четыремя битбордами.
Вертикальные/Горизонтальные битборды черных/белых.
Поля идут подряд, как в шахматных битбордах. Битборд это 6 64 разрядных чисел.
Пишем процедуры сдвига вправо/влево для битбордов состоящих из шести 64 разрядных чисел, и логических оперций (каждая превращается в 6 логических операций), а затем как обычно.
Несколькими операциями получаем все Дамэ по доске.

 

В общем случае у нас шесть 64-битных чисел. Получаем сдвиг

Код:

shift_down(uint64* bitgoban)
{
  bitgoban[0] >>= 19;
  bitgoban[0] |= (bitgoban[1] << 45) & (0x7FFFF << 45);
  bitgoban[1] >>= 19;
  bitgoban[1] |= (bitgoban[2] << 45) & (0x7FFFF << 45);
  ... 
  bitgoban[5] >>= 19;
}

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

 

Зачем так сложно? Сдвиг на единицу надо делать, просто писать на Асме. Сдвиг с использованием флага переноса. А потом накладываем маску (чтоб края не переносились)

 

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

Была еще задача по отдельному камню определить группу, к которой он принадлежит.

 

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

Определение групп, группы по камню, и дамэ отдельно по группе это отдельная задача.

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

 

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

Да, в моем варианте надо 8 заменить на 19

 

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

 

Хотя можно действительно использовать один битборд и сдвиг на 19 для вертикалей.

 

Группы вообще хочется кэшировать. вопрос в том, намного ли хуже вычислять?

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

 

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

 

Я шел по пути номер слова/битовая маска соседей/битовая маска соседей для следующего слова. Ну и заодно решил поискать решения в случае, когда нумерация битов в битбоарде не последовательная. Естественно, что в этом случае хотелось бы (а) чтобы по возможности хватало одной битовой маски и (2) битовых масок было бы более двух. Так возник этюд, который имеет элегантное решение В общем случае, думаю что решение хранить биты последовательно лучше (две последовательных битовых операции без условий vs вторая битовая операция по условию)

 

А какая битовая операция по условию?
Завели стек, поместили туда начальное поле, завели структуру для хранения группы.
Пока стек не пустой:
Заносим поле из стека в структуру, удаляем поле из стека, очищаем это поле на доске, для каждого из четырех соседей если они "наши" вносим их в стек. Элементарный алгоритм. проверка для каждого соседа одна.
С краями - на края добавляется 18 пустышек на поле. Итого 361+18=379, влезаем в 6 битбордов.

 

Вместо стека лучше использовать bitboard. Получается следующее:

Код:

void find_group(field_t filed, bitboard_t& group, bitboard_t& dame)
{
  bitboard_t new_stones = Field;
  group = 0;
  dame = 0;
  
  while(new_stones != 0)
  {
    field_t stone = extract_stone(new_stones);

//    dame |= free_points & neighbor(stone);
// На самом деле
  register int i = qword_index[stone];
  dame[i] |= free_points[i] & neighbor1[stone];
  dame[i+1] |= free_points[i+1] & neighbor2[stone];
  

    group |= stone;
//    new_stones |= my_stones & neighbor(stone) & ~group;
// Skipped...
  }

 

Закраска сразу по всей доске в битбордах (определение территории), и определение одиночных камней за несколько операций - может перекрыть все недостатки битбордов.

 

WinPooh #19 Сегодня 17:29:18

А чем это перспективней?

 

Да, надо. И оно надо, и более сложное надо.

 

Я не могу в приемлемом виде описать то, как я думаю. Ни в шахматах, ни в го. Ботвинник пытался.

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

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