Разработка искусственного интеллекта, в век компьютеризации, является актуальной востребованной задачей.
Методы алгоритмизации ИИ бывают разные, например:
- Метод перебора (полный, альфа-бета перебор, перебор с амортизацией отказов, перебор с нулевым окном и др.). Например для игр: шахматы, шашки, кристики-нолики;
- На основе знаний (база правил эксперта - в Прологе это факты и правила);
- Машинное обучение (нейронная сеть).
1. Причины написания программы
Игра в шашки с компьютером не “ново”, а алгоритмизацией ИИ для шахмат вообще занимаются более 50 лет. Мне же было интересно попробовать себя в написании ИИ для шашек на Прологе, так как хотелось увидеть насколько просто написать на Прологе такую непростую программу. Пролог позволяет написать программу гораздо быстрее, короче и читабельней, чем на вычислительных языках, например С++. Он как раз и предназначен для решения задач с искусственным интеллектом (англ. AI).
2. Причины опубликования статьи
В Интернете я не нашёл подобной статьи или программы (именно написанной на Прологе) со способом алгоритмизации ИИ использованном в моей программе, что и побудило меня опубликовать данную статью. Кроме того, программа запускается в приложении работающем на Андроиде (см. статью о приложении Prolog Classic и ссылку на скачивание [1]), что для многих может иметь удобство.
3. Алгоритм работы ИИ
Для алгоритмизации ИИ я выбрал метод полного перебора и метод с использованием базы знаний. Основным методом является метод на основе знаний.
Почему я выбрал именно этот метод основным, тут две причины:
- Полный перебор для такой игры невозможен (слишком много вариаций). Перебор с ограниченной глубиной, для такой игры, очень ресурсоёмок, даже при не очень большой глубине (стек приложения Prolog Classic будет есть много памяти; программа будет сильно тормозить из-за очень большого количества просчётов ходов), а с оптимизированными алгоритмами перебора я плохо знаком (альфа-бета перебор, перебор с амортизацией отказов и т.д.);
- Метод на основе знаний способен дать лучшие комбинации, даже если они очень длинные и поэтому тяжелы для просчёта.
Алгоритм работы ИИ такой:
Сначала, программа ищет в базе комбинаций ход, для состояния текущей доски (это могут быть как просто ходы, так и ходы-удары): среди дебютных ходов, если нет дебютной комбинации- тогда среди обычных комбинаций:
а) В дебютных ходах определяется точное расположение каждой шашки, каждой пустой клетки, так как от каждой мелочи зависит тот или иной розыгрыш дебюта;
б) В остальных же ходах, когда шашек на доске уже довольно меньше, определение состояния доски в базе правил является довольно вольным («абстрактным»), т.е. в правиле указывается точное расположение необходимых шашек и пустых клеток про остальные же указывается, что где-то могут стоять как простые шашки, так и дамки; где-то - шашка чёрная, или белая, или пустая клетка; и др. возможные комбинации; - Если программа не находит готовый ход, то затем она сначала проверяет нужно ли какой-нибудь шашкой бить, и если да - то ищет какой лучше. Вот здесь уже используется алгоритм полного перебора:
а) Собирается в список все возможные удары разными шашками компьютера;
б) Каждому ходу-удару компьютера приписывается оценочный вес. Он находится путем сложения веса хода (за выигрыш одной шашки игрока приписывается, скажем, +100) и лучшего веса удара игрока (наименьшее число), который будет после этого хода компьютера. Для ход-ударов игрока, в свою очередь, также считается оценочный вес: вес хода (за выигрыш одной шашки приписывается, скажем, -100) и лучший вес удара компьютера (наибольшее число), который будет после этого хода игрока. Для лучшего понимания сказанного, можно представить себе дерево, у которого первые ветки идущие от корня - это первые ходы-удары компьютера. От каждой этой ветки расходятся другие ветки представляющие собой ходы-удары противника. От последних веток расходятся ещё ветки опять являющимися ударами компьютера и т.д. пока кому-нибудь нечем будет бить.
Почему мы среди ударов компьютера берём удар с наибольшим числом, это понятно - нам нужен лучший ход. А почему из ходов игрока мы берём ход с наименьшим числом - это потому, что мы учитываем, что игрок может быть сильным игроком, поэтому мы рассчитываем на худшее;
в) Из найденных ходов-ударов компьютера выбирается ход с наибольшим весом, то есть, лучший ход; - Если и бить не надо, тогда просчитывается лучший простой ход:
а) Сначала программа собирает список всевозможных простых ходов шашками (не забывая про дамок).
б) Для каждого хода присваивается вес или по другому очки, значение которого зависит от:
i) Станет ли шашка дамкой на этом ходе (стать дамкой это как съесть около 2 пешек);
ii) Если в правом или левом верхнем углу есть простые шашки противника, а у компьютера есть дамка, то предпочтительнее сделать простой ход дамкой (для этого к весу прибавятся соответствующие очки) причём такой, чтобы прийти потом к диагонали, которая не даст пройти шашкам игрока к дамке (для этого идёт подсчёт с какой стороны больше шашек противника);
Iii) Если есть дамка, которая уже стоит на диагонали, на которой не даст пройти шашкам игрока, то ход простой шашкой предпочтительнее, чем этой дамкой (для этого к весу прибавляются соответствующие очки, но меньше чем в пункте ii))
iv) После всех выше сказанных пунктов для ходов, после которых игрок бьёт шашкой, методом полного перебора, вычисляется дополнительный вес, представляющий из себя наименьший вес из весов ответных ходов-ударов игрока, который и прибавляется (так же как при полном переборе для ударов компьютером, см. выше). Благодаря этому пункту, компьютер избежит не только нежелательных ходов, но и сможет совершать подставные ходы, зная, что его, после этого хода, ждёт выигрыш);
в) После всего и берётся лучший ход.
Таков алгоритм написанного мной искусственного интеллекта.
4. Разбор программы
Программа игры в шашки состоит из двух частей: самой программы и добавочного файла содержащего различные комбинации для победы над противником (то есть игроком).
Поскольку, Пролог является декларативно-процедурным языком программирования, то и описывать программу я буду, то с декларативной, то с процедурной точки зрения.
Итак, по порядку:
- Перед началом игры на экран выводится начальная позиция шашечной доски.
Как, наверно, вы заметили, черные шашки (шашки ИИ) стоят на месте белых, а белые на месте чёрных. Эту, свою, ошибку я заметил только под конец написания программы, и поскольку, чтобы исправить пришлось бы переделать очень много кода, то я оставил это как есть (это, может даже, имеет свой плюс, позволяя игроку играть в непривычной обстановке); - Ядром программы является предикат game, который состоит из нескольких правил (см. код ниже):
game:-
pos(P0),
moveMe(P0,P1),
retractA(pos( _)),
assertA(pos1(P1)),
false;
pos1(P1),
noWayOrEnd(P1,-),
write(вы_победили!),nl;
exit;
pos1(P0),
moveAI(P0,P1),
retractA(pos1( _)),
assertA(pos(P1)),
false;
pos(P1),
noWayOrEnd(P1,+),
write(ai_победил!),nl;
pos(P1),
draw(P1,0),
drawRead;
game.
а) Первое правило служит для выполнения хода игроком (предикат moveMe/2), заканчивающееся перезаписыванием расположения шашек на доске. В глубине предиката moveMe/2 проверяется: правильно ли сделан ход или может игрок должен бить шашкой, а он этого не делает, при отрицательном значении выводится соответствующее сообщение. В самом конце стоит false, это для того, чтобы программа переходила к следующему правилу;
б) Второе правило истинно, если побиты все шашки компьютера, или ему некуда ходить (предикат noWayOrEnd/2), и при доказательстве его программа заканчивает свою работу;
в) Третье правило истинно, если истинен предикат exit/0, для которого существует единственный факт при вводе игроком в консоли слово выход, после чего программа прекращает свою работу;
г) Четвёртым правилом компьютер совершает ход при помощи предиката moveAI/2 и перезаписыванием факта о расположении шашек на доске. Снова в конце правила стоит ложный предикат false, чтобы при продолжении игры вернуться к первому правилу (к ходу игроком). Ложный предикат false стоит в конце ещё с той целью, чтобы он своим откатом делал и откат стека программы, т.к., иначе, память устройства переполнится или же программа будет подтормаживать;
д) Пятое правило, подобно второму, истинно, если побиты все шашки игрока, или его шашки в тупике. При доказательстве правила программа завершает работу;
е) Шестое правило проверяет остались ли на доске одна дамка игрока и одна дамка компьютера, если да, то компьютер предлагает игроку завершить игру ничьёй, на что игрок может или согласиться, или отказаться (см. «Ничья в партии русских шашек» [2]);
ё) И последнее седьмое правило, в случае продолжения игры, отсылает нас снова на первое правило;
3) Предикат moveMe/2. Состоит из одного правила, тело которого состоит из двух предикатов: readMe/2 и writeMove/1. Второй предикат всегда истинен, и выводит на экран шашечную доску с шашками если ход сделан, а если пользователь ввел выход, тогда ничего не выводит. Первый же предикат - сначала считывает текст с экрана введённый пользователем, затем пытается доказать, что ход сделан правильно, если нет - то сработает второе правило выводящее на экран, что ход невозможен, или же третье выводящее предупреждение, что игрок должен бить шашкой (если вместо этого игрок просто ходит или не заканчивает бить шашкой);
4) Предикат moveAI/2. Состоит из одного правила, где, вначале, предикат moveAI_1/3 возвращает сделанный компьютером ход и новое состояние доски, а после выводится на экран сделанный компьютером ход и предикатом writePos/1 новое состояние доски;
5) Предикат moveAI_1/3 (см. код ниже). Рассмотрим правила данного предиката:
moveAI_1(P,AB,P1):-
moveHitComb_ai(P,AB,P1), !;%Удар в комбинации
moveSimpleComb0_ai(P,AB,P1), !;%Простой ход из точных комбинаций
write(ждите...),nl,
false;
moveSimpleComb_ai(P,AB,P1), !;%Простой ход из комбинаций
moveHit_ai(P,AB,P1), !;
moveSimple_ai(P,AB,P1).
%Простой ход шашкой или такой ход, чтобы потом съесть побольше шашек
а) Сначала с помощью предиката moveHitComb_ai/3 ищется - есть ли возможность ударить шашкой с помощью записанного хода в базе знаний рассчитанного на определённую комбинацию (тот самый дополнительный файл). Заметим, что программа может сама производить сложные комбинации ударов: считает количество побитых шашек противника против своих (даже при обоюдных ударах), учитывает, если будет побита дамка (об этом подробно см. ниже). Но, поскольку бывает, что есть случаи, когда нужно бить в убыток себе, зная, что в будущем это даст сокрушительную комбинацию против противника, то для таких случаев и записаны в базе знаний ходы-удары выходящие из общего правила программы. Обратим внимание, что здесь среди записанных ходов в базе знаний есть как точные (то есть, когда точно известно где какая шашка должна стоять или пустая клетка), так и «абстрактные» (когда при помощи разных цифр мы даём компьютеру понять где должна быть обязательно пустая клетка или, скажем белая шашка, а где может быть как чёрная так и белая шашка и т.д.). Точные ходы нужны для дебютов (см. выше). «Абстрактные» ходы используются в середине и в конце партии, где нужно чтобы некоторые определённые шашки были на месте и пустые клетки, в остальных местах же могут присутствовать шашки, а могут и нет, или даже дамки, в других местах могут быть как белые, так и черные шашки и т.д. (подробнее читайте в начале файла базы комбинаций);
б) Если записанного удара для текущей доски нет, тогда в следующем правиле, с помощью предиката moveSimpleComb0_ai/3 ищется - есть ли для текущей доски записанный простой ход разыгрывающий лучшую комбинацию для данного дебюта (из точных ходов);
в) Если второе правило тоже потерпело неудачу, то следующее правило выводит сообщение: «ждите…», т.к. четвёртое, а может и пятое правило займут немалое время (иногда полминуты на процессоре 3 ГГц), в конце стоит false, чтобы начало работать следующее правило;
г) Четвёртое правило и в нём предикат moveSimpleComb_ai/3 ищет простой ход, но из «абстрактных» ходов. Обратите внимание, в начале каждого факта базы знаний, первые два аргумента содержат количество белых шашек и количество чёрных (это значение либо точное, либо указаны пределы «от и до» - для «абстрактных» ходов). Это помогает быстро отсеивать ненужные для проверки факты, т.к. сравнивать матрицу 8х8 текущей доски с матрицей каждого факта, для большого количества фактов это очень накладно;
д) Пятое правило, при неудачах предыдущих правил, пытается сделать ход ударом с помощью предиката moveHit_ai/3 (см. ниже). Рассмотрим как программа выбирает какой шашкой бить:
moveHit_ai(P,AB,P1):-
getHitsBoard_ai(P,P,[8,7,6,5,4,3,2,1]),
hits( _, _, _, _, _),
assertZ(assert_hit),
setAllHits_ai,
getMaxNum_ai(1,N),
setMaxMinList_ai(N),
retractZ(hits(s(P1,AB), _, _,0,end)).
i) Предикат getHitsBoard_ai/3 находит все чёрные шашки на доске, которые могут ударить по белым, и записывает их всевозможные ходы-удары фактами hits/5 (если записывать в список, потом им пользоваться, при многом его использовании стек приложения будет быстро расти в объёме памяти»);
ii) Далее предикат setAllHits_ai/0 берёт начальные ходы и ищет есть ли белые шашки, которые обратно могут ударить. Потом снова ищет есть ли чёрные шашки, которые ответно могут ударить по белым. И так, до тех пор, пока не на какой позиции не смогут ответить (см. выше полный перебор), при этом в каждом факте записывается список с историей (например [c3-e5,b6-d4,a3-c5]) обоюдных ходов-ударов, каждый альтернативный вариант порождает новый факт со своим списком. Каждый список истории имеет список весов, то есть каждому ходу соответствует оценочный вес;
iii) После записи всех этих списков, предикат setMaxMinList_ai/1 берёт факты с самыми длинными историями и сгруппировав их по одинаковой историей, но с разным концом - из каждой группы берёт один факт у которого сумма веса последнего хода от ударов является: наименьшей - если это ход игрока (т.к. компьютер ожидает худшего), и наибольший - если это ход компьютера. Сохранённая сумма веса хода (очки за простой ход или удар) прибавляется к найденной сумме веса предыдущего хода и последний ход из истории убирается. В результате, в своей рекурсии, предикат setMaxMinList_ai/1 дойдёт до того, что останется один факт с одним наибольшим весом и одним ходом. Вместе с этим фактом мы получаем нужный нам ход-удар;
е) Последнее правило включает в себя предикат moveSimple_ai/3 (см. ниже). Суть его в том, что он собирает в фактах все возможные простые ходы шашками (не забывая про дамок) и находит лучший простой ход, как написано выше. К вышесказанному добавлю, что за выигрыш простой шашки компьютеру даётся плюс 105 очков, а игроку минус 100 - эта разница нужна для того, чтобы компьютеру было выгодно бить и при равном выигрыше простых шашек или дамок (см. стратегии игры в шашки [3]);
moveSimple_ai(P,AB,P1):-
getStepBoard_ai(P,P,[8,7,6,5,4,3,2,1]),
hits( _, _, _, _, _),
assertZ(assert_hit),
setAllHits_ai,
getMaxNum_ai(1,N),
setMaxMinList_ai(N),
retractZ(hits(s(P1,AB), _, _,0,end)).
- В начале целевого предиката (?–) находится предикат see_file, который загружает перед игрой базу знаний комбинаций состоящую из фактов.
На этом всё. При желании алгоритм простых ходов ИИ можно усовершенствовать, а базу знаний дополнить.
Кто-то может скажет, что база знаний должна быть очень большой для безупречной игры компьютера. Не знаю может и так. Но мне кажется, что когда у одной из сторон окажется на три и больше шашек чем у соперника - исход игры обычно предрешён, тоже самое при появлении у кого-нибудь первой дамки (с дамкой тоже бывают исключения, но думаю изредка), так что работать приходится в основном над сложными партиями).
Статью написал Елевферий elevferii_pechori@mail.ru. Составлять помогал Владимир Васильев rrrfer@mail.ru.
Программа по шашкам и файл с комбинациями находятся здесь: https://yadi.sk/d/VySvBx5CxxoMGA.
Файл с комбинациями (Combs.txt) нужно скопировать в папку Download внутренней памяти.
Приложение скачать можно здесь: https://disk.yandex.ru/d/5ED-43Uveub1ew.
Список литературы
- Исполнение Пролог-программ на Android. URL: https://www.programmersforum.rocks/t/programmirovanie-na-yazyke-prolog-na-androide/3662
- Правила игры в шашки. URL: https://minigames.mail.ru/info/article/shashki_pravila
- Как выиграть в шашки. URL: https://ru.wikihow.com/выиграть-в-шашки