Пишу игру шашки, уже реализовал вывод доски, ход, рубку. Не могу сделать AI для шашек. Пишу на с++, с использованием графического движка.Кто-нибудь может обьяснить какой-нибудь простой алгоритм или дать примеры.

Ну если "простой алгоритм", то сохраняешь копию доски, отключаешь вывод на экран, делаешь первый возможный ход, оцениваешь результаты (изменение общего количества белых, изменение количества дамок белых и то же самое для черных). Восстанавливаеш доску из сохраненной копии и делаешь слендующий возможный ход. Так повторяешь для всех вариантов. Потом из результататов оценки выбираеш лучший, включаешь вывод на экран и делаешь этот ход. Для увеличения качества результата потом можешь увеличить глубину перебора и продумывать на большее число ходов вперед. 
Но это все равно очень по простому, действительно крутые шашечные движки вытворяют страшные вещи   

я писал шашки,но там комп играет кабут неделю назад научился,но все по правилам и ходить умеет и знает когда бить.

Я взял 64 PictureBox,и придал шашкам цифру,так как комп думает по цифровому.
Белые это 1 черные -2 и пустая клетка -0......комп ходит так у меня......берет из ума число до 64 и проверяет есть ли шашка,то есть клетка равно ли двум.....потом смотрит куда пойти налево или направо..у шашки два варианта хода, вариант тоже из ума берется....если клетка пустая то ходит.Перерисовываем клетку.И при этом изменяем данные этой клетки...........надо написать все варианты как комп бьет как ходит и потом как дамки бьют....это вариантов 200.получится 200 строк....и если включить опцию " играют два компа" то все ходы переделать надо на белые шашки..дам ссылку на прогу,посмотришь

M arilou

а можно как-то попонятнее написать? а то этот поток сознания нечитабелен

Это сообщение отредактировал(а) arilou - 20.1.2009, 02:48

Насколько я знаю, современные шашечные программы имеют в себе базу позиций на все случаи жизни (книгу дебютов). С некоторых пор обучение шашкам среди людей превращается в тупую зубрёжку дебютов, иначе ты ошибешься и проиграешь. В шахматах дерево позиций много больше, но всёравно начало партий изучено на 20 ходов вперед, а для окончаний где по 5 фигур на доске даже построено дерево позиций с характеристикой результата при ходе той или иной стороны. короче, ИМХО, шашки умирают.

В принципе, если автор не хочет писать непобедимый комп, а просто хочет поразвлечься с ИИ, он может этим не пользоваться и писать ИИ без базы позиций.

Kakadu, как показывает практика людей которые потратили на шашечные программы не один месяц жизни, слишком большая база окончаний может даже мешать, а база дебютов эффективна только для игры программы с человеком, но никак не против другой программы (и против этого есть вариант игры "летающие шашки"). Настоящую силу игре придает только оценочная функция. И шашки умирают не из-за построенных баз (там еще далеко до исчерпывающего количества), а из-за того что высока вероятность ничьей.
Я начинал писать шашечный движок, но почитав обсуждения людей уже прошедших этот этап - забросил. Просто начиная с определенного (довольно высокого) класса программ-соперников результат зависит не от того кто сильнее, а от того насколько хороша слабейшая из программ. Когда она достаточно сильна она сможет свести результат к ничьей.

Самый простой алгоритм -- это рекурсивный перебор вариантов в будущее с выбором наилучшего хода для себя и наихудшего (для тебя) для противника.

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

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

Получается, что по каждому возможному ходу функция получает лучший ход на следующем этапе и его оценку. Комбинируя оценки вернувшихся ходов и оценки, сделанные на данном этапе, функция получает оценку каждого хода. После чего она выбирает лучший и возвращает назад его и его оценку.

В идеале такой алгоритм работал бы безошибочно и даже оценок никаких было бы не нужно. Дойдя до конца дерева вариантов, функция вернула бы 1 в случае выигрыша и 0 в случае проигрыша. 

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

Поэтому, рекурсию нужно ограничить по глубине. Думаю, 3-4 уровней будет достаточно. Кроме того, нужно добавить функции эмпирической оценки позиции и хода, которая бы оценивала ситуацию как есть, без перебора. Например, можно в эту функцию включить учёт количества шашек -- чем больше шашек у тебя и чем меньше у противника, тем больше оценка. Или можно учесть, что всегда хорошо съесть шашку противника и плохо отдать свою. Потом надо учесть, что попасть в дамки -- это явный плюс. И так далее.

Оценки можно подбирать, настраивая программу на наилучшую игру.

То есть, скомбинировав эмпирическую оценку и неглубокий перебор вариантов, можно получить реально работающий алгоритм, вполне достаточный, чтобы программа играла более-менее разумно.

у лидеров не меньше 12. А с повторяющимися позициями борятся по-другому.
ну и еще есть веса клеток, когда занять одну клетку считается более перспективным, чем другую. Конкретные значения весов для разных клеток авторы шашечных программ не сообщают 

Ну да, я слышал об этом. И про повторы понятно, что нужно бороться иначе. Просто, как я понял, топикстартеру нужно было простейший алгоритм предложить. Думаю, моё описание подходит под эту просьбу...

Ну есть еще правило чио при третьем повторе одного положения на доске объявляется ничья, поэтому повторы все-равно искать нужно

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

Для русских шашек это не верно

Подскажите плиз наиболее простой алгоритм для реализации дамок и их взятий. 

По поводу алгоритма "у которого невозможно выиграть в принципе" - это только про чеккерс (английские шашки). И там не алгоритм, там тупой перебор с отбрасыванием "плохих" продолжений, который не гарантирует выигрыша, но гарантированно не проигрывает - это разные вещи.

Есть сильные движки в русские шашки с открытыми исходниками - KestoG  и Скифи.
и есть очень простой - SiDra
http://igorkorshunov.narod.ru/Draughts/index.html
Они входят в комплект Каллисто4.
http://www.igorkorshunov.narod.ru/Kallisto4.rar

Добавлено @ 19:14

И для чеккерса тоже. Они просто нашли беспроигрышные варианты (построили беспроигрышное дерево)
из нескольких позиций входящих в стандартную жеребьевку дебютов.
При этом выиграть, если соперник совершит роковую ошибку - Чинук сможет далеко не всегда.
В любой игре, и даже в шахматах, есть позиции в которых программы не проигрывают. И чеккерс не исключение.
За счет чего так раздули их "достижение" совершенно непонятно.



Это сообщение отредактировал(а) NSSerg - 5.10.2010, 19:15

Эх...так никто и не откликнулся(