BitBoard в шахматах, какие бывают виды, чем они отличаются?

Тема в разделе "Машинное отделение", создана пользователем NS, 18 ноя 2006.

  1. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В чем преимущества и недостатки разных видов BitBoard-ов?
  2. atoku Модератор

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    2.949
    Симпатии:
    9
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    Давно надо было поднять такую тему. Из моего небольшого опыта выходит, что генератор получается очень быстро, а вот ОФ писать на этом сложнее чем на других вариантах. Я не прав?
  3. TopicStarter Overlay

    NS Нефёдов Сергей

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

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Насчет генератора - 0x88 генератор очень простой, и пишется очень быстро (Для любых игр 8x8)
    БитБоард генератор в любом случае сложней.
  5. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А кто из наших использует битборды?
  6. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Марков, Морозов, Медведев.
  7. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    "В чем преимущества и недостатки разных видов BitBoard-ов?"

    Да разница там лишь в способе генерирования ходов дальнобойных фигур :).

    По поводу сложности: я перепробовал все генераторы ходов (booot 2- 4) и остановился на битбордах как на самом удобном :). Что генерирование ходов, что ОФ там намного удобнее пишется, чем на других представлениях. Просто привыкнуть немного и все.
  8. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    То есть нет особого смысла в использовании повернутых... Или есть?
  9. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    "То есть нет особого смысла в использовании повернутых... Или есть?"

    Ну как... повернутые битборды позволяют крепко выиграть время при генерации ходов дальнобойных фигур. И только. В отличии от "просто битбордов" там всего лишь появляется 3 дополнительных битборда, содержащих повернутое представление шахматной доски. Ну и куча предвычисленных массивов :)
  10. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А тоо что Pradu писал по поводу Магических чисел в Битбоард генераторах читал?
    Или это глупости?
  11. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Нет! Это новый способ :). Причем судя по всему крайне быстрый! Но есть одно НО! (точнее 2 :) ).
    1. Нахождение магических чисел отдельная задача с шахматами малосвязанная.
    2. метод требует операции 64-разрядного умножения. Что подразумевает эффективность метода только в 64-разрядных системах.
  12. TopicStarter Overlay

    NS Нефёдов Сергей

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

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Перспективно еще чем: если хочешь таки как-то позиционные признаки распознавать, то битборды - то что для этого прямо и существует :)
  14. TopicStarter Overlay

    NS Нефёдов Сергей

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

    NS Нефёдов Сергей

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

    NS Нефёдов Сергей

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

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    12.02.2006
    Сообщения:
    2.201
    Симпатии:
    64
    Репутация:
    3
    Оффлайн
    Опасно переходить. Всё-таки МММ получается. ;)
  18. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    Согласен. Битборды просто не стоят того, чтобы ими заниматься. Я тоже использую схему 0x88 и меня это вполне устраивает. Быстро и просто, код понятный получается. А с битбордами слишком много заморочек.
  19. варяг Учаcтник

    • Участник
    Рег.:
    23.10.2006
    Сообщения:
    98
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Гонду-Раша
    Оффлайн
    Я бы даже сказал МММ в квадрате :)
  20. TopicStarter Overlay

    NS Нефёдов Сергей

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

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