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

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

Лекция 0 — Поиск

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

Поиск решения головоломки 15 потребует использования алгоритма поиска.

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

▪ Состояние: конфигурация агента в его среде. Например, в головоломке «15» состояние — это любой способ расположения всех чисел на доске.

  • Исходное состояние: состояние, с которого запускается алгоритм поиска. В приложении-навигаторе это будет текущее местоположение.

▪️ Действия: выбор, который можно сделать в состоянии. Точнее, действия можно определить как функцию. Получив на вход состояние s, Actions(s) возвращает на выходе набор действий, которые могут быть выполнены в состоянии s. Например, в головоломке 15 действия данного состояния — это способы, которыми вы можете перемещать квадраты в текущей конфигурации (4, если пустой квадрат находится посередине, 3, если рядом со стороной, 2, если в углу).

▪️ Модель перехода. Описание состояния, которое возникает в результате выполнения любого применимого действия в любом состоянии. Точнее, модель перехода можно определить как функцию. Получив в качестве входных данных состояние s и действие a, Results(s, a) возвращает состояние, полученное в результате выполнения действия a в состоянии s. Например, при определенной конфигурации головоломки 15 (состояние s) перемещение квадрата в любом направлении (действие a) приведет к новой конфигурации головоломки (новое состояние).

▪️ Пространство состояний:набор всех состояний, достижимых из начального состояния любой последовательностью действий. Например, в головоломке 15 пространство состояний состоит из всех 16!/2 конфигураций на доске, которые могут быть достигнуты из любого начального состояния. Пространство состояний можно представить в виде ориентированного графа с состояниями, представленными в виде узлов, и действиями, представленными в виде стрелок между узлами.

▪️ Целевой тест: условие, определяющее, является ли данное состояние целевым состоянием. Например, в приложении-навигаторе цель проверки будет состоять в том, находится ли текущее местоположение агента (представление автомобиля) в пункте назначения. Если да — проблема решена. Если нет — продолжаем поиск.

▪️ Стоимость пути: числовая стоимость, связанная с данным путем. Например, приложение-навигатор не просто приведет вас к цели; он делает это, минимизируя стоимость пути, находя для вас самый быстрый способ добраться до целевого состояния.

Решение проблем с поиском

▪️ Решение.Последовательность действий, которая ведет от начального состояния к целевому состоянию.

  • Оптимальное решение. Решение с наименьшей стоимостью пути среди всех решений.

В процессе поиска данные часто хранятся в узле, структуре данных, которая содержит следующие данные:

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

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

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

Повторить:

  1. Если граница пуста,
    ▪ ️Стоп. У проблемы нет решения.
  2. Удаление узла с границы. Это узел, который будет рассматриваться.
  3. Если узел содержит целевое состояние,
    ▪ ️ верните решение. Стоп.
    В противном случае
* Expand the node (find all the new nodes that could be reached from this node), and add resulting nodes to the frontier. 
* Add the current node to the explored set.

Поиск в глубину

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

Начнем с подхода поиск в глубину (DFS).

Алгоритм поиска в глубину исчерпывает каждое направление, прежде чем пробовать другое направление. В этих случаях граница управляется как структура данных stack. Вам нужно запомнить крылатую фразу: «последний пришел — первый ушел». После того, как узлы добавлены к границе, первый узел, который нужно удалить и рассмотреть, будет добавлен последним. Это приводит к алгоритму поиска, который идет как можно глубже в первом направлении, которое мешает ему, оставляя все остальные направления на потом.

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

▪️ Плюсы:

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

▪️ Минусы:

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

Пример кода:

# Define the function that removes a node from the frontier and returns it.
    def remove(self):
    	  # Terminate the search if the frontier is empty, because this means that there is no solution.
        if self.empty():
            raise Exception("empty frontier")
        else:
        	  # Save the last item in the list (which is the newest node added)
            node = self.frontier[-1]
            # Save all the items on the list besides the last node (i.e. removing the last node)
            self.frontier = self.frontier[:-1]
            return node

Поиск в ширину

Противоположностью поиска в глубину будет поиск в ширину (BFS).

Алгоритм поиска в ширину будет следовать нескольким направлениям одновременно, делая один шаг в каждом возможном направлении, прежде чем делать второй шаг в каждом направлении. В этом случае граница управляется как структура данных queue. Вам нужно запомнить крылатую фразу: «первым пришел — первым вышел». В этом случае все новые узлы складываются в очередь, и узлы рассматриваются в зависимости от того, какой из них был добавлен первым (первый пришел, первый обслужен!). Это приводит к алгоритму поиска, который делает один шаг в каждом возможном направлении, прежде чем сделать второй шаг в любом одном направлении.

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

▪️ Плюсы:

  • Этот алгоритм гарантированно находит оптимальное решение.

▪️ Минусы:

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

Пример кода:

# Define the function that removes a node from the frontier and returns it.
    def remove(self):
    	  # Terminate the search if the frontier is empty, because this means that there is no solution.
        if self.empty():
            raise Exception("empty frontier")
        else:
            # Save the oldest item on the list (which was the first one to be added)
            node = self.frontier[0]
            # Save all the items on the list besides the first one (i.e. removing the first node)
            self.frontier = self.frontier[1:]
            return node

Жадный поиск по первому наилучшему

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

Жадный поиск с поиском наилучших результатов расширяет узел, ближайший к цели, что определяется эвристической функцией h(n). Как следует из названия, функция оценивает, насколько близко к цели находится следующий узел, но может ошибаться. Эффективность жадного алгоритма поиска лучших первых зависит от качества эвристической функции. Например, в лабиринте алгоритм может использовать эвристическую функцию, которая зависит от манхэттенского расстояния между возможными узлами и концом лабиринта. Манхэттенское расстояние игнорирует стены и подсчитывает, сколько шагов вверх, вниз или в стороны потребуется, чтобы добраться из одного места в целевое. Это простая оценка, которую можно получить на основе координат (x, y) текущего местоположения и целевого местоположения.

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

Поиск A*

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

Опять же, поскольку этот алгоритм тоже опирается на эвристику, он так же хорош, как и эвристика, которую он использует. Возможно, что в некоторых ситуациях он будет менее эффективным, чем жадный поиск по принципу «лучше всего сначала» или даже неинформированные алгоритмы. Чтобы поиск A* был оптимальным, эвристическая функция h(n) должна быть:

  1. Допустимо или никогда не завышать истинную стоимость, и
  2. Непротиворечивый, что означает, что расчетная стоимость пути к цели нового узла в дополнение к стоимости перехода на него с предыдущего узла больше или равна расчетной стоимости пути к цели предыдущего узла. Чтобы выразить это в форме уравнения, h(n) непротиворечив, если для каждого узла n и последующего узла n’ со стоимостью шага c, h(n) ≤ h(n’) + c.

Состязательный поиск

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

Минимакс

Тип алгоритма состязательного поиска, Minimax, представляет условия победы как (-1) для одной стороны и (+1) для другой стороны. Дальнейшие действия будут определяться этими условиями: минимизирующая сторона пытается получить наименьший балл, а максимизирующая сторона пытается получить наивысший балл.

Представление ИИ в крестиках-ноликах:

  • S₀: исходное состояние (в нашем случае пустая доска 3X3).
  • Игроки: функция, которая по заданному состоянию s возвращает ход игрока (X или O).
  • Действия: функция, которая при заданном состоянии s возвращает все допустимые ходы в этом состоянии (какие места на доске свободны).
  • Результат(ы, а): функция, которая при наличии состояния s и действия a возвращает новое состояние. Это доска, полученная в результате выполнения действия a над состоянием s (совершения хода в игре).
  • Терминал(ы): функция, которая по заданному состоянию s проверяет, является ли это последним шагом в игре, т. е. выиграл ли кто-то или есть ничья. Возвращает True, если игра закончилась, и False в противном случае.
  • Полезность: функция, которая при заданном терминальном состоянии s возвращает значение полезности состояния: -1, 0 или 1.

Как работает алгоритм:

Рекурсивно алгоритм моделирует все возможные игры, которые могут иметь место, начиная с текущего состояния и до достижения конечного состояния. Каждое конечное состояние оценивается как (-1), 0 или (+1).

Минимаксный алгоритм в крестиках-ноликах

Зная на основе состояния, чей сейчас ход, алгоритм может определить, выберет ли текущий игрок при оптимальной игре действие, которое приведет к состоянию с более низким или более высоким значением. Таким образом, чередуя минимизацию и максимизацию, алгоритм создает значения для состояния, которое будет результатом каждого возможного действия. Чтобы привести более конкретный пример, мы можем представить, что максимизирующий игрок спрашивает на каждом ходу: «Если я предприму это действие, результатом станет новое состояние. Если минимизирующий игрок играет оптимально, какое действие может предпринять этот игрок, чтобы довести значение до наименьшего?» Однако, чтобы ответить на этот вопрос, максимизирующий игрок должен спросить: «Чтобы знать, что будет делать минимизирующий игрок, мне нужно смоделировать тот же процесс в уме минимизирующего: минимизирующий игрок попытается спросить: «Если я предприму это действие, какое действие может предпринять максимизирующий игрок, чтобы довести до наибольшего значения?» просмотр псевдокода ниже может помочь. В конце концов, посредством этого рекурсивного процесса рассуждений максимизирующий игрок генерирует значения для каждого состояния, которые могут быть результатом всех возможных действий в текущем состоянии. Получив эти значения, максимизирующий игрок выбирает самое высокое.

Максимизатор рассматривает возможные значения будущих состояний.

Если представить это в псевдокоде, то алгоритм Минимакс работает следующим образом:

️▪️ Учитывая состояние s

  • Максимизирующий игрок выбирает действие a в Действиях, которое дает наибольшее значение Min-Value(Result(s, a)).
  • Минимизирующий игрок выбирает действие a в Действиях, которое дает наименьшее значение Max-Value(Result(s, a)).

️▪️ Функция Максимальное значение (состояние):

  • v = -∞
  • если Терминал(состояние):
    вернуть Утилита(состояние)
  • для действие в Действия(состояние):
    v = Max(v, Min-Value(Result(state, action)))
    return v

️▪️ Функция Минимальное значение (состояние):

  • v = ∞
  • если Терминал(состояние):
    вернуть Утилита(состояние)
  • для действие в Действия(состояние):
    v = Min(v, Max-Value(Result(state, action)))
    return v

Альфа-бета обрезка

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

Проще всего это показать на примере: максимизирующий игрок знает, что на следующем шаге минимизирующий игрок попытается набрать наименьшее количество очков. Предположим, что у максимизирующего игрока есть три возможных действия, и первое оценивается в 4. Затем игрок начинает генерировать значение для следующего действия. Для этого игрок генерирует значения действий минимизатора, если это действие совершает текущий игрок, зная, что минимизатор выберет наименьшее. Однако, прежде чем закончить вычисление всех возможных действий минимизатора, игрок видит, что один из вариантов имеет значение три. Это означает, что нет причин продолжать исследовать другие возможные действия сворачивающего игрока. Значение еще не оцененного действия не имеет значения, будь то 10 или (-10). Если значение равно 10, минимизатор выберет наименьший вариант, 3, который уже хуже заранее установленного 4. Если еще не оцененное действие окажется (-10), минимизатор выберет этот вариант, (-10), который еще более неблагоприятен для максимизатора. Следовательно, вычисление дополнительных возможных действий для минимизатора в этот момент не имеет отношения к максимизатору, потому что максимизирующий игрок уже имеет однозначно лучший выбор, значение которого равно 4.

Минимакс с ограничением по глубине

Всего существует 255 168 возможных игр в крестики-нолики и 1⁰²⁹⁰⁰⁰ возможных игр в шахматы. Минимаксный алгоритм, представленный до сих пор, требует генерации всех гипотетических игр от определенной точки до конечного состояния. В то время как вычисление всех игр в крестики-нолики не представляет сложности для современного компьютера, в шахматах это в настоящее время невозможно.

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

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