Программирование игр и головоломок

МИНОБРНАУКИ  РОССИИ

ОГУ 

 

Орский гуманитарно-технологический институт (филиал)

федерального государственного

бюджетного образовательного учреждения

высшего профессионального образования

«Оренбургский государственный университет»

(Орский гуманитарно-технологический институт (филиал) ОГУ)

 

Экономический факультет

 

Кафедра прикладной информатики в экономике

       

                                                                                                        

 

КУРСОВАЯ РАБОТА

по дисциплине: «Интеллектуальные информационные системы»

 

Программирование игр и головоломок

 

 

Орский гуманитарно-технологический институт (филиал) ОГУ 

080801.65.5 014.10 ОО

 

             

             

 

 

Руководитель

д.экон.н, профессор

_________________ М.А. Жук

«___» ____________ 2014 г.

Исполнитель

студент группы 12ПИЭ

_________________ А.И. Петров

«____»_________________2014 г.

 

                                                        

 

 

 

 

 

Орск 2014

 

Аннотация

 

 

Курсовая работа по дисциплине «Интеллектуальные информационные системы» на тему «Программирование игр и головоломок» состоит из двух частей.

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

Во второй главе показана практическая реализация логической игры с выигрышной стратегией средствами языка программирования С++.

Курсовая работа содержит 35 страниц, 4 рисунка, 8 источников, 1 приложение.

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Издавна люди сталкивались с проблемой принятия решений в тех или иных ситуациях. При этом естественно стремление к таким решениям, которые приводят к наилучшим результатам. Такой выбор принято называть оптимальным.

Говоря о факторах, обуславливающих правильность принятия того или иного решения, следует выделить две основные группы – объективные и субъективные факторы.

К объективным факторам, в первую очередь, относятся:

• исходные данные, использующиеся при принятии решения;
• модели, методы и алгоритмы принятия решений;
• условия, при которых происходит принятие решений, и требования, предъявляемые к принимаемым решениям;
• имеющиеся базы данных, знаний для данной области принятия решений;
• применяемые средства автоматизации принятия решения.

К субъективным факторам следует отнести:

• возраст, пол, общее физическое состояние человека;
• тип характера человека-оператора;
• психоэмоциональное состояние человека в данной ситуации при принятии решения;
• условия работы;

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

 

1. Основы математической теории игр

 

1. Теория игр как раздел теории принятия решений

 

 

Теория игр как раздел математики возникла сравнительно недавно. Она связана с такими концептуальными понятиями как принятие решений, исследование операций, конфликт, принцип оптимальности и т. д. Принятие решений - это достаточно широкое понятие. С точки зрения математического описания под принятием решения понимается выбор из некоторого множества U элемента u. При этом определяется правило выбора u ∈ U и целесообразность выбора.

Математическая теория принятия оптимальных (рациональных, целенаправленных) решений называется теорией исследования операций. Таким образом, задачей теории исследования операций является построение количественных методов анализа процессов принятия решений во всех областях человеческой деятельности. Эта деятельность должна быть, во-первых, целенаправленна, т. е. направлена на достижение определенной цели или целей, и, во-вторых, при предварительном анализе целесообразности должны быть использованы количественные методы, т. е. формализованные (математические) модели.

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

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

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

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

механизме, заинтересовывающем исследователя операций поддерживать именно те цели, которые преследует оперирующая сторона.

Рассмотрим простейшую модель исследования операций. Она включает: U — множество значений контролируемых факторов, которые выбираются оперирующей стороной; А - множество значений неконтролируемых факторов α , которые выбираются партнерами по операции или определяются внешней средой ("природой"); функцию g(u,α ), отражающую целенаправленность действий оперирующей стороны (например, стремление к максимизации этой функции водностью описывает интересы оперирующей стороны и, соответственно, исследователя операций).

Примером неконтролируемых факторов, выбираемых целенаправленно партнерами по операции, являются военные действия противника, экономические планы взаимодействующих экономических субъектов и т. п. Если неконтролируемые факторы определяются "природными" условиями, то в этом случае модель исследования операций можно свести к модели взаимодействия с разумным партнером. Действительно, если исследователь операции и оперирующая сторона осторожны, то они считают, что природные факторы "выбираются" природой из условия минимизации целевой функции g.

Конфликтом (конфликтной ситуацией) называется процесс столкновения интересов нескольких участвующих сторон.

Он может быть задан следующими компонентами:

1) перечнем  субъектов, участвующих в конфликте;

2) определением  множеств их выборов;

3) интересами (мотивами), определяющими выбор.

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

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

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

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

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

1) "чисто" математическое, определяемое внутренней  логикой

развития теории игр;

2) прикладное, ориентированное на широкий круг практически

интересных задач.

Возникновение теории игр и термина "игра" связано с попыткой использовать математику в задачах анализа ситуаций, возникающих в азартных играх, анализа конфликтных ситуаций в военном деле, при принятии решений в условиях неопределенности, поиска компромисса в неантагонистических конфликтах и т.д.

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

Сложность практических задач анализа конфликтных ситуаций приводит к необходимости использования современных методов анализа и вычислительной техники. Для решения задач принятия решений оказывается недостаточным ограничиться какой-то одной "универсальной" моделью или даже системой моделей. Необходимо иметь "инструмент" – системный проблемно-ориентированный комплекс, представляющий собой систему (сеть) ЭВМ и математическое обеспечение (система моделей, методов, алгоритмов и программ), ориентированную на решение конкретных классов проблем. Для создания и использования такого мощного инструмента необходимо привлечение коллектива людей различных (далеко не родственных) специальностей: системных аналитиков, специалистов в прикладной области, математиков, программистов и т. д. Фактически построение такого инструмента эквивалентно построению языка общения всех участвующих в работе специалистов и ЛПР.

 

2. Основные понятия и классификация игр

 

Теория игр занимается исследованием математических моделей принятия оптимальных решений в конфликтных ситуациях. Формальное описание принятия решений удобно разбить на две части:

1) математическая  модель конфликтной ситуации  или игра — описание конфликтной ситуации, включающее в себя описание субъектов, принимающих

решения, их возможностей и интересов;

2) принцип  оптимальности - описание правил  рационального поведения игроков.

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