Многие знакомы с проектом Seti@home: мощнейшей инициативой по поиску следов внеземных цивилизаций в океане данных, получаемых с неба, с использованием мощностей миллионов компьютеров по всему земному шару («матрицы»).
Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.
На прошлых выходных команда из Joshfire (Томас, Натан, Майкл и я) участвовала в 48-часовом соревновании Node Knockout. Правила были простыми: закодировать наиболее занятную штуку за выходные, которая использует серверный JavaScript.
JavaScript – старая, но увлекательная технология, перерождающаяся сейчас из-за увеличения производительности, серверных движков и кучи новых возможностей, предлагаемых HTML5. К тому же, это самый распространенный язык. Любой компьютер, подключенный к вебу, может запросто выполнять код на JavaScript, достаточно набрать в браузере адрес или запустить скрипт из командной строки.
Мы решили использовать его распространенность и высокую производительность Node для того, чтобы построить проект широкомасштабных распределенных вычислений, к которому люди могли бы присоединиться, просто зайдя на веб-страницу. Поиск инопланетян был быстро вычеркнут, т.к. у нас не оказалось под рукой системы радаров. Потому мы стали решать задачу попроще: Шахматы.
Никто из нас не является хорошим шахматистом, но в книге рекордов Гиннесса мы нашли упоминание о самом большом шахматном ИИ, состоящем из 2070 узлов, и решили, что сможем его побить. Так родился проект Chess@home.
Спустя 48 часов в прототипе было еще несколько багов, но он был во вполне играбельном состоянии и выглядел вот так:
Начав исследование, мы выявили следующие проблемные области:
Задержка. У нас было желание следовать стандартным турнирным правилам (~90 минут на игру), что приводило к требованию рассчитывать ход в среднем за минуту. Более того, игроки в вебе однозначно предпочли бы более короткий отклик, и мы поставили себе цель сделать его как можно короче.
Малое временное окно для расчетов не позволяет хорошо играть на большинстве существующих инфраструктурах распределенных вычислений, которые в основном оптимизированы под большие мощности. Нам нужно было построить новую, практически реального времени, инфраструктуру. Websockets напрашивались как часть решения.
Параллелизм. Оптимизация времени отклика означает, что нужно посылать небольшие объемы для обработки каждому вычислителю. Так что нам нужно было придумать, как разбить расчет кода на тысячи небольших кусочков.
Не вдаваясь в подробности, минимаксный алгоритм, используемый в большинстве шахматных ИИ, основан на обходе дерева, и, по сути своей, последователен при применении альфа-бета отсечения. Мы рассмотрели различные алгоритмы, которые подошли бы для распараллеливания, помня о следующем:
Мы нашли двух потенциальных кандидатов: APHID (простой, используется в ChessBrain.net, является текущим чемпионом рекордов Гиннесса) и вариации YBWC (сложнее, но эффективнее). Имея ограничение в 48 часов на кодирование, мы решили начать с APHID.
Производительность JavaScript. Самые крутые шахматные ИИ могут проходить до 15 миллионов узлов дерева в секунду (NPS=nodes per second), используя самое современное железо. Мы взяли за основу GarboChess, открытый шахматный ИИ на JavaScript, производительность которого 100k NPS под Chrome на современном Macbook Pro. Коэффициент 150 нас особого не расстроил, тем более что за 48 часов мы бы не успели профилировать и оптимизировать код, способный выиграть у любого из нас, используя только один компьютер.
Для справки, говорят что Deep Blue работал со скоростью 200m NPS, чтобы победить Каспарова, что в общем-то было теоретически достижимо на нашей 2070-нодной цели.
Отказоустойчивость / безопасность. Запуск JavaScript на сторонних компьютерах означает то, что его результатам нельзя доверять по двум причинам: доступность (пользователи могут покинуть страницу в любой момент) и достоверность (злоумышленники могут подсунуть неверные результаты, и ИИ сделает дурацкий ход).
Мы решили не заниматься достоверностью в первом варианте, но доступность оставалась критической для того, чтобы наш алгоритм завершался вовремя, не пропустив очевидные ходы в дереве решений. Мы настроили FIFO-очередь для вычислительных задач в MangoDB и установили таймаут в 5 секунд, чтобы другой вычислитель мог забрать задание и обработать его, если от первого не пришло ответа.
Вот схема нашего прототипа:
Разберем основные компоненты:
В этой реализации есть что улучшать, но не забывайте – все делалось за 48 часов. Но запуск ИИ на Web Worker’ах, как браузерных, так и серверных, останется основной идеей.
Этика для виджетов. Обычно, чтобы использовать чужие вычислительные мощности, необходимо согласие их владельца: люди устанавливают ПО SETI@home или BOINC, таким образом допуская их к своему процессору. JavaScript позволяет использовать чужие процессоры без явного разрешения, стоит только зайти на страницу с виджетом, что не очень хорошо.
Мы решили получать согласие пользователей, но установка виджета на чужих сайтах с высокой посещаемостью остается основной нерешенной задачей к нашей 2070-узловой цели, и мы сделаем все возможное, чтобы ответить на возражения или недовольство, которое может возникнуть.
Например, раз уж мы планируем использовать «публичные» ресурсы, мы должны держать результаты настолько открытыми, насколько возможно. Код останется открытым на GitHub. Так же мы планируем открыть API для шахматного ИИ.
Улучшения ИИ. После того, как разберемся несколькими оставшимися интерфейсными багами, мы продолжим оптимизации ИИ в следующих областях:
План на час Х. Когда ИИ станет достаточно сильным, мы позовем настоящего французского гроссмейстера и представителя Гиннесса, чтобы провести самую захватывающую шахматную партию!
Нам потребуется скоординировать множество людей, чтобы они одновременно подключились матрице. Установка виджет на нескольких высоко-посещаемых сайтах должна помочь. Так же мы хотим, чтобы люди имели возможность наблюдать за партией на Chess@home, и тоже участвовали в вычислениях.
Если у вас есть идеи как подключить максимальное количество людей, пожалуйста, расскажите нам! Еще мы ищем талантливых разработчиков на JavaScript, чтобы справиться со всем описанным выше.
Если вы хотите нам помочь, посмотрите на текущий список задач или попробуйте найти новые на Chess@home. Удачи в поединке с Матрицей!
P.S.Мы победили на Node Knockout в категории «Завершенность».
Для тех, кто не умеет пользоваться Хабром:
Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.
На прошлых выходных команда из Joshfire (Томас, Натан, Майкл и я) участвовала в 48-часовом соревновании Node Knockout. Правила были простыми: закодировать наиболее занятную штуку за выходные, которая использует серверный JavaScript.
JavaScript – старая, но увлекательная технология, перерождающаяся сейчас из-за увеличения производительности, серверных движков и кучи новых возможностей, предлагаемых HTML5. К тому же, это самый распространенный язык. Любой компьютер, подключенный к вебу, может запросто выполнять код на JavaScript, достаточно набрать в браузере адрес или запустить скрипт из командной строки.
Мы решили использовать его распространенность и высокую производительность Node для того, чтобы построить проект широкомасштабных распределенных вычислений, к которому люди могли бы присоединиться, просто зайдя на веб-страницу. Поиск инопланетян был быстро вычеркнут, т.к. у нас не оказалось под рукой системы радаров. Потому мы стали решать задачу попроще: Шахматы.
Никто из нас не является хорошим шахматистом, но в книге рекордов Гиннесса мы нашли упоминание о самом большом шахматном ИИ, состоящем из 2070 узлов, и решили, что сможем его побить. Так родился проект Chess@home.
Спустя 48 часов в прототипе было еще несколько багов, но он был во вполне играбельном состоянии и выглядел вот так:
Проблемы распределенного шахматного ИИ
Начав исследование, мы выявили следующие проблемные области:
Задержка. У нас было желание следовать стандартным турнирным правилам (~90 минут на игру), что приводило к требованию рассчитывать ход в среднем за минуту. Более того, игроки в вебе однозначно предпочли бы более короткий отклик, и мы поставили себе цель сделать его как можно короче.
Малое временное окно для расчетов не позволяет хорошо играть на большинстве существующих инфраструктурах распределенных вычислений, которые в основном оптимизированы под большие мощности. Нам нужно было построить новую, практически реального времени, инфраструктуру. Websockets напрашивались как часть решения.
Параллелизм. Оптимизация времени отклика означает, что нужно посылать небольшие объемы для обработки каждому вычислителю. Так что нам нужно было придумать, как разбить расчет кода на тысячи небольших кусочков.
Не вдаваясь в подробности, минимаксный алгоритм, используемый в большинстве шахматных ИИ, основан на обходе дерева, и, по сути своей, последователен при применении альфа-бета отсечения. Мы рассмотрели различные алгоритмы, которые подошли бы для распараллеливания, помня о следующем:
- вычислители не должны особо зависеть от общих переменных т.к. вебсокеты не работают по схеме клиент-клиент (а прогон данных через сервер мешает масштабированию);
- расчет каждого хода должен разбиваться на тысячи небольших задач.
Мы нашли двух потенциальных кандидатов: APHID (простой, используется в ChessBrain.net, является текущим чемпионом рекордов Гиннесса) и вариации YBWC (сложнее, но эффективнее). Имея ограничение в 48 часов на кодирование, мы решили начать с APHID.
Производительность JavaScript. Самые крутые шахматные ИИ могут проходить до 15 миллионов узлов дерева в секунду (NPS=nodes per second), используя самое современное железо. Мы взяли за основу GarboChess, открытый шахматный ИИ на JavaScript, производительность которого 100k NPS под Chrome на современном Macbook Pro. Коэффициент 150 нас особого не расстроил, тем более что за 48 часов мы бы не успели профилировать и оптимизировать код, способный выиграть у любого из нас, используя только один компьютер.
Для справки, говорят что Deep Blue работал со скоростью 200m NPS, чтобы победить Каспарова, что в общем-то было теоретически достижимо на нашей 2070-нодной цели.
Отказоустойчивость / безопасность. Запуск JavaScript на сторонних компьютерах означает то, что его результатам нельзя доверять по двум причинам: доступность (пользователи могут покинуть страницу в любой момент) и достоверность (злоумышленники могут подсунуть неверные результаты, и ИИ сделает дурацкий ход).
Мы решили не заниматься достоверностью в первом варианте, но доступность оставалась критической для того, чтобы наш алгоритм завершался вовремя, не пропустив очевидные ходы в дереве решений. Мы настроили FIFO-очередь для вычислительных задач в MangoDB и установили таймаут в 5 секунд, чтобы другой вычислитель мог забрать задание и обработать его, если от первого не пришло ответа.
Реализация прототипа за 48 часов
Вот схема нашего прототипа:
Разберем основные компоненты:
- dnode. Библиотека Node.js для двухстороннего асинхронного удаленного вызовов методов. Предоставляет транспорт в стиле сокетов и вебсокетов (с помощью socket.io), чтобы системные процессы могли общаться друг с другом и с процессами, работающими в браузерах, используя один и тот же интерфейс. Мы использовали ее практически для всех сетвых взаимодействий.
- Web Workers (веб-вычислители). Однопоточная (single-thread) среда JavaScript, ограничивающая исполнение одним скриптом, чтобы не завис пользовательский интерфейс. Web Worker’ы позволяют нам запускать скрипты с большим временем исполнения для решения требовательных к вычислениям задач, но без блокировки интерфейса или других скриптов пользовательского взаимодействия. Со стороны сервера мы использовали node-webworker (реализация Web Worker’а для Node), так что у нас был единый интерфейс для общения с ИИ.
- MongoDB. MongoHQ являлась спонсором Node Knockout, и мы решили использовать готовые экземпляры MongoDB для хранения состояний игры и потенциально большого кэша позиций.
- Node. Центральное звено архитектуры, Node имеет и быструю разработку (одинаковый код и на сервере, и на клиенте), и высокую производительность (его неблокирующая ввод-вывод парадигма подтвердила свою конкурентно-способность и скорость).
- Локальный ИИ на сервере. Это место явно не масштабируется, но тем не менее нам приходится делать несколько вызовов ИИ на сервере, в основном потому, что APHID нужно построить вначале маленькое дерево, чтобы распределить работу по клиентам. Возможно, в будущем мы его уберем.
В этой реализации есть что улучшать, но не забывайте – все делалось за 48 часов. Но запуск ИИ на Web Worker’ах, как браузерных, так и серверных, останется основной идеей.
Что впереди
Этика для виджетов. Обычно, чтобы использовать чужие вычислительные мощности, необходимо согласие их владельца: люди устанавливают ПО SETI@home или BOINC, таким образом допуская их к своему процессору. JavaScript позволяет использовать чужие процессоры без явного разрешения, стоит только зайти на страницу с виджетом, что не очень хорошо.
Мы решили получать согласие пользователей, но установка виджета на чужих сайтах с высокой посещаемостью остается основной нерешенной задачей к нашей 2070-узловой цели, и мы сделаем все возможное, чтобы ответить на возражения или недовольство, которое может возникнуть.
Например, раз уж мы планируем использовать «публичные» ресурсы, мы должны держать результаты настолько открытыми, насколько возможно. Код останется открытым на GitHub. Так же мы планируем открыть API для шахматного ИИ.
Улучшения ИИ. После того, как разберемся несколькими оставшимися интерфейсными багами, мы продолжим оптимизации ИИ в следующих областях:
- Улучшение параллелизма: мы планируем переключиться с APHID на YBWC, чтобы более гибко распределять задачи между вычислителями. Это особенно важно из-за низкой производительности JavaScript, необходимо компенсировать ее большими масштабами.
- Юнит-тесты: Мы уже провели юнит-тестирование пары сотен позиций, но еще много доступно в сети, и мы собираемся интегрировать их на манер STS.
- Улучшения алгоритма: в GarboChess уже реализовано альфа-бета отсечение, определение нулевого окна, поиск спокойных позиций и несколько других функций, но улучшение функции оценки и некоторые модификации ИИ, позволят ему играть лучше.
План на час Х. Когда ИИ станет достаточно сильным, мы позовем настоящего французского гроссмейстера и представителя Гиннесса, чтобы провести самую захватывающую шахматную партию!
Нам потребуется скоординировать множество людей, чтобы они одновременно подключились матрице. Установка виджет на нескольких высоко-посещаемых сайтах должна помочь. Так же мы хотим, чтобы люди имели возможность наблюдать за партией на Chess@home, и тоже участвовали в вычислениях.
Если у вас есть идеи как подключить максимальное количество людей, пожалуйста, расскажите нам! Еще мы ищем талантливых разработчиков на JavaScript, чтобы справиться со всем описанным выше.
Если вы хотите нам помочь, посмотрите на текущий список задач или попробуйте найти новые на Chess@home. Удачи в поединке с Матрицей!
P.S.Мы победили на Node Knockout в категории «Завершенность».
Для тех, кто не умеет пользоваться Хабром:
- перевел: unconnected
- автор текста: Sylvain Zimmer
- оригинал: Chess@home: Building the largest Chess AI ever
