Искуственный интеллект

Описание: Новости науки и техники. Всё то, о чём раньше Вы могли только мечтать. Магия современности.

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#7 dyvniy » Ср, 19 августа 2015, 16:33:38

Выбор компьютера для глубокого обучения.
И программы упоминаются
http://habrahabr.ru/company/it-grad/blog/265167/
Спойлер
уководство по аппаратному обеспечению для глубокого обучения перевод
Машинное обучение*, ИТ-инфраструктура*, Анализ и проектирование систем*, Блог компании ИТ-ГРАД
Примечание переводчика: На Хабре и в нашем блоге о корпоративном IaaS мы много пишем об облачных технологиях, и рассматриваем интересные инфраструктурные проекты различных компаний и исследователей. Мы уже рассказывали о масштабировании Apache Storm в Spotify и создании технологий для стриминга видео, а сегодня представляем вашему вниманию рассказ немецкого математика Тима Деттмерса о том, какое «железо» стоит выбрать для осуществления проектов по глубокому обучению.



Глубокое обучение – это процесс, требующий больших вычислительных мощностей, поэтому вам потребуется быстрый процессор с большим количеством ядер. Или покупать процессор совершенно необязательно? Нет ничего хорошего в том, чтобы тратить деньги на покупку ненужного аппаратного обеспечения при сборке системы глубокого обучения. Сейчас я шаг за шагом хочу провести вас по основным компонентам, которые потребуются для создания дешевой и высокопроизводительной системы.

Работая над распараллеливанием процессов глубокого обучения, я собрал себе кластер из видеокарт, для которого я тщательно выбирал оборудование. Несмотря на проводимое мною исследование и следующие из него умозаключения, я допустил множество ошибок в выборе аппаратных компонентов, которые обнаруживались только после проверки работы кластера на практике. Сейчас я хочу помочь вам избежать ловушек, в которые я попался, и поделиться своим опытом.

Графический процессор (ГП)

Этот пост предполагает, что для глубокого обучения вы будете использовать графический процессор. Создавая подобную систему, очень неблагоразумно обходить его стороной. Графический процессор – это сердце приложений глубокого обучения. Повышение производительности, которое он дает, слишком велико, чтобы его игнорировать.

Я подробно рассказывал о выборе графического процессора в своем предыдущем посте, и, считаю, что вероятно, это самое важное решение, которое вы принимаете при сборе системы глубокого обучения. Обычно, если у вас мало денег, я рекомендую брать GTX 680 на eBay. Если деньги есть, то лучшими графическими процессорами на данный момент будут GTX Titan X (для свертки) или GTX 980 (лучшее решение за свои деньги; имеет ограничения для очень больших сверточных нейронных сетей). GTX Titan с eBay отлично подойдет, если вам нужна дешевая память. Ранее я поддерживал GTX 580, но обновление библиотеки cuDNN значительно увеличило скорость свертки, поэтому все графические процессоры, которые её не поддерживают, потеряли свою актуальность. GTX 580 не поддерживает cuDNN, однако если вы не занимаетесь сверточными сетями, то это по-прежнему достойный выбор.



Подозреваемые

Можете определить «железо», виновное в плохой производительности? Это одна из этих графических карточек? Или во всем виноват центральный процессор?

Центральный процессор (ЦП)

Чтобы выбрать правильный центральный процессор, нам нужно понять, что это такое, и какое он имеет отношение к глубокому обучению. Что делает процессор во время глубокого обучения? Во время работы глубокой нейросети центральный процессор выполняет очень мало вычислений, но по-прежнему производит нижеследующее:

Запись и чтение переменных в коде;
Выполнение инструкций, например, вызов функций;
Инициализацию функциональных вызовов к графическому процессору;
Формирование mini-batch выборки;
Передачу параметров графическому процессору.

Необходимое число ядер процессора

Когда я провожу обучение глубоких нейронных сетей, используя три разные библиотеки, то всегда замечаю, что один поток процессора постоянно загружен на 100% (периодически другие потоки также загружаются на 100%). Это говорит нам о том, что большинство библиотек глубокого обучения (как и большинство приложений) используют всего один поток. Это означает, что многоядерные процессоры бесполезны. Однако они могут вам пригодиться для запуска нескольких программ одновременно, если вы работаете с фреймворками, использующими параллельные вычисления, как, например, MPI. Вам должно хватить одного потока на графический процессор, но два потока на графический процессор повысят производительность при использовании большинства библиотек глубокого обучения; каждая библиотека работает с одним ядром, но, иногда, осуществляет асинхронный вызов функций, для чего задействуется второй поток. Помните, что многие процессоры могут обрабатывать несколько потоков на одном ядре (в особенности процессоры Intel), поэтому одного ядра на графический процессор часто бывает достаточно.

Центральный процессор и PCI-Express

Это ловушка. Некоторые из новых процессоров Haswell, в отличие от старых, не поддерживают 40 полос PCIe – избегайте этих процессоров, если хотите собрать систему с несколькими графическими процессорами. Если материнская плата имеет поддержку PCIe 3.0, то убедитесь, что процессор также его поддерживает.

Размер кэша центрального процессора

Как мы увидим позднее, размер кэша процессора не играет большой роли при обмене данными между ЦП и ГП, но я включил короткий обзор, дабы убедится, что рассмотрены все возможные проблемные места, и понятен весь процесс.

Люди, покупая процессор, часто не обращают внимания на кэш, но это достаточно важный аспект, сильно влияющий на производительность. Кэш – это небольшой блок памяти, расположенной на кристалле, которая физически располагается очень близко к процессору и используется для быстрого выполнения вычислений и других операций. Процессор часто имеет целую иерархию кэшей: маленькие, но быстрые кэши (L1, L2), и большие, но медленные (L3, L4). Как программист, вы можете представить себе кэш в виде хэш-таблицы, где каждая строка – это пара ключ-значение, и где можно проводить быстрый поиск по ключу. Если ключ найден, то можно прочитать или записать переменную; если ключ не обнаружен (это называется промахом), то ЦП нужно обратиться к оперативной памяти и прочитать значение оттуда – этот процесс происходит гораздо медленнее. Повторяющиеся промахи кэша ведут к серьезному снижению производительности. Эффективные архитектуры и процедуры кэширования часто оказывают серьезное влияние на производительность процессора.

Как процессор выполняет кэширование? Сложный вопрос, но вы должны знать, что в кэше хранятся переменные, инструкции и адреса оперативной памяти, которые используются чаще других.

В глубоком обучении для обработки каждой mini-batch выборки перед её отправкой в графический процессор (память просто перезаписывается) читается один и тот же участок памяти, и ответ на вопрос, сможет ли эта память поместиться в кэш, зависит только от размера mini-batch. При размере выборки, равном 128, мы получаем 0,4 Мб и 1,5 Мб для MNIST и CIFAR соответственно, что поместится в большинство кэшей процессоров. Для ImageNet mini-batch займет более 85 Мб (4 X 128 X 2442 X 3 X 1024-2), что значительно превышает даже самый большой кэш (кэш третьего уровня ограничен несколькими мегабайтами).

Так как наборы данных, обычно, слишком большие, чтобы уместиться в кэше, для каждой новой mini-batch данные приходится читать из памяти – поэтому в любом случае понадобится постоянный доступ к оперативной памяти.

Адреса оперативной памяти хранятся в кэше (процессор может быстро просматривать кэш и находить адреса, точно указывающие на месторасположение данных в оперативной памяти), но только в том случае, если весь набор данных помещается в оперативную память, иначе адреса будут меняться, и никакого ускорения от кэширования мы не получим (можно предотвратить это с помощью заблокированных страниц, но, как мы увидим позднее, нет смысла это делать).

Другие части кода глубокого обучения – обращение к переменным и вызовы функций – будут выполняться быстрее, но обычно это маленькие числа, которые легко помещаются в маленький и быстрый кэш первого уровня практически любого процессора.

Из этого следует, что размер кэша процессора не особо важен, и дальнейший анализ в следующих главах только подтверждает это заключение.

Необходимая частота процессора

Когда люди говорят о быстром процессоре, то первое, о чем они думают – это тактовая частота. 4 ГГц лучше, чем 3,5 ГГц, так ли это? Это верно только в том случае, если сравнивать процессоры с одинаковой архитектурой, например, Ivy Bridge. Тактовая частота не всегда является оптимальной мерой производительности.

В процессе глубокого обучения ЦП практически не производит вычислений: увеличивает пару переменных тут, вычисляет булево выражение там, совершает несколько функциональных вызовов в графический процессор или внутри программы – скорость выполнения этих операций зависит от частоты процессора.

Все выглядит вполне разумно, однако во время запуска программ глубокого обучения центральный процессор загружается на 100%, так в чем здесь проблема? Чтобы понять причину, я провел несколько экспериментов, уменьшив частоту процессора (андерклокинг):



Андерклокинг на базах MNIST и ImageNet: Производительность измерялась за время формирования 200 эпох MNIST или 25 эпох на ImageNet с ядрами различной частоты, где максимальная тактовая частота бралась как основная для каждого ЦП. Для сравнения: апгрейд с GTX 680 до GTX Titan дает прирост производительности около 15%; с GTX Titan до GTX 980 еще 20%; оверклокинг прибавляет еще около 5% производительности любому процессору.

Так почему ЦП используется на 100%, если его тактовая частота практически не оказывает влияния на производительность? Ответом могут послужить промахи кэша: ЦП постоянно занят обращениями к памяти (которая имеет меньшую частоту) и вынужден дожидаться, пока она обработает запрос – это ведет к парадоксально огромным задержкам. Если все так, то андерклокинг частоты процессора не должен сильно повлиять на производительность – что подтверждают результаты, которые вы могли видеть выше.

Центральный процессор также управляет и другими операциями, например, копированием данных в mini-batch и подготовкой данных к передаче в графический процессор, но все это зависит от частоты оперативной памяти, а не от частоты самого процессора. Поэтому давайте перейдем к памяти.

Необходимая частота оперативной памяти

Все взаимодействия, в частности, взаимодействие процессора, с оперативной памятью довольно сложны. Сейчас я попробую упростить. Давайте рассмотрим поподробнее процесс работы с памятью графического и центрального процессоров, чтобы лучше разобраться в ситуации.

Частоты работы ЦП и оперативной памяти связаны. Частота работы процессора определяет максимальную частоту работы оперативной памяти, и обе эти частоты определяют результирующую пропускную способность памяти процессора. Чаще всего пропускную способность определяет только оперативная память, так как она работает медленнее памяти процессора. Вы можете определить пропускную способность следующим образом:

Частота RAM в гигагерцах x каналы памяти CPU x 64 x 8-1

Где 64 означает 64-битную архитектуру. Для моих процессоров и планок оперативной памяти пропускная способность составила 51,2 Гб/сек.

Однако пропускная способность имеет значение только тогда, когда вы копируете большие объемы данных. Тайминги (например, 8-8-8) оперативной памяти обычно оказываются более важными при обработке небольших кусков данных. Они определяют, как долго процессор должен ожидать ответа от памяти. Но, как я уже отмечал выше, практически все данные вашей программы глубокого обучения или будут легко помещаться в кэш процессора, или будут слишком большими и поэтому не получат никакой выгоды от кеширования. В связи с этим, можно сказать, что пропускная способность важнее таймингов.

Какое отношение имеет все это к программам глубокого обучения? Я просто упомянул, что пропускная способность может быть важна, но далее мы увидим, что это не так. Давайте пойдем дальше. Пропускная способность оперативной памяти определяет, насколько быстро может быть переписана и размещена mini-batch, чтобы можно было начать инициализацию передачи данных графическому процессору. Здесь мы снова упираемся в ограничение, так как память ЦП и ГП взаимодействует в режиме прямого доступа к памяти (ПДП). Как было отмечено выше, пропускная способность моих модулей оперативной памяти составляет 51,2 Гб/сек, а скорость обмена в режиме ПДП – всего лишь 12 Гб/сек.

Пропускная способность ПДП связана с обычной пропускной способностью, но сейчас детали не важны, поэтому я просто дам вам ссылку на страницу Википедии, где вы сможете посмотреть пропускную способность модулей оперативной памяти в режиме ПДП (пиковая скорость передачи). Но давайте посмотрим, как он работает.

Прямой доступ к памяти (ПДП)

ЦП может общаться с графическим процессором только с помощью ПДП. На первом этапе в памяти ЦП и ГП резервируется специальный буфер передачи. На втором этапе ЦП записывает запрашиваемые данные в свой ПДП буфер. На третьем этапе этот буфер передается в память ГП – в этот процесс ЦП не вмешивается. Пропускная способность вашей шины PCIe (PCIe 2.0) равна 8 Гб/сек или 15,75 Гб/сек (PCIe 3.0), поэтому из того, что сказано выше, следует, что вы должны выбирать оперативную память с высокой пиковой скоростью передачи данных, так?

Необязательно. Здесь большую роль играет программное обеспечение. Если будете правильно осуществлять передачу, то сможете обойтись более дешевой и медленной памятью. Вот что нужно сделать.

Асинхронное распределение mini-batch

Когда ГП завершил работу с текущей mini-batch, он хочет незамедлительно начать работу над следующим набором данных. Разумеется, сейчас вы можете инициировать ПДП передачу, а затем ждать её завершения, чтобы ГП мог продолжить обрабатывать цифры. Но существует гораздо более эффективный способ: подготовьте следующую mini-batch выборку заранее, чтобы вашему графическому процессору не пришлось ждать. Это можно легко сделать асинхронно и без потерь в производительности.



Код CUDA для асинхронного распределения mini-batch: Первые два вызова выполняются, когда ГП начинает работать с mini-batch; последние два вызова выполняются, когда ГП закончил обработку mini-batch. Передача данных будет завершена задолго до завершения всех операций потока, поэтому задержки перед началом обработки следующей mini-batch не возникнет.

Сверточной сети Алекса Крижевского (Alex Krishevsky) требуется 0,35 секунд, чтобы выполнить полный проход по методу обратного распространения ошибки с mini-batch ImageNet 2012 размером 128. Сможем ли мы предоставить следующую mini-batch выборку за это время?
Если мы примем размер mini-batch равным 128, а размеры данных 244x244x3, то в сумме получим около 0,085 Гб (4 x 128 x 2442 x 3 x 1024-3). С супермедленной памятью мы получим скорость 6,4 Гб/сек или 75 mini-batch в секунду. Так что, если использовать асинхронный метод распределения mini-batch, то даже самая медленная оперативная память подойдет для глубокого обучения. Если вы используете этот способ, то покупка более быстрых модулей оперативной памяти не приведет к увеличению производительности.

Это косвенно указывает на то, что кэш процессора не играет особой роли. Неважно, насколько быстро ваш ЦП может перезаписать данные (в быстром кэше) и подготовить (записать из кэша в память) mini-batch для ПДП передачи, потому что передача закончится задолго до того, как графический процессор затребует новые данные – большой кэш не так важен.

Подведем итоги: частота оперативной памяти не имеет значения. Покупайте то, что дешевле. Но сколько всего вы должны купить?

Размеры оперативной памяти

Вы должны иметь объем оперативной памяти, который был бы не меньше объема памяти графического процессора. Можно работать и с меньшим её количеством, но вам может потребоваться осуществить пошаговую передачу данных. Однако из собственного опыта скажу, что гораздо удобнее работать с большими объемами памяти.

Психология говорит нам, что концентрация – это такая вещь, которая со временем снижается. Оперативная память – это один из нескольких аппаратных модулей, который позволяет вам сохранить вашу концентрацию для более сложных проблем программирования. Вместо того, чтобы тратить кучу времени на борьбу с нехваткой оперативной памяти, вы можете направить эти усилия на другие цели, просто увеличив её количество. Если памяти много, можно избежать массы проблем, сохранить время и увеличить продуктивность, занявшись решением более сложных вопросов. Работая в Kaggle, я понял, что дополнительная оперативная память очень помогает в подготовке наборов оптимальных параметров (feature engineering). Так что если вы часто выполняете первичную обработку, и у вас есть деньги, то дополнительная память – это отличное приобретение.

Жесткий диск/SSD

В некоторых случаях жесткий диск может серьезно снижать производительность. Если у вас большой набор данных, то, скорее всего, вы будете хранить одну его часть на жёстком диске или SSD, другую часть в оперативной памяти и третью часть (две небольшие выборки) в памяти графического процессора. Чтобы ГП постоянно получал данные, нам нужно обеспечить поступление новых mini-batch с такой же частотой, с какой ГП сможет их обрабатывать.

Для этого воспользуемся той же идеей с асинхронным размещением mini-batch. Нам нужно асинхронно читать файлы с группами mini-batch – это очень важно! Если не делать это асинхронно, то производительность упадет на 5-10% и сведет на нет все преимущества, за которые вы так боролись – хорошо настроенное глубокое обучение будет работать быстрее на GTX 680, чем плохо настроенное – на GTX 980.

В случае со сверточной сетью ImageNet Алекса выходит, что нам нужно читать 0,085 Гб (4 x 128 x 2442 x 3 x 1024-3) каждые 0,3 секунды, что равно 290 МБ/сек, если мы сохраняем данные как 32-битные числа с плавающей точкой. Если мы сохранили данные в формате jpeg, то можем сжать их 5-15-кратной сверткой, получив требуемую пропускную способность около 30 МБ/сек. Стандартная скорость жестких дисков составляет 100-150 Мб/сек – этого будет достаточно для данных, сжатых в формате jpeg. Для звуковых файлов можно использовать mp3 или другие методы сжатия, но для наборов данных, представленных в виде 32-битных чисел с плавающей точкой, подобное сжатие невозможно: мы можем уменьшить их объем только на 10-15%. Так что если вы работаете с большим набором 32-битных данных, то вам определенно понадобится SSD, так как жесткие диски со скоростью 100-150 Мб/сек слишком медленные и не будут поспевать за ГП. Если у вас такие наборы данных, то берите SSD, в противном случае можете смело работать с жесткими дисками.

Многие люди покупают SSD просто для удобства: запуск и отклик программ, а также предобработка больших файлов выполняется быстрее, но для глубокого обучения он необходим только в том случае, если размерность входных данных велика, и вы не можете их эффективно сжать.

Если вы покупаете SSD, выбирайте его так, чтобы он вместил наборы данных, с которыми вы работаете, с дополнительными несколькими десятками гигабайт буферного пространства. Хорошей идеей будет подключить жесткий диск, на котором будут храниться неиспользуемые наборы данных.

Блок питания (БП)

Вам нужен БП, способный обеспечить работу всех ваших будущих графических процессоров. Со временем ГП становятся все более энергоэффективными, БП, в отличие от остальных компонентов, не будет меняться довольно долго, поэтому имеет смысл в него вложиться.

Вы можете просчитать необходимое число ватт, сложив мощность ЦП и всех ГП с дополнительными 100-300 ваттами, которые понадобятся для других компонентов и выступят в качестве резерва при скачках напряжения.

Важно проверить, чтобы разъемы питания PCIe вашего БП имели 8-контактный и 6-контактный коннектор на одном кабеле. Как-то я купил БП, который мог запитать 6 PCIe-портов, но мог подавать напряжение или только на 8-контактный, или только на 6-контактный коннекторы. С тем блоком питания я не мог подключить 4 графических процессора.

Также очень важно приобретать БП с высоким КПД, особенно если у вас подключено множество графических процессоров, работающих длительное время.

Система с 4 графическими процессорами, работающими на полной мощности (1000-1500 ватт) и тренирующими сверточную сеть на протяжении двух недель, накрутит 300-500 кВт/ч, что в Германии, стране с достаточно высокой стоимостью электроэнергии (20 евроцентов за кВт/ч), будет стоить вам €60-100 ($66-111). Если такая стоимость получается при 100% КПД, то тренировка подобной сети при КПД равном 80% увеличит стоимость на €18-26 – ой-ёй! При работе с одним графическим процессором увеличение стоимости менее заметно, но тенденция ясна – поэтому стоит потратить чуть больше денег на эффективный БП.

Охлаждение

Охлаждение очень важно и может влиять на производительность в большей степени, чем это делает плохое аппаратное обеспечение. Центральный процессор должен работать нормально со стандартным радиатором, но графическому процессору следует уделить отдельное внимание.

Во время работы алгоритма современные ГП повышают свою частоту и энергопотребление до максимума, но как только температура процессора достигает 80 °C, скорость сбрасывается, чтобы избежать превышения температурного порога. Это гарантирует наилучшую производительность и не дает графическому процессору перегреться.

Однако стандартный план скоростей вращения вентиляторов плохо подходит для программ глубокого обучения, поэтому температурный порог достигается за несколько секунд после старта алгоритма. Это ведет к уменьшению производительности (на несколько процентов), что выливается в потерю 10-25%, если вы используете несколько ГП, поскольку они расположены близко друг от друга и сильно нагреваются.

Так как графические процессоры NVIDIA лучше всех подходят для компьютерных игр, то они оптимизированы под Windows. Вы можете изменить настройки вентилирования всего несколькими кликами, но вот в Linux так не получится, а так как большинство обучающих библиотек написаны для Linux – возникает проблема.

Самый простой и дешевый способ обойти ограничения – это установить прошивку BIOS, имеющую новые, более адекватные настройки вентиляторов, которые сохранят температуру и шумы на приемлемом уровне (Если у вас сервер, то вы можете подкрутить скорость вентиляторов на максимум, но шум будет непереносимый). Вы можете немного «разогнать» частоту ГП на 30-50 МГц – это не повредит системе. Программа для прошивки BIOS написана для Windows, но вы можете использовать wine, чтобы запустить её на операционных системах Linux/Unix.

Другой вариант – это установить в конфигурационном файле сервера Xorg (Ubuntu) опцию «coolbits». Такое решение отлично подойдет для одного ГП, но если у вас их несколько, и не ко всем их них подключен монитор, вам придется его эмулировать, что довольно сложно. Я как-то пытался сделать это, но потом провел долгие утомительные часы с загрузочным диском, восстанавливая графические настройки. Мне так и не удалось корректно настроить карты без мониторов.

Есть другой способ, он более затратный и трудный. Можно использовать водяное охлаждение. Водяное охлаждение практически вдове снизит температуру одного графического процессора даже при максимальной нагрузке, и температурный порог никогда не будет достигнут. Останутся холодными даже несколько ГП, чего не может добиться воздушное охлаждение. Еще одним преимуществом водяного охлаждения является бесшумность, что большой плюс, если несколько ГП работают в помещении с другими людьми. Водяное охлаждение обойдется вам в $100 за каждый графический процессор, плюс, нужно будет добавить сверху около $50. Водяное охлаждение немного сложно в установке, но существует большое количество подробных инструкций и руководств, так что весь процесс займет всего несколько часов. Обслуживание не требует особых усилий и не должно стать проблемой.

По своему опыту скажу, что это – один из самых важных моментов. Я купил большие тауэры для моего кластера глубокого изучения, потому что у них есть дополнительные кулеры в зоне с графическими процессорами, но я понял, что это совершенно излишне: температура упала всего на 2-5 °C, которые не стоят денег, вложенных в огромные корпусы. Очень важно решить вопрос с охлаждением ГП – обновите BIOS, используйте водяное охлаждение или живите с пониженной производительностью – в разных ситуациях, все три решения вполне приемлемы. Просто выберите то, которое подходит именно вам.

Материнская плата и корпус

Материнская плата должна иметь достаточное количество PCIe портов, чтобы на ней можно было закрепить все ГП (обычно ограничиваются 4 ГП, даже если у вас есть больше слотов). Помните, что многие ГП занимают два слота сразу, так что для подключения 4 ГП вам может потребоваться 7 слотов PCIe. PCIe 2.0 подойдет для одного ГП, но PCIe 3.0 обладает лучшими показателями цена/производительность. Для нескольких ГП всегда берите платы с поддержкой PCIe 3.0 – это сыграет вам на руку, когда вы будете проводить мультипроцессорные вычисления, так как PCIe-соединение в этом случае оказывается «узким местом».

Выбор материнской платы – простая задача: выбирайте ту, которая поддерживает нужное вам аппаратное обеспечение.
При выборе корпуса убедитесь, что в него влезут полноразмерные ГП, установленные на материнскую плату. Большинство корпусов позволяют это сделать, но стоит проверить, если вы покупаете небольшой экземпляр. Изучите его размеры и параметры, вы даже можете попробовать найти в Google его изображение с видеокартами внутри.

Мониторы

Сначала я думал, что будет глупо писать про мониторы, но они оказались так важны, что я должен это сделать. Между одним и тремя мониторами – огромная разница.

Три 27-дюймовых монитора – вероятно, лучшее, на что я когда-либо тратил деньги – они многократно увеличивают продуктивность. Я чувствую себя неполноценным, если работаю всего за одним монитором. Не ограничивайте себя в этом. Что хорошего в быстрой системе глубокого обучения, если вы неспособны эффективно ей управлять?



Классическая расстановка мониторов, когда я занимаюсь глубоким обучением: слева – книги, Google, почта, stackoverflow; посередине – код; справа – окна вывода, R, папки, системные мониторы и мониторы графических процессоров, список дел и другие небольшие приложения.

Еще пара слов о сборе ПК

Многих пугает сама мысль о сборке компьютера. Аппаратные компоненты дорогие, и вы боитесь сделать что-то неправильно. Но это просто, так как компоненты, не подходящие друг к другу, нельзя соединить вместе. В руководстве к материнской плате подробно показано, как все подключить, а огромное количество обучающих видео и других источников помогут вам, если у вас нет опыта.

Чтобы разобраться в том, как собирать компьютер, вам достаточно сделать это всего один раз, и это замечательно, так как сборка компьютера станет полезным навыком, который вы сможете применять снова и снова. Нет причин медлить!

Заключение / TL;DR

ГП: GTX 680 или GTX 960 (если нет денег); GTX 980 (лучшая производительность); GTX Titan (если нужна память); GTX 970 (не для сверточных сетей)

ЦП: Два потока на ЦП; поддержка всех 40 полос PCIe и его правильной версии (такой же как для материнской платы); тактовая частота >2ГГц; кэш не имеет значения.

Оперативная память: Используйте асинхронное распределение mini-batch; тактовая частота и тайминги не имеют значения; количество памяти равно количеству графической памяти или больше.

Жесткий диск/SSD: Асинхронно читайте файлы mini-batch выборками и сжимайте звук или изображение; жесткий диск подойдет, только если вы не работаете с большими объемами 32-битных данных с плавающей точкой.

БП: Для подсчета мощности сложите ватты ЦП + ГП + (100-300); для работы с большими сверточными сетями берите БП с высоким КПД; убедитесь, что он имеет достаточное количество PCIe коннекторов (6-контактный + 8-контактный) и достаточную мощность для будущих ГП.

Охлаждение: установите флажок «coolbits» в конфигурационном файле, если используете один ГП; иначе прошейте BIOS для увеличения скорости кулеров – это самое простое и дешевое решение; используйте водяное охлаждение для нескольких ГП и/или когда вам нужно снизить шум (если вы работаете в помещении с другими людьми).

Материнская плата: берите PCIe 3.0 и такое количество слотов, чтобы они уместили все будущие ГП (некоторые ГП занимают два слота, максимум 4 ГП на систему).

Мониторы: если вы хотите улучшить систему и повысить продуктивность, то имеет смысл вместо апгрейда ГП купить дополнительный монитор.
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#8 dyvniy » Ср, 2 сентября 2015, 10:09:39

Изображение
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#9 dyvniy » Чт, 3 сентября 2015, 14:56:49

ИИ для игр
http://habrahabr.ru/company/intel/blog/265679/
Спойлер
Сегодня – первое сентября. А значит, многие читатели хабры начинают прохождение нового уровня одной древней известной игры – той самой, в которой требуется прокачать интеллект, и, в итоге, получить магический артефакт – аттестат или диплом, подтверждающий ваше образование. К этому дню мы сделали реферативный перевод статьи про реализацию искусственного интеллекта (ИИ) для игр – от его проектирования до оптимизации производительности. Надеемся, что она будет полезна как начинающим, так и продвинутым разработчикам игр.

Создание искусственного интеллекта для игр

В традиционных исследованиях в области ИИ целью является создание настоящего интеллекта, хотя и искусственными средствами. В таких проектах, как Kismet Массачусетского технологического института (МТИ) делается попытка создать ИИ, способный к обучению и к социальному взаимодействию, к проявлению эмоций. На момент написания этой статьи в МТИ ведется работа над созданием ИИ, располагающего уровнем способностей маленького ребенка, и результаты этой работы весьма перспективны.

С точки зрения игр подлинный ИИ далеко выходит за рамки требований развлекательного программного проекта. В играх такая мощь не нужна. Игровой ИИ не должен быть наделен чувствами и самосознанием (честно говоря, и очень хорошо, что это именно так!), ему нет необходимости обучаться чему-либо за пределами рамок игрового процесса. Подлинная цель ИИ в играх состоит в имитации разумного поведения и в предоставлении игроку убедительной, правдоподобной задачи.

Принятие решений

Основным принципом, лежащим в основе работы ИИ, является принятие решений. Для выбора при принятии решений система должна влиять на объекты с помощью ИИ. При этом такое воздействие может быть организовано в виде «вещания ИИ» или «обращений объектов».

В системах с «вещанием ИИ» система ИИ обычно изолирована в виде отдельного элемента игровой архитектуры. Такая стратегия зачастую принимает форму отдельного потока или нескольких потоков, в которых ИИ вычисляет наилучшее решение для заданных параметров игры. Когда ИИ принимает решение, оно передается всем участвующим объектам. Такой подход лучше всего работает в стратегиях реального времени, где ИИ анализирует общий ход событий во всей игре.

Системы с «обращениями объектов» лучше подходят для игр с простыми объектами. В таких играх объекты обращаются к системе ИИ каждый раз, когда объект «думает» или обновляет себя. Такой подход отлично подходит для систем с большим количеством объектов, которым не нужно «думать» слишком часто, например в шутерах. Такая система также может воспользоваться преимуществами многопоточной архитектуры, но для нее требуется более сложное планирование (подробные сведения см. в статье Ориона Гранатира Многопоточный ИИ).

Базовое восприятие

Чтобы искусственный интеллект мог принимать осмысленные решения, ему необходимо каким-либо образом воспринимать среду, в которой он находится. В простых системах такое восприятие может ограничиваться простой проверкой положения объекта игрока. В более сложных системах требуется определять основные характеристики и свойства игрового мира, например возможные маршруты для передвижения, наличие естественных укрытий на местности, области конфликтов.
При этом разработчикам необходимо придумывать способ выявления и определения основных свойств игрового мира, важных для системы ИИ. Например, укрытия на местности могут быть заранее определены дизайнерами уровней или заранее вычислены при загрузке или компиляции карты уровня. Некоторые элементы необходимо вычислять на лету, например карты конфликтов и ближайшие угрозы.

Системы на основе правил

Простейшей формой искусственного интеллекта является система на основе правил. Такая система дальше всего стоит от настоящего искусственного интеллекта. Набор заранее заданных алгоритмов определяет поведение игровых объектов. С учетом разнообразия действий конечный результат может быть неявной поведенческой системой, хотя такая система на самом деле вовсе не будет «интеллектуальной».
Классическим игровым приложением, где используется такая система, является Pac-Man. Игрока преследуют четыре привидения. Каждое привидение действует, подчиняясь простому набору правил. Одно привидение всегда поворачивает влево, другое всегда поворачивает вправо, третье поворачивает в произвольном направлении, а четвертое всегда поворачивает в сторону игрока. Если бы на экране привидения появлялись по одному, их поведение было бы очень легко определить и игрок смог бы без труда от них спасаться. Но поскольку появляется сразу группа из четырех привидений, их движения кажутся сложным и скоординированным выслеживанием игрока. На самом же деле только последнее из четырех привидений учитывает расположение игрока.


Наглядное представление набора правил, управляющих привидениями в игре Pac-Man, где стрелки представляют принимаемые «решения»

Из этого примера следует, что правила не обязательно должны быть жестко заданными. Они могут основываться на воспринимаемом состоянии (как у последнего привидения) или на редактируемых параметрах объектов. Такие переменные, как уровень агрессии, уровень смелости, дальность обзора и скорость мышления, позволяют получить более разнообразное поведение объектов даже при использовании систем на основе правил.

В более сложных и разумных системах в качестве основы используются последовательности условных правил. В тактических играх правила управляют выбором используемой тактики. В стратегических играх правила управляют последовательностью строящихся объектов и реакцией на конфликты. Системы на основе правил являются фундаментом ИИ.

Конечные автоматы в качестве ИИ

Конечный автомат (машина с конечным числом состояний) является способом моделирования и реализации объекта, обладающего различными состояниями в течение своей жизни. Каждое «состояние» может представлять физические условия, в которых находится объект, или, например, набор эмоций, выражаемых объектом. Здесь эмоциональные состояния не имеют никакого отношения к эмоциям ИИ, они относятся к заранее заданным поведенческим моделям, вписывающимся в контекст игры.


Схема состояний в типичном конечном автомате, стрелки представляют возможные изменения состояния

Существуют как минимум два простых способа реализации конечного автомата с системой объектов. Первый способ: каждое состояние является переменной, которую можно проверить (зачастую это делается с помощью крупных инструкций переключения). Второй способ: использовать указатели функций (на языке С) или виртуальные функции (С++ и другие объектно-ориентированные языки программирования).

Адаптивный ИИ

Если же в игре требуется большее разнообразие, если у игрока должен быть более сильный и динамичный противник, то ИИ должен обладать способностью развиваться, приспосабливаться и адаптироваться.
Адаптивный ИИ часто используется в боевых и стратегических играх со сложной механикой и огромным количеством разнообразных возможностей в игровом процессе.

Предсказание

Способность точно предугадывать следующий ход противника крайне важна для адаптивной системы. Для выбора следующего действия можно использовать различные методы, например распознавание закономерностей прошлых ходов или случайные догадки.
Одним из простейших способов адаптации является отслеживание решений, принятых ранее, и оценка их успешности. Система ИИ регистрирует выбор, сделанный игроком в прошлом. Все принятые в прошлом решения нужно каким-то образом оценивать (например, в боевых играх в качестве меры успешности можно использовать полученное или утраченное преимущество, потерянное здоровье или преимущество по времени). Можно собирать дополнительные сведения о ситуации, чтобы образовать контекст для решений, например относительный уровень здоровья, прежние действия и положение на уровне (люди играют по-другому, когда им уже некуда отступать).
Можно оценивать историю для определения успешности прежних действий и принятия решения о том, нужно ли изменять тактику. До создания списка прежних действий объект может использовать стандартную тактику или действовать произвольно. Эту систему можно увязать с системами на основе правил и с различными состояниями.

В тактической игре история прошлых боев поможет выбрать наилучшую тактику для использования против команды игрока, например ИИ может играть от обороны, выбрать наступательную тактику, атаковать всеми силами невзирая на потери или же избрать сбалансированный подход. В стратегической игре можно для каждого игрока подбирать оптимальный набор различных боевых единиц в армии. В играх, где ИИ управляет персонажами, поддерживающими игрока, адаптивный ИИ сможет лучше приспособиться к естественному стилю игрока, изучая его действия.

Восприятие и поиск путей

До сих пор речь шла о простейших способах решений, принимаемых интеллектуальными агентами; так в исследованиях в области искусственного интеллекта называются объекты, использующие ИИ. Далее я предоставляю нашему герою (или чудовищу, или игровому объекту любого другого типа) контекст для принятия решений. Интеллектуальные агенты должны выявлять области интереса в игровом мире, а затем думать о том, как туда добраться.

Здесь мы уже достаточно близко подходим к настоящему искусственному интеллекту. Всем интеллектуальным агентам требуется базовая способность восприятия своей среды и какие-либо средства навигации и перемещения в окружающем их мире (реальном или каком-либо ином). Нашим игровым объектам требуется то же самое, хотя подход сильно отличается. Кроме того, по отношению к игровому миру можно жульничать, и вам придется это делать, чтобы все работало быстро и плавно.

Как ИИ воспринимает окружающий мир

Зрение

Если ваш агент собирается принимать достаточно взвешенные решения, ему необходимо знать, что происходит вокруг. В системах ИИ, применяемых в робототехнике, значительный объем исследований посвящен компьютерному зрению: роботы получают способность воспринимать окружающий мир с помощью объемного трехмерного зрения точно так же, как люди. Но для наших целей такой уровень совершенства, разумеется, избыточен.

Виртуальные миры, в которых происходит действие большинства игр, имеют огромное преимущество над реальным миром с точки зрения ИИ и его восприятия. В отличие от реального мира нам известно количество буквально всего, что есть в виртуальном мире: где-то среди ресурсов игры есть список, где перечисляется все, что существует в игре. Можно выполнить поиск по этому списку, указав нужный запрос, и мгновенно получить информацию, которую ваш агент сможет использовать, чтобы принимать более обоснованные решения. При этом можно либо остановиться на первом же объекте, который будет представлять интерес для вашего агента, либо получить список всех объектов в пределах заданной дальности, чтобы агент смог принять оптимальное решение в отношении окружающего мира.

Такой подход неплохо работает для простых игр, но, когда стиль игры усложняется, ваши агенты должны быть более избирательными в отношении того, что они «видят». Если вы не хотите, чтобы агенты вели себя так, будто у них глаза на затылке, можно провести выборку в списке потенциальных объектов, находящихся в пределах радиуса зрения агента. Это можно сделать довольно быстро с помощью несложной математики.
Рассчитайте вектор между агентом и нужным объектом путем вычитания положения цели из положения агента.
Вычислите угол между этим вектором и направлением взгляда агента.
Если абсолютное значение угла превышает заданный угол поля зрения агента, то ваш агент не видит объект.

В более сложных играх нужно учитывать, что игрок или другие объекты могут находиться за каким-либо укрытием. Для таких игр может потребоваться построить бегущие лучи (так называемый метод ray casting), чтобы узнать, не загорожена ли возможная цель чем-либо. Построение бегущих лучей — это математический способ проверить, пересекается ли луч с какими-либо объектами, начиная с одной точки и двигаясь в заданном направлении. Если хотите узнать, как именно это делается на конкретном примере, ознакомьтесь со статьей Одна голова хорошо, а две лучше.

Описанный выше метод позволяет узнать, загораживает ли что-либо центр цели, но этого может быть недостаточно, чтобы скрыть вашего агента. Ведь может быть и так, что центр агента скрыт, но зато его голова удобнейшим (для противника) образом торчит над укрытием. Использование нескольких бегущих лучей, направленных на определенные точки цели, поможет не только определить, можно ли попасть в цель, но и куда именно можно поразить цель.

Слух

Казалось бы, между слухом и зрением не так много разницы. Если вы можете видеть объект, то, безусловно, вы можете его и слышать. Верно, что, если ваш агент заметил объект, агент может активно обнаруживать все действия объекта до тех пор, пока объект не окажется вне поля зрения. Тем не менее если добавить агентам дополнительный уровень слуха, то и зрение будет работать эффективнее. Отслеживание шума, издаваемого объектами, — это важнейший уровень восприятия для любых игр с подкрадыванием.

Как и в случае со зрением, сначала нужно получить список находящихся рядом объектов. Для этого можно снова просто проверить дистанцию, но выборка нужных объектов из этого списка происходит уже совсем иначе.

С каждым действием, которое может выполнить объект, связывается определенный уровень звука. Можно заранее задать уровни звука (для оптимизации игрового баланса) либо рассчитывать их на основе фактической энергии звуковых эффектов, связанных с теми или иными действиями (это позволяет добиться высокого уровня реализма, но вряд ли необходимо). Если производимый звук громче заданного порога, то ваш агент заметит объект, издающий звук.

Если нужно учитывать препятствия, то можно снова сократить список объектов и с помощью бегущих лучей определить, есть ли какие-либо преграды на пути звука. Но лишь немногие материалы полностью звуконепроницаемы, поэтому следует более творчески подойти к сокращению списка.

Базовая функциональность, необходимая для придания вашим агентам зрения и слуха, может использоваться и для имитации других органов чувств. Например, обоняния. (Возможность отслеживания игроков интеллектуальными агентами по запаху существует в современных играх, таких как Call of Duty 4*). Добавление обоняния в игру не вызывает особенных трудностей: достаточно назначить каждому игровому объекту отличительный номер запаха и его интенсивность. Интенсивность запаха определяет два фактора: радиус запаха и силу запаха следа, который остается позади. Активные объекты игроков часто отслеживают свои предыдущие положения по ряду причин. Одной из таких причин может быть использование объектов с запахом. С течением времени сила запаха следа уменьшается, след «остывает». Когда данные агента о запахе изменяются, он должен проверить наличие запаха точно так же, как наличие звука (с учетом радиуса и препятствий). Успешность обоняния вычисляется на основе интенсивности запаха и силы обоняния агента: эти значения сравниваются с объектом и его следом.
Осязание в играх поддерживается изначально, поскольку в любой игре уже есть система автоматической обработки столкновений объектов. Достаточно добиться того, чтобы интеллектуальные агенты реагировали на события столкновений и повреждения.

Способность ощущать окружающий мир — это замечательно, но что именно должны ощущать агенты? Необходимо указывать и идентифицировать доступные для восприятия вещи в настройках агентов. Когда вы распознаете то, что видите, агенты смогут реагировать на это на основе правил, управляющих данным объектом.

Временные объекты

Их иногда называют частицами, спрайтами или спецэффектами. Временные объекты являются визуальными эффектами в игровом мире. Временные объекты схожи с обычными объектами в том, что одна общая структура класса определяет их все. Разница же состоит в том, что временные объекты не думают, не реагируют и не взаимодействуют ни с другими объектами игрового мира, ни друг с другом. Их единственная цель — красиво выглядеть, в течение некоторого времени улучшать детализацию мира, а затем исчезнуть. Временные объекты используются для таких эффектов, как следы от пуль, дым, искры, брызги крови и даже отпечатки подошв на земле.

В силу природы временных объектов для них не требуется значительного объема вычислений и обнаружения столкновений (за исключением очень простых столкновений с окружающим миром). Проблема заключается в том, что некоторые временные объекты предоставляют игроку наглядные подсказки о недавно произошедших событиях. Например, пулевые отверстия и следы обгорания могут указывать, что недавно здесь было сражение; следы в снегу могут привести к потенциальной цели. Почему бы и интеллектуальным агентам не использовать такие подсказки?

Эту задачу можно решить двумя способами. Можно либо расширить систему временных объектов, добавив поддержку бегущих лучей (но при этом будет искажен весь смысл системы временных объектов), либо схитрить: размещать пустой объект недалеко от временных объектов. Этот пустой объект не будет способен думать, с ним не будут связаны никакие графические элементы, но ваши агенты смогут его обнаруживать, а временный объект будет располагать связанной информацией, которую сможет получить ваш агент. Итак, когда вы рисуете на полу временную лужицу крови, можно также разместить там невидимый объект, по которому ваши агенты узнают, что здесь что-то произошло. Что касается отпечатков: этот вопрос уже решается с помощью следа.

Укрытие

Во многих играх со стрельбой было бы здорово, если бы агенты умели прятаться за укрытиями, если они есть поблизости, а не просто стоять под огнем противника на открытом месте. Но эта проблема несколько сложнее всех перечисленных ранее проблем. Каким же образом агенты смогут определять, есть ли рядом какие-нибудь подходящие укрытия?


Художники из Penny Arcade* сатирически описывают проблему ИИ противника и укрытий

Эта проблема на самом деле состоит из двух задач: во-первых, нужно правильно распознать укрытия на основе геометрии окружающего мира; во-вторых, нужно правильно распознать укрытия на основе объектов окружающего мира (как показано в приведенном выше комиксе). Чтобы определить, способно ли укрытие защищать от атак, можно просто один раз сравнить размер граничной рамки агента с размерами возможного укрытия. Затем следует проверить, сможет ли ваш объект поместиться за этим укрытием. Для этого нужно провести лучи от различий в положениях вашего стрелка и укрытия. С помощью этого луча можно определить, свободно ли место, находящееся за укрытием (если смотреть со стороны стрелка), а затем пометить это место как следующую цель перемещения агента.


На этой схеме наш агент определил, что в месте, помеченном зеленой звездочкой, можно будет укрыться в безопасности

Навигация ИИ

До сих пор мы говорили о том, каким образом ИИ принимает решения и как ИИ узнает, что происходит в окружающем мире (чтобы принимать более взвешенные решения). Теперь посмотрим, как ИИ выполняет принятые решения. Приняв решение, интеллектуальному агенту нужно понять, как двигаться из точки А в точку Б. Для этого можно использовать разные подходы, выбрав оптимальный в зависимости от характера игры и от нужного уровня производительности.

Алгоритм, условно называемый Столкнуться и повернуть, является одним из простейших способов формирования маршрута движения объекта. Вот как это работает.
Двигайтесь в направлении цели.
Если столкнетесь со стеной, повернитесь в направлении, при котором вы окажетесь ближе всего к цели. Если ни один из доступных для выбора вариантов не имеет очевидных преимуществ, выбор делается произвольным образом.

Такой подход неплохо работает для несложных игр. Пожалуй, я не смогу даже сосчитать, в каком огромном количестве игр чудовища применяют этот алгоритм, чтобы выслеживать игрока. Но при использовании алгоритма «Столкнуться и повернуть» объекты, охотящиеся за игроком, оказываются запертыми за вогнутыми стенами или за углами. Поэтому такой алгоритм идеален разве что для игр с зомби или для игр без стен и других препятствий.

Если же агенты в игре должны действовать не столь бестолково, можно расширить простое событие столкновения и снабдить агентов памятью. Если агенты способны запоминать, где они уже побывали, то они смогут принимать более грамотные решения относительно того, куда поворачивать дальше. Если же повороты во всех возможных направлениях не привели к удаче, агенты смогут вернуться назад и выбрать другой маршрут движения. Таким образом, агенты будут производить систематический поиск пути к цели. Вот как это работает.
Двигайтесь в направлении цели.
Если путь разветвляется, выберите одно из возможных направлений.
Если путь приводит в тупик, возвращайтесь к последнему разветвлению и выберите другое направление.
Если все возможные пути пройдены безрезультатно, отказывайтесь от дальнейшего поиска.

Преимущество этого метода состоит в невысокой нагрузке на вычислительные ресурсы. Это означает, что можно поддерживать большое количество перемещающихся агентов без замедления игры. Этот метод также может использовать преимущества многопоточной архитектуры. Недостатком является расход огромного объема памяти впустую, поскольку каждый агент может отслеживать целую карту возможных путей.

Впрочем, нерационального использования памяти можно избежать, если агенты будут хранить отслеживаемые пути в общей памяти. В этом случае могут возникнуть проблемы в связи с конфликтом потоков, поэтому рекомендуем хранить пути объектов в отдельном модуле, в который все агенты будут отправлять запросы (по мере перемещения) и обновленные данные (при обнаружении новых путей). Модуль карты путей может анализировать полученную информацию, чтобы не допускать конфликтов.

Поиск путей

Карты, на которых пути прокладываются с помощью алгоритма «Столкнуться и повернуть», позволяют приспособиться к изменяющимся картам. Но в стратегических играх игроки не могут ждать, пока их войска разберутся с прокладыванием маршрутов. Кроме того, карты путей могут быть очень большими, и на выбор правильного пути на таких картах будет расходоваться очень много ресурсов. В таких ситуациях на помощь приходит алгоритм поиска путей.

Поиск путей можно считать уже давно и успешно решенной проблемой в разработке игр. Даже в таких старых играх, как первая версия легендарной игры Starcraft* (Blizzard Entertainment*), огромные количества игровых объектов могли определять пути движения по крупным и сложным картам.

Для определения путей движения используется алгоритм под названием A* (произносится э-стар). С его помощью можно находить оптимальный путь между двумя любыми точками в графе (в данном случае — на карте). Простой поиск в Интернете выдает чистый алгоритм, использующий крайне «понятные» описательные термины, такие как F, G и H. Сейчас я попробую описать этот алгоритм более удобопонятным образом.

Сначала нужно создать два списка: список узлов, которые еще не проверены (Unchecked), и список уже проверенных узлов (Checked). Каждый список включает узел расположения, предполагаемое расстояние до цели и ссылку на родительский объект (узел, который поместил данный узел в список). Изначально списки пусты.

Теперь добавим начальное расположение в список непроверенных, не указывая ничего в качестве родительского объекта. Затем вводим алгоритм.

Выбираем в списке наиболее подходящий узел.
Если этот узел является целью, то все готово.
Если этот узел не является целью, добавляем его в список проверенных.
Для каждого узла, соседнего с данным узлом.
Если этот узел непроходим, игнорируем его.
Если этот узел уже есть в любом из списков (проверенных или непроверенных), игнорируем его.
В противном случае добавляем его в список непроверенных, указываем текущий узел в качестве родительского и рассчитываем длину пути до цели (достаточно просто вычислить расстояние).

Когда объект достигает поля цели, можно построить путь, отследив родительские узлы вплоть до узла, у которого нет родительского элемента (это начальный узел). При этом мы получаем оптимальный путь, по которому может перемещаться объект.
Этот процесс работает, только когда агент получает приказ или самостоятельно принимает решение о движении, поэтому здесь можно с большой выгодой использовать многопоточность. Агент может отправить запрос в поток поиска пути, чтобы получить обнаруженный путь, не влияя на производительность ИИ. В большинстве случаев система может быстро получить результаты. При загрузке большого количества запросов путей агент может либо подождать, либо, не дожидаясь выдачи путей, просто начать двигаться в нужном направлении (например, по алгоритму «Столкнуться и повернуть»). На очень больших картах можно разделить систему на области и заранее вычислить все возможные пути между областями (или точки маршрута).
В этом случае модуль поиска путей просто находит наилучший путь и немедленно возвращает результаты. Поток карты путей может просто отслеживать изменения на карте (например, когда игрок строит стену), а затем снова запускает проверку путей по мере необходимости. Поскольку этот алгоритм работает в собственном потоке, он может адаптироваться, не влияя на производительность остальной игры.

Многопоточность может повысить производительность даже внутри подсистемы поиска путей. Этот подход широко применяется во всех стратегиях в реальном времени (RTS) и в системах с большим количеством объектов, каждый из которых пытается обнаружить потенциально уникальный путь. В разных потоках можно одновременно находить множество путей. Разумеется, система должна отслеживать, какие пути обнаруживаются. Каждый путь достаточно обнаружить только один раз.

Пример кода

Вот пример алгоритма А*, реализованного на языке С. Ради упрощения я убрал из этого примера поддерживающие функции.
Этот пример основывается на игровой карте в виде прямоугольной координатной сетки, каждое поле которой может быть проходимым либо непроходимым. Приведенный алгоритм поддерживает только перемещение на соседнее поле, но с незначительными изменениями его можно будет использовать и для перемещения по диагонали, и даже в играх, где карты уровней состоят из шестиугольных полей.

/*Get Path will return -1 on failure or a number on distance to path
if a path is found, the array pointed to by path will be set with the path in Points*/
int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
{
int u,i,p;
memset(&Checked,0,sizeof(Checked));
memset(&Unchecked,0,sizeof(Unchecked));
Unchecked[0].s.x = sx;
Unchecked[0].s.y = sy;
Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
Unchecked[0].p.x = -1;
Unchecked[0].p.y = -1;
Unchecked[0].used = 1;
Unchecked[0].steps = 0;

В приведенном выше фрагменте кода обрабатывается инициализация списка проверенных и непроверенных узлов, а начальный узел помещается в список непроверенных. После этого остаток алгоритма запускается в виде цикла.

do
{
u = GetBestUnchecked();
/*add */
AddtoList(Checked,Unchecked[u]);
if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
{
break;
}

Приведенный выше фрагмент кода анализирует узел из списка непроверенных, ближайший к цели. Функция GetBestUnchecked() проверяет расчетное расстояние каждого узла до цели. Если данное поле является целью, цикл разрывается, процесс завершен.

Ниже видно, как вычисляется расстояние: берем предполагаемые значения расстояния до цели в направлениях X и Y и складываем их. При этом может возникнуть желание использовать теорему Пифагора (сумма квадратов катетов равна квадрату гипотенузы), но это излишне. Нам нужно получить лишь относительное значение расстояния, а не его точную величину. Процессоры обрабатывают сложение и вычитание во много раз быстрее, чем умножение, которое, в свою очередь, работает гораздо быстрее, чем деление. Этот фрагмент кода запускается по много раз в каждом кадре, поэтому во главу угла ставим оптимизацию.

/*tile to the left*/
if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
}
}

В приведенном выше разделе функция анализирует поле слева от текущего узла. Если это поле пока отсутствует в списках «Проверенные» или «Непроверенные», функция попытается добавить его в список. TileValid() — еще одна функция, которую нужно приспособить для игры. Если она передает проверку TileValid(), то она вызовет NewToList() и новое расположение будет добавлено в список непроверенных. В следующих фрагментах кода повторяется этот же процесс, но в других направлениях: справа, сверху и снизу.

/*tile to the right*/
if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
}
}
/*tile below*/
if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
}
}
/*tile above*/
if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
}
}
memset(&Unchecked[u],0,sizeof(PNode));


Последнее, что осталось сделать в этой итерации, — удалить текущий узел из списка непроверенных. Нет необходимости еще раз анализировать это поле.
}
while(1)
;


Заключительный фрагмент кода выстраивает путь из списка проверенных путем возвращения к исходному положению. Путь к исходному расположению всегда можно найти, поскольку каждый узел на пути отслеживает свой родительский узел. Затем возвращается итоговый путь (с помощью ссылки). Функция возвращает длину нового пути.
IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
p = Checked[u].steps;
if(path != NULL)
{
for(i = (p - 1);i >= 0;i--)
{
path[i].x = Checked[u].s.x;
path[i].y = Checked[u].s.y;
IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
}
}
return p;
}


Тактический и стратегический ИИ

Теперь пора поговорить о том, как отдавать агентам более сложные приказы. Агенты должны научиться справляться с ситуацией, в которой они оказались. То есть, перейдем к искусственному интеллекту, способному работать с более широкими целями и воспринимать обстановку более масштабно.

Тактический ИИ

Роль тактического ИИ состоит в координации усилий групп агентов в игре. Группы более эффективны, поскольку члены группы могут поддерживать друг друга, могут действовать как единое подразделение, обмениваться информацией и распределять действия по получению информации.
Принцип тактического ИИ построен вокруг динамики группы. Игра должна отслеживать различные группы объектов. Каждую группу необходимо обновлять отдельно от индивидуальных объектов. Для этого можно использовать выделенный модуль обновления, отслеживающий различные группы, их цели и их состав. Недостаток этого метода состоит в том, что требуется разработка отдельной системы для игрового движка. Поэтому я предпочитаю использовать метод командира группы.

Одному юниту в составе группы можно назначить роль командира группы. Все остальные члены группы связаны со своим командиром, их поведение определяется информацией, полученной из приказов командира. Командир группы обрабатывает все вычисления тактического ИИ для всей группы.

Движение группы: поиск путей

Движение объектов можно улучшить с помощью динамики группы. Когда несколько агентов действуют как единое подразделение, их движение можно сделать более эффективным и реалистичным.
Поиск пути может занимать немало времени даже при ускорении с помощью заранее вычисленных карт путей и многопоточного ИИ. Динамика групп позволяет существенно снизить нагрузку, образуемую системой поиска путей.

Когда группе юнитов отдается приказ на перемещение (игроком или искусственным интеллектом), ближайший к цели юнит назначается командиром группы, а все остальные члены группы следуют за командиром. При обновлении командира группы он запрашивает систему путей. При наличии пути командир группы начинает движение к цели. Всем остальным юнитам в группе достаточно просто следовать за своим командиром.
Для более упорядоченного передвижения применяется строй. При использовании строя группа передвигается упорядоченно, например построившись фалангой или треугольником.


В игре Overlord рядовые (красного цвета) действуют как одна команда и передвигаются строем по команде игрока (воин в броне)

Управлять строем очень просто, для этого достаточно несколько расширить сферу действий командира группы. Каждый юнит в строю выполняет определенную роль. При построении каждому члену группы назначается место в строю точно так же, как одному из юнитов назначается роль командира группы. Цель каждого юнита — сохранить свое место на относительном расстоянии до других членов группы.
Для примера возьмем рядовых в игре Overlord. Они передвигаются треугольным строем. На рисунке ниже по маршруту должен двигаться только командир группы (обозначенный буквой «С»). Юнит 1 следует за юнитом «С» с такой же скоростью сзади и немного левее. Юнит 2 следит и следует за юнитом 1, двигаясь немного в стороне. Юнит 3 делает то же самое, что и юнит 1, но следует за юнитом 1, а не за командиром. Все члены группы соблюдают этот порядок.


Порядок движения треугольным строем

Тактика групп

Тактика, разумеется, не ограничивается ходьбой строем, а включает также поддержку и ведение боя группой как единой командой. Командир принимает на себя обязанности по планированию и координации работы команды. В конце концов, ведь именно командир несет ответственность за жизни всех подчиненных в своем отряде.
Для реализации тактики групп могут использоваться ранее описанные системы, например системы на основе правил или конечные автоматы. Типичные примеры поведения групп в играх: поддержка лечением (врачи остаются рядом с юнитами, которые с наибольшей вероятностью будут атакованы), разведка, прикрытие огнем, жертвование (заслон ценных юнитов менее ценными)


В игре Enemy Territory Quake Wars компаний Id Software* и Splash Damage, Ltd.* существует пять классов, которые выполняют разные роли в динамике группы

Кроме того, в группе может пригодиться еще один уровень анализа — анализ возможностей каждого члена группы. Командиру важно знать, в каких ситуациях группа может быть эффективна, когда группа получит преимущество, а когда группе следует отступить.
Например, в стратегии реального времени Starcraft* компании Blizzard существуют наземные войска и летающие войска. При этом не все виды наземных войск могут стрелять по летающим войскам. Группе важно знать о наличии такой возможности. Если в группе нет ни одного юнита, способного вести огонь по летающим юнитам, то при обнаружении летающего юнита лучше всего пуститься в бегство. Но если в группе есть юниты, способные поражать летающего противника, даже если таких юнитов и немного, лучше не отступать, а остановиться и обороняться (если в этой группе есть вспомогательные юниты, способные лечить тех, которые ведут огонь по воздушным целям).

В зависимости от наличия различных возможностей и от количества юнитов, располагающих такими возможностями, можно оценивать боевую эффективность группы в различных ситуациях. Группы, в которых эти факторы принимаются во внимание, будут вести бой гораздо эффективнее.

Стратегический ИИ

Стратегический ИИ — это ИИ более высокого порядка, он управляет целой армией и вырабатывает оптимальные стратегии.
Стратегический ИИ обычно применяется в стратегиях в реальном времени, но в последнее время его все чаще реализуют и в тактических шутерах от первого лица. Управляемый игроком командир может представлять собой отдельную систему или может быть настроен как пустой объект, не имеющий места и графического изображения, но обновляемый и размышляющий.

Командиры подчиняются иерархическим системам правил и конечным автоматам, которые управляют такой деятельностью, как сбор ресурсов, изучение дерева технологий, создание армии и т. д. Как правило, для базового поддержания игровых элементов не требуется особо сложных размышлений. Интеллект нужен главным образом при взаимодействии с другими игроками.

Управление этим взаимодействием (или сражением) — вот где прежде всего работает ИИ. Командир должен изучить карту игры, чтобы обнаружить игрока, выявить основные области интереса, например узкие проходы, выстроить оборону и проанализировать оборону другого игрока. Как именно это сделать? Очевидного ответа на этот вопрос нет, но для упрощения можно использовать карты решений.
Карты решений
Карты решений представляют собой двухмерные массивы, приближенно соответствующие игровой карте. Каждая ячейка массива соответствует определенной области в игре и содержит важную информацию об этой области. Эти карты помогают стратегическому ИИ принимать грамотные решения относительно игры в целом.

Карты ресурсов

Карты ресурсов содержат информацию о расположении ресурсов в стратегической игре. Данные о местах сосредоточения ресурсов на карте могут повлиять на многие решения командира. Где расширять базу, где развертывать дополнительные базы (ресурсы рядом с базой командира), где противник с наибольшей вероятностью будет расширять свою территорию (ресурсы рядом с базой противника), в каких местах наиболее вероятны столкновения за овладение ресурсами (ресурсы посередине между своей базой и базой противника).

Получение информации о количестве возможных доступных ресурсов также влияет на решения о том, какие юниты следует поддерживать и как нужно развертывать армию. При дефиците ресурсов следует осторожнее использовать каждый юнит, поскольку меньше вероятность получить пополнение. При избытке ресурсов можно использовать стратегии массового создания дешевых юнитов или создания дорогостоящих мощных юнитов.

Карты целей

Эти карты содержат информацию о целях командира, например расположение баз противника, положение целей на карте (взорвать объект такой-то, защитить объект такой-то, взломать компьютер там-то и т. п.) и важнейшие юниты в армии нашего командира (главная база, юниты-герои и т. д.). Отслеживание этой информации помогает командиру эффективнее управлять своей армией. Места, нуждающиеся в защите, следует окружать оборонительными сооружениями и рядом с ними всегда следует располагать отряды войск. Цели, подлежащие атаке, следует разведывать и изучать, как они защищены. Анализ обороны, устроенной вокруг целей, требуется для выработки оптимального способа преодоления этой обороны. На основе этих данных образуется краеугольный камень всех военных игр — карты конфликтов.

Карты конфликтов

Карты конфликтов используются и обновляются гораздо чаще, чем все перечисленные выше карты. На картах конфликтов отслеживаются все сражения на данном уровне игры. Всякий раз, когда один из юнитов командира вступает в бой с противником, этот юнит обновляет карту конфликтов, передавая такие данные как тип конфликта, его сила, возможности и количество юнитов.
Анализ этой информации поможет сделать нужные выводы об эффективности развернутой обороны и нападения, а также о необходимых контрмерах (вовлечении дополнительных юнитов)


Пример карты конфликта при наложении на карту местности. Чем больше красного цвета, тем больше конфликтов

Создание и применение карт

Ранее я уже сказал, что карты составляются юнитами из состава армии командира. Правила, управляющие искусственным интеллектом, должны предусматривать отправку разведчиков на как можно более раннем этапе, поскольку это позволит приступить к созданию карт. Продуманный ИИ периодически проверяет актуальность карт. На ранних этапах игры, когда поддержкой карт занимается всего несколько юнитов, обновление не должно образовывать существенную нагрузку на игровой движок. На более поздних этапах игры, когда информацию одновременно выдают десятки или сотни юнитов, возможно снижение производительности.

Впрочем, добиться быстрого обновления карт решений не так трудно. Достаточно поместить систему карт решений в отдельный поток. В идеале каждый игрок, управляемый искусственным интеллектом, должен располагать собственным потоком для обработки собственного набора карт решений. Значительный прирост производительности будет достигнут в том случае, если все объекты уже разделены на несколько потоков. Потоки с картами решений будут обрабатывать только запросы от сообщений обновления распараллеленных объектов.

Наибольшая эффективность ИИ: обработка потоков

Какой бы прекрасной ни была ваша система искусственного интеллекта, она бесполезна, если замедляет игру. Эффективное программирование и различные приемы по оптимизации обеспечивают некоторое ускорение, но одних лишь этих мер недостаточно.


В игре Starcraft* II компании Blizzard Entertainment одновременно работает ИИ огромного количества юнитов. Лучше всего использовать для этого многопоточную архитектуру

При работе с системой, где установлено несколько процессоров (процессор с несколькими ядрами), можно разделить работу между ними. Для этого есть два способа: распараллеливание задач (функциональное распараллеливание) и распараллеливание данных.

Распараллеливание задач

Простейший способ приспособить приложение к многопоточной архитектуре — разделить его на отдельные задачи.


Функциональное распараллеливание позволяет каждой подсистеме использовать собственный поток и ядро

Характерный пример — звуковая система игрового движка. Звуку не нужно взаимодействовать с другими системами: эта система занимается только одним — воспроизводит звуки и их сочетания по запросу. Функции обмена данными представляют собой вызовы для воспроизведения звуков и остановки воспроизведения. Благодаря этому звуковая система является автономной и идеально подходит для функционального распараллеливания.

В зависимости от потребностей игры может быть множество разных задач, каждой из которых можно предоставить отдельный поток. Здесь мы рассматриваем три такие задачи: поиск путей, стратегический ИИ и собственно система объектов.

Поиск путей

Система поиска путей может быть реализована таким образом, что каждый объект, пытающийся найти путь, вызывает свой собственный алгоритм поиска путей каждый раз, когда в этом возникает необходимость. Такой метод будет работать, но в этом случае движок будет дожидаться завершения работы алгоритма поиска путей при каждом запросе пути. Если выделить поиск путей в отдельную подсистему, можно вывести ее в отдельный поток. Теперь система поиска путей будет работать как диспетчер ресурсов, в котором пути являются ресурсами.

Любой объект, которому нужно найти путь, отправляет запрос на поиск путей и немедленно получает «квитанцию» от системы поиска путей. Эта квитанция представляет собой просто уникальный дескриптор, который система поиска путей может использовать для работы. После этого объект продолжает заниматься своими делами до следующего кадра в игровом цикле. Объект может проверить, обработана ли его квитанция. Если да, то объект получает рассчитанный путь; в противном случае объект продолжает заниматься своими делами в ожидании обработки пути.
В системе поиска путей квитанция используется для отслеживания запросов путей, пока система работает над ними, не влияя на производительность остальных компонентов. У такого подхода есть интересное преимущество — автоматическое отслеживание всех обнаруженных путей. Поэтому при поступлении запроса на найденный ранее путь система поиска путей может просто выдать квитанцию на уже существующий путь. Этот метод великолепно подходит для систем, где множество объектов запрашивают путь, поскольку все найденные пути с большой вероятностью будут запрошены многократно.

Стратегический ИИ

Как было упомянуто ранее, хорошо, если система ИИ, управляющая всем ходом игры в целом, будет работать в собственном отдельном потоке. Эта система сможет анализировать игровое поле и отдавать команды различным объектам, которые смогут получать и распознавать эти команды.
Система объектов в собственном потоке будет занята работой по сбору информации для карт решений. Полученная информация будет отправлена в систему стратегического ИИ в виде запросов на обновление карт решений. При обновлении стратегический ИИ будет анализировать эти запросы, обновлять карты решений и принимать решения. При этом не имеет значения, работают ли эти две системы (стратегический ИИ и объекты) синхронно: любая рассинхронизация будет незначительной и не повлияет на решения ИИ. (Речь идет о рассинхронизации в пределах 1/60 секунды, то есть, с точки зрения игрока, реакция ИИ не замедлится ни на один кадр.)

Распараллеливание данных

Функциональное распараллеливание очень эффективно и использует возможности систем с несколькими ядрами. Но, к сожалению, если в системе количество ядер превышает количество задач, то программа не использует всю доступную вычислительную мощность Поэтому переходим к распараллеливанию данных, при котором одна функция может воспользоваться всеми доступными ядрами


Распараллеливание данных

При функциональном распараллеливании мы брали автономный модуль и предоставляли ему отдельный поток. Теперь мы разделим одно задание на части и распределим их обработку между разными потоками. При этом производительность возрастает пропорционально количеству ядер в системе. В системе 8 ядер? Отлично! В системе 64 ядра? Еще лучше! Функциональное распараллеливание позволяет обозначать фрагменты кода как многопоточные, после чего эти фрагменты работают самостоятельно. При распараллеливании данных требуется дополнительная работа для согласования. Например, можно использовать один поток ядра (главный поток), чтобы отслеживать работу всех остальных потоков. Подчиненные потоки будут запрашивать «работу» в главном потоке, чтобы исключить дублирование выполнения одной и той же работы.

Использование одного потока ядра для управления распараллеливанием данных является на самом деле гибридным подходом. Получается, что главный поток использует функциональное распараллеливание, а затем разделяет данные между ядрами для распараллеливания данных.

Реализация

В примере с системой поиска путей эта система хранит список запрошенных путей. Затем система циклически просматривает этот список и запускает функции поиска путей для отдельных запросов, сохраняя их в списке путей. Этот цикл можно распределить по потокам так, чтобы каждая итерация цикла разделялась на разные потоки. Эти потоки будут запускаться на первом же доступном ядре, что позволяет использовать всю доступную вычислительную мощность. Ядро процессора должно бездействовать только при отсутствии работы.
В таких системах есть возможность получения нескольких запросов на одно и то же задание. Если эти запросы разделены по времени, функция поиска путей автоматически проверяет, был ли уже обработан такой запрос ранее. При работе с распараллеливанием данных несколько запросов одного и того же пути может возникнуть одновременно. Это может привести к дублированию работы, в случае чего теряется весь смысл многопоточных вычислений.

Для исключения таких (и прочих) случаев дублирования работы система должна отслеживать выполняемые задания и удалять их из очереди запросов только после завершения. Если же поступает запрос на путь, который уже запрошен, система должна проверить это и вернуть существующий путь, назначенный данной квитанции.
На образование новых потоков тратятся ресурсы. Этот процесс включает системные вызовы к операционной системе (ОС). Когда у ОС до этого «доходят руки», она выделяет необходимый код и создает поток. Это может занять много времени (по отношению к скорости работы ЦП). Поэтому нет смысла создавать слишком много потоков. Если запрошенная работа уже обрабатывается, то не нужно запускать задачу. Кроме того, если задача несложная (например, поиск путей между двумя точками, находящимися рядом одна с другой), то может не иметь смысла разделять такую задачу на несколько потоков.
Вот как функциональный поток поиска путей будет работать и разделять данные на потоки.
RequestPath(start, goal).Эта функция вызывается снаружи системы поиска путей для получения потока. Эта функция выполняет следующие задачи:
просматривает список выполненных запросов и определяет, был ли уже найден такой путь (или близкий путь), затем возвращает квитанцию на этот путь;
просматривает список активных запросов (если путь не был найден) для поиска этого пути; если путь в нем есть, функция возвращает квитанцию на рассчитываемый путь;
создает новый запрос и возвращает новую квитанцию (если поиск по обоим указанным выше спискам не дал результата).
CheckPath(«ticket»). Используя квитанцию, эта функция просматривает список выполненных запросов и находит путь, для которого действует данная квитанция. Функция возвращает данные о том, был ли найден такой путь.
UpdatePathFinder().Это управляющая функция, обрабатывающая издержки для потоков поиска путей. Эта функция выполняет следующие задачи.
Анализ новых запросов. Возможно одновременное создание разными ядрами нескольких запросов на один и тот же путь. Эта секция удаляет дублирующиеся запросы и назначает несколько квитанций (из разных запросов) одному и тому же запросу.
Циклический просмотр активных запросов. Эта функция просматривает все активные запросы и распределяет их по потокам. В начале и в конце каждого цикла код помечается как поток. Каждый поток:
находит запрошенный путь;
сохраняет его в списке готовых путей вместе с назначенными этому пути квитанциями;
удаляет задание из списка активных заданий.

Устранение конфликтов

Возможно, вы обратили внимание, что при таком распределении работ могут возникнуть проблемы. Различным потокам нужно производить запись в очередь запросов; потокам данных нужно добавлять результаты в список готовых путей. Все это может привести к конфликтам записи, когда один поток записывает что-либо в ячейку А в то же самое время, когда другой поток записывает в эту же ячейку А что-то другое. Такой поток может привести к хорошо известному «состоянию состязания».

Чтобы избежать конфликтов, можно пометить некоторые части кода как особо важные. При выполнении особо важного кода только один поток сможет получить доступ к этой секции кода в один момент времени. Всем остальным потокам, которые собираются сделать то же самое (получить доступ к той же области памяти), придется подождать. Такое поведение может привести к СЕРЬЕЗНЕЙШИМ проблемам, таким как взаимная блокировка, возникающая, когда несколько потоков блокируют друг друга, препятствуя в получении доступа к памяти. Это решение позволяет избежать взаимной блокировки. Когда фактическая работа потока будет завершена, можно предоставлять доступ к важной области памяти сразу же по доступности без блокирования других секций, которые могут быть необходимы другим потокам.

Синхронизация

Итак, мы добились автономности всех отдельных подсистем ИИ и предоставили им все вычислительные ресурсы нашей системы. Все работает быстро, но все ли работает правильно?
Действия разных элементов игры должны быть согласованными. Игровой движок должен синхронизировать элементы игры. Нельзя, чтобы половина элементов игры работала на пару кадров быстрее остальных элементов. Нельзя, чтобы юниты бездействовали, ожидая вычисления пути, тогда как юниты противника уже пришли в движение. Образно говоря, хорошие родители делят шоколадку поровну между своими детьми.
Основной цикл игрового движка занимается двумя классами действий: отрисовка и обновление. При последовательном программировании синхронизация таких действий не представляет затруднений. Сначала все обновляется, а затем то, что было обновлено, заново отрисовывается. При параллельных вычислениях ситуация усложняется.

Обновления движения (которые часто выполняются на основе траекторий) могут обработаться на несколько кадров быстрее, чем отрисовка. В результате получится «дерганая» анимация: объекты игрового мира будут не перемещаться плавно, а «перепрыгивать» с одного места на другое быстрее, чем следует. При поиске путей, когда анализируется снимок положений различных объектов в мире, это может привести к обработке неверных входных данных.
Решение этой проблемы заключается в синхронизации различных элементов и отличается изяществом и простотой. Более того, нужные функции могут уже быть встроены в большинство игровых движков. При обновлении главного цикла игры отслеживается глобальный индекс времени. Все разнообразные потоки должны обрабатывать запросы только для текущего (и для прошлого, но не для будущего) индекса времени.

Когда вся работа по полученной задаче завершена для текущего индекса времени, поток может перейти в состояние сна до нового индекса времени. Такой алгоритм не только гарантирует синхронизацию различных игровых элементов, но и высвобождает ресурсы системы: потоки не загружают ядра, когда в этом нет необходимости. Поэтому задание по перемещению, способное устранять столкновения, вычислять траектории и т. д., любезно предоставит свои вычислительные ресурсы другим заданиям, если справится с работой раньше. При этом все доступные ядра используются в полной мере.

Заключение

Итак, задача искусственного интеллекта для игр состоит в имитации поведения объектов реального мира. И это совсем не сложно, если начать рассмотрение искусственного интеллекта с базовых компонентов — от низкоуровневых правил и алгоритмов поиска путей до более высокого уровня, на котором работает тактический и стратегический ИИ. При этом, следует добиться высокой эффективности работы системы ИИ, оптимизировать ее для использования на компьютерах с большим количеством вычислительных ядер. Возможности ИИ в системе должны ограничиваться только фактически наличными ресурсами оборудования, а не неспособностью использовать эти ресурсы. Только тогда мы сможем создать более интересных и сложных противников для игроков, которые будут с нетерпением ожидать продолжения игры.

Полный текст статей на русском языке

Создание искусственного интеллекта для игр (часть 1)
Создание искусственного интеллекта для игр (часть 2)
Создание искусственного интеллекта для игр (часть 3)
Создание искусственного интеллекта для игр (часть 4)
разработка игр, искусственный интеллект
— 17933
363Donald Kehoe vikky13 31,2
Похожие публикации

Разработка игр с помощью Unity и 3D-камеры Intel RealSense (2)
Разработка игр для детей с использованием Intel Perceptual Computing. Пример «Приключений Клифорда» (1)
Игры разума. Разбираемся с Intel HD graphics. И играем? (60)
Разрабатываем игры с Intel: осенняя серия вебинаров (6)
Разрабатываем игры с Intel: GPA и первоиюльский вебинар (14)
Комментарии (2) отслеживать новые: в почте в трекере

+1 BIanF 1 сентября 2015 в 20:49 (комментарий был изменён)#
Спасибо за прекрасный перевод интересной статьи.
Получил дозу позитива от прочтения.
+1 delosgatos 2 сентября 2015 в 17:55#
Мне кажется, уже надо вводить термин ИИИ — имитация искусственного интеллекта
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#10 dyvniy » Вс, 25 октября 2015, 20:38:30

Про негумоноидальную жизнь и разум, фантасты.
Спойлер
Это реальность. А как насчет фантастики? Инопланетной жизни там с избытком. Герберт Уэллс пугал нас марсианским красным мхом. В Плоском мире Терри Пратчетта живут тролли — существа с кремниевой органикой, питающиеся камнями (для этого у них есть алмазные зубы). Грегори Бенфорд описывал жизнь на комете, активизирующуюся с ее приближением к Солнцу («Сердце кометы», 1986), а знаменитый астрофизик Фред Хойл, автор термина «Большой Взрыв», написал роман «Черное облако» (1957), в котором фигурировало огромное скопление космической пыли, обладавшее коллективным интеллектом.
В романе физика Роберта Форварда «Камелот 30К» на отдаленном астероиде в облаке Оорта (окраины Солнечной системы) существовала экосистема, основанная на фтороуглероде, и даже разумные существа, создавшие культуру вроде английской времен короля Артура. Тот же автор описывал и ядерную форму жизни, существующую на поверхности нейтронных звезд («Яйцо дракона», «Звездотрясение»). Но дальше всего шагнул Стивен Бакстер — в его цикле «Ксили» имелась фотонная жизнь, населявшая гравитационные колодцы звезд.
Не обходилось и без юмора. Дэвид Духовны в фильме «Эволюция» (2001) боролся с инопланетной живностью (с азотным метаболизмом), отравляя ее селеном из шампуня Head & Shoulders.
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#11 dyvniy » Чт, 29 октября 2015, 17:16:42

ABBY сильно продвинулась оказывается!
http://www.abbyy.ru/isearch/compreno/
Но пользоваться триалом наверно не даст ((
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3631
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#12 dyvniy » Вт, 29 декабря 2015, 07:25:54

Досье искуственного интеллекта
http://www.computer-museum.ru/frgnhist/ai1.htm
Спойлер
Сергей Бобровский

Искусственный интеллект (ИИ) применяется сегодня во многих прикладных областях. Практически все они, может быть, и не так быстро, как хотелось бы, но неуклонно и непрерывно развиваются. В последние годы современные ИТ-технологии совершили очень резкий скачок вперед, в основном за счет повышения производительности массовых процессоров и стремительного удешевления памяти (как оперативной, так и "жесткой"). Это привело к появлению приложений, в которых воплощены серьезные теоретические наработки ИИ.


При этом можно отметить две тенденции. С одной стороны крупнейший в мире финансист исследований по ИИ (особенно по робототехнике) – это военное научное агентство DARPA. Современное оружие немыслимо без подходов ИИ (преимущественно нейронных технологий, нечетких экспертных систем и интеллектуальных решателей), позволяющих с помощью относительно малых ресурсов получать достаточно точные результаты, для нахождения которых классическими методами численной математики потребовались бы мощности суперкомпьютеров. Например, реализация режима автономного полета на небольшой высоте в плохих погодных условиях без использования заранее подготовленной компьютерной базы рельефа требует применения высокоэффективных механизмов синхронизации движения с данными, получаемыми от системы навигации GPS, видеокамер, радаров и других датчиков.

В связи с этим состояние определенных направлений в ИИ закрыто от посторонних глаз.

С другой стороны рынок бытовых роботов и интеллектуальных домашних устройств уже сегодня приносит немалую прибыль, а в перспективе это будет огромный бизнес, поэтому коммерческие компании занимаются исследованиями по ИИ своими силами, в чем-то дублируя DARPA и другие подобные организации (хотя, скорее всего, не опережая их).

В настоящем обзоре рассматриваются наиболее значимые события, произошедшие в различных областях ИИ за последние несколько лет. Надо отметить, что основная часть реально используемых систем обычно создается с привлечением разных технологий ИИ, что позволяет существенно повысить качество конечного результата.

Более подробную информацию по ИИ можно без проблем найти в Интернете. Например, большая подборка материалов расположена по адресу http://dir.yahoo.com/Science/Computer_Science/Artificial_Intelligence/.

Экспертные системы

Создание экспертных систем (ЭС) традиционно считается классическим занятием для специалистов по ИИ. ЭС многократно хоронились, признавались тупиковым направлением, тем не менее компьютеры научились давать советы в конкретных областях человеческой деятельности на уровне хороших экспертов.

Основной акцент в современных ЭС делается на принятии оперативных решений в реальном масштабе времени. Это объясняется нуждами современного бизнеса. Коммерческие ЭС контролируют крупные промышленные процессы, принимают решения по результатам показаний сотен периферийных устройств, управляют большими сетями, распределенными СУБД, подсказывая оператору, как поступить в сложной обстановке, а в критических ситуациях, требующих немедленного решения, берут управление на себя. Достаточно активно развивается и такое направление, как автоматическое накопление знаний, снимающее с человека рутинную работу по качественному анализу различных процессов. Практически все современные системы раскопки данных представляют собой ЭС.

Правда, старая схема ЭС, основанных на системе правил и создававшихся на базе версий Лиспа и Пролога, сегодня не столь популярна, как раньше. Практически во всех коммерческих продуктах применяются более гибкие походы – нечеткие технологии (когда вместо обычной двоичной логики "да-нет" используется логика с бесконечным числом состояний), Bayesian-сети, учитывающие вероятности перехода узлов в другие состояния, и т. д.

Например, система MOBAL дает возможность строить модель понятия в терминах логических правил и фактов, позволяя с помощью языка поиска похожих объектов Query-by-Similarity в сочетании с нечеткой логикой создавать очень гибкие системы хранения и обработки информации.

Интеллектуальный решатель C-PRS (Procedural Reasoning System in C), написанный на стандарте ANSI C, используется НАСА, в авиапромышленности, в системах управлении перевозками и мобильными роботами. Он переносим, очень компактен и с помощью кросс-платформных компиляторов допускает встраивание практически в любое оборудование.

В России осуществлено несколько внедрений крупной ЭС контроля, управления и моделирования сложных процессов Gensym G2.

Группа адаптивных систем корпорации Microsoft трудится над совершенствованием технологии Office Assistant, которая позволяет отслеживать поведение пользователя и подсказывать ему правильные действия в запутанных ситуациях.

В открытый проект AIOS (http://blkbox.com/~cravey/aios) приглашаются все желающие. Он посвящен созданию ОС с элементами ИИ. В нее будут встроены технологии обработки естественной речи, автоматического решения задач и самообучения.

Коммерческие системы имеют довольно большой ценовой диапазон, и если простые настольные системы стоят несколько сотен долларов, то цена промышленных приложений возрастает в тысячу раз, что свидетельствует об их несомненной востребованности.

Робототехника

При создании домашних автономных устройств подчас возникает больше проблем, чем при создании военных и космических роботов. Хотя в жилых домах не бывает перепадов температур в сотни градусов, а превышение скорости на десятки сантиметров несущественно (что в условиях невесомости может сразу привести к аварии), требование максимальной безопасности значительно осложняет жизнь разработчикам.

Быстрее всего сегодня развивается рынок автономных домашних пылесосов (см. PC Week/RE, № 40/99, с. 4). Такие модели оборудованы навигационной системой и всевозможными периферийными датчиками. Роботы-пылесосы перемещаются по квартире по случайным траекториям, собирая мусор и объезжая статические предметы, и удирают от движущихся объектов (людей и животных). Кроме того, умные пылесосы способны самостоятельно возвращаться на свое "место жительства" для подзарядки.

Другой перспективный рынок – автономные газонокосилки. Например, фирма Electrolux выпускает косилки, способные подзаряжаться от солнечной батареи, запасаться энергией на ночь и работать практически круглосуточно.

Более совершенные модели интеллектуальных бытовых устройств помимо уборки мусора способны выполнять множество дополнительных функций – например, подносить напитки и тапочки. Робот Cye фирмы Probotics, постоянно подключенный к ПК, дистанционно управляется заложенной в компьютер программой. С помощью удобного визуального инструмента пользователь может, используя план комнат, определить для Cye траектории передвижения, доступные и запрещенные области в квартире. Общение с роботом выполняется по протоколу, содержащему 35 команд и 20 ответных сообщений от робота. Немаловажно, что ПО Cye открыто для совершенствования, позволяет расширять базовые возможности системы и создавать на его основе собственные программы управления роботом. В будущих версиях Cye будет поддерживаться навигационная система GPS, и он сможет передвигаться не только по комнатам, но и на приусадебном участке.

Спрос на подобные устройства растет, и известная компания NEC уже представила модель Personal Robot R100, которая поступит в продажу в 2001 г. Сейчас модель проходит тестирование в исследовательском центре компании, и журналисты уже могли лицезреть, как робот высотой 44 см и весом 8 кг въезжает в комнату руководительницы проекта Йошихиро Фуджито, вращает телеглазом, распознает ее лицо среди лиц других присутствующих и обращается к ней со словами: "Мама! Вам что-нибудь надо?". В общей сложности робот способен произносить 300 фраз, понимать сотни команд и различать 10 лиц.

R100 может приносить мелкие вещи, вынимать почту из ящика, включать и выключать телевизор и кондиционер, записывать видеосообщения и передавать их по назначению. Он подключен к ПК и имеет встроенный процессор Intel 486 DX4. На основе этой модели NEC планирует в будущем выпускать робокошек и робособак.

Сотрудники лаборатории ИИ Массачусетского института считают, что робот – это не просто прислуга. Он обязательно должен взаимодействовать с окружающим миром и выполнять социально значимые функции. Исходя из этой посылки, они разрабатывают робота Cog, своим внешним видом и отчасти устройством напоминающего человека. Чтобы придать роботу привычную людям походку, допустимые углы сгибания его рук и ног сделаны примерно равными человеческим. В качестве глаз робота применяются четыре видеокамеры (по две на каждый "глаз"), распознающие оттенки серого и имитирующие режим бинокулярного зрения. В ушных раковинах, работающих по принципу локатора, установлены микрофоны, на конечностях и туловище – датчики давления (имитация осязания).

Вестибулярный аппарат моделируется тремя гироскопами, расположенными в голове робота. Единственное, что пока не реализовано по аналогии – обоняние.

Система управления представляет собой сложную иерархию устройств, от периферийных микроконтроллеров управления положением ступни до сети цифровой сигнальной системы обработки видео- и аудиоинформации. В большинство узлов Cog встроены процессоры Motorola 68332 16 МГц, на которых выполняется интерпретатор L (версия Common Lisp). Интенсивная обработки информации происходит в сети промышленных 200 МГц процессоров в ОС реального времени QNX.

Университет Северной Каролины разрабатывает роботов, способных перемещаться в завалах и спасать людей, оказавшихся под развалинами в результате различных катастроф. Робот Moccasin II, напоминающий сегментированного червяка, может проползать в туннелях диаметром 20 см и поворачивать на 90 градусов в любых направлениях, анализируя информацию от видеокамеры с подсветкой и датчиков давления, с помощью которых он "ощущает" стены и их изгибы. Moccasin II использует не электрический, а пневматический двигатель (потому что электрические искры могут спровоцировать взрыв скоплений газа) и передвигается как обычный червяк – сжимая и растягивая свое тело. Следующие модели робота можно будет без опаски применять при обследовании крупных технологических конструкций (танкеров, самолетов).

НАСА создала робота величиной с небольшой мячик. Он понимает голосовые команды, снабжен видеокамерой, датчиками температуры, давления и газовыми анализаторами и способен самостоятельно путешествовать внутри космических станций, выполняя мониторинг их состояния.


Военная лаборатория США Jet Propulsion Laboratory совместно с японским институтом аэрокосмических исследований наметила на январь 2002 г. первую в истории человечества высадку робота на астероид Nereus (1989ML). Он должен будет собрать образцы грунта и вернуться обратно на корабль. Пока прообраз этого робота представляет собой четырехколесный вездеход весом 2 кг и размером 28 куб. см. Он может поднимать свое "тело" значительно выше положения колесных осей или опускать его на грунт для взятия проб, подпрыгивать, пробираться в узких туннелях и, что очень важно, переворачиваться со спины на колеса в случае неожиданного неудачного падения. Робот снабжен солнечными батареями, видеокамерой, инфракрасным излучателем и системой связи с посадочным модулем и Землей. Для управления манипуляторами планируется использовать искусственные мускулы на основе электроактивных полимеров. В перспективе для исследования Марса, астероидов и комет этой же командой будут создаваться микророботы весом от 100 до 10 граммов.

Американская Ассоциация по ИИ на Национальной конференции 1999 г. организовала интересный турнир. Согласно его условиям роботы должны были самостоятельно добраться до зала заседаний. Для этого им требовалось выстоять в очереди на регистрацию, подняться по эскалатору, получить цветной баджет на "шею", выйти (или выползти) на сцену, в течение 2 минут рассказать о себе и попробовать ответить на простейшие вопросы. При этом учитывалась степень внешней похожести робота на человека. В первом турнире роботы двух университетских команд, добираясь до конференц-зала, пробовали хитрить – один просил окружающих подсказать ему правильное направление движения, а второй легонько подталкивал людей, обращаясь к ним с просьбой отнести его в зал.

Японские ученые, традиционно склонные к миниатюризации, создали робот длиной 1 см и массой в полграмма. Он предназначен для обслуживания АЭС и ТЭС и восстановления поврежденных участков электростанций. Робот способен проникать в поврежденные зоны, проползать по тончайшим трубкам и закрывать пораженные области своим телом.

В медицинском центре государственного университета штата Огайо создан робот-хирург, который имеет видеокамеру и две небольшие руки-манипулятора, а управляет им человек с помощью компьютера. Через небольшие разрезы на теле устройство проникает в сердце, после чего на основании полученной от него видеоинформации компьютер формирует трехмерный образ органа, позволяющий выполнять операцию значительно эффективнее. Хирурги единодушно признали пользу такого устройства.

Военные медики США создали робот для проведения операций в полевых условиях. Им можно дистанционно управлять с любого расстояния. Робот снабжен двумя манипуляторами, на каждом из которых установлено по 7 моторов и еще 14 моторов определяют положение тела. Система передает врачу трехмерное изображение оперируемой области и звуковой фон и обеспечивает обратную связь с хирургом, сообщая ему информацию, связанную с нагрузкой на скальпель. Компьютерный модуль компенсирует естественное дрожание кистей рук человека, повышена точность движений манипуляторов.

Похожие работы проводятся в российском Научном центре сердечно-сосудистой хирургии имени Бакулева РАМН. Используемый там робот также снабжен несколькими манипуляторами, способными держать различные инструменты (скальпель, пинцет и т. д.). Благодаря повышенному числу степеней свободы он может работать в самых неудобных, недоступных для человека положениях. Врач за монитором следит за увеличенной зоной операции и управляет манипуляторами, подавая через компьютер голосовые команды.

Военных в робототехнике интересуют прежде всего автономные летающие устройства для сбора разведывательной информации. Агентство DARPA готово финансировать выпуск беспилотных самолетов, в течение 20–60 мин полета преодолевающих 30–60 км и имеющих при этом массу не более 1 кг, а размеры – 20 см.

Фирма AeroVironment разработала снабженный различными датчиками самолет длиной 7,5 см, который может быть послан на разведку в очень сложных условиях – например, в городе. Пока главной проблемой остается посадка такого самолета, обычно не обходящаяся без поломок. Кроме того, трудно найти небольшой и достаточно мощный двигатель, поэтому фирма рассматривает возможность применения альтернативных (химических) источников энергии. Пока ее самолетик с двухграммовым пропеллером держится в воздухе 16 мин, развивая с попутным ветром скорость 70 км/ч.

Сотрудники лаборатории Вандербилтского университета пошли по другому пути. Они пытаются создать роботы, имитирующие движения насекомых. В них будут применены пьезоэлектрические приводы, используемые в пейджерах и имеющие КПД до 90% (КПД моторов, выполненных по другим технологиям, как правило, составляет около 60%).

Пока военные только готовятся к сражениям без участия людей, энтузиасты уже превратили такие войны в доходный бизнес. В США ежегодно проводится множество состязаний между роботами, цель которых одна – любой ценой "замочить" противника. В турнире BattleBots сражаются радиоуправляемые роботы, вооруженные молотками и прутьями; в уже шестом по счету конкурсе Fire-Fighting Home Robot Contest автономные роботы стреляют друг в друга, перемещаясь внутри жилого дома; организация Seattle Robotics Society проводит целый турнир для роботов Robothon, в который помимо драк входят такие виды "спорта", как сумо, отжимание и т. д.
Изображение


Название раздела: Технокалипсис
Описание: Новости науки и техники. Всё то, о чём раньше Вы могли только мечтать. Магия современности.

Быстрый ответ


Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
Код подтверждения
:) ;) :hihi: :P :hah: :haha: :angel: :( :st: :_( :cool: 8-| :beee: :ham: :rrr: :grr: :* :secret: :stupid: :music: Ещё смайлики…
   

Вернуться в «Технокалипсис»

Кто сейчас на форуме (по активности за 15 минут)

Сейчас этот раздел просматривают: 1 гость