Программирование на языке Prolog для искуственного интеллекта 1

Программирование Статьи и материалы о программировании
#1

Игра в шашки с компьютером

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

Общий алгоритм программы следующий:
а1) первым ходит игрок. Он вводит, в консоли, ход шашкой, например: b6-a5;
а2) сначала проверяется нет ли “ударных” ходов и является ли данный ход одним из них. Если нет, тогда - правилен ли данный простой ход;
а3) ход сделан. В консоль выводится сообщение, что игрок сходил и текущее положение шашек на доске;
а4) проверяется: не является ли данный ход выигрышным для игрока (то-есть на доске шашек компьютера не осталось) или у компьютера зажаты шашки, так что он не может ходить, что тоже является выигрышем;
б1) ходит компьютер. Сначала компьютер ищет в комбинациях, по данной позиции, лучший ход;
б2) если нет, тогда проверяет: нет ли ударных ходов. Если есть, просчитывает какой шашкой лучше бить, где больше выигрыша и мень потерь (для этого я использовал вычисление “стоимости” каждого хода);
б3) если нет ударных ходов, тогда думает какой шашкой лучше ходить. Думает на шаг вперед, то-есть: если сходить такой-то шашкой попадут ли свои шашки под удар и какой из этого исход;
б4) ход сделан. В консоль выводится сообщение, что компьютер сделал такой-то ход и выводится текущее положение шашек на доске;
б5) проверяется не является ли данный ход выигрышным для ai (то-есть на доске шашек игрока не осталось) или у игрока зажаты шашки, так что он не может ходить, что тоже является выигрышем.

Вот, вкратце, весь алгоритм программы.

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

Программа по шашкам и файл с комбинациями находятся здесь: https://yadi.sk/d/VySvBx5CxxoMGA.

Файл с комбинациями (Combs.txt) нужно скопировать в папку Download внутренней памяти.

Приложение для данной программы, Prolog Classic на андроид, находится здесь: https://yadi.sk/d/dEcW3dQE_DU2Dw.

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

Книга по Прологу, в классическом варианте, находится здесь: https://yadi.sk/d/8WKBcqJBIysUYw.

Моя почта: elevferii_pechori@mail.ru.

#2

А они нужны разве? Вроде ж уже несколько десятков лет назад придуманы более эффективные способы.

https://www.google.com/search?q=checkers+ai
https://www.cs.huji.ac.il/~ai/projects/old/English-Draughts.pdf
GitHub - Hsankesara/Draughts-AI: AI based checkers game-bot
GitHub - KAI10/CheckersAI: This is a simple checkers game playing AI agent that follows the Minimax algorithm with alpha-beta pruning and depth limited search.

#3

Во всех ссылках которых вы мне написали говорится о Минимакс’ом подходе. В реальном времени это использовать нет смысла, слишком много вариаций: игроку придется ждать компьютер не меньше 15 минут, а может даже 30 и более: это при том, если допустить что просчитываются ходы только до того момента, когда позиция игрока является обязательно проигрышной (компьютер имеет дамку, а игрок нет или количество шашек игрока, хотябы, на 3 меньше чем у компьютера); процессор смартфона должен иметь хорошую тактовую частоту; программа должна быть подточена под эту задачу и написана на быстром языке, например С. Таким образом, чтобы программа работала быстро нужно просчитанные варианты записывать в файл, который придётся загружать перед игрой.
Мой ai когда бьёт может заранее просчитать где он больше выйграет шашек, при этом учитывается что и игрок следующим ходом может ударить (подход Минимакс). Также мой ai может правильно подставить шашку под удар с той целью, чтобы потом самому ударить или наоборот не подставлять, чтобы не проиграть её или несколько шашек. Он даже может играть без базы комбинаций, но так он будет играть на уровне чуть лучше новичка. Таким образом для моего ai нужно знать, в базе комбинаций, только те ходы, которые он не может просчитать самостоятельно, то-есть не все подряд (это большинство а начале и середине партии).
В заключение скажу: моей целью было не столько создать программу играющую именно в шашки, сколько научиться решать подобные задачи с помощью Пролога.

#4

Так там ведь и пишут о том что максимумом ограничивается глубина вычислений.
А Вы, так понимаю, желаете просчитать всю игру со всеми возможными комбинациями. Тогда да, прийдеться ждать после каждого хода пока алгоритм закончит вычисления оставшихся комбинаций…

#5

Так он же с оптимизациями там, а не в чистом виде и с неограниченной глубиной.

Запустил Питоновский вариант, считает мгновенно.

#6

Так смысл программирования на Прологе в том, чтобы этого не делать.

Вместо этого программа должна поиграть сама с собой.

А у Вас это на Прологе ранее доказывается или откуда оно?

#7

В программу встроенно несложное решение: когда компьютер имеет дамку, а противник нет исход игру предопределен несложными ходами (достаточно не дать дамкой пройти шашкам дальше). также я не знаю случаев, когда можно победить имея в минусах 3 шашки и более, хотя все может быть, но на этот случай можно забить комбинацию, при чем довольно-таки абстрактную (у меня уже есть около 30 таких в файле комбинаций, в конце).

#8

Очень подробно данную статью я расписал здесь: https://www.programmersforum.rocks/t/programmirovanie-na-yazyke-prolog-dlya-iskusstvennogo-intellekta-1-igra-v-shashki-s-kompyuterom/4900.

#9

По какой причине выбран именно “Пролог”?
Ведь это как изучать язык Паскаля если вдруг решил себя посвятить программированию.

#11

Есть Си компиляторы для смартфонов на Google Play. Правда сам не юзал, за корректность сборки не скажу.

#15

Люблю писать на Прологе. Это короче и красивее, чем на других языках. Кроме того, позволяет за короткое время писать сложные, умные программы (например здесь).

#16

Кроме минимакса, можно поискать решения на нейросетях. Играют же они в Go, а там перебор слишком сложный для минимакса.