Компьютерные шахматы взорвались за последние двадцать лет, с установлением чемпионата мира по компьютерным шахматам, и многие шахматные компьютерные дизайнеры становятся весьма прибыльными от их усилий. Некоторые из программ скрывают свой исходный код, но многие из них с открытым исходным кодом, в частности Fruit, который послужил основой для семейства шахматных движков.
Каковы некоторые примеры эвристики или алгоритмов, используемых шахматными компьютерами, и которые были наиболее успешными или наиболее популярными?
engines
chess-algorithms
Эндрю Лэтэм
источник
источник
Ответы:
В основном используемые алгоритмы основаны на поиске пространства состояний. Проблема в том, что возможные позиции, которые может занять фигура в следующем ходу, очень велики. Но это конечно. Это в основном проблема поиска. Есть правильная позиция, которую может занять фигура. То есть существует известное начальное состояние и известное конечное состояние. Нет никакой вероятности, связанной с подбрасыванием монеты.
Типичным алгоритмом является использование грубой силы и вычисление ходов для фиксированного количества ходов. MiniMax можно использовать в таких случаях. Альфа-бета-обрезка также является хорошо известным алгоритмом. В основном, пространства поиска представлены с использованием древовидной структуры данных.
Компьютерная программа также активно использует базы данных, содержащие ходы, дебюты, позиции в конце игры и т. Д.
источник