В какой-то из email рассылок с edX мне на глаза попался курс по искусственному интеллекту от ColumbiaX. Тема для меня интересная и я решил ввязаться.
Сейчас я уже прошел 4-е недели этого курса и, мне кажется, настало время поделиться впечатлениями. Курс оказался очень интересным! Примерно такой же, как Machine Learning от Andrew Ng на Coursera, а может даже и лучше.
Первая неделя курса вводная: рассказывается о современном понимании самого термина искусственный интеллект и какие школы сейчас есть этой области. Сам курс сфокусирован лишь на одном из направлений - называемым Рациональные Агенты. По простому "Рациональные Агенты" - нацелены на нахождение правильного решения. Уже на этом заявлении можно было понять, что никакой философии и прочих заморочек и паранойи о том, что машины захватят мир тут не будет. И еще стало понятно, что алгоритмов будет много и задачи будут решаться самые разные.
С первой теоретической неделей я справился на отлично, хотя курс и потребовал от меня намного больше времени, чем я рассчитывал изначально. На данный момент он у меня занимает больше восьми часов в неделю - для заочных курсов, что я посещал, это редкость. Но и я к изучению в этот раз подошел довольно основательно - пишу конспекты, пересматриваю видео по несколько раз, если нужно. Пытаюсь в каждой теме разобраться по максимуму и выжать из лекционного материала все, что там есть. Да и не стесняюсь поставить на паузу лектора и погуглить тот или иной вопрос, если для меня он не понятен.
На второй неделе началась веселуха. На будущие две недели нам анонсировали раздел поисковых алгоритмов (Search Algorithms). Непосредственно неделя 2 была посвящена группе алгоритмов объединенных в группу Uniformed Search (можно погуглить по сокращениям BFS, DFS, DLS, IDS, UCS).
Пару слов о том, что такое Uniformed Search. Большая часть рассматриваемых в курсе алгоритмов ищут решение в дереве возможных состояний, где вершина дерева - это изначальное состояние системы из которого мы ищем путь, а его потомки (ветви дерева) - это состояния в которые мы можем перейти из этой вершины. Эти ветви в свою продолжают деление по такой же логике.
Почему штука, которая если и тянет в лучшем случае на перевернутое дерево называется просто деревом - я вам могу ответить лишь то, что иногда мы упоротые - да.
Все Uniformed Search работают с деревом возможных состояний (state), примерно таким как на картинке выше. Только вместо цифр там может быть, что угодно. Например - положение всех фигур шахматной доски или точка на карте. Да и вообще, что угодно.
Идея Uniformed Search алгоритмов заключается в том, что алгоритм не делает никаких предположений о элементах которые он ищет и принимает в учет только параметры пути которые ведут к этому решению. Например, один из самых простых алгоритмов - это Breadth First Search (BFS). Суть алгоритма заключается в том, что он проходит в поиске каждое состояние по порядку, слой за слоем.
Я еще буду называть состояния нодами дерева (от англ. node).
Для наглядности - гифка.
Алгоритм не идет глубже, пока не переберет все ноды на текущем уровне, а на следующем уровне начинает слева и проходит все возможные ноды снова, и так до тех пор, пока не найдет то состояние, которое требуется.
Другие алгоритмы просто предлагают иные способы обхода этого дерева. Более эффективные или менее ресурсоемкие. Иногда подключаются дополнительные параметры, например сколько ресурсов расходуется на путь к каждой ветке и т.д.
Звучит совсем не интересно? Вот и я до курса не понимал всей крутости происходящего.
Вообще, именно это и цепляет в этом курсе. Здесь рассказывают не просто теорию, а и то куда и как знания применить.
На 2-й же неделе в практическое задание было дано написать, используя полученные знания, поиск решения игры пятнашки. Причем не просто решить, а решить четырьмя разными алгоритмами!
Пришлось погрузиться в программирование. Причем в программирование на python. Мне, как ниразу не писавшему на python, это стало определенным вызовом. Параллельно разбираясь в новом языке программирования и новых же концепция для себя - я взялся писать решение. Черт побери, это очень интересно! А самое главное - на практическом примере видна разница между всеми этими алгоритмами, что позволяет в 100 раз лучше запомнить их.
Нужно оговориться, это практическое задание было сразу на следующие две недели (неделя 2 и 3), потому, что два из четырех алгоритмов еще не были освящены в лекциях (это были алгоритмы Informed Search).
Нормально не понимая, как решить практическое задание, я начал смотреть лекции третьей недели посвященные Informed Search. В противопоставление uninformed search, informed search выбирает пути решения в дереве основываясь на каком-то предположении о перспективности того, или иного пути.
Как алгоритм может оценить перспективность? Для этого нам на помощь приходят так называемые эвристические функции. Основная идея в том, что имея состояние мы можем оценить насколько это состояние близко к решению. Пусть не идеально, но можем ведь!
На примере тех же пятнашек, эвристической функцией может быть просто количество ячеек уже стоящих на своих местах. Просто? Да, но главное, что такие вот функции позволяют прежде всего идти по тем веткам дерева, которые наиболее близки к решению, а если уже они в какой-то момент оказываются не такими уж и привлекательными - перейти к исследованию других. Круто? Наверное звучит не очень, но на практике - очень даже интересно наблюдать, как алгоритм перебирает варианты уже не просто по порядку, а с какой-то собственной логикой.
Подробно были рассмотрены такие алгоритмы как A* (A-star) и Greedy Search. Не буду вдаваться в подробности каждого из них, но для привлечения внимания гифку с демонстрацией работы A* я вам тут оставлю.
Чертовски приятно осознавать, что теперь эта гифка для меня не просто красивая анимация, а вполне понятное напоминание о работе алгоритма.
Помимо Informed Search, на этой неделе еще делается поверхностный обзор Local Search и генетических алгоритмов (Genetic Algorithm). Наконец таки я перестал бояться этих слов и понял, что не так там все и сложно на самом деле. Жаль только не было практических заданий и мои знания так и остались довольно поверхностными. Все равно - не пропадут, я уверен.
Темой недели номер 4 стали Adversarial Search and Games (состязательный поиск и игры). Вот тут я уже не на шутку заинтересовался.
Сразу глянув, что за проект придется решать я понял - это будет новый рубеж для меня. Предлагалось написать бота для игры 2048 (кто не знает что это - гуглите) и написать не просто бота, а такого который будет выигрывать (набирать заветное 2048) в 50% случаев. Не слабо. Я набирал этот результат считанное число раз.
Мало того, на каждый ход отводится не больше 100мс - за секунду нужно делать 10 ходов! Сделать это с информацией из лекций предыдущих недель не выходило. Ну, что же - я сел за лекции недели 4-е.
Идея Adversarial Search в лекциях была раскрыта через minimax алгоритм, а также рассмотрены несколько его модификаций. Идея minimax снова сводиться к поиску оптимального решения в дереве состояний. Только в этот раз каждый "слой" дерева представляет все возможные состояния игры после каждого хода: вашего или оппонента. Собственно алгоритм и занимается построением этого дерева и поиском решения, способного максимизировать результат.
При этом на каждом слое (ходе в игре) решение принимается исходя из выгоды того, кто ходит. В шахматах, например, один будет пытаться сохранить максимальное число своих фигур, а второй - наоборот сократить их. Делается предположение, что противник будет играть рационально базируясь на такой же как и оппонент оценке ситуации в игра.
В общем объяснить это в одном абзаце я пока не могу - не настолько я хорошо владею темой еще.
Модификации этого алгоритма в основном призваны уменьшить глубину поиска по дереву или обрубить неперспективные ветви. Например - можно ввести эвристическую функцию которая позволит выразить состояние доски в каком-то цифровом выражении и останавливать поиск на определенном уровне, а не идти до самого низа дерева, пока игра не закончиться. Все это нужно, так как дойти до какой-либо серьезной глубины в дереве возможных решений практически невозможно - просто заканчивается память в компьютере или каждый ход будет занимать слишком долго.
Другой вид модификаций minimax вводит понятие вероятности в игру. Вероятности могут пригодиться, если в игре, которую мы будем решать через этот алгоритм, есть различные случайные события, например бросок игральной кости.
Я когда слушал лекции, даже близко не мог представить как это все применить. Но тем и ценен курс - начав выполнять задание, во всем разобрался.
Конкретно в случае 2048 бота появление случайного числа на поле - было действиями оппонента, а сдвиг в любую из возможных сторон - ходом игрока. Для меня в начале показалось сомнительным такое решение, но реализовав алгоритм я могу подтвердить - оно работает.
Особенно интересной частью в задании стала разработка той самой эвристической функции. Это было нечто! В начале мой бот стабильно играл хуже, чем его случайный выбирающий направление брат, написанный мною в самом начале для проверки работоспособности моего алгоритма вообще.
Много вечеров я провел переписывая эту функцию и бесконечно запуская игру. Нужно сказать, когда мой бот все еще был хуже случайных чисел, но уже начал делать какие-то кажущиеся осознанными движения - я ликовал. Ну, а наблюдать как по мере добавления или изменения строчек кода ваш бот умнеет и умнеет - это вообще способно вызвать интеллектуальный оргазм.
Когда бот набрал в первый раз 1024 - я был на седьмом небе. Правда, это как уменьшенная копия радости, когда твой ребенок делает первый шаги.
После долгого копания в разных частях алгоритма моя версия смогла набирать 2048 чаще чем в раз из четырех.
Отправив её на проверку я получил 0 из возможных 200 баллов. Оказалось, что их сервера куда медленнее моего ноутбука и я вышел за предел 100мс. Я начал ломать голову снова. Предстояло обойти и это. Хотя мой алгоритм и так использовал максимально облегченную версию minimax. Честно, в оптимизации я не силен, но пара идей у меня появилась. Потом еще попросил коллегу с работы прогнать алгоритм профайлером, чтобы найти самые узкие места - еще пара минимальных изменений и алгоритм стал работать раз в 5 быстрее оригинального - а значит достаточно чтобы попробовать еще раз.
Я получил 188.89 / 200 - вот этого уже вполне хватает для перехода на следующую неделю!
На повестке дня у меня machine learning, а я пожалуй закончу этот пост, он и так оказался слишком длинным. Хорошо, что меня никто не читает :)