Comments 11
До этого дня я думал, что самое впечатляющее использование битмапов это blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/
И вот #:) моя вера разрушена #:)
И вот #:) моя вера разрушена #:)
Всё это наверняка компилируется под 64-битную архитектуру, чтобы быстрее работало?
UFO just landed and posted this here
Большое спасибо за подсказку. Я оформлял пост первый раз и не обратил внимание, как оформляется перевод. Теперь я вижу, как оформить, но изменить пост, к сожалению, не получается. Не могу найти ни как изменить тип поста, ни как удалить старый (чтобы создать правильный новый). В будущем намотаю на ус.
Кстати интересно, они в кэше позиций тоже её хранят 16x64 бит представлении?
Както расточительно использовать 16 64х битных слова на доску, в классических шахматах. Ведь у нас максимум 24 фигуры на доске, разнообразие которых (учитывая цвет) всеголишь 12. То есть для кодировки доски достаточно 1го 64 битного слова определяющего занятые позиции, и перечисления этих позиций 24*4=96 бит. Итого два с половиной 64битных слова. Для расчета битых полей можно было бы использовать предустановленные маски отсечения вертикалей и горзинталей.
Както расточительно использовать 16 64х битных слова на доску, в классических шахматах. Ведь у нас максимум 24 фигуры на доске, разнообразие которых (учитывая цвет) всеголишь 12. То есть для кодировки доски достаточно 1го 64 битного слова определяющего занятые позиции, и перечисления этих позиций 24*4=96 бит. Итого два с половиной 64битных слова. Для расчета битых полей можно было бы использовать предустановленные маски отсечения вертикалей и горзинталей.
Для тех кто не понял про расточительность в данном случае поясняю, количество просмотренных позиций при расчете в глубину растет экспоненциально. Соответственно чтобы не обсчитывать кучу раз одну и туже позицию её выгоднее хранить в кэше. При этом естественно чем меньше размер занимаемый позицией, тем больше их может в кэше хранится. Разница на милиарде позиций по памяти будет очень значительна.
Возможно, в данном случае важнее было оптимизировать по производительности, чем по памяти.
Интересно, а можно как-то еще уменьшить объем занимаемой позиции?
В указанном расчете, например, не учтено, что пешки могут занимать только 6 клеток. Например, чтобы сохранить позицию половины фигур на доске (16 пешек), достаточно 36 бит.
Также в указанном расчете все 24 фигуры могут быть одного цвета. А мы знаем, что это не так. Более того, есть статистика, которая могла бы быть полезна для уменьшения хранения позиции. Например, в очень незначительном количестве позиций, участвующих в реальном расчете на доске есть более 3 ферзей, 4 слонов, 4 коней или 4 ладей.
Также точно известно что королей всегда ровно два.
Крайне любопытно, на сколько компактно ЭТО можно уложить? Можно ли уложить в 128 бит?
Ну и конечно, для реальной задачи надо учесть не только расстановку фигур. В шахматах две идентичные по расстановке позиции могут отличаться тем, что есть ли у каждой из сторон возможность провести рокировку в обе стороны, и можно ли следующим ходом какую-то пешку взять на проходе.
В указанном расчете, например, не учтено, что пешки могут занимать только 6 клеток. Например, чтобы сохранить позицию половины фигур на доске (16 пешек), достаточно 36 бит.
Также в указанном расчете все 24 фигуры могут быть одного цвета. А мы знаем, что это не так. Более того, есть статистика, которая могла бы быть полезна для уменьшения хранения позиции. Например, в очень незначительном количестве позиций, участвующих в реальном расчете на доске есть более 3 ферзей, 4 слонов, 4 коней или 4 ладей.
Также точно известно что королей всегда ровно два.
Крайне любопытно, на сколько компактно ЭТО можно уложить? Можно ли уложить в 128 бит?
Ну и конечно, для реальной задачи надо учесть не только расстановку фигур. В шахматах две идентичные по расстановке позиции могут отличаться тем, что есть ли у каждой из сторон возможность провести рокировку в обе стороны, и можно ли следующим ходом какую-то пешку взять на проходе.
Если брать классические шахматы, то уже кодировать 64битным словом маску занятых полей накладно. Ведь очевидно, что это слово будет хорошо сжимаемо стандартными алгоритмами сжатия (если рассматривать не байты, а биты). Например кодирование пересечений уже будет занимать меньше места: один байт на проекцию сверху, один байт на проекцию сбоку плюс байт (на всякий случай, а то сейчас прям доказать однозначность/неоднозначность такого кодирования не смогу) на кодирование противоречий. То есть 24 бита на маску доски вместо 64х.
То что на одну фигуру надо 12 значений, вместо 16, которые кодируются 4мя битами, тоже намекает нам о неэффективности. Значит типы и цвета фигур представимы в 12ричной системе максимум 24ю цифрами. В двоичной системе такое число представимо 56ю битами. Итого уложились в 128 бит с лихвой :)
То что на одну фигуру надо 12 значений, вместо 16, которые кодируются 4мя битами, тоже намекает нам о неэффективности. Значит типы и цвета фигур представимы в 12ричной системе максимум 24ю цифрами. В двоичной системе такое число представимо 56ю битами. Итого уложились в 128 бит с лихвой :)
Sign up to leave a comment.
Вращаемые битборды: новый виток старой идеи