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

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

  1. TopicStarter Overlay

    olpa Oleg Parashchenko

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

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

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

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

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

    Не нравятся мне все эти проверки. Наверняка изящное решение уже существует. Подскажите, пожалуйста.
  2. VladAndreev Учаcтник

    • Участник
    Рег.:
    30.06.2011
    Сообщения:
    58
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Stuttgart
    Оффлайн
    Если эффективность не нужна, то все просто. Держим позицию в массиве 8х8, делаем ход (1...Rg8, например), смотрим есть ли шах черным. Шах есть, значит ход нелегальный.
  3. Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.434
    Симпатии:
    1.020
    Репутация:
    26
    Адрес:
    Киев
    Онлайн
    Для скриптовых языков (JavaScript, PHP) напрашивается 0x88 на асоциативных массивах. Дома есть генератор ходов на JavaScript, если интересно, могу выложить исходники.
  4. VladAndreev Учаcтник

    • Участник
    Рег.:
    30.06.2011
    Сообщения:
    58
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Stuttgart
    Оффлайн
    Согласен, хотя если простота реализации важнее эффективности, то 0x88/mailbox наверное все-таки не оптимальны. Хотя кому как.
  5. Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.434
    Симпатии:
    1.020
    Репутация:
    26
    Адрес:
    Киев
    Онлайн
    Ну так на JavaScript bitboard-ы будут медленнее и прожорливее :) Хотя бы потому, что там нет 64-битных чисел, и надо будет их эмулировать.
  6. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
  7. Chemer Максим

    • Участник
    Рег.:
    14.09.2006
    Сообщения:
    1.674
    Симпатии:
    13
    Репутация:
    0
    Адрес:
    Запорожье
    Оффлайн
    Народ, нафига плодить темы? Слабо поискать в этом же разделе эпические темы о представлении доски. :/
  8. TopicStarter Overlay

    olpa Oleg Parashchenko

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

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

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

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

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