Совместимость. Как контролировать искусственный интеллект (Рассел) - страница 183

Выбор действия на основе прогноза будущего и оценки результатов возможных последовательностей действий — фундаментальная способность интеллектуальных систем. Ваш сотовый телефон делает это всякий раз, как вы спрашиваете у него, в каком направлении двигаться. На рис. 14 приведен типичный пример: как попасть из текущего местоположения, 19-й пирс, в целевое, Койт-Тауэр. Алгоритм должен знать, какие действия ему доступны; в случае навигации по карте, как правило, каждое действие связано с фрагментом дороги, соединяющим два соседних перекрестка. В данном примере у 19-го пирса доступно лишь одно действие: повернуть направо и ехать по Эмбаркадеро до следующего перекрестка. Затем имеется выбор: продолжить движение или резко повернуть налево на Бэттери-стрит. Алгоритм последовательно исследует все эти возможности, пока не находит маршрут. Обычно мы добавляем некоторые указания, исходя из здравого смысла, например предпочтение улиц, ведущих прямо к цели, а не в сторону от нее. Благодаря этим указаниям и еще нескольким хитростям алгоритм очень быстро находит оптимальное решение — обычно за несколько миллисекунд, даже в случае поездки по сложным маршрутам.

Поиск маршрута на карте — очевидный и всем известный пример, но, возможно, недостаточно объективный, поскольку отдельных локаций очень мало. Например, в США имеется лишь около 10 млн перекрестков. Казалось бы, большое число, но это ничто по сравнению с количеством отдельных позиций в пятнашках. Пятнашки — это игра с сеткой 4 × 4, где находятся 15 пронумерованных фишек и пустое место. Перемещая фишки, нужно достичь целевой конфигурации, скажем, расположить их все по порядку номеров. В пятнашках около 10 трлн состояний (в миллион раз больше, чем перекрестков в США!); пазл с 24 клетками допускает около 8 триллионов триллионов состояний. Это пример того, что в математике называется комбинаторной сложностью, — очень быстрого увеличения количества комбинаций с ростом числа «подвижных элементов» задачи. Вернемся к карте США: если компания-грузоперевозчик хочет оптимизировать движение 100 своих грузовиков по территории страны, количество возможных состояний составит 10^>700.

Многие игры отличаются комбинаторной сложностью, в том числе шахматы, шашки, нарды и го. Поскольку правила го просты и изящны (рис. 15), я использую эту игру для примера. Задача сформулирована четко: выиграть, окружив больше территории, чем противник. Возможные действия также понятны: клади камень на свободное пересечение. Как и в случае навигации по карте, очевидный способ принятия решения о действии состоит в том, чтобы представить разные варианты будущего, вытекающие из разных последовательностей действий, и выбрать наилучший. Вы спрашиваете себя: «Если я сделаю это, как может поступить мой противник? Что я сделаю тогда?» Эта мысль продемонстрирована на рис. 16 на примере го размерности 3 × 3. Даже для доски 3 × 3 я могу показать лишь малую часть возможных вариантов будущего, но, надеюсь, мысль ясна. Действительно, этот способ принятия решений кажется проявлением самого обычного здравого смысла.