?

Log in

Google AI Challenge - Не кинокритик. Не палеонтолог.

окт. 14, 2010

02:16 pm - Google AI Challenge

Previous Entry Поделиться Next Entry

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

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

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

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

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

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

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

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

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

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

Сим победиши

Tags: , ,

Comments:

From:ext_285022
Date:Октябрь 14, 2010 11:06 am
(Link)
Спасибо, очень интересный подход. Но.

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

Точками бифуркации будут не только случаи захвата планеты, но и вылеты достаточно больших флотов, а значит БХ будут завершаться слишком быстро, и перебор далеко не продвинется.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Октябрь 14, 2010 11:15 am
(Link)
> Свой полу-БХ и полу-БХ противника исполняются параллельно,
> поэтому минимакс (как и максимин) не прокатят
Это уже нужно смотреть по ситуации. В футболе роботов получалось так, что минимакс и максимин - практически всегда одно и то же, поэтому затруднение кажущееся. Тут не совсем футбол, конечно.

Еще, как вариант, если БХ завершается по timeout'у, то очередность можно ввести прямо "шахматную", а если в точке бифуркации - отдавать право перевыбора стратегии тому, кто планету потерял.

> Точками бифуркации будут не только случаи захвата планеты,
> но и вылеты достаточно больших флотов
Обходится, если есть класс тактик (ну или "аспект") "защищаться", который реагирует на такие события штатным образом.
(Ответить) (Parent) (Thread)
[User Picture]
From:dabino
Date:Октябрь 14, 2010 12:30 pm
(Link)
О, спасибо за такой развернутый ответ (думаю, что если бы время на написание поста было инвестировано в код, то в топ100 попал бы точно 8)). Для меня этот как раз развлечение и отвлечение от основной деятельности.

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

Думаю над тем, как по-научному свести вектор возможных ходов (размерности примерно число планет^2) к меньшему базису из независимых координат. И уже в них искать/ветвиться.
(Ответить) (Thread)
From:(Anonymous)
Date:Октябрь 21, 2010 08:24 pm
(Link)
сейчас в топ100 попасть уже не так тривиально.

Один из моих ботов 20-21 сентября был в топ10 (пару часов держался на 7 месте), теперь он на грани вылета из пятой сотни
(Ответить) (Parent) (Thread)
[User Picture]
From:avkh
Date:Октябрь 14, 2010 12:33 pm
(Link)
играл в очень-очень похожую флешовую игруху, ребёнок мой
http://armorgames.com/play/2675/phage-wars
тут противники могут отличаться в параметрах
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Октябрь 14, 2010 12:51 pm
(Link)
клёво!
(Ответить) (Parent) (Thread)
[User Picture]
From:scmorr
Date:Октябрь 14, 2010 02:04 pm
(Link)
Таких на самом деле много. Самая крутая реализация http://www.kongregate.com/games/tjcarlos/civilizations-wars
(Ответить) (Parent) (Thread)
[User Picture]
From:avkh
Date:Октябрь 14, 2010 12:34 pm
(Link)
.. ребёнок мой её очень любит ..
(Ответить) (Thread)
[User Picture]
From:druxa_druxa
Date:Октябрь 14, 2010 05:54 pm
(Link)
> Искренне завидую тем, кто найдет время поучаствовать.
хватит оправданий, давай уже участвуй!!
(Ответить) (Thread)
[User Picture]
From:bortengineer
Date:Октябрь 14, 2010 06:27 pm
(Link)
А я просто вчера ночью написал наитупейший жадный алгоритм, который просто пытается зохавать самые вкусные планеты, забивая на их местоположение и возможные действия противника :) Конечно, атомной войной тут и не пахнет, но всё равно получил большое удовольствие от пары часов фофан программирования :)

http://ai-contest.com/profile.php?user_id=11225
(Ответить) (Thread)
From:(Anonymous)
Date:Октябрь 22, 2010 08:39 pm
(Link)
попал в топ10.

насколько могу судить, научный подход использован не был.

прогноз состояния на несколько ходов ( в моем случае - 40 )
защита своих планет
виртуальная защита ( от потенциальной атаки )
экспансия - последовательная, на базе нетривиальной оценочной функции, с использование коллекторов
перегруппировка войск к точкам экспансии

атаки как таковой нет, просто захватывать вражеские планеты в 2 раза выгоднее :)

смены состояний ( атака, защита, накопление, экспансия ) тоже нет ( хотя в первых версиях были ).

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

в коде у меня полное мракобесие ( в пике было около 4000 строк ), поэтому по окончании контеста с удовольствием ознакомился бы с лаконичными ботами из топ100.

//привет от бывших нивальцев
(Ответить) (Parent) (Thread)
From:(Anonymous)
Date:Октябрь 28, 2010 06:27 pm
(Link)
Такое ощущение, что выбор даже самой оптимальной из нескольких тупых тактик -будет проигрывать одной, но не очень тупой. Тем более если эти тупые тактики будут выбираться по результатам сражения с не менее тупыми. А если эти тактики будут не тупыми... то секунда - это вроде не очень много. Сколько полу-БХ можно успеть сделать? Сомневаюсь, чтоб больше 1000-10000.
С другой стороны перебор, чтоб польза какая-то от него была как-то прикрутить хочется.
(Ответить) (Thread)
[User Picture]
From:xoposhiy
Date:Февраль 23, 2011 11:08 am
(Link)
Я похожую идею использовал в sapka-contest 2009.
http://xoposhiy.livejournal.com/60162.html

Только до БХ не додумался, а сравнивал тактики на каждом МХ. Как следствие:

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

После контеста я уже и сам вышел в каком-то виде на идею БХ. :)
(Ответить) (Thread)