Но это все равно очень по простому, действительно крутые шашечные движки вытворяют страшные вещи
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Программирование игр, графики и искусственного интеллекта > Помогите реализовать AI для игры шашки |
| Автор: Lirius 10.12.2008, 18:28 |
| Пишу игру шашки, уже реализовал вывод доски, ход, рубку. Не могу сделать AI для шашек. Пишу на с++, с использованием графического движка.Кто-нибудь может обьяснить какой-нибудь простой алгоритм или дать примеры. |
| Автор: bems 11.12.2008, 13:50 |
| Ну если "простой алгоритм", то сохраняешь копию доски, отключаешь вывод на экран, делаешь первый возможный ход, оцениваешь результаты (изменение общего количества белых, изменение количества дамок белых и то же самое для черных). Восстанавливаеш доску из сохраненной копии и делаешь слендующий возможный ход. Так повторяешь для всех вариантов. Потом из результататов оценки выбираеш лучший, включаешь вывод на экран и делаешь этот ход. Для увеличения качества результата потом можешь увеличить глубину перебора и продумывать на большее число ходов вперед. Но это все равно очень по простому, действительно крутые шашечные движки вытворяют страшные вещи |
| Автор: Gongex 19.1.2009, 17:24 | ||
| я писал шашки,но там комп играет кабут неделю назад научился,но все по правилам и ходить умеет и знает когда бить. Я взял 64 PictureBox,и придал шашкам цифру,так как комп думает по цифровому. Белые это 1 черные -2 и пустая клетка -0......комп ходит так у меня......берет из ума число до 64 и проверяет есть ли шашка,то есть клетка равно ли двум.....потом смотрит куда пойти налево или направо..у шашки два варианта хода, вариант тоже из ума берется....если клетка пустая то ходит.Перерисовываем клетку.И при этом изменяем данные этой клетки...........надо написать все варианты как комп бьет как ходит и потом как дамки бьют....это вариантов 200.получится 200 строк....и если включить опцию " играют два компа" то все ходы переделать надо на белые шашки..дам ссылку на прогу,посмотришь
|
| Автор: DeMoNN 26.1.2009, 21:40 |
Модератор: Сообщение скрыто. |
| Автор: Kakadu 29.1.2009, 16:07 |
| Насколько я знаю, современные шашечные программы имеют в себе базу позиций на все случаи жизни (книгу дебютов). С некоторых пор обучение шашкам среди людей превращается в тупую зубрёжку дебютов, иначе ты ошибешься и проиграешь. В шахматах дерево позиций много больше, но всёравно начало партий изучено на 20 ходов вперед, а для окончаний где по 5 фигур на доске даже построено дерево позиций с характеристикой результата при ходе той или иной стороны. короче, ИМХО, шашки умирают. В принципе, если автор не хочет писать непобедимый комп, а просто хочет поразвлечься с ИИ, он может этим не пользоваться и писать ИИ без базы позиций. |
| Автор: bems 29.1.2009, 18:12 |
| Kakadu, как показывает практика людей которые потратили на шашечные программы не один месяц жизни, слишком большая база окончаний может даже мешать, а база дебютов эффективна только для игры программы с человеком, но никак не против другой программы (и против этого есть вариант игры "летающие шашки"). Настоящую силу игре придает только оценочная функция. И шашки умирают не из-за построенных баз (там еще далеко до исчерпывающего количества), а из-за того что высока вероятность ничьей. Я начинал писать шашечный движок, но почитав обсуждения людей уже прошедших этот этап - забросил. Просто начиная с определенного (довольно высокого) класса программ-соперников результат зависит не от того кто сильнее, а от того насколько хороша слабейшая из программ. Когда она достаточно сильна она сможет свести результат к ничьей. |
| Автор: Dims 8.2.2009, 15:48 |
| Самый простой алгоритм -- это рекурсивный перебор вариантов в будущее с выбором наилучшего хода для себя и наихудшего (для тебя) для противника. Назовём функцию "выбрать ход". У этой функции будет два параметра: исходная позиция, чей ход (цвет шашки). Возвращать функция будет оценку хода (число, которое, тем больше, чем лучше ход). На первом этапе функция смотрит, какие ходы может сделать заданный цвет и генерирует все новые комбинации, возникающие при этих ходах. Затем она каждую получившуюся комбинацию передаёт самой себе (рекурсия), заменяя только цвет шашки на обратный. Получается, что по каждому возможному ходу функция получает лучший ход на следующем этапе и его оценку. Комбинируя оценки вернувшихся ходов и оценки, сделанные на данном этапе, функция получает оценку каждого хода. После чего она выбирает лучший и возвращает назад его и его оценку. В идеале такой алгоритм работал бы безошибочно и даже оценок никаких было бы не нужно. Дойдя до конца дерева вариантов, функция вернула бы 1 в случае выигрыша и 0 в случае проигрыша. Но перебрать все варианты невозможно. Во-первых, их очень много разных, никакой компьютер не сможет их перебрать за обозримое время. Во-вторых, варианты повторяются (шашки могут ходить взад вперёд). Поэтому, рекурсию нужно ограничить по глубине. Думаю, 3-4 уровней будет достаточно. Кроме того, нужно добавить функции эмпирической оценки позиции и хода, которая бы оценивала ситуацию как есть, без перебора. Например, можно в эту функцию включить учёт количества шашек -- чем больше шашек у тебя и чем меньше у противника, тем больше оценка. Или можно учесть, что всегда хорошо съесть шашку противника и плохо отдать свою. Потом надо учесть, что попасть в дамки -- это явный плюс. И так далее. Оценки можно подбирать, настраивая программу на наилучшую игру. То есть, скомбинировав эмпирическую оценку и неглубокий перебор вариантов, можно получить реально работающий алгоритм, вполне достаточный, чтобы программа играла более-менее разумно. |
| Автор: bems 8.2.2009, 16:35 | ||||
у лидеров не меньше 12. А с повторяющимися позициями борятся по-другому.
 |
| Автор: Dims 8.2.2009, 19:59 |
| Ну да, я слышал об этом. И про повторы понятно, что нужно бороться иначе. Просто, как я понял, топикстартеру нужно было простейший алгоритм предложить. Думаю, моё описание подходит под эту просьбу... |
| Автор: bems 8.2.2009, 20:36 |
| Ну есть еще правило чио при третьем повторе одного положения на доске объявляется ничья, поэтому повторы все-равно искать нужно |
| Автор: Xela 3.3.2009, 00:35 | ||
Уже создан алгоритм игры в шашки у которого не возможно выиграть в принципе. |
| Автор: bems 3.3.2009, 02:10 |
| Для русских шашек это не верно |
| Автор: pelikesha 2.10.2010, 08:10 |
| Подскажите плиз наиболее простой алгоритм для реализации дамок и их взятий. По поводу алгоритма "у которого невозможно выиграть в принципе" - это только про чеккерс (английские шашки). И там не алгоритм, там тупой перебор с отбрасыванием "плохих" продолжений, который не гарантирует выигрыша, но гарантированно не проигрывает - это разные вещи. |
| Автор: NSSerg 5.10.2010, 19:00 | ||
| Есть сильные движки в русские шашки с открытыми исходниками - KestoG и Скифи. и есть очень простой - SiDra http://igorkorshunov.narod.ru/Draughts/index.html Они входят в комплект Каллисто4. http://www.igorkorshunov.narod.ru/Kallisto4.rar Добавлено @ 19:14
И для чеккерса тоже. Они просто нашли беспроигрышные варианты (построили беспроигрышное дерево) из нескольких позиций входящих в стандартную жеребьевку дебютов. При этом выиграть, если соперник совершит роковую ошибку - Чинук сможет далеко не всегда. В любой игре, и даже в шахматах, есть позиции в которых программы не проигрывают. И чеккерс не исключение. За счет чего так раздули их "достижение" совершенно непонятно. |
| Автор: pelikesha 5.4.2011, 20:22 | ||
Эх...так никто и не откликнулся( |
| Автор: DegX 8.7.2012, 00:21 |
| Забей в поисковик AI для http://www.gambiter.ru/checkers.html. |
| Автор: 500mhz 8.7.2012, 01:16 |
| Продаю AI для игры в "Чапаевцев". |
| Автор: Bitter 9.7.2012, 13:46 |
| 500mhz, сколько? |
| Автор: baldina 9.7.2012, 14:37 | ||
 достойно башорга
|
| Автор: bems 9.7.2012, 14:43 |
| я джва года ждал такие шашки |
| Автор: 500mhz 9.7.2012, 17:05 |
| Ну наконец то нармальные шашки будут! |
