Слово обрезка действительно напоминает вырубку ветвей, а тем, кто знаком с наукой о данных, — пост- и предварительную обрезку деревьев. Альфа-бета-обрезка — это, по сути, удаление бесполезных ветвей. Мы обсудим следующие указатели:
- Алгоритм МинМакс
- Альфа-бета обрезка
В этом блоге мы рассмотрим сокращение альфа-бета и то, как мы можем использовать его для создания стратегий в играх с несколькими путями. Каждый из этих путей приводит к разным результатам. Когда у нас есть такое огромное количество ходов (например, в шахматах или судоку), нам действительно нужно четко определить стратегию игры. Такие игры в конечном итоге развиваются и приводят к странно большому количеству возможных результатов. Поэтому нам нужно подумать о том, как мы можем выбрать наилучший возможный ход. Этого нужно достичь, не тратя столько времени, сколько потребовалось кошкам, чтобы заселить Землю.
Алгоритм Минмакс
Алгоритм минимакса более интуитивно понятен с точки зрения подхода грубой силы. Он пытается увидеть все возможные результаты, а затем пытается оптимизировать имеющиеся варианты.
Как и в случае с судоку, мы можем в конечном итоге создать дерево, состоящее из ветвей, уходящих в глубину, содержащих весь набор всех возможных ходов, сделанных игроком (игроками) в игре. Далее нам нужно пройти через это дерево.
Альфа-бета обрезка
Альфа-бета-обрезка — это уменьшение размера (обрезка) нашего дерева поиска. Хотя подход грубой силы является более простым в использовании, это не обязательно означает, что он является наиболее оптимальным подходом. Во многих случаях не нужно посещать все возможные филиалы, чтобы найти наилучшее возможное решение.
Таким образом, нам нужно предоставить алгоритму минимума-максимума некоторые критерии остановки, с помощью которых он прекратит поиск области дерева, как только найдет гарантированный минимум или максимум на этом уровне. Это предотвратило бы использование алгоритмом дополнительного вычислительного времени, что сделало бы его намного более отзывчивым и быстрым.
Первоначальный алгоритм min-max выполняет обход дерева слева направо, а также достигает максимально возможной глубины дерева. По сути, это подход в глубину. Затем он обнаруживает значения, которые должны быть присвоены узлам непосредственно над ним, даже не глядя на другие ветви дерева.
Таким образом, добавление условия остановки заставляет мин-макс принимать решения, как это было раньше, но оптимизирует аспект производительности алгоритма.
На изображении ниже у нас есть дерево с различными оценками, присвоенными каждому узлу. Некоторые узлы заштрихованы красным, что указывает на то, что их не нужно просматривать.
В левом нижнем углу дерева минимакс проходит через значения 5 и 6 на нижнем максимальном уровне. Он определяет, что 5 должно быть присвоено минимальному уровню прямо над ним.
Но, посмотрев на 7 и 4 правой ветки максимального уровня, он понимает, что указанному выше узлу минимального уровня должно быть присвоено максимальное значение 4. Поскольку второй максимальный уровень прямо над первым минимальным уровнем будет принимать максимум между 5 и самое большее 4, ясно, что он выберет 5. После этого он продолжит обход дерева, чтобы выполнить тот же набор операций в других ветвях дерева.
В заключение мы можем легко понять, как сокращение альфа-бета действует как отличная оптимизация по сравнению с алгоритмом минимума-максимума и как эти алгоритмы являются основой методов поиска в пространстве состояний, прокладывая путь для гораздо более продвинутых подходов к решению таких проблем.
На этом мы подошли к концу этой статьи об альфа-бета-обрезке в искусственном интеллекте.
Если вы хотите прочитать больше статей о самых популярных на рынке технологиях, таких как искусственный интеллект, DevOps, этический взлом, вы можете обратиться к официальному сайту Edureka.
Обратите внимание на другие статьи из этой серии, в которых объясняются различные другие аспекты глубокого обучения.
17. Кью-обучение
Первоначально опубликовано на www.edureka.co 12 сентября 2019 г.
