- В этой теме 5 ответов, 3 участника, последнее обновление 15 лет, 8 месяцев назад сделано
.
-
Сообщения
-
Собираюсь начать писать программы, играющею в Русские шашки. Точнее не полноценную программу, а класс для игры компьютера. Это уже 3-я моя попытка сделать игру Русские шашки.
Пока продумываю алгоритмы. Есть несколько моментов, которые хотелось бы узнать, как реализуются в других программах (если это не является секретом):
1. Какие структуры данных используются для представления шашечной доски, массивы или что-то иное (например, битовые поля)?
2. Как просчитывается оценка хода, применяется ОФ в момент достижения самой глубокой позиции или она строится динамически во время всего прохождения по дереву игры?
3. Как реализуются возможности запоминать уже рассмотренные позиции (тут вообще пока что не придумал каких-либо нормальных и быстрых решений)?Первая версия моей программы будет работать без баз, только перебор. Сейчас стоит задача максимально повысить качество перебора (за счёт увеличения глубины перебора и улучшения ОФ).
3. Их не надо придумывать, они известны уже несколько десятков лет.
А первые два пункта можно посмотреть в исходниках SiDra.
Они есть тут:Думаю важнее для начала получитьс просто правильно работающую программу, а затем заняться оптимизацией. Иначе проект с места сдвинуть будет трудно.
Забудьте про битывые поля и прочее, просто для начала обычный массив 8х8 — есть боле эффективные структуры, но это следующим шагом.
Эффективность структур для данных повысит производительность на линейный коэффициэнт.
Хооший алгоритм даже при примитивных структурах данных увеличит силу игры гораздо гораздо больше.Навесить хеш, ходы-убийцы, историю, справочники и прчее надо уже на работающий скелет (сделать это все сразу с нуля будет очень ирудно и долго)
Думаю важнее для начала получитьс просто правильно работающую программу, а затем заняться оптимизацией. Иначе проект с места сдвинуть будет трудно.
Забудьте про битывые поля и прочее, просто для начала обычный массив 8х8 — есть боле эффективные структуры, но это следующим шагом.
Дело в том, что у меня уже есть опыт, есть 1-я программа, которую я писал, она рабочая, доска — массив 8*4 (по чёрным клеткам), считает только перебором с отсечением и сортировкой узлов. Глубина перебора была 12-14 полуходов.
Вот её я начал писать как раз по принципу «главное, что бы заработала, а потом буду оптимизировать». В конечном счёте от бесконечных оптимизаций зашёл в тупик.
Теперь хочу писать сразу правильно, что бы потом не ворочать большие куски кода. Вот интересуют некоторые моменты, как лучше сделать.ходы-убийцы
Что это такое, можно подробнее?
если какой-то ход является сильнейшим в уже просчитанной позиции, то вполне вероятно, что он будет достаточно хорош в позиции схожей с данной (например полученной от одной и тойже родительской позиции)
- Для ответа в этой теме необходимо авторизоваться.