0,0
рейтинг
26 октября 2014 в 20:50

Разработка → Russian AI Cup 2014: стратегия победителя

Продолжая хорошую традицию «раскрытия секретов» победителей ежегодного конкурса Russian AI Cup от Mail.Ru, представляю вниманию всех интересующихся эту статью. Описывать механику игрового мира и прочие правила я не буду, если же вдруг найдутся интересующиеся данной статьей, но не знающие правил, то они смогут найти их на официальной странице чемпионата.





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

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

Бета-тест


Большую часть недели бета-теста я потратил на реверс игровой физики. Причем мне, физику по образованию, гораздо проще получить требуемые формулы с помощью экспериментов, а не декомпиляцией local-runner-а. Все одиночные контакты (удары), кроме столкновения двух хоккеистов (которым я, в принципе, не занимался) и фронтального удара шайбы об вратаря (в котором участвовало чье-то скрытое вращение) я научился предсказывать с точностью float-ов. В устройстве мира хватало странных и хитрых моментов, например устройство штанги (секция длинной 25 единиц с десятикратно уменьшенным отскоком), или выталкивающая стенка для хоккеистов в воротах (причем без обнуления скорости), или положение шайбы, удерживаемой хоккеистом (с компенсацией скорости без учета трения), однако все эти мелочи не имели особого значения для стратегии (да еще менялись в процессе чемпионата), поэтому останавливаться на них не буду.

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

Ключевой алгоритм


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

Рассмотрим сначала метод наибыстрейшего достижения определенной точки (без учета стенок и других хоккеистов) с нулевой начальной скоростью. Ненулевая начальная скорость приводит только к фиксированному смещению области достижимых точек на каждый временной шаг, не меняя саму конфигурацию области. Достаточно хитрые геометрические соображения (сами соображения я приводить не буду ввиду их сложности и отсутствия математической строгости) приводят к следующему набору «оптимальных» траекторий.
  • Поворот влево/вправо с ускорением вперед/назад на угол, меньший 90°, затем продолжение движения без поворота не меняя ускорения.
  • Поворот влево/вправо с ускорением назад/вперед на угол, меньший 90°, затем реверс ускорения с продолжением поворота в течение следующих 90°, затем продолжение движения с ускорением, но без поворота.

Ввиду отсутствия строгости, реальные оптимальные траектории могут немного отличаться от этих, однако это не принципиально (см. рассуждения выше о достаточной точности). Таким образом, траектории параметризуются флагом типа ускорения на основном участке траектории (вперед/назад) и направления поворота (влево/вправо), а также временем окончания поворота. В случае, если это время больше времени поворота на 90°, то в начале траектории движения присутствует участок с обратным направлением ускорения продолжительностью [время окончания поворота] − [время поворота на 90°].

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

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

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

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

Первая версия


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


Первый раунд


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

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

Играющая в первой части первого раунда 8-я версия от 7-й отличалась минимально, однако одно из изменений оказалось решающим. Убрав затухание по времени при расчете вероятности перехвата шайбы врагом я добился того, что мои хоккеисты перестали «тупить» перед воротами противника, ожидая непонятно чего. На вторую часть первого раунда я добавил оценку пасов с отскоком от горизонтальных бортов. Для этого целевая точка отражалась от нужного борта с учетом коэффициента отскока. 8-я и 9-я версии стратегии дали мне 6-е место в первом раунде и, в целом, показали, что я на верном пути.

Второй раунд


В 10-й версии я занимался адаптацией стратегии к изменениям правил во втором раунде и, заодно, финале (правда, без учета изменения выносливости во время предсказания). А вот в 11-й версии добавилось то, что, в конечном счете, и принесло мне победу в конкурсе.

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

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

Финал


В 12-й версии я, по-быстрому, реализовал логику замен для финала: QuickStartGuy-образное следование в область замен на «вне игры» и немного модифицированный алгоритм следования в точку для замен в процессе игры. А дальше я засел реализовывать разные мелкие задумки, которые образовывались у меня в процессе чемпионата. Перечислю их в хронологическом порядке.
  • Добавил штраф за перенос шайбы в место, с которого враг может ее выбить прямо мне в ворота.
  • Добавил логику игры в овертайме без вратарей: поправил оценку сектора попадания и немного задвинул защитника вглубь ворот. При обновлении кода расчета углов заметил вышеупомянутый баг с завышенным сектором попадания и исправил его.
  • Реализовал нормальную обработку состояния замаха: раньше я просто выполнял замах на запомненное количество тиков, теперь провожу полный перебор на выбор оптимального момента прекращения замаха.
  • Реализовал учет вероятности перехвата каждым отдельным хоккеистом противника, а не всех скопом, как раньше.
  • В процессе выхода на целевую позицию стал стремиться держать ориентацию не на конечное направление, а на конкретную точку. Это решило проблему с долгим скольжением хоккеиста до целевой точки, при котором оставались дыры в защите, а также убрало залипания, когда защитник не мог решить, в какую сторону ему поворачиваться.
  • Сделал более точную, чем грубая карта достижимости, оценку секторов перехвата шайбы на первые пару десятков шагов.
  • Добавил защиту от голов в одно касание — в случае свободнолетящей шайбы прогоняя алгоритм оптимизации за врага и обновляя предсказанную позицию шайбы. Этот алгоритм добавил негативный побочный эффект — казалось бы, совсем безопасная траектория шайбы причислялась к опасным и мои хоккеисты стали пытаться выбивать шайбу, вместо того, чтобы просто подобрать.

Изменение силы игры от каждого из этих улучшений в отдельности было не заметно, однако все вместе они дали двукратный отрыв по голам 13-й версии от 12-й на длинных матчах. Все эти улучшения в составе стратегии 13-й версии играли в первой части финала, однако я (и не только я) заметил достаточно большое количество голов в свои ворота из-за побочного эффекта. А т. к. моя стратегия шла вровень со своим основным конкурентом, я решил, что даже такое небольшое количество голов может определить победителя. Поэтому в 14-й версии, которая играла во второй части финала, я добавил штраф за попытку выбивать шайбу в свои ворота. То ли это изменение, то ли изменения стратегии конкурента (я больше склоняюсь ко второй версии), позволили моей стратегии уйти в отрыв, а мне стать двукратным победителем чемпионата Russian AI Cup.

Послесловие


Отрыв моей стратегии от соперников в этом году оказался гораздо серьезнее, чем это было в танках. Я уверенно держался на первом месте песочницы до ее закрытия, чего в 2012 мне сделать не удалось. Тогда, в результате случайных колебаний, я даже не попал в призеры песочницы. Правда, дополнительный приз мне все равно не достался, но уже не из-за слабости стратегии, а благодаря новым правилам.

Смотреть бои можно в моем профиле.
Исходный код стратегии доступен здесь.
Моя старая статья за 2012 год (танки).
Вабищевич Николай @DrSmile
карма
63,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (17)

  • +5
    Мда, я понял, как мне было далеко до финала…
  • 0
    Так как работает отскок от стены, а?
    Каждый тик проверяется пересечение центром шайбы границ поля. Если произошло пересечение, то скорость инвертируется с умножением на 0.25. А вот координата — по разному. Если в следующий тик шайба просто вследствие инверса скорости попадает в поле, то все ОК. А вот если нет — там какая-то чудесная магия происходит, корелляцию я так ни с одним параметром и не увидел.
    А автор физику восстановил без декомпиляции локалраннера, просто глядя на изменения параметров? мощь.
    • +3
      Я восстанавливал физику следующим образом. Один хоккеист бегал, подбирал шайбу и бил ее в случайном направлении и так по кругу всю ночь :)
      В процессе я записывал все соударения шайбы со стеной(вектор входной скорости, вектор выходной скорости, об какой борт ударяемся) в файл.

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

      График зависимости угла отражения от угла падения и скорости. Видно, что от скорости угол отражения не зависит.


      График скорости отражения от угла падения и скорости падения.

      Видно :), что скорость отражения линейно зависит от скорости падения, а значит что нужно искать зависимость ускорения от угла падения.
      • 0
        Подождите, я все равно не понял. Изменение скорости — это всегда 1/4 от скорости ДО удара. Там без графиков за минуту это очевидным становится (но инструмент мне освоить надо, спасибо!). А вот изменение координаты на десяток пикселей, если шайба слишком глубоко погружается в стенку — вот тот чертополох мне непонятнен.
        • 0
          Ну у меня получилась нелинейная зависимость коэффициента поглощения от угла. Возможно у меня где-то закрался баг, возможно при углах близких к 45 градусам коэффициент не сильно отличается от 0.25, но при углах около 0 и 90 значение может быть другим. Возможно после бета теста, что-то поменялось. В целом, полет шайбы у меня предсказывался хорошо даже после нескольких соударений со стенками.

          Если за тик шайба ушла в стенку слишком далеко, то очевидно что ее нужно вытолкнуть. Это можно сделать несколькими способами, самый простой вытолкнуть шайбу точно до границы ринга и изменить ее вектор скорости. Примерно так и делалось в хоккее.
          • 0
            Неа, не до конца ты разобрался. Там каждый тик идет проверка — где мы? За полем, ок, _просто инвертируем скорость_. Т.е. шайба уже за полем, а мы целый тик только скорость инвертнули. Ок, на след тик она поехала в обратном направлении. Если выехала в ринг обратно — все хорошо, нехай катится. А вот если нет — координата меняется вручную. А как — фиг поймаешь. Есть только ощущение, что как-то строится нормаль к стенке, берутся отношения отрезков радиуса и т.д. В общем — магия!
    • 0
      Детальные формулы можно посмотреть в исходниках. Например, отскок от верхней стенки:

      constexpr double wallBounce = 0.25;
      constexpr double minDepth = 0.01, depthFactor = 0.8;
      
      if((delta = rinkTop + puckRad - pos.y) > 0)
      {
          if(spd.y < 0)spd.y *= -wallBounce;
          if(spd.y < delta)pos.y += depthFactor * (delta - minDepth);
      }
      

      И да, я тоже восстанавливал экспериментами и анализом логов в экселе. Правда, уже был опыт с танками, так что не совсем с нуля начинал.
      • 0
        А вот есть ощущение, что весь этот цирк — необходим был? Почему не сделать тупо «оптическое» отражение шайбы от борта? Зачем все эти расчеты непонятные, дающие +-5точек? Уверен, что на поведение шайбы это бы не сказалось _никак_.
        • 0
          Ну так я, вроде, и написал в статье, что эти мелочи не важны были. Просто, если у меня уже есть рабочая формула, зачем ее упрощать, рискуя что-то сломать?
  • 0
    И я ничего не понял про главный алгоритм :-( «Параметризуется» — значит интерполяция, т.е. перебор не по набору ускорений [-1, 0, 1]? Что значит абзац про выход под определенным углом и соезинение двух траекторий коцами? :-(
    • 0
      Все ускорения фиксированы, рассматривается только минимум и максимум, а для поворота еще и ноль. Оптимизация идет по времени переключения с одного режима на другой.

      Траектория первого типа — это, например, 15 тиков полный вперед и влево, а потом просто полный вперед.
      Или 10 тиков полный вперед и вправо, потом 30 тиков (поворот на 90°) полный назад и вправо, потом просто полный назад. В первом варианте 15 тиков поворота, во втором 40 — по этому параметру и ведется начальный перебор.

      Траектория второго типа — это одна траектория первого типа плюс еще одна, но назад по времени.
      Например, 15 тиков полный вперед и влево, потом полный вперед 50 тиков, потом 20 тиков полный вперед и вправо.
      Тут параметры — это 15 тиков первого поворота и 65 тиков — начало второго поворота.
  • +1
    Отличная работа. А сколько часов (хотя бы примерно), у вас ушло на все работы по конкурсу, если не секрет?
    • +2
      Специально не считал, но, думаю, несколько суток полного времени наберется. Особенно напряженными были дни перед раундами.
  • 0
    Вот как значит оказывается, кого-то физика отпугивает, а кого-то наоборот привлекает.
    Я вот (GreenTea) из-за необходимости реверс инжиниринга физики вообще решил не участвовать… Как-то этот класс задач не особо интересен.

    Но за статью все равно спасибо, было интересно почитать.
    Если действительно на все это ушло в сумме по времени только несколько дней — то ты мегамонстр! :)
  • 0
    Случайность добавляет сложности точного предсказания (делает его принципиально невозможным), однако это плохой, «читерский» способ. Настоящая «глубокая» физика позволяет строить все более точные модели (ценой вычислительной сложности или более продвинутых алгоритмов), случайность же не дает этой глубины.

    ВОт это мощная мысль, до которой я не додумался, предлагая ввести случайную составляющую. Посмотрел еще твои комментарии к другим топикам — жалко ты чаще не пишешь…
  • +2
    Я разочарован… собрали статистику, выявили физику, построили модель, и где здесь AI?
    • 0
      Зависит от того как вы понимаете термин AI. Многие его понимают как нечто что обязательно должно самообучаться, но это не всего так. Если посмотреть статью на вики то там видим такое определение:
      Major AI researchers and textbooks define this field as «the study and design of intelligent agents»,where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success.

      Intelligent agent — хоккеисты.
      environement — поле, шайба, правила игры, хоккеисты соперника, физика мира.
      actions — действия хоккеистов.
      Так что формально это и есть AI.

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