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

Тема в разделе "Машинное отделение", создана пользователем Mustitz, 18 дек 2007.

  1. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Вот родился такой этюд :)

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

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

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

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

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Если это нужно для алгоритма закраски - то лучше делать иначе.
    Закраску вести сразу по всей поверхности.
  3. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    В даном случае это просто получился этюд, а родился он из размышлений на тему, как оптимальным образом определять дамэ у группы.
  4. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Все дамэ так-же получаются сразу по всей доске :) Также как в шахматных битбордах получают все поля битые пешками.
  5. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Доска представляется четыремя битбордами.
    Вертикальные/Горизонтальные битборды черных/белых.
    Поля идут подряд, как в шахматных битбордах. Битборд это 6 64 разрядных чисел.
    Пишем процедуры сдвига вправо/влево для битбордов состоящих из шести 64 разрядных чисел, и логических оперций (каждая превращается в 6 логических операций), а затем как обычно.
    Несколькими операциями получаем все Дамэ по доске.
  6. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    В общем случае у нас шесть 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;
    }
    Были мысли придумать что-то оптимальное, учитывая тот факт, что группа обычно находится в одной части доски и большинство операций будут над нулями. Ну и побочным образом возник этот этюд.
  7. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Зачем так сложно? Сдвиг на единицу надо делать, просто писать на Асме. Сдвиг с использованием флага переноса. А потом накладываем маску (чтоб края не переносились)
  8. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    А если ли смысл использовать два вида битбоардов? Конвертация одного в другой достаточно нетривиальна. Конечно, можно пройтись по всем вертикальным дамэ, вычеркивая их попутно из горизонтальной реализации. А потом по оставшимся горизонтальным дамэ. Но если понадобится что-то более сложное...

    Была еще задача по отдельному камню определить группу, к которой он принадлежит.
  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Обычно используют, в шахматах даже четыре :) Вертикальный/горизонтальный и два диагональных (повернутых), на преобразовании больше потеряешь чем выиграешь.

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

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

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Про шахматы я знаю, реализовывал. Но основное назначение вращенных битбоардов в шахматах это получение залпом по таблице всех возможных ходов ладьи/слона. В го таких фигур нет, остается единственное преимущество: простота сдвига с учетов флага переноса.

    Да, в моем варианте надо 8 заменить на 19 :)
  11. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Такое впечатление что лучше иметь оба представления сразу.
    На битбордах очень быстро определяются одинокие камни, территория, все дамэ.
    А группы быстрее определять на массиве.
  12. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Хотя можно действительно использовать один битборд и сдвиг на 19 для вертикалей.
  13. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Группы вообще хочется кэшировать. вопрос в том, намного ли хуже вычислять?

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Это легко. Предопределенный массив на 361 элемент, в котором для каждого поля хранится номер слова и номер бита в нем. Или вычислять адрес сдвигом на 64.
  15. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Я шел по пути номер слова/битовая маска соседей/битовая маска соседей для следующего слова. Ну и заодно решил поискать решения в случае, когда нумерация битов в битбоарде не последовательная. Естественно, что в этом случае хотелось бы (а) чтобы по возможности хватало одной битовой маски и (2) битовых масок было бы более двух. Так возник этюд, который имеет элегантное решение :) В общем случае, думаю что решение хранить биты последовательно лучше (две последовательных битовых операции без условий vs вторая битовая операция по условию)
  16. NS Нефёдов Сергей

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Битовое представление в Го - это не то место, где можно сэкономить, ИМХО.
    В шахматах-то, гдё всё как специально под битборды заточено - и то для perft мэйлбокс и битборд идут ноздря в ноздрю...
  18. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Вместо стека лучше использовать 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...
      }
  19. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Возможно, с точки зрения предметной области, в Го перспективнее использовать представление не для отдельных пересечений, а для связей между ними. Получаем доску 18х18 элементов, где каждый элемент может быть в 3х3=9 состояниях (белый, чёрный камень или ничего в каждой из двух вершин).
  20. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Закраска сразу по всей доске в битбордах (определение территории), и определение одиночных камней за несколько операций - может перекрыть все недостатки битбордов.
  21. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    WinPooh #19 Сегодня 17:29:18

    А чем это перспективней?
  22. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    А оно надо, для сколь-нибудь приемлемой силы игры?
    Или надо всё-таки что-то чуть более сложное?
  23. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.222
    Симпатии:
    2.526
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Не знаю :)
    Я написал, "возможно".

    Интуиция + опыт игрока в Го подсказывают.
    Не думаю я в терминах отдельных камней во время партии.
  24. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да, надо. И оно надо, и более сложное надо.
  25. TopicStarter Overlay

    Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.136
    Симпатии:
    553
    Репутация:
    25
    Адрес:
    Киев
    Оффлайн
    Я не могу в приемлемом виде описать то, как я думаю. Ни в шахматах, ни в го. Ботвинник пытался.

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

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

Поделиться этой страницей