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

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

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

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

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

Игры заставляли людей напрягать свои интеллектуальные способности (иногда до угрожающей степени) на протяжении всего существования цивилизации. В силу своего абстрактного характера игры являются привлекательным объектом исследований и в области искусственного интеллекта.

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

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

Игры, в отличие от большинства учебных задач, которые рассматривались в статье, интересны тем, что в них очень трудно найти решение. Например, шахматы характеризуются в среднем коэффициентом ветвления, примерно равным 35, а игра часто продолжается до 50 ходов со стороны каждого игрока, поэтому дерево поиска имеет приблизительно 35100 или 10154 узлов (хотя граф поиска включает "всего лишь" около 1040 различных узлов).

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

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

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

Теория игр

В результате изучения данной главы студент должен:

знать

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

уметь

• различать игры в стратегической и развернутой формах, строить "дерево игры"; формулировать игровые модели конкуренции для различных типов рынков;

владеть

• методами определения исходов игры.

Игры: основные понятия и принципы

Первую попытку создать математическую теорию игр предпринял в 1921 г. Э. Борель. Как самостоятельная область науки впервые теория игр была систематизированно изложена в монографии Дж. фон Неймана и О. Моргенштерна "Теория игр и экономическое поведение" в 1944 г. C тех пор многие разделы экономической теории (например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр[1]. Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от "естественной свободы" к "гражданской свободе" формально соответствует с позиций теории игр точке зрения на кооперацию.

Игра – это идеализированная математическая модель коллективного поведения нескольких лиц (игроков), интересы которых различны, что и порождает конфликт. Об этом говорит сайт https://intellect.icu . Конфликт необязательно предполагает наличие антагонистических противоречий сторон, но всегда связан с определенного рода разногласиями. Конфликтная ситуация будет антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину и наоборот. Антагонизм интересов порождает конфликт, а совпадение интересов сводит игру к координации действий (кооперации).

Примерами конфликтной ситуации являются ситуации, складывающиеся во взаимоотношениях покупателя и продавца; в условиях конкуренции различных фирм; в ходе боевых действий и др. Примерами игр являются и обычные игры: шахматы, шашки, карточные, салонные и др. (отсюда и название "теория игр", и ее терминология).

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

Теория игр – это математическая теория конфликтных ситуаций.

Цель теории игр – выработка рекомендаций но разумному поведению участников конфликта (определение оптимальных стратегий поведения игроков).

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

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

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

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

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

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

В настоящее время ведутся научные исследования, направленные на расширение областей применения теории игр.

В литературе встречаются следующие определения элементов, составляющих игру.

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

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

Определение исхода (результата) игры. Для каждой комбинации действий игроков исход игры устанавливается почти механически. Результатом может быть: состав потребительской корзины, вектор выпусков фирмы или набор других количественных показателей.

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

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

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

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

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

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

Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией.

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

Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от того, какие стратегии применяет противник. Могут быть использованы и другие критерии оптимальности.

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

Повторим, что задача теории игр – нахождение оптимальных стратегий.

Классификация игр представлена на рис. 8.1.

• 1. В зависимости от видов ходов игры подразделяются на стратегические и азартные. Азартные игры состоят только из случайных ходов, которыми теория игр не занимается. Если наряду со случайными ходами есть личные ходы или все ходы личные, то такие игры называются стратегическими.
• 2. В зависимости от числа игроков игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной – более двух.
• 3. Участники множественной игры могут образовывать коалиции, как постоянные, так и временные. По характеру взаимоотношений игроков игры делятся на бескоалиционные, коалиционные и кооперативные.

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

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

Рис. 8.1. Классификация игр

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

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

• 4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).
• 5. По количеству информации, имеющейся у игроков относительно прошлых ходов, игры подразделяются на игры с полной информацией (имеется вся информация о предыдущих ходах) и неполной информацией. Примерами игр с полной информацией могут быть шахматы, шашки и т.п.
• 6. По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями.

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

7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой.

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

Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответствует номеру применяемой стратегии первого игрока, столбец – номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).

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

Приведем следующий пример. Игра "Зачет". Пусть игрок 1 – студент, готовящийся к зачету, а игрок 2 – преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: A1 – хорошо подготовиться к зачету; A2 – не подготовиться. У преподавателя имеется тоже две стратегии: B1 – поставить зачет; B2 – не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей:

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

Задача состоит в определении оптимальных стратегий для студента и для преподавателя.

Еще один пример хорошо известной биматричной игры "Дилемма заключенного".

Каждый из двух игроков располагает двумя стратегиями: A2 и B2 – стратегии агрессивного поведения, a Ai и Bi – миролюбивое поведение. Предположим, что "мир" (оба игрока миролюбивы) лучше для обоих игроков, чем "война". Случай, когда один игрок агрессивный, а другой миролюбивый, выгоднее агрессору. Пусть матрицы выигрышей игроков 1 и 2 в данной биматричной игре имеют вид

Для обоих игроков агрессивные стратегии A2 и B2 доминируют мирные стратегии Ах и Bv Таким образом, единственное равновесие в доминирующих стратегиях имеет вид (А2, B2), т.е. постулируется, что результатом некооперативного поведения является война. В то же время исход (A1, B1) (мир) дает больший выигрыш для обоих игроков. Таким образом, некооперативное эгоистическое поведение вступает в противоречие с коллективными интересами. Коллективные интересы диктуют выбор мирных стратегий. В то же время, если игроки не обмениваются информацией, война является наиболее вероятным исходом.

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

Существует две основные формы игры. Игра в экстенсивной форме представляется как диаграмма типа "дерево" принятия решений, при этом "корень" соответствует точке начала игры, а начало каждой новой "ветки", называемое узлом, – состоянию, достигнутому на данном этапе при данных действиях, уже предпринятых игроками. Каждому конечному узлу – каждой точке окончания игры – ставится в соответствие вектор выигрышей, по одной компоненте для каждого игрока.

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

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

На рис. 8.2 представлена экстенсивная форма игры, а в табл. 8.1 – стратегическая форма.

Рис. 8.2. Игра с одновременным принятием решений в экстенсивной форме

Таблица 8.1. Игра с одновременным принятием решений в стратегической форме

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

Некооперативные игры обычно представляются в нормальной (стратегической) и развернутой (экстенсивной) формах.

• [1] Воробьев Η. Н. Теория игр для экоиомистов-кибериетиков. М.: Наука, 1985.
• [2] Вентцель Е. С. Исследование операций. М.: Наука, 1980.

Если я не полностью рассказал про ведение теорию игр? Напиши в комментариях Надеюсь, что теперь ты понял что такое ведение теорию игр и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Математические методы исследования операций .Теория игр и расписаний.