Доброго времени суток. Появилось свободное время, решил написать игру в шашки. Так вот сейчас думаю над тем, как компьютер будет искать лучший ход. По идее, если комп думает на n ходов вперёд, то последовательность его действий должна быть приблизительно такая:
для всех возможных дозволенных ходов:
1. записать ход
2. пересмотреть все возможные ответы соперника и найти из них самый лучший (с точки зрения соперника) причем думать за соперника надо с наверное на n-1 хода вперёд.
3. пересмотреть все свои возможные ответы на такой ход думая на n-2 хода вперёд.
и так далее, пока глубина просчета не достигнет 0. Вроде бы получается рекурсивный алгоритм, но программа при любом не совсем маленьком n будет тормозить наверное ужасно. Не подскажете ли что нибудь получше? Любые идеи прочитаю с интересом.

А ты напиши и проверь скорость.. а то раздумывать над алгоритмами долго можно

Можно на все возможные варианты расстановки шашек создать по нейронной сети: 2 слоя, у первого слоя 1 вход и N выходов, у второго N входов и M выходов, где входам N соответствует позиция своей шашки, которая ходит; выходам M соответствует позиция, куда эта шашка ходит; обучающим значением служит эффективность хода, т.е. 1 или 0 в зависимости от того, выиграна вся партия или нет, разделённая на номер хода (чем ближе к началу, тем больше вес). Работать сеть будет так: на единственный вход подаём единицу и анализируем, на каком из M выходов максимальное значение - это и будет позиция, "куда ходим".

Обучить все эти нейронные сети, перебрав random-ом все возможные ходы. В конце каждой партии возвращать ошибку по всем участвовавшим НС, зная результат (1 или 0). Это займёт большое время. Результатом будет база данных весовых коэффициентов нейронных сетей, которую можно дополнительно пообучать вручную, усадив какого-нибудь любителя шашек . Всё что останется делать программе в real-time - это для текущей расстановки шашек найти соотв. конфигурацию нейронной сети из базы данных (т.е. "поднять" весовые к-ты ходов) и получить результат у сети - куда ходить компу.

З.Ы. сеть простая, обратного распространения ошибки.

mr.DUDA, спасибо, это интересный вариант. Я слышал, что нейронные сети как раз часто используются для такого рода проблем. К сожалению, знаком с ними только понаслышке, но заодно будет возможность изучить их получше. Только как то влом обучать потом эту сеть - шашечным энтузиастом я не являюсь (больше шахматы люблю) ну может можно будет без этого обойтись.

Цитата(segmentation_fault @ 20.11.2005, 13:13)

Только как то влом обучать потом эту сеть - шашечным энтузиастом я не являюсь (больше шахматы люблю) ну может можно будет без этого обойтись.

Бывают сети с самообучением, но имхо если "посадить друг напротив друга" два компа -- вначале оба будут тупить по страшному, а через пару сотен игр выработают каждый свою стратегию и будут постоянно её применять с небольшими вариациями, так что придётся либо менять одного из противников, либо вносить "элемент неожиданности" - в произвольный момент времени в игру вмешивается третий игрок: функция random(), и делает пару-тройку ходов за оба компа... В любом случае, можно ведь изменять тактику обучения НС на ходу, глядя на результат. Ещё было бы неплохо прогнать через НС все известные игры, сыгранные гроссмейстерами когда-либо, вначале за белых, потом за чёрных.

Пожалуйста, подскажите где можно скачать скрипты онлайн шахмат или шашек 

Ну, есть способ поначалу долго парить комп, но потом AI быстро будет работать. См. подход Fogel и Chellapilla - они лет 15 назад запускали генетический алгоритм над популяцией нейросеток, стравливая сетки друг с другом и потом по результатам игр назначая значения фитнес-функции в зависимости от результативности. В итоге отбираются-эволюционируют сетки вплоть до достижения уровня чуть ли не международного мастера. Подробнее см. статью на английском - к фамилиям добавь checkers (шашки по-английски) и запусти в гугле поиск. Pdf-ки статьи валялись в инете свободно.
Т.е. если есть в наличии алгоритмы по НС и ГА, то такой подход может потребовать минимум трудозатрат - не надо программировать никаких переборов ходов и оценок позиции, а комп можно запустить на выходные поработать - он и найдет лучшую сетку. Не хватит у сетки умения - еще на пару дней можно оставить комп считать ;)
В итоге можно хоть на мобильник саму игру и код обученной сетки перенести - никакого перебора там не будет, всё считаться будет за доли секунды