Можете подсказать хорошие книги по программиованию шахматных программ (или связянные с этим)?
Написал шахматную программу на C++. Она получилась относительно медленной (считает с приемлемой скоростью до 5 полуходов). Собираюсь переписать эту программу с использованием BitBoard и других вещей (хеш, сортировка ходов). Можете подсказать какие-то хорошие книги (можно на английском языке). На русском - почти единственная книга "Программирование шахматных программ и других логических игр".
Прирост скорости будет только от сортировки ходов и отсечения заведомо проигрышных вариантов. битборды, хэши и прочее принципиально на скорости не скажутся. Даже ускорив в разы, удастся увеличить глубину на один-два полухода. Отсечением же проигрышных веток графа можно добиться огромной глубины, вплоть до эндшпилей.
Спасибо! Теперь не буду забивать голову битбоардами - пусть пишут те, кто хочет сделать лучший движок. Все равно буду переписывать движок (т. к. тот очень сильно забит кодом и он не всегда правильно работает). Реализую сортировку ходов. А можете подсказать, какие примерно алгоритмы лучше использовать для отсечения проигрышных веток? Еще раз, спасибо за ответ!
Удивительно, но после компиляции с -O3 у меня программа стала перебирать в 10 раз быстрее (~40 000 позиций/с). Но это очень мало - мне бы хотелось миллион, как минимум))
Олег Смирнов: Ну да, включение оптимизации компилятором это первый шаг. Но 10 раз это пшик и не позволяет увеличивать глубину поиска. Про выбор ходов написано в упомянутой вами книге, там вообще много полезного написано, включая битборды и хэши. Но это уже оптимизации по памяти, по скорости, но на глубине поиска принципиально не скажутся. В первую очередь стоит пытаться увеличить глубину поиска, а для этого нужно отбрасывать заведомо проигрышные ходы. В книжке описано и про оценку позиции на доске и про порядок фигур и прочее. По хорошему, нужно делать оценку не только по положению исследуемой фигуры, но и по взаимному расположению других фигур, но это уже высший пилотаж и нужно хорошо в шахматы играть.
Лично от себя рекомендую сперва реализовать шашки, а уже потом браться за шахматы. Как раз и в алгоритмах разберётесь и в структурах данных и прочем.
Я разделил это на 2 части: алгоритмы, сокращающие дерево и алгоритмы, увеличивающие скорость. Для увеличения скорости буду использовать хеш. Битбоард не буду использовать (т. к. с ним легко запутаться и, как вы сказали, он не сильно влияет). Для отсечения,само собой, альфа-бета с сортировкой ходов, хеш (для того, чтобы не просчитывать несколько раз одну и ту же позицию), и некоторые эвристики. Сейчас моя программа играет очень слабо (рейтинг примерно 1100-1200). Да и бывает такое, что зевает фигуры ни с того ни с сего. Решил переписать, т. к. там в корне много чего надо менять.
Альфа-бета отсечение, строить дерево рассматриваемых ходов, при следующем расчете хода продлевать его листы, сортируя их по ранее полученной оценке, не оценивать уже оцененные позиции с учетом глубины их оценки
