Откуда вообще зародилась концепция машинного обучения?
Что ж, это хороший вопрос. Все началось… когда-то в прошлом… с простых поисковых алгоритмов, которые дают компьютеру возможность принимать наиболее выгодные решения. Целью компьютеров является точка E, и добраться до точки E можно тремя путями. Маршрут A имеет расстояние 6, маршрут B имеет расстояние 2, а маршрут C имеет расстояние 21. Чтобы решить, какой маршрут выбрать, компьютер ищет наиболее выгодный маршрут, в данном случае кратчайший. После поиска компьютер решает выбрать маршрут B.
Лучшим примером могут быть игры и алгоритмы поиска. Чтобы быть более конкретным, игры для 2 игроков с «идеальной информацией», такие как крестики-нолики или шахматы. Что я имею в виду под идеальной информацией? Полная информация означает, что каждый игрок полностью информирован обо всех происходящих событиях, в отличие от неполной информации, когда события игроков происходят одновременно, и игроки не знают, что делает или может сделать друг друга.
Для решения простых задач на основе ИИ с полной информацией (в данном случае крестики-нолики) вводится концепция игровых деревьев. Дерево игр связано с теорией игр и представляет собой ориентированный граф, узлы которого представляют собой позиции/состояния в игре, а его ребра — ходы. Каждый узел (точка) на дереве игры представляет собой различное состояние игры, при этом текущее состояние игры является корневым узлом, а слои дерева представляют ход текущего игрока. Дерево игры представляет состояния доски, но это только первый шаг к решению задачи «Крестики-нолики» или любой другой совершенной информационной задачи. По-прежнему существует проблема того, «как» заставить ИИ использовать игровое дерево и пытаться победить.
Чтобы объяснить «как», я введу еще одно понятие, называемое минимаксным алгоритмом, который представляет собой рекурсивный алгоритм, используемый для принятия решений в теории игр. Он обеспечивает оптимальный ход для текущего игрока, предполагая, что его противник также играет оптимально.
Рис. 1.1 представляет собой пример дерева игры, которое представляет текущее состояние игры в крестики-нолики, близкое к кульминации (конец игры). В минимаксном алгоритме есть максимизатор (Max-будет представлять наш ИИ), его цель — максимизировать свои шансы на победу… что может быть лучше, чем убедиться, что его противник не выиграет, пытаясь победить себя, и у нас есть минимизатор (Мин будет представлять своего противника), его цель — свести к минимуму свои шансы на проигрыш… что может быть лучше, чем попытаться выиграть, убедившись, что ее противник не выиграет.
Первый узел на рис. 1.1 показывает текущее состояние игры, означающее, что настала очередь Макса играть. Прежде чем я продолжу, если бы вы были Максом и пытаетесь максимизировать свои шансы на победу, какую ветку выбрать? Чтобы принять это решение, Макс заглядывает в будущее, создавая дерево игры (рис. 1.1), чтобы увидеть результаты игры во всех доступных позициях. Если побеждает максимизатор, он получает +1 очко, если побеждает минимизатор, он получает -1, а если они равны, никто не получает очко, это называется очками полезности, и они помогают игроку решить, какой узел принесет ему наибольшую пользу.
Узлы помечены на рис. 1.2, чтобы вам было легче ориентироваться. Давайте назначим точки полезности их соответствующим узлам. Давайте посмотрим на последние узлы, также известные как терминальные состояния. Узел 11 заканчивается ничьей, поэтому его очки полезности = 0. Узел 12 заканчивается победой Макса, поэтому его очки полезности = +1. Узел 7 заканчивается победой Мин, поэтому его очки полезности = -1 и так далее и тому подобное. После применения этого ко всем терминальным узлам диаграмма выглядит так (рис. 1.3)
Если Макс сыграет узел 2, чтобы добраться до узла 12 и получить +1, Мин не допустит этого, потому что она пытается минимизировать очки. Таким образом, предполагая, что Мин делает свой оптимальный выбор, она выберет узел 5, чтобы свести к минимуму шансы Макса на победу. Очки полезности для выбора узла 2 будут = 0. Если Макс играет узлом 3, чтобы добраться до узла 13 и получить +1, когда наступит очередь Мин, предполагая, что она выберет свой оптимальный выбор, она выберет узел 7, поэтому очки полезности для выбора узла 3 будет = -1. И если Макс выберет узел 4, а Мин сыграет свой оптимальный выбор, она выберет узел 9, поэтому очки полезности за выбор узла 4 будут = -1. После всех этих расчетов дерево игры теперь выглядит так (рис. 1.4).
Помните, что это игровое дерево с идеальной информацией с точки зрения Макса. Он пытается максимизировать свои очки и получить столько очков, сколько у него есть возможность, поэтому обычно Макс пытается добраться до узла, который ведет к +1 очку. Но, глядя на все его варианты в текущем состоянии игры, узел, который приведет к получению наибольшего количества очков, — это узел 2, у которого точка полезности = 0. Этот результат приведет к ничьей с Мин, поскольку Макс скорее сравняет игру, чем терять. Любой другой ход даст Мин возможность выиграть игру, набрав -1 очко.
Игровое древо жизни похоже, и мы являемся игроками. Чтобы удержаться в игре жизни, подумайте о своем следующем шаге, загляните вперед, чтобы взвесить последствия, следите за своими врагами и сделайте свой оптимальный ход.
