Курсовая на тему Создание игровой программы шашки для игры между человеком и компьютером на языке С Builder
Работа добавлена на сайт bukvasha.net: 2014-11-30Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Курсовая Работа
На тему:
Создание игровой программы “шашки” для игры между человеком и компьютером на языке С++ Builder
1. Базовые понятия ИИ.. 4
2. История развития систем ИИ.. 8
Различные подходы к построению систем ИИ.. 16
Сокращенный листинг программы и описание алгоритма. 21
компоненты искусственного интелекта (ии) 26
Описание работы программы.. 37
Выводы.. 39
Литература. 40
Поэтому, в теоретическую часть вынесены основные сведения про разработку алгоритмов ИИ, показана историческая линия развития задач ИИ.
Для создания игры “шашки” требуется относительно несложная функция ИИ, главными задачами которой является предсказание на установленную глубину своих ходов и ходов противника. Это предсказание базируется на выборе наилучших ходов с обеих сторон. На финальном этапе функция ИИ избирает наиболее выгодную для компьютера цепочку ходов.
Терминология.
Термин интеллект (intelligence) происходит от латинского intellectus - что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificial intelligence) - ИИ (AI) обычно толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий.
Мы, в нашем курсе, интеллектом будем называть способность мозга решать (интеллектуальные) задачи путем приобретения, запоминания и целенаправленного преобразования знаний в процессе обучения на опыте и адаптации к разнообразным обстоятельствам.
В этом определении под термином "знания" подразумевается не только ту информацию, которая поступает в мозг через органы чувств. Такого типа знания чрезвычайно важны, но недостаточны для интеллектуальной деятельности. Дело в том, что объекты окружающей нас среды обладают свойством не только воздействовать на органы чувств, но и находиться друг с другом в определенных отношениях. Ясно, что для того, чтобы осуществлять в окружающей среде интеллектуальную деятельность (или хотя бы просто существовать), необходимо иметь в системе знаний модель этого мира. В этой информационной модели окружающей среды реальные объекты, их свойства и отношения между ними не только отображаются и запоминаются, но и, как это отмечено в данном определении интеллекта, могут мысленно "целенаправленно преобразовываться". При этом существенно то, что формирование модели внешней среды происходит "в процессе обучения на опыте и адаптации к разнообразным обстоятельствам".
Мы употребили термин интеллектуальная задача. Для того, чтобы пояснить, чем отличается интеллектуальная задача от просто задачи, необходимо ввести термин "алгоритм" - один из краеугольных терминов кибернетики.
Под алгоритмом понимают точное предписание о выполнении в определенном порядке системы операций для решения любой задачи из некоторого данного класса (множества) задач. Термин "алгоритм" происходит от имени узбекского математика Аль-Хорезми, который еще в IX веке предложил простейшие арифметические алгоритмы. В математике и кибернетике класс задач определенного типа считается решенным, когда для ее решения установлен алгоритм. Нахождение алгоритмов является естественной целью человека при решении им разнообразных классов задач. Отыскание алгоритма для задач некоторого данного типа связано с тонкими и сложными рассуждениями, требующими большой изобретательности и высокой квалификации. Принято считать, что подобного рода деятельность требует участия интеллекта человека. Задачи, связанные с отысканием алгоритма решения класса задач определенного типа, будем называть интеллектуальными.
Что же касается задач, алгоритмы решения которых уже установлены, то, как отмечает известный специалист в области ИИ М. Минский, "излишне приписывать им такое мистическое свойства, как "интеллектуальность". В самом деле, после того, как такой алгоритм уже найден, процесс решения соответствующих задач становится таким, что его могут в точности выполнить человек, вычислительная машина (должным образом запрограммированная) или робот, не имеющие ни малейшего представления о сущность самой задачи. Требуется только, чтобы лицо, решающее задачу, было способно выполнять те элементарные операции, их которых складывается процесс, и, кроме того, чтобы оно педантично и аккуратно руководствовалось предложенным алгоритмом. Такое лицо, действуя, как говорят в таких случаях, чисто машинально, может успешно решать любую задачу рассматриваемого типа.
Поэтому представляется совершенно естественным исключить их класса интеллектуальных такие задачи, для которых существуют стандартные методы решения. Примерами таких задач могут служить чисто вычислительные задачи: решение системы линейных алгебраических уравнений, численное интегрирование дифференциальных уравнений и т.д. Для решения подобного рода задач имеются стандартные алгоритмы, представляющие собой определенную последовательность элементарных операций, которая может быть легко реализована в виде программы для вычислительной машины. В противоположность этому для широкого класса интеллектуальных задач, таких, как распознавание образов, игра в шахматы, доказательство теорем и т.п., напротив это формальное разбиение процесса поиска решения на отдельные элементарные шаги часто оказывается весьма затруднительным, даже если само их решение несложно.
Таким образом, мы можем перефразировать определение интеллекта как универсальный сверхалгоритм, который способен создавать алгоритмы решения конкретных задач.
Еще интересным замечанием здесь является то, что профессия программиста, исходя из наших определений, является одной из самых интеллектуальных, поскольку продуктом деятельности программиста являются программы - алгоритмы в чистом виде. Именно поэтому, создание даже элементов ИИ должно очень сильно повысить производительность его труда.
Деятельность мозга (обладающего интеллектом), направленную на решение интеллектуальных задач, мы будем называть мышлением, или интеллектуальной деятельностью. Интеллект и мышление органически связаны с решением таких задач, как доказательство теорем, логический анализ, распознавание ситуаций, планирование поведения, игры и управление в условиях неопределенности. Характерными чертами интеллекта, проявляющимися в процессе решения задач, являются способность к обучению, обобщению, накоплению опыта (знаний и навыков) и адаптации к изменяющимся условиям в процессе решения задач. Благодаря этим качествам интеллекта мозг может решать разнообразные задачи, а также легко перестраиваться с решения одной задачи на другую. Таким образом, мозг, наделенный интеллектом, является универсальным средством решения широкого круга задач (в том числе неформализованных) для которых нет стандартных, заранее известных методов решения.
Следует иметь в виду, что существуют и другие, чисто поведенческие (функциональные) определения. Так, по А.Н. Колмогорову, любая материальная система, с которой можно достаточно долго обсуждать проблемы науки, литературы и искусства, обладает интеллектом. Другим примером поведенческой трактовки интеллекта может служить известное определение А. Тьюринга. Его смысл заключается в следующем. В разных комнатах находится люди и машина. Они не могут видеть друг друга, но имеют возможность обмениваться информацией (например, с помощью электронной почты). Если в процессе диалога между участниками игры людям не удается установить, что один из участников - машина, то такую машину можно считать обладающей интеллектом.
Кстати интересен план имитации мышления, предложенный А. Тьюрингом. "Пытаясь имитировать интеллект взрослого человека, - пишет Тьюринг, - мы вынуждены много размышлять о том процессе, в результате которого человеческий мозг достиг своего настоящего состояния… Почему бы нам вместо того, чтобы пытаться создать программу, имитирующую интеллект взрослого человека, не попытаться создать программу, которая имитировала бы интеллект ребенка? Ведь если интеллект ребенка получает соответствующее воспитание, он становится интеллектом взрослого человека… Наш расчет состоит в том, что устройство, ему подобное, может быть легко запрограммировано… Таким образом, мы расчленим нашу проблему на две части: на задачу построения "программы-ребенка" и задачу "воспитания" этой программы".
Забегая вперед, можно сказать, что именно этот путь используют практически все системы ИИ. Ведь понятно, что практически невозможно заложить все знания в достаточно сложную систему. Кроме того, только на этом пути проявятся перечисленные выше признаки интеллектуальной деятельности (накопление опыта, адаптация и т.д.).
В рамках первого подхода объектом исследований являются структура и механизмы работы мозга человека, а конечная цель заключается в раскрытии тайн мышления. Необходимыми этапами исследований в этом направлении являются построение моделей на основе психофизиологических данных, проведение экспериментов с ними, выдвижение новых гипотез относительно механизмов интеллектуальной деятельности, совершенствование моделей и т.д.
Второй подход в качестве объекта исследования рассматривает ИИ. Здесь речь идет о моделировании интеллектуальной деятельности с помощью вычислительных машин. Целью работ в этом направлении является создание алгоритмического и программного обеспечения вычислительных машин, позволяющего решать интеллектуальные задачи не хуже человека.
Наконец, третий подход ориентирован на создание смешанных человеко-машинных, или, как еще говорят, интерактивных интеллектуальных систем, на симбиоз возможностей естественного и искусственного интеллекта. Важнейшими проблемами в этих исследованиях является оптимальное распределение функций между естественным и искусственным интеллектом и организация диалога между человеком и машиной.
Самыми первыми интеллектуальными задачами, которые стали решаться при помощи ЭВМ были логические игры (шашки, шахматы), доказательство теорем. Хотя, правда здесь надо отметить еще кибернетические игрушки типа "электронной мыши" Клода Шеннона, которая управлялась сложной релейной схемой. Эта мышка могла "исследовать" лабиринт, и находить выход из него. А кроме того, помещенная в уже известный ей лабиринт, она не искала выход, а сразу же, не заглядывая в тупиковые ходы, выходила из лабиринта.
Американский кибернетик А. Самуэль составил для вычислительной машины программу, которая позволяет ей играть в шашки, причем в ходе игры машина обучается или, по крайней мере, создает впечатление, что обучается, улучшая свою игру на основе накопленного опыта. В 1962 г. эта программа сразилась с Р. Нили, сильнейшим шашистом в США и победила.
Каким образом машине удалось достичь столь высокого класса игры?
Естественно, что в машину были программно заложены правила игры так, что выбор очередного хода был подчинен этим правилам. На каждой стадии игры машина выбирала очередной ход из множества возможных ходов согласно некоторому критерию качества игры. В шашках (как и в шахматах) обычно невыгодно терять свои фигуры, и, напротив, выгодно брать фигуры противника. Игрок (будь он человек или машина), который сохраняет подвижность своих фигур и право выбора ходов и в то же время держит под боем большое число полей на доске, обычно играет лучше своего противника, не придающего значения этим элементам игры. Описанные критерии хорошей игры сохраняют свою силу на протяжении всей игры, но есть и другие критерии, которые относятся к отдельным ее стадиям - дебюту, миттэндшпилю, эндшпилю.
Разумно сочетая такие критерии (например в виде линейной комбинации с экспериментально подбираемыми коэффициентами или более сложным образом), можно для оценки очередного хода машины получить некоторый числовой показатель эффективности - оценочную функцию. Тогда машина, сравнив между собой показатели эффективности очередных ходов, выберет ход, соответствующий наибольшему показателю. Подобная автоматизация выбора очередного хода не обязательно обеспечивает оптимальный выбор, но все же это какой-то выбор, и на его основе машина может продолжать игру, совершенствуя свою стратегию (образ действия) в процессе обучения на прошлом опыте. Формально обучение состоит в подстройке параметров (коэффициентов) оценочной функции на основе анализа проведенных ходов и игр с учетом их исхода.
По мнению А. Самуэля, машина, использующая этот вид обучения, может научиться играть лучше, чем средний игрок, за относительно короткий период времени.
Можно сказать, что все эти элементы интеллекта, продемонстрированные машиной в процессе игры в шашки, сообщены ей автором программы. Отчасти это так. Но не следует забывать, что программа эта не является "жесткой", заранее продуманной во всех деталях. Она совершенствует свою стратегию игры в процессе самообучения. И хотя процесс "мышления" у машины существенно отличен оттого, что происходит в мозгу играющего в шашки человека, она способна у него выиграть.
Ярким примером сложной интеллектуальной игры до недавнего времени являлись шахматы. В 1974 г. состоялся международный шахматный турнир машин, снабженных соответствующими программами. Как известно, победу на этом турнире одержала советская машина с шахматной программой "Каисса".
Почему здесь употреблено "до недавнего времени"? Дело в том, что недавние события показали, что несмотря на довольно большую сложность шахмат, и невозможность, в связи с этим произвести полный перебор ходов, возможность перебора их на большую глубину, чем обычно, очень увеличивает шансы на победу. К примеру, по сообщениям в печати, компьютер фирмы IBM, победивший Каспарова, имел 256 процессоров, каждый из которых имел 4 Гб дисковой памяти и 128 Мб оперативной. Весь этот комплекс мог просчитывать более 100'000'000 ходов в секунду. До недавнего времени редкостью был компьютер, могущий делать такое количество целочисленных операций в секунду, а здесь мы говорим о ходах, которые должны быть сгенерированы и для которых просчитаны оценочные функции. Хотя с другой стороны, этот пример говорит о могуществе и универсальности переборных алгоритмов.
В настоящее время существуют и успешно применяются программы, позволяющие машинам играть в деловые или военные игры, имеющие большое прикладное значение. Здесь также чрезвычайно важно придать программам присущие человеку способность к обучению и адаптации. Одной из наиболее интересных интеллектуальных задач, также имеющей огромное прикладное значение, является задача обучения распознавания образов и ситуаций. Решением ее занимались и продолжают заниматься представители различных наук - физиологи, психологи, математики, инженеры. Такой интерес к задаче стимулировался фантастическими перспективами широкого практического использования результатов теоретических исследований: читающие автоматы, системы ИИ, ставящие медицинские диагнозы, проводящие криминалистическую экспертизу и т.п., а также роботы, способные распознавать и анализировать сложные сенсорные ситуации.
В 1957 г. американский физиолог Ф. Розенблатт предложил модель зрительного восприятия и распознавания - перцептрон. Появление машины, способной обучаться понятиям и распознавать предъявляемые объекты, оказалось чрезвычайно интересным не только физиологам, но и представителям других областей знания и породило большой поток теоретических и экспериментальных исследований.
Перцептрон или любая программа, имитирующая процесс распознавания, работают в двух режимах: в режиме обучения и в режиме распознавания. В режиме обучения некто (человек, машина, робот или природа), играющий роль учителя, предъявляет машине объекты и о каждом их них сообщает, к какому понятию (классу) он принадлежит. По этим данным строится решающее правило, являющееся, по существу, формальным описанием понятий. В режиме распознавания машине предъявляются новые объекты (вообще говоря, отличные от ранее предъявленных), и она должна их классифицировать, по возможности, правильно.
Проблема обучения распознаванию тесно связана с другой интеллектуальной задачей - проблемой перевода с одного языка на другой, а также обучения машины языку. При достаточно формальной обработке и классификации основных грамматических правил и приемов пользования словарем можно создать вполне удовлетворительный алгоритм для перевода, скажем научного или делового текста. Для некоторых языков такие системы были созданы еще в конце 60-г. Однако для того, чтобы связно перевести достаточно большой разговорный текст, необходимо понимать его смысл. Работы над такими программами ведутся уже давно, но до полного успеха еще далеко. Имеются также программы, обеспечивающие диалог между человеком и машиной на урезанном естественном языке. На тему:
Создание игровой программы “шашки” для игры между человеком и компьютером на языке С++ Builder
Содержание
Введение. 31. Базовые понятия ИИ.. 4
2. История развития систем ИИ.. 8
Различные подходы к построению систем ИИ.. 16
Сокращенный листинг программы и описание алгоритма. 21
компоненты искусственного интелекта (ии) 26
Описание работы программы.. 37
Выводы.. 39
Литература. 40
Введение
Основой данной работы является создание игровой программы “шашки” для игры между человеком и компьютером. Для создания “думающих” игр требуется написание главного двигателя игры – функции искусственного интеллекта.Поэтому, в теоретическую часть вынесены основные сведения про разработку алгоритмов ИИ, показана историческая линия развития задач ИИ.
Для создания игры “шашки” требуется относительно несложная функция ИИ, главными задачами которой является предсказание на установленную глубину своих ходов и ходов противника. Это предсказание базируется на выборе наилучших ходов с обеих сторон. На финальном этапе функция ИИ избирает наиболее выгодную для компьютера цепочку ходов.
1. Базовые понятия ИИ
В современном мире прогресс производительности программиста практически достигается только в тех случаях, когда часть интеллектуальной нагрузки берут на себя компьютеры. Одним из способов достигнуть максимального прогресса в этой области, является "искусственный интеллект", когда компьютер берет на себя не только однотипные, многократно повторяющиеся операции, но и сам сможет обучаться. Кроме того, создание полноценного "искусственного интеллекта" открывает перед человечеством новые горизонты развития.Терминология.
Термин интеллект (intelligence) происходит от латинского intellectus - что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificial intelligence) - ИИ (AI) обычно толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий.
Мы, в нашем курсе, интеллектом будем называть способность мозга решать (интеллектуальные) задачи путем приобретения, запоминания и целенаправленного преобразования знаний в процессе обучения на опыте и адаптации к разнообразным обстоятельствам.
В этом определении под термином "знания" подразумевается не только ту информацию, которая поступает в мозг через органы чувств. Такого типа знания чрезвычайно важны, но недостаточны для интеллектуальной деятельности. Дело в том, что объекты окружающей нас среды обладают свойством не только воздействовать на органы чувств, но и находиться друг с другом в определенных отношениях. Ясно, что для того, чтобы осуществлять в окружающей среде интеллектуальную деятельность (или хотя бы просто существовать), необходимо иметь в системе знаний модель этого мира. В этой информационной модели окружающей среды реальные объекты, их свойства и отношения между ними не только отображаются и запоминаются, но и, как это отмечено в данном определении интеллекта, могут мысленно "целенаправленно преобразовываться". При этом существенно то, что формирование модели внешней среды происходит "в процессе обучения на опыте и адаптации к разнообразным обстоятельствам".
Мы употребили термин интеллектуальная задача. Для того, чтобы пояснить, чем отличается интеллектуальная задача от просто задачи, необходимо ввести термин "алгоритм" - один из краеугольных терминов кибернетики.
Под алгоритмом понимают точное предписание о выполнении в определенном порядке системы операций для решения любой задачи из некоторого данного класса (множества) задач. Термин "алгоритм" происходит от имени узбекского математика Аль-Хорезми, который еще в IX веке предложил простейшие арифметические алгоритмы. В математике и кибернетике класс задач определенного типа считается решенным, когда для ее решения установлен алгоритм. Нахождение алгоритмов является естественной целью человека при решении им разнообразных классов задач. Отыскание алгоритма для задач некоторого данного типа связано с тонкими и сложными рассуждениями, требующими большой изобретательности и высокой квалификации. Принято считать, что подобного рода деятельность требует участия интеллекта человека. Задачи, связанные с отысканием алгоритма решения класса задач определенного типа, будем называть интеллектуальными.
Что же касается задач, алгоритмы решения которых уже установлены, то, как отмечает известный специалист в области ИИ М. Минский, "излишне приписывать им такое мистическое свойства, как "интеллектуальность". В самом деле, после того, как такой алгоритм уже найден, процесс решения соответствующих задач становится таким, что его могут в точности выполнить человек, вычислительная машина (должным образом запрограммированная) или робот, не имеющие ни малейшего представления о сущность самой задачи. Требуется только, чтобы лицо, решающее задачу, было способно выполнять те элементарные операции, их которых складывается процесс, и, кроме того, чтобы оно педантично и аккуратно руководствовалось предложенным алгоритмом. Такое лицо, действуя, как говорят в таких случаях, чисто машинально, может успешно решать любую задачу рассматриваемого типа.
Поэтому представляется совершенно естественным исключить их класса интеллектуальных такие задачи, для которых существуют стандартные методы решения. Примерами таких задач могут служить чисто вычислительные задачи: решение системы линейных алгебраических уравнений, численное интегрирование дифференциальных уравнений и т.д. Для решения подобного рода задач имеются стандартные алгоритмы, представляющие собой определенную последовательность элементарных операций, которая может быть легко реализована в виде программы для вычислительной машины. В противоположность этому для широкого класса интеллектуальных задач, таких, как распознавание образов, игра в шахматы, доказательство теорем и т.п., напротив это формальное разбиение процесса поиска решения на отдельные элементарные шаги часто оказывается весьма затруднительным, даже если само их решение несложно.
Таким образом, мы можем перефразировать определение интеллекта как универсальный сверхалгоритм, который способен создавать алгоритмы решения конкретных задач.
Еще интересным замечанием здесь является то, что профессия программиста, исходя из наших определений, является одной из самых интеллектуальных, поскольку продуктом деятельности программиста являются программы - алгоритмы в чистом виде. Именно поэтому, создание даже элементов ИИ должно очень сильно повысить производительность его труда.
Деятельность мозга (обладающего интеллектом), направленную на решение интеллектуальных задач, мы будем называть мышлением, или интеллектуальной деятельностью. Интеллект и мышление органически связаны с решением таких задач, как доказательство теорем, логический анализ, распознавание ситуаций, планирование поведения, игры и управление в условиях неопределенности. Характерными чертами интеллекта, проявляющимися в процессе решения задач, являются способность к обучению, обобщению, накоплению опыта (знаний и навыков) и адаптации к изменяющимся условиям в процессе решения задач. Благодаря этим качествам интеллекта мозг может решать разнообразные задачи, а также легко перестраиваться с решения одной задачи на другую. Таким образом, мозг, наделенный интеллектом, является универсальным средством решения широкого круга задач (в том числе неформализованных) для которых нет стандартных, заранее известных методов решения.
Следует иметь в виду, что существуют и другие, чисто поведенческие (функциональные) определения. Так, по А.Н. Колмогорову, любая материальная система, с которой можно достаточно долго обсуждать проблемы науки, литературы и искусства, обладает интеллектом. Другим примером поведенческой трактовки интеллекта может служить известное определение А. Тьюринга. Его смысл заключается в следующем. В разных комнатах находится люди и машина. Они не могут видеть друг друга, но имеют возможность обмениваться информацией (например, с помощью электронной почты). Если в процессе диалога между участниками игры людям не удается установить, что один из участников - машина, то такую машину можно считать обладающей интеллектом.
Кстати интересен план имитации мышления, предложенный А. Тьюрингом. "Пытаясь имитировать интеллект взрослого человека, - пишет Тьюринг, - мы вынуждены много размышлять о том процессе, в результате которого человеческий мозг достиг своего настоящего состояния… Почему бы нам вместо того, чтобы пытаться создать программу, имитирующую интеллект взрослого человека, не попытаться создать программу, которая имитировала бы интеллект ребенка? Ведь если интеллект ребенка получает соответствующее воспитание, он становится интеллектом взрослого человека… Наш расчет состоит в том, что устройство, ему подобное, может быть легко запрограммировано… Таким образом, мы расчленим нашу проблему на две части: на задачу построения "программы-ребенка" и задачу "воспитания" этой программы".
Забегая вперед, можно сказать, что именно этот путь используют практически все системы ИИ. Ведь понятно, что практически невозможно заложить все знания в достаточно сложную систему. Кроме того, только на этом пути проявятся перечисленные выше признаки интеллектуальной деятельности (накопление опыта, адаптация и т.д.).
2. История развития систем ИИ
Исторически сложились три основных направления в моделировании ИИ.В рамках первого подхода объектом исследований являются структура и механизмы работы мозга человека, а конечная цель заключается в раскрытии тайн мышления. Необходимыми этапами исследований в этом направлении являются построение моделей на основе психофизиологических данных, проведение экспериментов с ними, выдвижение новых гипотез относительно механизмов интеллектуальной деятельности, совершенствование моделей и т.д.
Второй подход в качестве объекта исследования рассматривает ИИ. Здесь речь идет о моделировании интеллектуальной деятельности с помощью вычислительных машин. Целью работ в этом направлении является создание алгоритмического и программного обеспечения вычислительных машин, позволяющего решать интеллектуальные задачи не хуже человека.
Наконец, третий подход ориентирован на создание смешанных человеко-машинных, или, как еще говорят, интерактивных интеллектуальных систем, на симбиоз возможностей естественного и искусственного интеллекта. Важнейшими проблемами в этих исследованиях является оптимальное распределение функций между естественным и искусственным интеллектом и организация диалога между человеком и машиной.
Самыми первыми интеллектуальными задачами, которые стали решаться при помощи ЭВМ были логические игры (шашки, шахматы), доказательство теорем. Хотя, правда здесь надо отметить еще кибернетические игрушки типа "электронной мыши" Клода Шеннона, которая управлялась сложной релейной схемой. Эта мышка могла "исследовать" лабиринт, и находить выход из него. А кроме того, помещенная в уже известный ей лабиринт, она не искала выход, а сразу же, не заглядывая в тупиковые ходы, выходила из лабиринта.
Американский кибернетик А. Самуэль составил для вычислительной машины программу, которая позволяет ей играть в шашки, причем в ходе игры машина обучается или, по крайней мере, создает впечатление, что обучается, улучшая свою игру на основе накопленного опыта. В 1962 г. эта программа сразилась с Р. Нили, сильнейшим шашистом в США и победила.
Каким образом машине удалось достичь столь высокого класса игры?
Естественно, что в машину были программно заложены правила игры так, что выбор очередного хода был подчинен этим правилам. На каждой стадии игры машина выбирала очередной ход из множества возможных ходов согласно некоторому критерию качества игры. В шашках (как и в шахматах) обычно невыгодно терять свои фигуры, и, напротив, выгодно брать фигуры противника. Игрок (будь он человек или машина), который сохраняет подвижность своих фигур и право выбора ходов и в то же время держит под боем большое число полей на доске, обычно играет лучше своего противника, не придающего значения этим элементам игры. Описанные критерии хорошей игры сохраняют свою силу на протяжении всей игры, но есть и другие критерии, которые относятся к отдельным ее стадиям - дебюту, миттэндшпилю, эндшпилю.
Разумно сочетая такие критерии (например в виде линейной комбинации с экспериментально подбираемыми коэффициентами или более сложным образом), можно для оценки очередного хода машины получить некоторый числовой показатель эффективности - оценочную функцию. Тогда машина, сравнив между собой показатели эффективности очередных ходов, выберет ход, соответствующий наибольшему показателю. Подобная автоматизация выбора очередного хода не обязательно обеспечивает оптимальный выбор, но все же это какой-то выбор, и на его основе машина может продолжать игру, совершенствуя свою стратегию (образ действия) в процессе обучения на прошлом опыте. Формально обучение состоит в подстройке параметров (коэффициентов) оценочной функции на основе анализа проведенных ходов и игр с учетом их исхода.
По мнению А. Самуэля, машина, использующая этот вид обучения, может научиться играть лучше, чем средний игрок, за относительно короткий период времени.
Можно сказать, что все эти элементы интеллекта, продемонстрированные машиной в процессе игры в шашки, сообщены ей автором программы. Отчасти это так. Но не следует забывать, что программа эта не является "жесткой", заранее продуманной во всех деталях. Она совершенствует свою стратегию игры в процессе самообучения. И хотя процесс "мышления" у машины существенно отличен оттого, что происходит в мозгу играющего в шашки человека, она способна у него выиграть.
Ярким примером сложной интеллектуальной игры до недавнего времени являлись шахматы. В 1974 г. состоялся международный шахматный турнир машин, снабженных соответствующими программами. Как известно, победу на этом турнире одержала советская машина с шахматной программой "Каисса".
Почему здесь употреблено "до недавнего времени"? Дело в том, что недавние события показали, что несмотря на довольно большую сложность шахмат, и невозможность, в связи с этим произвести полный перебор ходов, возможность перебора их на большую глубину, чем обычно, очень увеличивает шансы на победу. К примеру, по сообщениям в печати, компьютер фирмы IBM, победивший Каспарова, имел 256 процессоров, каждый из которых имел 4 Гб дисковой памяти и 128 Мб оперативной. Весь этот комплекс мог просчитывать более 100'000'000 ходов в секунду. До недавнего времени редкостью был компьютер, могущий делать такое количество целочисленных операций в секунду, а здесь мы говорим о ходах, которые должны быть сгенерированы и для которых просчитаны оценочные функции. Хотя с другой стороны, этот пример говорит о могуществе и универсальности переборных алгоритмов.
В настоящее время существуют и успешно применяются программы, позволяющие машинам играть в деловые или военные игры, имеющие большое прикладное значение. Здесь также чрезвычайно важно придать программам присущие человеку способность к обучению и адаптации. Одной из наиболее интересных интеллектуальных задач, также имеющей огромное прикладное значение, является задача обучения распознавания образов и ситуаций. Решением ее занимались и продолжают заниматься представители различных наук - физиологи, психологи, математики, инженеры. Такой интерес к задаче стимулировался фантастическими перспективами широкого практического использования результатов теоретических исследований: читающие автоматы, системы ИИ, ставящие медицинские диагнозы, проводящие криминалистическую экспертизу и т.п., а также роботы, способные распознавать и анализировать сложные сенсорные ситуации.
В 1957 г. американский физиолог Ф. Розенблатт предложил модель зрительного восприятия и распознавания - перцептрон. Появление машины, способной обучаться понятиям и распознавать предъявляемые объекты, оказалось чрезвычайно интересным не только физиологам, но и представителям других областей знания и породило большой поток теоретических и экспериментальных исследований.
Перцептрон или любая программа, имитирующая процесс распознавания, работают в двух режимах: в режиме обучения и в режиме распознавания. В режиме обучения некто (человек, машина, робот или природа), играющий роль учителя, предъявляет машине объекты и о каждом их них сообщает, к какому понятию (классу) он принадлежит. По этим данным строится решающее правило, являющееся, по существу, формальным описанием понятий. В режиме распознавания машине предъявляются новые объекты (вообще говоря, отличные от ранее предъявленных), и она должна их классифицировать, по возможности, правильно.
Что же касается моделирования логического мышления, то хорошей модельной задачей здесь может служить задача автоматизации доказательства теорем. Начиная с 1960 г., был разработан ряд программ, способных находить доказательства теорем в исчислении предикатов первого порядка. Эти программы обладают, по словам американского специалиста в области ИИ Дж. Маккатти, "здравым смыслом", т.е. способностью делать дедуктивные заключения.
В программе К. Грина и др., реализующей вопросно-ответную систему, знания записываются на языке логики предикатов в виде набора аксиом, а вопросы, задаваемые машине, формулируются как подлежащие доказательству теоремы. Большой интерес представляет "интеллектуальная" программа американского математика Хао Ванга. Эта программа за 3 минуты работы IBM-704 вывела 220 относительно простых лемм и теорем из фундаментальной математической монографии, а затем за 8.5 мин выдала доказательства еще 130 более сложных теорем, часть их которых еще не была выведена математиками. Правда, до сих пор ни одна программа не вывела и не доказала ни одной теоремы, которая бы, что называется "позарез" была бы нужна математикам и была бы принципиально новой.
Очень большим направлением систем ИИ является роботехника. В чем основное отличие интеллекта робота от интеллекта универсальных вычислительных машин?
Для ответа на этот вопрос уместно вспомнить принадлежащее великому русскому физиологу И.М. Сеченову высказывание: "… все бесконечное разнообразие внешних проявлений мозговой деятельности сводится окончательно лишь к одному явлению - мышечному движению". Другими словами, вся интеллектуальная деятельность человека направлена в конечном счете на активное взаимодействие с внешним миром посредством движений. Точно так же элементы интеллекта робота служат прежде всего для организации его целенаправленных движений. В то же время основное назначение чисто компьютерных систем ИИ состоит в решении интеллектуальных задач, носящих абстрактный или вспомогательный характер, которые обычно не связаны ни с восприятием окружающей среды с помощью искусственных органов чувств, ни с организацией движений исполнительных механизмов.
Первых роботов трудно назвать интеллектуальными. Только в 60-х годах появились очувствленные роботы, которые управлялись универсальными компьютерами. К примеру в 1969 г. в Электротехнической лаборатории (Япония) началась разработка проекта "промышленный интеллектуальный робот". Цель этой разработки - создание очуствленного манипуляционного робота с элементами искусственного интеллекта для выполнения сборочно-монтажных работ с визуальным контролем.
Манипулятор робота имеет шесть степеней свободы и управляется мини-ЭВМ NEAC-3100 (объем оперативной памяти 32000 слов, объем внешней памяти на магнитных дисках 273000 слов), формирующей требуемое программное движение, которое отрабатывается следящей электрогидравлической системой. Схват манипулятора оснащен тактильными датчиками.
В качестве системы зрительного восприятия используются две телевизионные камеры, снабженные красно-зелено-синими фильтрами для распознавания цвета предметов. Поле зрения телевизионной камеры разбито на 64*64 ячеек. В результате обработки полученной информации грубо определяется область, занимаемая интересующим робота предметом. Далее, с целью детального изучения этого предмета выявленная область вновь делится на 4096 ячеек. В том случае, когда предмет не помещается в выбранное "окошко", оно автоматически перемещается, подобно тому, как человек скользит взглядом по предмету. Робот Электротехнической лаборатории был способен распознавать простые предметы, ограниченные плоскостями и цилиндрическими поверхностями при специальном освещении. Стоимость данного экспериментального образца составляла примерно 400000 долларов.
Постепенно характеристики роботов монотонно улучшались, Но до сих пор они еще далеки по понятливости от человека, хотя некоторые операции уже выполняют на уровне лучших жонглеров. К примеру удерживают на лезвии ножа шарик от настольного тенниса.
Еще пожалуй здесь можно выделить работы киевского Института кибернетики, где под руководством Н.М. Амосова и В.М. Глушкова (ныне покойного) ведется комплекс исследований, направленных на разработку элементов интеллекта роботов. Особое внимание в этих исследованиях уделяется проблемам распознавания изображений и речи, логического вывода (автоматического доказательства теорем) и управления с помощью нейроподобных сетей.
К примеру можно рассмотреть созданный еще в 70-х годах макет транспортного автономного интегрального робота (ТАИР). Конструктивно ТАИР представляет собой трехколесное шасси, на котором смонтирована сенсорная система и блок управления. Сенсорная система включает в себя следующие средства очуствления: оптический дальномер, навигационная система с двумя радиомаяками и компасом, контактные датчики, датчики углов наклона тележки, таймер и др. И особенность, которая отличает ТАИР от многих других систем, созданных у нас и за рубежом, это то, что в его составе нет компьютера в том виде, к которому мы привыкли. Основу системы управления составляет бортовая нейроподобная сеть, на которой реализуются различные алгоритмы обработки сенсорной информации, планирования поведения и управления движением робота.
В конце данного очень краткого обзора рассмотрим примеры крупномасштабных экспертных систем.
MICIN - экспертная система для медицинской диагностики. Разработана группой по инфекционным заболеваниям Стенфордского университета. Ставит соответствующий диагноз, исходя из представленных ей симптомов, и рекомендует курс медикаментозного лечения любой из диагностированных инфекций. База данных состоит из 450 правил.
PUFF - анализ нарушения дыхания. Данная система представляет собой MICIN, из которой удалили данные по инфекциям и вставили данные о легочных заболеваниях.
DENDRAL - распознавание химических структур. Данная система старейшая, из имеющих звание экспертных. Первые версии данной системы появились еще в 1965 году во все том же Стенфордском университете. Пользователь дает системе DENDRAL некоторую информацию о веществе, а также данные спектрометрии (инфракрасной, ядерного магнитного резонанса и масс-спектрометрии), и та в свою очередь выдает диагноз в виде соответствующей химической структуры.
PROSPECTOR - экспертная система, созданная для содействия поиску коммерчески оправданных месторождений полезных ископаемых.
Архитектура и основные составные части систем ИИ.
Различные подходы к построению систем ИИ (логический, структурный, эволюционный, имитационный) и методы представления знаний. Краткое ознакомление с данными подходами. Вспомогательные системы (распознавание образов зрительных и звуковых, идентификация, моделирование, жесткое программирование) и их место в системах ИИ.
Различные подходы к построению систем ИИ
Существуют различные подходы к построению систем ИИ. Это разделение не является историческим, когда одно мнение постепенно сменяет другое, и различные подходы существуют и сейчас. Кроме того, поскольку по-настоящему полных систем ИИ в настоящее время нет, то нельзя сказать, что какой-то подход является правильным, а какой-то ошибочным.Для начала кратко рассмотрим логический подход. Почему он возник? Ведь человек занимается отнюдь не только логическими измышлениями. Это высказывание конечно верно, но именно способность к логическому мышлению очень сильно отличает человека от животных.
Основой для данного логического подхода служит Булева алгебра. Каждый программист знаком с нею и с логическими операторами с тех пор, когда он осваивал оператор IF. Свое дальнейшее развитие Булева алгебра получила в виде исчисления предикатов - в котором она расширена за счет введения предметных символов, отношений между ними, кванторов существования и всеобщности. Практически каждая система ИИ, построенная на логическом принципе, представляет собой машину доказательства теорем. При этом исходные данные хранятся в базе данных в виде аксиом, правила логического вывода как отношения между ними. Кроме того, каждая такая машина имеет блок генерации цели, и система вывода пытается доказать данную цель как теорему. Если цель доказана, то трассировка примененных правил позволяет получить цепочку действий, необходимых для реализации поставленной цели. Мощность такой системы определяется возможностями генератора целей и машиной доказательства теорем.
Конечно можно сказать, что выразительности алгебры высказываний не хватит для полноценной реализации ИИ, но стоит вспомнить, что основой всех существующих ЭВМ является бит - ячейка памяти, которая может принимать значения только 0 и 1. Таким образом было бы логично предположить, что все, что возможно реализовать на ЭВМ, можно было бы реализовать и в виде логики предикатов. Хотя здесь ничего не говорится о том, за какое время.
Добиться большей выразительности логическому подходу позволяет такое сравнительно новое направление, как нечеткая логика. Основным ее отличием является то, что правдивость высказывания может принимать в ней кроме да/нет (1/0) еще и промежуточные значения - не знаю (0.5), пациент скорее жив, чем мертв (0.75), пациент скорее мертв, чем жив (0.25). Данный подход больше похож на мышление человека, поскольку он на вопросы редко отвечает только да или нет. Хотя правда на экзамене будут приниматься только ответы из разряда классической булевой алгебры.
Для большинства логических методов характерна большая трудоемкость, поскольку во время поиска доказательства возможен полный перебор вариантов. Поэтому данный подход требует эффективной реализации вычислительного процесса, и хорошая работа обычно гарантируется при сравнительно небольшом размере базы данных.
Под структурным подходом мы подразумеваем здесь попытки построения ИИ путем моделирования структуры человеческого мозга. Одной из первых таких попыток был перцептрон Френка Розенблатта. Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нейрон.
Позднее возникли и другие модели, которые в простонародье обычно известны под термином "нейронные сети" (НС). Эти модели различаются по строению отдельных нейронов, по топологии связей между ними и по алгоритмам обучения. Среди наиболее известных сейчас вариантов НС можно назвать НС с обратным распространением ошибки, сети Хопфилда, стохастические нейронные сети.
НС наиболее успешно применяются в задачах распознавания образов, в том числе сильно зашумленных, однако имеются и примеры успешного применения их для построения собственно систем ИИ, это уже ранее упоминавшийся ТАИР.
Для моделей, построенных по мотивам человеческого мозга характерна не слишком большая выразительность, легкое распараллеливание алгоритмов, и связанная с этим высокая производительность параллельно реализованных НС. Также для таких сетей характерно одно свойство, которое очень сближает их с человеческим мозгом - нейронные сети работают даже при условии неполной информации об окружающей среде, то есть как и человек, они на вопросы могут отвечать не только "да" и "нет" но и "не знаю точно, но скорее да".
Довольно большое распространение получил и эволюционный подход. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и НС и набор логических правил и любая другая модель. После этого мы включаем компьютер и он, на основании проверки моделей отбирает самые лучшие из них, на основании которых по самым различным правилам генерируются новые модели, из которых опять выбираются самые лучшие и т.д.
В принципе можно сказать, что эволюционных моделей как таковых не существует, существует только эволюционные алгоритмы обучения, но модели, полученные при эволюционном подходе имеют некоторые характерные особенности, что позволяет выделить их в отдельный класс.
Такими особенностями являются перенесение основной работы разработчика с построения модели на алгоритм ее модификации и то, что полученные модели практически не сопутствуют извлечению новых знаний о среде, окружающей систему ИИ, то есть она становится как бы вещью в себе.
Еще один широко используемый подход к построению систем ИИ - имитационный. Данный подход является классическим для кибернетики с одним из ее базовых понятий - "черным ящиком" (ЧЯ). ЧЯ - устройство, программный модуль или набор данных, информация о внутренней структуре и содержании которых отсутствуют полностью, но известны спецификации входных и выходных данных. Объект, поведение которого имитируется, как раз и представляет собой такой "черный ящик". Нам не важно, что у него и у модели внутри и как он функционирует, главное, чтобы наша модель в аналогичных ситуациях вела себя точно так же.
Таким образом здесь моделируется другое свойство человека - способность копировать то, что делают другие, не вдаваясь в подробности, зачем это нужно. Зачастую эта способность экономит ему массу времени, особенно в начале его жизни.
Основным недостатком имитационного подхода также является низкая информационная способность большинства моделей, построенных с его помощью.
С ЧЯ связана одна очень интересная идея. Кто бы хотел жить вечно? Я думаю, что почти все ответят на этот вопрос "я".
Представим себе, что за нами наблюдает какое-то устройство, которое следит за тем, что в каких ситуациях мы делаем, говорим. Наблюдение идет за величинами, которые поступают к нам на вход (зрение, слух, вкус, тактильные, вестибулярные и т.д.) и за величинами, которые выходят от нас (речь, движение и др.). Таким образом человек выступает здесь как типичный ЧЯ.
Далее это устройство пытается отстроить какую-то модель таким образом, чтобы при определенных сигналах на входе человека, она выдавала на выходе те же данные, что и человек. Если данная затея будет когда-нибудь реализована, то для всех посторонних наблюдателей такая модель будет той же личностью, что и реальный человек. А после его смерти она, будет высказывать те мысли, которые предположительно высказывал бы и смоделированный человек.
Мы можем пойти дальше и скопировать эту модель и получить брата близнеца с точно такими же "мыслями".
Можно сказать, что "это конечно все интересно, но при чем тут я? Ведь эта модель только для других будет являться мной, но внутри ее будет пустота. Копируются только внешние атрибуты, но я после смерти уже не буду думать, мое сознание погаснет (для верующих людей слово "погаснет" необходимо заменить на "покинет этот мир")". Что ж это так. Но попробуем пойти дальше.
Согласно философским представлениям автора данного курса, сознание представляет собой сравнительно небольшую надстройку над нашим подсознанием, которая следит за активностью некоторых центров головного мозга, таких как центр речи, конечной обработки зрительных образов, после чего "возвращает" эти образы на начальные ступени обработки данной информации. При этом происходит повторная обработка этих образов, мы как бы видим и слышим, что думает наш мозг. При этом появляется возможность мысленного моделирования окружающей действительности при нашем "активном" участии в данном процессе. И именно наш процесс наблюдения за деятельностью этих немногих центров является тем, что мы называем сознанием. Если мы "видим" и "слышим" наши мысли, мы в сознании, если нет, то мы находимся в бессознательном состоянии.
Если бы мы смогли смоделировать работу именно этих немногих "сознательных" нервных центров (работа которых правда основана на деятельности всего остального мозга) в качестве одного ЧЯ, и работу "супервизора" в качестве другого ЧЯ, то можно было бы с уверенностью говорить, что "да, данная модель думает, причем так же, как и я". Здесь я ничего не хочу говорить о том, как получить данные о работе этих нервных центров, поскольку на мой взгляд сегодня нет ничего такого, что позволило бы следить за мозгом человека годами и при этом не мешало бы его работе и жизни.
И заканчивая беглое ознакомление с различными методами и подходами к построению систем ИИ, хотелось бы отметить, что на практике очень четкой границы между ними нет. Очень часто встречаются смешанные системы, где часть работы выполняется по одному типу, а часть по другому.
главный класс оконного интерфейса - TCheckersWindow
главный думающий, играющий класс - BOARD
КРАТКОЕ ОПИСАНИЕ АЛГОРИТМА
УПРАВЛЕНИЕ производится через оконный интерфейсный класс TCheckersWindow.
Ход человека начинается нажатием левой кнопки мышки над фишкой (при этом запускается
функция WMLButtonDown() из класса TCheckersWindow), дальше не отпуская кнопку курсор
передвигается на новую позицию фишки и кнопка отпускается (при этом запускается
функция WMLButtonUp() из класса TCheckersWindow). Рассмотрим работу этих двух
функций подробнее (см. примечания в тексте функции):
Функция WMLButtonDown():
void TCheckersWindow:: WMLButtonDown(TMessage&) // =====НАЧИНАЕМ ХОД======
{
POINT Point;
if (WhoseTurn == Black) // =====ПРОВЕРЯЕМ, ДЕЙСТВИТЕЛЬНО ЛИ ХОДИТ ЧЕЛОВЕК=====
return;
SetCapture(HWindow);
GetCursorPos(&Point);
ScreenToClient(HWindow, &Point);
MoveStartPoint = bd->GetValidSquare(Point, WhoseTurn);
if (MoveStartPoint. x)
{
MovingPieceType = bd->GetPieceType(MoveStartPoint);
HDC hDC = GetDC(HWindow);
bd->ClearSquare(hDC, MoveStartPoint);
HoldingPiece = TRUE;
ReleaseDC(HWindow, hDC);
}
}
Функция WMLButtonUp():
void TCheckersWindow:: WMLButtonUp(TMessage&)
{
POINT Point;
ReleaseCapture();
if (! HoldingPiece || WhoseTurn == Black)
return;
GetCursorPos(&Point);
ScreenToClient(HWindow, &Point);
MoveEndPoint = bd->GetEmptySquare(Point);
HDC hDC = GetDC(HWindow);
if (MoveEndPoint. x && bd->UserMove(MoveStartPoint, MoveEndPoint))
{ // ====ЕСЛИ ЧЕЛОВЕК МОЖЕТ СЮДА ПОСТАВИТЬ ФИШКУ... =====
bd->RedrawBoard(hDC); // =========ТО ПЕРЕРИСОВЫВАЕМ ДОСКУ=======
EnableMenuItem(hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED);
EnableMenuItem(hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
if (! bd->AnotherJump()) // =====МОЖНО СДЕЛАТЬ ПОВТОРНЫЙ ХОД? ========
{
if (bd->NoMoreBlack()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК КОМПЬЮТЕРА... . ===
{
if (GetApplication() - >ExecDialog(new TEndDialog(this, "UserWonDlg")) // ТО ЧЕЛОВЕК ВЫИГРАЛ!
== IDYES)
{
PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L);
ReleaseDC(HWindow, hDC);
return;
}
else
{
PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L);
ReleaseDC(HWindow, hDC);
return;
}
}
PostMessage(HWindow, WM_COMMAND, CM_MOVE, 0L); // ==ПЕРЕКЛЮЧАЕМСЯ НА ХОД===
} // =======КОМПЬЮТЕРА=======
else // НЕЯВНЫЙ ВЫЗОВ ФУНКЦИИ
; // ComputersMove()
}
else
{
bd->DrawPiece(hDC, MovingPieceType, MoveStartPoint);
}
HoldingPiece = FALSE;
ReleaseDC(HWindow, hDC);
}
Функция ComputersMove():
void TCheckersWindow:: ComputersMove(RTMessage)
{
bd->EndUsersTime();
WhoseTurn = Black;
EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
ModifyMenu(hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_STOP, "&Stop");
DrawMenuBar(HWindow);
bd->ComputersTurn(); // =======ПЕРЕКЛЮЧАЕМСЯ НА РАБОТУ ИИ========
HDC hDC = GetDC(HWindow);
bd->RedrawBoard(hDC);
ReleaseDC(HWindow, hDC);
WhoseTurn = Red;
POINT CursorPoint;
GetCursorPos(&CursorPoint);
ScreenToClient(HWindow, &CursorPoint);
#pragma warn - stv
if (PtInRect(&MainWndRect, CursorPoint))
/*SetCursor(CursorHand) */;
#pragma warn +stv
ModifyMenu(hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_MOVE, "move you");
EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_ENABLED);
DrawMenuBar(HWindow);
if (bd->NoMoreRed()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК ЧЕЛОВЕКА... . ===
{
if (GetApplication() - >ExecDialog(new TEndDialog(this, "GameWonDlg")) // ===ТО КОМПЬЮТЕР===
== IDYES) // ======ВЫИГРАЛ======
{
PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L);
return;
}
else
{
PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L);
return;
}
}
bd->StartUsersTime(); // ======ХОД ЧЕЛОВЕКА========
}
BOOL BOARD:: ComputersTurn()
{
int iter, i, val, row = 0, col = 0;
double t;
time_t itime1, itime2;
long lNodes;
int alpha = - MAXINT, beta = MAXINT;
StopSearch = FALSE;
ClearRedoStack();
memcpy(SavedBoard, Board, sizeof(Board));
if(! OnlyOneMove(Black, &row, &col))
{
Nodes = 0;
time(&start_t);
PreEvaluate(); // =======ПОЛИТИКА ИГРЫ (НАПАДАТЬ ИЛИ ОТБИВАТЬСЯ) =====
/* clear out the best-variation table */
for(i = 0; i <= MAXPLY; ++i)
{
BestVar [i] [i]. org. SetRow(0);
BestVar [0] [i]. org. SetRow(0);
}
/* clear out the Killer table */
for(i = 0; i <= MAXPLY; ++i)
{
Killer [i] [0]. org. SetRow(0);
Killer [i] [0]. Value = - 1;
}
for(iter = IterFlag? 1: SearchDepth; iter <= SearchDepth; ++iter)
{
lNodes = Nodes;
time(&itime1);
val = Evaluate(alpha, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
if(val >= beta)
{
val = Evaluate(alpha, MAXINT, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
else
{
if(val <= alpha)
{
val = Evaluate(- MAXINT, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
}
alpha = val - 12;
beta = val + 12;
/* seed the killer table with the best variation */
for(i = 0; BestVar [0] [i]. org. GetRow(); ++i)
{
memcpy(&Killer [i] [0], &BestVar [0] [i], sizeof(MOVE));
Killer [i] [0]. Value = 1;
/* eliminate the other killer move */
Killer [i] [1]. Value = - 1;
Killer [i] [1]. org. SetRow(0);
}
/* clear the rest of the killer table */
do
{
Killer [i] [0]. org. SetRow(0);
Killer [i] [1]. org. SetRow(0);
}
while(i++ < MAXPLY);
time(&itime2);
t = difftime(itime2, itime1);
DisplaySearchStats(iter, val, Nodes - lNodes, t);
}
time(&end_t);
if((t = difftime(end_t, start_t)) ! = 0)
{
sprintf(buf, "%.0f", t);
sprintf(buf, "%ld", Nodes);
ComputerTotalTime += t;
}
else
{
sprintf(buf, "%ld", Nodes);
}
for (i = 0; Man [Board [BestVar [0] [i]. org. GetRow()]
[BestVar [0] [i]. org. GetCol()]. What]. GetSide() == Black; ++i)
{
MakeActualMove(BestVar [0] [i]);
}
}
TimeToStr(buf, ComputerTotalTime);
return(TRUE);
}
Функция PreEvaluate() разрабатывает политику игры:
void BOARD:: PreEvaluate()
{
int i, j, xman, inside;
int tBSizeDiv2 = BoardSize >> 1; // (BoardSize / 2)
/*********************************************************
This code gets a rough idea as to who is ahead in Material.
**********************************************************/
Material [Red] = 0;
Material [Black] = 0;
Man [REDMAN]. SetValue(100);
Man [BLACKMAN]. SetValue(100);
Man [REDKING]. SetValue (140);
Man [BLACKKING]. SetValue(140);
Man [EMPTY]. SetValue(0);
Man [OFFBOARD]. SetValue(0);
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide()] += Man [xman]. GetValue();
}
}
/****************************************************
Now adjust the Material weights based on who is ahead.
This is to encourage the fellow who is winning to exchange pieces
and the fellow who is behind to not exchange pieces.
If Material is dead even then you shouldn't try to force exchanges
just on general principles.
*****************************************************/
if(Material [Red] >= Material [Black])
{
- -Man [REDMAN] ;
--Man [REDKING] ;
}
else
{
- -Man [BLACKMAN] ;
--Man [BLACKKING] ;
}
/****************************************************
Examine each and every square and calculate the bonus values.
*****************************************************/
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
inside = (j > 1 && j < BoardSize) ? 1: 0;
SValue [i] [j] [REDMAN] = Man [REDMAN]. GetValue() + inside;
SValue [i] [j] [REDKING] = Man [REDKING]. GetValue() + inside;
SValue [i] [j] [BLACKMAN] = Man [BLACKMAN]. GetValue() + inside;
SValue [i] [j] [BLACKKING] = Man [BLACKKING]. GetValue() + inside;
/* bonus points for central squares */
if(abs(tBSizeDiv2 - i) < 2 && abs(tBSizeDiv2 - j) < 3)
{
++SValue [i] [j] [REDMAN] ;
++SValue [i] [j] [REDKING] ;
++SValue [i] [j] [BLACKMAN] ;
++SValue [i] [j] [BLACKKING] ;
}
/* bonus for non-Crown piece advancement */
if(i > 2)
{
SValue [i] [j] [REDMAN] += i - 2;
}
if(i < BoardSize - 2)
{
SValue [i] [j] [BLACKMAN] += BoardSize - i - 1;
}
if(i == 1)
++SValue [i] [j] [REDMAN] ;
if(i == BoardSize)
++SValue [i] [j] [BLACKMAN] ;
}
}
Material [Red] = 0;
Material [Black] = 0;
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide()] += SValue [i] [j] [xman] ;
}
}
}
Функция Evaluate() представляет непосредственно функцию ИИ. Основной принцип -
на глубину depth анадблжлизируются возможные ходы компьютера и ответные ходы человека - ищем наилучшую стратегию:
int BOARD:: Evaluate(int alpha, int beta, SIDE player, int row, int col, int limit, int ply)
{
MOVE *list = new MOVE [MAXMOVES] ;
MOVE *mptr, *endptr;
int NumMoves, val;
int num_back = 0;
int retval = 0;
int t1 = WIN - 2 - ply;
int plyp1 = ply + 1;
if (StopSearch)
goto END_EVALUATE;
++Nodes;
if((NumMoves = Lmg(list, player, row, col, ply)) == 0)
{
retval = LOSS + ply;
goto END_EVALUATE;
}
MessageScan();
if (StopSearch)
{
retval = 0;
goto END_EVALUATE;
}
if(list->Quiescent(limit, NumMoves, ply))
{
retval = (Material [player] - Material [OPLAYER] + (NumMoves > 3? 1: 0));
goto END_EVALUATE;
}
for(mptr = list, endptr = mptr + NumMoves; mptr < endptr && alpha < t1; mptr++)
{
MakeMove(*mptr);
if(mptr->Capture! = EMPTY)
{
if(! (mptr->Crown) && CanJump(player, mptr->dest. GetRow(), mptr->dest. GetCol()))
{
val = Evaluate(alpha, beta, player, mptr->dest. GetRow(), mptr->dest. GetCol(), limit, plyp1);
}
else
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
}
else
{
if(limit == 0 || NumMoves == 1)
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
else
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit? limit - 1: 0, plyp1) * - 1;
}
}
UnMakeMove(*mptr);
if(val > alpha)
{
if(val >= beta)
{
if(KillerFlag)
UpdateKillerTable(*mptr, ply);
retval = beta;
goto END_EVALUATE;
}
else
{
alpha = val;
++num_back;
UpdateBestVariation(mptr, ply);
}
}
BestVar [plyp1] [plyp1]. org. SetRow(0);
}
retval = alpha;
END_EVALUATE:
delete list;
return retval;
}
Вспомагательная функция GenMoves() генерурует возможные ходы и
записывает их в список:
/********************************************
generates the list of moves for a given player at a row, col
returns the number of legal moves found
********************************************/
int BOARD:: GenMoves(MOVE *list, int row, int col)
{
int NumMoves;
int what;
int trow1 = row + 1, tcol1 = col + 1, trowm1 = row - 1, tcolm1 = col - 1;
NumMoves = 0;
what = Board [row] [col]. What;
if(what == REDKING || what == BLACKKING || what == BLACKMAN)
{
if(Board [trowm1] [tcolm1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trowm1);
list->dest. SetCol(tcolm1);
list->Capture = EMPTY;
list->Crown = ((row == 2) && (what == BLACKMAN));
++NumMoves;
++list;
}
if(Board [trowm1] [tcol1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trowm1);
list->dest. SetCol(tcol1);
list->Capture = EMPTY;
list->Crown = ((row == 2) && (what == BLACKMAN));
++NumMoves;
++list;
}
}
if(what == REDKING || what == BLACKKING || what == REDMAN)
{
if(Board [trow1] [tcolm1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trow1);
list->dest. SetCol(tcolm1);
list->Capture = EMPTY;
list->Crown = ((row == BoardSize - 1) && (what == REDMAN));
++NumMoves;
++list;
}
if(Board [trow1] [tcol1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trow1);
list->dest. SetCol(tcol1);
list->Capture = EMPTY;
list->Crown = ((row == BoardSize - 1) && (what == REDMAN));
++NumMoves;
++list;
}
}
return(NumMoves);
}
BC30RTL. DLL
OWL31. DLL
TCLASS31. DLL
В текстовом файле DEPTH хранится единственная настройка игры – глубина анализа ходов, по умолчанию она установлена в 3 – средний уровень игры в шашки.
Меню игры предельно простое и состоит из единственного пункта – “move you” – пропуск хода.
Ниже приведено две экранные копии программы.
Начало игры
Была разработана относительно несложная функция ИИ, главными задачами которой является предсказание на установленную глубину своих ходов и ходов противника. Это предсказание базируется на выборе наилучших ходов с обеих сторон. На финальном этапе функция ИИ избирает наиболее выгодную для компьютера цепочку ходов.
Программа отличается от существующих на рынке простотой интерфейса и настроек.
2. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си. Мн., 1992. 240 С.
3. Нейбауэр А. Моя первая программа на С/С++.П., 1995. 368 С.
4. Бруно Бабэ. Просто и ясно о Borland C++.М., 1996. 400 С.
5. Шамас Н.К. Основы С++ и обьектно-ориентированного программирования. К., 1996. 448 С.
6. Справочник по классам Borland C++ 4.0.К., 1994.256 С.
7. ObjectWindows для C++. К., 1993., 208 С.
8. Том Сван. Программирование для Windows в Borland C++. М., 480 С.
9. Н. Барканати. Программирование игр для Windows на Borland C++. М., 1994. 512 С.
Сокращенный листинг программы и описание алгоритма
ОСНОВНЫЕ КЛАССЫглавный класс оконного интерфейса - TCheckersWindow
главный думающий, играющий класс - BOARD
КРАТКОЕ ОПИСАНИЕ АЛГОРИТМА
УПРАВЛЕНИЕ производится через оконный интерфейсный класс TCheckersWindow.
Ход человека начинается нажатием левой кнопки мышки над фишкой (при этом запускается
функция WMLButtonDown() из класса TCheckersWindow), дальше не отпуская кнопку курсор
передвигается на новую позицию фишки и кнопка отпускается (при этом запускается
функция WMLButtonUp() из класса TCheckersWindow). Рассмотрим работу этих двух
функций подробнее (см. примечания в тексте функции):
Функция WMLButtonDown():
void TCheckersWindow:: WMLButtonDown(TMessage&) // =====НАЧИНАЕМ ХОД======
{
POINT Point;
if (WhoseTurn == Black) // =====ПРОВЕРЯЕМ, ДЕЙСТВИТЕЛЬНО ЛИ ХОДИТ ЧЕЛОВЕК=====
return;
SetCapture(HWindow);
GetCursorPos(&Point);
ScreenToClient(HWindow, &Point);
MoveStartPoint = bd->GetValidSquare(Point, WhoseTurn);
if (MoveStartPoint. x)
{
MovingPieceType = bd->GetPieceType(MoveStartPoint);
HDC hDC = GetDC(HWindow);
bd->ClearSquare(hDC, MoveStartPoint);
HoldingPiece = TRUE;
ReleaseDC(HWindow, hDC);
}
}
Функция WMLButtonUp():
void TCheckersWindow:: WMLButtonUp(TMessage&)
{
POINT Point;
ReleaseCapture();
if (! HoldingPiece || WhoseTurn == Black)
return;
GetCursorPos(&Point);
ScreenToClient(HWindow, &Point);
MoveEndPoint = bd->GetEmptySquare(Point);
HDC hDC = GetDC(HWindow);
if (MoveEndPoint. x && bd->UserMove(MoveStartPoint, MoveEndPoint))
{ // ====ЕСЛИ ЧЕЛОВЕК МОЖЕТ СЮДА ПОСТАВИТЬ ФИШКУ... =====
bd->RedrawBoard(hDC); // =========ТО ПЕРЕРИСОВЫВАЕМ ДОСКУ=======
EnableMenuItem(hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED);
EnableMenuItem(hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);
if (! bd->AnotherJump()) // =====МОЖНО СДЕЛАТЬ ПОВТОРНЫЙ ХОД? ========
{
if (bd->NoMoreBlack()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК КОМПЬЮТЕРА... . ===
{
if (GetApplication() - >ExecDialog(new TEndDialog(this, "UserWonDlg")) // ТО ЧЕЛОВЕК ВЫИГРАЛ!
== IDYES)
{
PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L);
ReleaseDC(HWindow, hDC);
return;
}
else
{
PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L);
ReleaseDC(HWindow, hDC);
return;
}
}
PostMessage(HWindow, WM_COMMAND, CM_MOVE, 0L); // ==ПЕРЕКЛЮЧАЕМСЯ НА ХОД===
} // =======КОМПЬЮТЕРА=======
else // НЕЯВНЫЙ ВЫЗОВ ФУНКЦИИ
; // ComputersMove()
}
else
{
bd->DrawPiece(hDC, MovingPieceType, MoveStartPoint);
}
HoldingPiece = FALSE;
ReleaseDC(HWindow, hDC);
}
Функция ComputersMove():
void TCheckersWindow:: ComputersMove(RTMessage)
{
bd->EndUsersTime();
WhoseTurn = Black;
EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);
ModifyMenu(hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_STOP, "&Stop");
DrawMenuBar(HWindow);
bd->ComputersTurn(); // =======ПЕРЕКЛЮЧАЕМСЯ НА РАБОТУ ИИ========
HDC hDC = GetDC(HWindow);
bd->RedrawBoard(hDC);
ReleaseDC(HWindow, hDC);
WhoseTurn = Red;
POINT CursorPoint;
GetCursorPos(&CursorPoint);
ScreenToClient(HWindow, &CursorPoint);
#pragma warn - stv
if (PtInRect(&MainWndRect, CursorPoint))
/*SetCursor(CursorHand) */;
#pragma warn +stv
ModifyMenu(hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |
MF_STRING, CM_MOVE, "move you");
EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_ENABLED);
EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_ENABLED);
DrawMenuBar(HWindow);
if (bd->NoMoreRed()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК ЧЕЛОВЕКА... . ===
{
if (GetApplication() - >ExecDialog(new TEndDialog(this, "GameWonDlg")) // ===ТО КОМПЬЮТЕР===
== IDYES) // ======ВЫИГРАЛ======
{
PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L);
return;
}
else
{
PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L);
return;
}
}
bd->StartUsersTime(); // ======ХОД ЧЕЛОВЕКА========
}
компоненты искусственного интелекта (ии)
Компоненты ИИ вызываются функцией ComputersTurn() из класса BOARD:BOOL BOARD:: ComputersTurn()
{
int iter, i, val, row = 0, col = 0;
double t;
time_t itime1, itime2;
long lNodes;
int alpha = - MAXINT, beta = MAXINT;
StopSearch = FALSE;
ClearRedoStack();
memcpy(SavedBoard, Board, sizeof(Board));
if(! OnlyOneMove(Black, &row, &col))
{
Nodes = 0;
time(&start_t);
PreEvaluate(); // =======ПОЛИТИКА ИГРЫ (НАПАДАТЬ ИЛИ ОТБИВАТЬСЯ) =====
/* clear out the best-variation table */
for(i = 0; i <= MAXPLY; ++i)
{
BestVar [i] [i]. org. SetRow(0);
BestVar [0] [i]. org. SetRow(0);
}
/* clear out the Killer table */
for(i = 0; i <= MAXPLY; ++i)
{
Killer [i] [0]. org. SetRow(0);
Killer [i] [0]. Value = - 1;
}
for(iter = IterFlag? 1: SearchDepth; iter <= SearchDepth; ++iter)
{
lNodes = Nodes;
time(&itime1);
val = Evaluate(alpha, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
if(val >= beta)
{
val = Evaluate(alpha, MAXINT, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
else
{
if(val <= alpha)
{
val = Evaluate(- MAXINT, beta, Black, row, col, iter, 0);
if (StopSearch)
return FALSE;
}
}
alpha = val - 12;
beta = val + 12;
/* seed the killer table with the best variation */
for(i = 0; BestVar [0] [i]. org. GetRow(); ++i)
{
memcpy(&Killer [i] [0], &BestVar [0] [i], sizeof(MOVE));
Killer [i] [0]. Value = 1;
/* eliminate the other killer move */
Killer [i] [1]. Value = - 1;
Killer [i] [1]. org. SetRow(0);
}
/* clear the rest of the killer table */
do
{
Killer [i] [0]. org. SetRow(0);
Killer [i] [1]. org. SetRow(0);
}
while(i++ < MAXPLY);
time(&itime2);
t = difftime(itime2, itime1);
DisplaySearchStats(iter, val, Nodes - lNodes, t);
}
time(&end_t);
if((t = difftime(end_t, start_t)) ! = 0)
{
sprintf(buf, "%.0f", t);
sprintf(buf, "%ld", Nodes);
ComputerTotalTime += t;
}
else
{
sprintf(buf, "%ld", Nodes);
}
for (i = 0; Man [Board [BestVar [0] [i]. org. GetRow()]
[BestVar [0] [i]. org. GetCol()]. What]. GetSide() == Black; ++i)
{
MakeActualMove(BestVar [0] [i]);
}
}
TimeToStr(buf, ComputerTotalTime);
return(TRUE);
}
Функция PreEvaluate() разрабатывает политику игры:
void BOARD:: PreEvaluate()
{
int i, j, xman, inside;
int tBSizeDiv2 = BoardSize >> 1; // (BoardSize / 2)
/*********************************************************
This code gets a rough idea as to who is ahead in Material.
**********************************************************/
Material [Red] = 0;
Material [Black] = 0;
Man [REDMAN]. SetValue(100);
Man [BLACKMAN]. SetValue(100);
Man [REDKING]. SetValue (140);
Man [BLACKKING]. SetValue(140);
Man [EMPTY]. SetValue(0);
Man [OFFBOARD]. SetValue(0);
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide()] += Man [xman]. GetValue();
}
}
/****************************************************
Now adjust the Material weights based on who is ahead.
This is to encourage the fellow who is winning to exchange pieces
and the fellow who is behind to not exchange pieces.
If Material is dead even then you shouldn't try to force exchanges
just on general principles.
*****************************************************/
if(Material [Red] >= Material [Black])
{
- -Man [REDMAN] ;
--Man [REDKING] ;
}
else
{
- -Man [BLACKMAN] ;
--Man [BLACKKING] ;
}
/****************************************************
Examine each and every square and calculate the bonus values.
*****************************************************/
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
inside = (j > 1 && j < BoardSize) ? 1: 0;
SValue [i] [j] [REDMAN] = Man [REDMAN]. GetValue() + inside;
SValue [i] [j] [REDKING] = Man [REDKING]. GetValue() + inside;
SValue [i] [j] [BLACKMAN] = Man [BLACKMAN]. GetValue() + inside;
SValue [i] [j] [BLACKKING] = Man [BLACKKING]. GetValue() + inside;
/* bonus points for central squares */
if(abs(tBSizeDiv2 - i) < 2 && abs(tBSizeDiv2 - j) < 3)
{
++SValue [i] [j] [REDMAN] ;
++SValue [i] [j] [REDKING] ;
++SValue [i] [j] [BLACKMAN] ;
++SValue [i] [j] [BLACKKING] ;
}
/* bonus for non-Crown piece advancement */
if(i > 2)
{
SValue [i] [j] [REDMAN] += i - 2;
}
if(i < BoardSize - 2)
{
SValue [i] [j] [BLACKMAN] += BoardSize - i - 1;
}
if(i == 1)
++SValue [i] [j] [REDMAN] ;
if(i == BoardSize)
++SValue [i] [j] [BLACKMAN] ;
}
}
Material [Red] = 0;
Material [Black] = 0;
for(i = 1; i <= BoardSize; ++i)
{
for(j = 1; j <= BoardSize; ++j)
{
xman = Board [i] [j]. What;
Material [Man [xman]. GetSide()] += SValue [i] [j] [xman] ;
}
}
}
Функция Evaluate() представляет непосредственно функцию ИИ. Основной принцип -
на глубину depth анадблжлизируются возможные ходы компьютера и ответные ходы человека - ищем наилучшую стратегию:
int BOARD:: Evaluate(int alpha, int beta, SIDE player, int row, int col, int limit, int ply)
{
MOVE *list = new MOVE [MAXMOVES] ;
MOVE *mptr, *endptr;
int NumMoves, val;
int num_back = 0;
int retval = 0;
int t1 = WIN - 2 - ply;
int plyp1 = ply + 1;
if (StopSearch)
goto END_EVALUATE;
++Nodes;
if((NumMoves = Lmg(list, player, row, col, ply)) == 0)
{
retval = LOSS + ply;
goto END_EVALUATE;
}
MessageScan();
if (StopSearch)
{
retval = 0;
goto END_EVALUATE;
}
if(list->Quiescent(limit, NumMoves, ply))
{
retval = (Material [player] - Material [OPLAYER] + (NumMoves > 3? 1: 0));
goto END_EVALUATE;
}
for(mptr = list, endptr = mptr + NumMoves; mptr < endptr && alpha < t1; mptr++)
{
MakeMove(*mptr);
if(mptr->Capture! = EMPTY)
{
if(! (mptr->Crown) && CanJump(player, mptr->dest. GetRow(), mptr->dest. GetCol()))
{
val = Evaluate(alpha, beta, player, mptr->dest. GetRow(), mptr->dest. GetCol(), limit, plyp1);
}
else
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
}
else
{
if(limit == 0 || NumMoves == 1)
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1;
}
else
{
val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit? limit - 1: 0, plyp1) * - 1;
}
}
UnMakeMove(*mptr);
if(val > alpha)
{
if(val >= beta)
{
if(KillerFlag)
UpdateKillerTable(*mptr, ply);
retval = beta;
goto END_EVALUATE;
}
else
{
alpha = val;
++num_back;
UpdateBestVariation(mptr, ply);
}
}
BestVar [plyp1] [plyp1]. org. SetRow(0);
}
retval = alpha;
END_EVALUATE:
delete list;
return retval;
}
Вспомагательная функция GenMoves() генерурует возможные ходы и
записывает их в список:
/********************************************
generates the list of moves for a given player at a row, col
returns the number of legal moves found
********************************************/
int BOARD:: GenMoves(MOVE *list, int row, int col)
{
int NumMoves;
int what;
int trow1 = row + 1, tcol1 = col + 1, trowm1 = row - 1, tcolm1 = col - 1;
NumMoves = 0;
what = Board [row] [col]. What;
if(what == REDKING || what == BLACKKING || what == BLACKMAN)
{
if(Board [trowm1] [tcolm1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trowm1);
list->dest. SetCol(tcolm1);
list->Capture = EMPTY;
list->Crown = ((row == 2) && (what == BLACKMAN));
++NumMoves;
++list;
}
if(Board [trowm1] [tcol1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trowm1);
list->dest. SetCol(tcol1);
list->Capture = EMPTY;
list->Crown = ((row == 2) && (what == BLACKMAN));
++NumMoves;
++list;
}
}
if(what == REDKING || what == BLACKKING || what == REDMAN)
{
if(Board [trow1] [tcolm1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trow1);
list->dest. SetCol(tcolm1);
list->Capture = EMPTY;
list->Crown = ((row == BoardSize - 1) && (what == REDMAN));
++NumMoves;
++list;
}
if(Board [trow1] [tcol1]. What == EMPTY)
{
list->org. SetRow(row);
list->org. SetCol(col);
list->dest. SetRow(trow1);
list->dest. SetCol(tcol1);
list->Capture = EMPTY;
list->Crown = ((row == BoardSize - 1) && (what == REDMAN));
++NumMoves;
++list;
}
}
return(NumMoves);
}
Описание работы программы
Игра запускается файлом CHECKERS. EXE. Вследствии того, что программа компилировалась в пакете BORLAND C++ 3.1. для WINDOWS, для запуска программы необходимы следующие DLL – файлы:BC30RTL. DLL
OWL31. DLL
TCLASS31. DLL
В текстовом файле DEPTH хранится единственная настройка игры – глубина анализа ходов, по умолчанию она установлена в 3 – средний уровень игры в шашки.
Меню игры предельно простое и состоит из единственного пункта – “move you” – пропуск хода.
Ниже приведено две экранные копии программы.
 |
 |
Начало игры
Выводы
В ходе курсовой работы были исследованы источники по задачам искусственного интеллекта (ИИ), рассмотрены уже существующие программы для шашечных игр.Была разработана относительно несложная функция ИИ, главными задачами которой является предсказание на установленную глубину своих ходов и ходов противника. Это предсказание базируется на выборе наилучших ходов с обеих сторон. На финальном этапе функция ИИ избирает наиболее выгодную для компьютера цепочку ходов.
Программа отличается от существующих на рынке простотой интерфейса и настроек.
Литература
1. http: // newasp. omskreg. ru/intellect2. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си. Мн., 1992. 240 С.
3. Нейбауэр А. Моя первая программа на С/С++.П., 1995. 368 С.
4. Бруно Бабэ. Просто и ясно о Borland C++.М., 1996. 400 С.
5. Шамас Н.К. Основы С++ и обьектно-ориентированного программирования. К., 1996. 448 С.
6. Справочник по классам Borland C++ 4.0.К., 1994.256 С.
7. ObjectWindows для C++. К., 1993., 208 С.
8. Том Сван. Программирование для Windows в Borland C++. М., 480 С.
9. Н. Барканати. Программирование игр для Windows на Borland C++. М., 1994. 512 С.
