Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Categories:

Google AI Challenge

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

Я вот прямо об этом защищал диссертацию, которую никто нигде не применяет, к сожалению, потому что Россия что-то передумала готовиться к атомной войне с участием Скайнета, Периметра и ОБЧР.

В контесте я бы воспользовался плодами науки, и сделал бы вот что.
Сначала написал бы обычный минимаксный обход дерева, но с необычными "ходами". Каждый "ход" в нашем переборе будет состоять из нескольких тактов игры (чтобы не путать, обозначим их БХ - Большой Ход и МХ - маленький ход). На каждом полу-БХ (читать: большой полуход) соответствующий игрок выбирает свою тактику, после чего оба разыгрывают свою текущую тактику до тех пор, пока БХ не закончится. Полу-БХ считается закончившимся, когда прошло сколько-то МХ (сколько именно - нужно подбирать), либо когда мы достигли точки бифуркации, например, сменился владелец планеты.

Тактика - это некоторый тупой hardcoded алгоритм из ограниченного набора. Например: ничего не делать, сидеть и копить силы; осуществлять экспансию всеми силами; завоевывать (или оборонять) такую-то планету и т.п. На каждом полу-БХ имеет смысл перебирать некоторое не очень большое количество тактик.

Смысл всего этого примерно такой: пусть мы не можем перебирать в глубину всё дерево МХ, но мы всё же можем пройтись по нему "крупноячеистой сетью".

Ну вот, сначала мы сделаем вот такое, и оно уже будет играть хорошо, лучше "любительских" жестко впаянных стратегий. Но потом мы сделаем еще три вещи: 1) подберем правильный набор тактик, 2) настроим "стратегический модуль", который на полуходе выбирает из этой кучи несколько наиболее разумных, и 3) настроим оценочную функцию (и у нас, и у противника есть несколько величин - размер флота, прирост, общее число планет и т.п.; как их правильно скомбинировать?)

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

1 вот как: мы реализуем сразу очень много возможных тактик (например, параметризацией), после чего будем на каждом полу-БХ тестировать часть из них случайным образом и смотреть, какие зажигают, а какие нет. Отправим программу много-много раз играть с каким-то быстрым, но не очень тупым автоматом (лучше не с самой собой). Окажется, что некоторые тактики вообще никогда не выбираются в качестве лучших для полу-БХ, а некоторые - наоборот, очень часто. Упорядочим тактики по тому, насколько часто они выбирались. Перебирать их именно в этом порядке, с линией отреза в зависимости от имеющихся выч.ресурсов - уже само по себе нормальный стратегический модуль. Пришла в голову идея новой тактики или обнаружился баг в старой? Отлично, для начала вообще не думаем, как бы это учесть в "стратегическом модуле", а сразу пишем, запускаем, и смотрим, куда она попадёт в этом списке.

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

Наконец, 3: фактическии, наша задача - найти такую оценочную функцию, которая хорошо предсказывает саму себя при более глубоком переборе. Тут есть один подводный камень: лучше всего сам себя предсказывает тождественный ноль, поэтому её нужно как-то стабилизировать. Например, в неё всегда должен входить член "суммарное число моих кораблей" с коэффициентом единица.

Сим победиши
Tags: 2017, gamedev, soft
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 13 comments