Интеллектуальные игры. Обучение игровых программ

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

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

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

Рис.1. Дерево возможных продолжений шахматной игры

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

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

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

S = к1а1 + к2а2 + к3а3 +..., (1)

где к1 к2 к3 — весовые коэффициенты; а1 а2 а3 — некоторые признаки силы позиции.

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

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

Другой важной компонентой оценивающей функции (а2) дол­жна быть некая мера подвижности фигур, развитости позиции. Критерием подвижности может быть число допустимых ходов, имеющихся у игрока. Далее идет оценка контроля центра шахмат­ной доски (а3) и т.д.

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

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

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

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

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

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

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

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

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

S = klal + k2a2 + k3a3 + ...,

Полином может быть также и более высокой степени относительно переменных а, например, S = klal + k2a2 + k11a12 + k12 a1a2 + ...,

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

Если S – результат прямой оценки с помощью оценочной функции, a Sb – результат передачи оценки по дереву (с большой глубиной), то можно считать их разность ошибкой е, где e = S - Sb.

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

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

Таким образом, А. Сэмюэлем был создан алгоритм программы, обладающий свойством самообучения (обучение без учителя). Эту программу считают первой в мире действующей самообучающейся программой.

А. Сэмюэль держал в своей программе больший ассортимент критериев (а1, а2 и т.д.), чем тот, что допускался для использования в конкретной оценивающей функции. Используемое множество критериев видоизменялось во время игры: если какое-то из значений весовых множителей ki оставалось близким к нулю в течение длительного времени, то тот компонент оценивающей функции, к которому относился этот коэффициент, изымался из рабочего множества, а на его место ставился другой из числа ожидавших своей очереди. Изъятый критерий добавлялся к множеству ожидавших своей очереди и мог быть впоследствии заново внесен в оценивающую функцию.

Далее А. Сэмюэль предложил организовать работу программы таким образом, что она могла вести игру и самообучаться непрерывно днем и ночью, имитируя одновременно двух игроков (x и y). Таким образом, А. Сэмюель создал программу, которая позволяла не только правильно играть в шашки, но и улучшать стратегию игры, используя опыт, накопленный в предыдущих партиях.


 

Теорема Геделя

Курт Гёдель (1906 – 1978) – немецкий логик и математик.

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

Простейшая формулировка первой теоремы Гёделя о неполноте говорит о том, что существует предложение, не доказуемое и не опровержимое в рамках рассматриваемой теории P.

Гёдель формулирует свою первую теорему в более общей форме, которая говорит о принципиальной непополняемости системы P.

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

Роль первой теоремы Геделя в описании интеллектуальных систем

«Геделевском аргументом» используется как довод против возможности создания искусственного интеллекта. Полагают, что из теоремы К. Геделя о неполноте формальных систем вытекает принципиальное различие между искусственным интеллектом и человеческим умом, а именно, полагают, что теорема Геделя указывает на принципиальное преимущество человеческого ума перед "умом" машинным - т.е. человек обладает способностью решать проблемы, неразрешимые для любых искусственных "интеллектуальных" систем. Теорема Геделя утверждает, что в достаточно "выразительных" формальных языках непременно найдутся истинные, но недоказуемые утверждения - причем этот результат не зависит от конкретного выбора дедуктики. Это означает, что множество "содержательных" истин всегда превосходит по объему множество истин, доказуемых с помощью любой сколь угодно сложной формализованной системы доказательств. Если смысл теоремы Геделя сводится к невозможности формализации содержательного понятия истины, то уже отсюда следует невозможность создания машины способной различать истину и ложь столь же эффективно, как это делает человек. Преимущество человека перед машиной можно усмотреть в том, что человек способен в любых случаях распознавать истинность "геделевских предложений", а машина делать это не способна. Геделевский аргумент против искусственного интеллекта часто формулируют в несколько иной форме - говорят об "алгоритмической невычислимости" функции сознания. Этот тезис означает, что невозможно построить алгоритмическое устройство функционально эквивалентное человеческому мозгу. Впервые данный аргумент был сформулирован Дж. Лукасом в 1961 году. В последнее время подобные идеи активно отстаивает Р. Пенроуз. Идеи Лукаса и Пенроуза вызвали обширную дискуссию, в ходе которой были сформулированы различные возражения против Геделевского аргумента.

Возражения против «Геделевского аргумента»

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

Отсюда следует важный вывод: если окажется, что построить машину, выдерживающую "тест Тьюринга" (Тьюринг задался целью определить, может ли машина мыслить. Стандартная интерпретация этого теста звучит следующим образом: «Человек взаимодействует с одним компьютером и одним человеком. На основании ответов на вопросы он должен определить, с кем он разговаривает: с человеком или компьютерной программой. Задача компьютерной программы — ввести человека в заблуждение, заставив сделать неверный выбор»), невозможно, то эта невозможность будет проистекает не из теоремы Геделя о неполноте, - а будет проистекать из некоторых физических ограничений ("нехватки ресурсов").

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

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