структура данных для шахматной доски?

Тема в разделе "Машинное отделение", создана пользователем olpa, 5 авг 2011.

  1. olpa
    Оффлайн

    olpa Oleg Parashchenko

    Репутация:
    0
    Описан ли где стандартный подход для представления позиции в памяти? Эффективность не нужна, важнее простота реализации.

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

    Рассмотрим позицию:

    Чёрные играют Rg8. Программа должна воспроизвести этот ход.

    * Между полем a8 и g8 всё свободно, так что ход Ra8-g8 возможен
    * Между полем g7 и g8 всё свободно, так что ход Rg7-g8 возможен?
    * Нет, Rg7-g8 невозможен из-за слона a1, ибо ладья связана.
    * На чтобы это понять, надо заметить того слона (+ усложнение кода)
    * При этом, если бы ладья a8 была на b8, а на a8 была бы белая ладья, то хотя бы чёрная ладья и была бы связана, но на g8 ей бы всё равно можно было сходить.

    Не нравятся мне все эти проверки. Наверняка изящное решение уже существует. Подскажите, пожалуйста.
     
    olpa, 5 авг 2011
    #1
  2. VladAndreev
    Оффлайн

    VladAndreev Учаcтник

    Репутация:
    0
    Если эффективность не нужна, то все просто. Держим позицию в массиве 8х8, делаем ход (1...Rg8, например), смотрим есть ли шах черным. Шах есть, значит ход нелегальный.
     
    VladAndreev, 5 авг 2011
    #2
  3. Mustitz
    Оффлайн

    Mustitz баннер

    Репутация:
    36
    Для скриптовых языков (JavaScript, PHP) напрашивается 0x88 на асоциативных массивах. Дома есть генератор ходов на JavaScript, если интересно, могу выложить исходники.
     
    Mustitz, 5 авг 2011
    #3
  4. VladAndreev
    Оффлайн

    VladAndreev Учаcтник

    Репутация:
    0
    Согласен, хотя если простота реализации важнее эффективности, то 0x88/mailbox наверное все-таки не оптимальны. Хотя кому как.
     
    VladAndreev, 5 авг 2011
    #4
  5. Mustitz
    Оффлайн

    Mustitz баннер

    Репутация:
    36
    Ну так на JavaScript bitboard-ы будут медленнее и прожорливее :) Хотя бы потому, что там нет 64-битных чисел, и надо будет их эмулировать.
     
    Mustitz, 5 авг 2011
    #5
  6. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    WildCat, 5 авг 2011
    #6
  7. Chemer
    Оффлайн

    Chemer Максим

    Репутация:
    0
    Народ, нафига плодить темы? Слабо поискать в этом же разделе эпические темы о представлении доски. :/
     
    Chemer, 6 авг 2011
    #7
  8. olpa
    Оффлайн

    olpa Oleg Parashchenko

    Репутация:
    0
    Спасибо за советы и ссылки. На "chessprogramming", на первый взгляд, много информации, но как-то всё очень водянисто. Зато там есть ссылка на статью Robert Hyatt'a (автор crafty)

    Похоже, что самое простое — это массив 12x12, а представление 0x88 — это уже низкоуровневая оптимизация.

    С доской всё понятно. Следующий вопрос: как "выполнять" ходы (тот же Rg8: Rg7-g8 vs Ra8-g8)?

    Похоже что да, без усложнения структур данных (заранее просчитанных атак), придётся каждый раз проверять на шах.
     
    olpa, 6 авг 2011
    #8