Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Ведение игр Печать

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

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

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

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

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

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

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

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

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

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

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