Многие люди знакомы с проектом.
Сети@дома : мощная инициатива по поиску следов внеземных цивилизаций в океане данных, полученных с неба, с использованием мощности миллионов компьютеров по всему земному шару («матрица»).
Хотя инопланетяне еще не обнаружены, Seti@home весьма успешно демонстрирует потенциал крупномасштабных распределенных вычислений.
Такие проекты, как БОИН распространил аналогичные инициативы на другие области: биологию, медицину и физику.
В минувшие выходные команда из Джошфайр ( Томас , Натан , Майкл И я ) участвовал в 48-часовом соревновании Нокаут узла .
Правила были просты: напишите самую интересную вещь за выходные, использующую серверный JavaScript. JavaScript — старая, но увлекательная технология, которая сейчас возрождается благодаря Повысить продуктивность , серверные движки и кучи новый возможности предложенный HTML5 .
Кроме этого Самый распространенный язык.
Любой компьютер, подключенный к Интернету, может легко выполнить код JavaScript, просто введя адрес в браузере или запустив сценарий из командной строки.
Мы решили использовать повсеместность и высокую производительность Node для создания крупномасштабного проекта распределенных вычислений, к которому могли бы присоединиться люди.
просто посетив веб-страницу .
Поиски инопланетян были быстро сорваны, потому что.
У нас не было под рукой радиолокационной системы.
Поэтому мы начали решать проблему более простым способом: шахматы .
Никто из нас не является хорошим шахматистом, но в Книге рекордов Гиннесса мы нашли упоминание о крупнейший шахматный ИИ , состоящий из 2070 узлов, и решили, что сможем его победить.
Так родился проект шахматы@дома .
Спустя 48 часов прототип все еще имел несколько ошибок, но он был в вполне играбельном состоянии и выглядел вот так: 
Проблемы с распределенным шахматным ИИ
Начав исследование, мы выявили следующие проблемные области: Задерживать .
Мы хотели следовать стандартным турнирным правилам (~90 минут на игру), что привело к требованию рассчитывать ход в среднем за минуту.
Более того, игроки в сети определенно предпочли бы более короткое время отклика, и мы ставим перед собой цель сделать его как можно короче.
Небольшое временное окно для вычислений не позволяет хорошо играть на большинстве существующих распределенных вычислительных инфраструктур, которые в основном оптимизирован для высокой мощности .
Нам нужно было построить новую инфраструктуру, работающую практически в реальном времени.
Вебсокет s предложили себя как часть решения.
Параллелизм .
Оптимизация времени ответа означает отправку небольших объемов обработки на каждый компьютер.
Поэтому нам пришлось придумать, как разбить вычисления кода на тысячи мелких частей.
Не вдаваясь в подробности, минимакс алгоритм, используемый в большинстве шахматных ИИ, основан на обход дерева и по существу последователен в применении альфа-бета отсечка .
Мы рассмотрели различные алгоритмы, подходящие для распараллеливания, учитывая следующее:
- Калькуляторы не должны особенно зависеть от общих переменных, поскольку вебсокеты не работают по принципу клиент-клиент (а отправка данных через сервер мешает масштабированию);
- расчет каждого хода необходимо разбить на тысячи мелких задач.
Поскольку ограничение на кодирование составляет 48 часов, мы решили начать с APHID. Производительность JavaScript .
Самые крутые шахматные ИИ могут проходить до 15 миллионов узлов дерева в секунду (NPS = узлы в секунду), используя новейшее оборудование.
Мы взяли за основу ГарбоЧесс , шахматный ИИ с открытым JavaScript, который достигает производительности 100 тыс.
NPS под Chrome на современном Macbook Pro. Шанс в 150 нас не сильно расстроил, тем более, что за 48 часов мы бы не успели профилировать и оптимизировать код, который мог бы победить любого из нас, пользующегося всего лишь одним компьютером.
Для справки говорят, что Темно-синий пробежал на 200 м NPS, чтобы победить Каспарова, что в целом было теоретически достижимо на нашей цели в 2070 узлов.
Отказоустойчивость / безопасность .
Запуск JavaScript на сторонних компьютерах означает, что его выводам нельзя доверять по двум причинам: доступность (пользователи могут покинуть страницу в любой момент) и надежность (злоумышленники могут подать неверные результаты, и ИИ сделает глупый ход).
Мы решили не учитывать надежность в первом варианте, но доступность оставалась критически важной для обеспечения того, чтобы наш алгоритм завершился вовремя, не пропуская очевидных шагов в дереве решений.
Мы настроили очередь FIFO для вычислительных задач в MangoDB и установили таймаут 5 секунд, чтобы другой компьютер мог забрать задание и обработать его, если не было ответа от первого.
Реализация прототипа за 48 часов
Вот схема нашего прототипа: 
Давайте рассмотрим основные компоненты:
- Днод .
Библиотека Node.js для двусторонних асинхронных удаленных вызовов методов.
Обеспечивает транспорт в стиле сокетов и веб-сокетов (с использованием сокет.io ), чтобы системные процессы могли взаимодействовать друг с другом и с процессами, запущенными в браузерах, используя один и тот же интерфейс.
Мы использовали его почти для всех онлайн-взаимодействий.
- Веб-работники (веб-калькуляторы).
Однопоточная среда JavaScript, которая ограничивает выполнение одним скриптом, чтобы пользовательский интерфейс не зависал.
Веб-воркеры позволяют нам запускать долго выполняющиеся сценарии для решения проблем с интенсивными вычислениями, но без блокировки интерфейса или других сценариев взаимодействия с пользователем.
На стороне сервера мы использовали узел-веб-работник (реализация Web Worker для Node), поэтому у нас был единый интерфейс для общения с ИИ.
- МонгоБД .
МонгоШтаб-квартира был спонсором Node Knockout, и мы решили использовать готовые экземпляры MongoDB для хранения состояний игры и потенциально большого кеша позиций.
- Узел .
Центральное звено архитектуры, Node, обладает как быстрой разработкой (один и тот же код как на сервере, так и на клиенте), так и высокой производительностью (его неблокирующая парадигма ввода-вывода доказала свою конкурентоспособность и скорость).
- Локальный ИИ на сервере.
Очевидно, что это место не масштабируется, но нам все равно приходится выполнять несколько вызовов ИИ на сервере, главным образом потому, что APHID необходимо сначала построить небольшое дерево, чтобы распределить работу между клиентами.
Возможно, в будущем мы удалим его.
Но основной идеей останется использование ИИ на веб-воркерах, как на базе браузера, так и на сервере.
Что впереди Этика для виджетов .
Обычно для использования чужой вычислительной мощности необходимо согласие ее владельца: люди устанавливают программное обеспечение SETI@home или BOINC, открывая тем самым доступ к своему процессору.
JavaScript позволяет использовать чужие процессоры без явного разрешения, как только вы заходите на страницу с виджетом, что не очень хорошо.
Мы решили получить согласие пользователя, но установка виджета на чужие сайты с высокой посещаемостью остается серьезной проблемой на пути к нашей цели в 2070 узлов, и мы сделаем все возможное, чтобы ответить на возражения или недовольство, которые могут возникнуть.
Например, поскольку мы планируем использовать «общедоступные» ресурсы, мы должны сохранять результаты открыть как можно .
Код останется открытым на GitHub. Мы также планируем открыть API для шахматного ИИ.
Улучшения ИИ .
После того, как мы это выясним несколько оставшихся ошибок интерфейса , мы продолжим оптимизировать ИИ в следующих областях:
- Улучшенный параллелизм : Мы планируем перейти с APHID на YBWC, чтобы более гибко распределять задачи между компьютерами.
Это особенно важно из-за низкой производительности JavaScript, которую необходимо компенсировать более крупными масштабами.
- Модульные тесты : Мы уже протестировали пару сотен элементов, но многие из них еще доступны в Интернете, и мы собираемся интегрировать их, например СТС .
- Улучшения алгоритма: в GarboChess уже реализовано отсечение альфа-бета, определение нулевого окна , поиск тихих позиций и несколько других функций, но улучшения функции подсчета очков и некоторые модификации ИИ позволят играть лучше.
Когда ИИ станет достаточно сильным, мы призовем настоящего французского гроссмейстера и представителя Книги Гиннесса, чтобы провести самую захватывающую шахматную партию в истории! Нам нужно будет координировать работу множества людей для одновременного подключения к матрице.
Установка виджета на несколько сайтов с высокой посещаемостью должна помочь.
Мы также хотим, чтобы люди могли смотреть игру на Chess@home, а также участвовать в расчетах.
Если у вас есть идеи, как соединить как можно больше людей, расскажите нам! Мы также ищем талантливых разработчиков JavaScript, которые смогут справиться со всем, что описано выше.
Если вы хотите нам помочь, взгляните на текущий список задач или попробуйте найти новые на шахматы@дома .
Удачи в борьбе с Матрицей! P.S. Мы выиграли Node Knockout в категория «Завершение» .
Для тех, кто не умеет пользоваться Хабром:
- переведено: несвязанный
- автор текста: Сильвен Циммер
- оригинал: Chess@home: создание крупнейшего шахматного искусственного интеллекта в истории
-
5 Основных Правил Типографики
19 Oct, 24 -
Как Сменить Учетную Запись Айклауд?
19 Oct, 24 -
Как Называют Пиратов, Которые Не Пираты?
19 Oct, 24
