Как составить алгоритм выбора наиболее эффективной команды героев?

Question

[Евгений Иванов]

Интересуют ваши размышления, предложения или даже решения поставленной задачи.
Задача поставлена (придумана) мной.

Существует много компьютерных игр, где герои сражаются друг с другом. Известно, что один герой эффективен относительно другого.
Пусть эффективность героя определяется числом от 0 до 100. Где 0 - абсолютно неэффективен, а 100 максимально эффективен.
Пусть всего 4 героя. Пусть можно выбрать команду из 3х героев. Герои могут быть не уникальными (можно выбрать 3 одинаковых героя).
Бои идет команда на команду (3 на 3).

Пример таблицы эффективности

Например:
Герой1 эффективен относительно Героя1 на 50 единиц. Проще говоря, при их битве шансы на победу 50 единиц из 100 возможных (50%). Что логично.
Герой1 эффективен относительно Героя2 на 60 единиц. Т.е. при битве Героя1 с Героем2 шансы на победу Героя1 60 единиц. Наверно Герой1 победит...
Герой2 эффективен относительно Героя1 на 40 единиц.

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

Answer 1

[Андрей]

Если команда противника уже определена, а размеры команд такие, какие Вы описали (скажем до 5-6 персонажей), то полным перебором. (Вы кстати не рассказали о правилах ведения боя - один на один один бой или выживший может помогать другим "коллегам" и т.п.)

Если команда противника еще не определена, то теория игр и минимаксный подход.

Comments

[Евгений Иванов]

Что значит полный перебор? Кого и как перебирать? Пока неясно.

Команда определена. Все герои противника известны. Пусть всего 3 героя в любой из команд. Всего героев 4.
Если мы говорим о командах, разумеется - бой команда на команду.

Answer 2

[xmoonlight]

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

S=(A1-B1)+(A1-B2)+(A1-B3) > 0 => ∞

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

Я бы еще добавил такие параметры (коэффициенты, которые ещё нужно более детально прорабатывать), как:
1. урон атаки каждым из возможных способов атаки (АТАКА)
2. время перезарядки каждого из возможных способов
3. возможность атаки каждого типа цели
4. дальность атаки до каждого типа цели
5. защита каждым из возможных способов (ЗАЩИТА)
6. время восстановления защиты каждого из возможных способов защиты
7. возможность защиты от каждого типа атаки
8. скорость передвижения каждым из возможных способов (ПЕРЕДВИЖЕНИЕ)
9. свобода передвижения (полная - когда летает, частичная - зависит от ландшафта, стационарная - например, защитная турель или бункер)

При пошаговой игре: время перезарядки может быть рассчитано, как количество атак за ход.
Большая разница тут: ПОШАГОВЫЙ или REAL-TIME бой.
Я тут вспомню про старик (StarCraft - RTS от Blizzard):
1. Когда загораживают выход двумя MCV (рабы) которые умеют друг друга чинить, а за ними ставят пару маринов, которые отбивают полчища, пока те атакуют рабов. Вроде бы, при любом расчёте: убить 2-х маринов и 2-х рабов - не проблема, если у тебя 6 маринов и при любом просчёте - это будет явно видно!
Однако, как показывает реальность: всё зависит от конкретного ландшафта/местности и умения стратегически мыслить.
2. Маринов ставят за здания полукругом с равным удалением для одновременной атаки перед входом, если атакуют войска ближнего боя (например, зерлинги): сделано, чтобы те, кто вбегает : оказывается сразу под огнём всех маринов и, чтобы убить всех этих маринов, нужно атаковать одновременно каждого с небольшим превосходством, что сделать мышью - практически нереально.
3. Банальный лабиринт: когда есть узкий проход и в ближнем бое может участвовать лишь несколько единиц, остальные стоят и ждут (или умирают под обстрелом).
Варианты создания лабиринта: узкие проходы на местности, специфичная застройка, специфичная организация войсковых единиц (юнитов) или любые сочетания всего перечисленного.

Многое зависит от доп.данных и по этой таблице - не возможно ответить на Ваш вопрос. Нужны ещё данные.

Comments

[Евгений Иванов]

Вы не правы.
Мой вопрос носит чисто математический - алгоритмический характер.
Заметьте, я не говорил про бой. Я говорил про пик, когда изначально известна эффективность героев. Я уже определил её в таблице.

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

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

PS
Про SC2 можете писать любым текстом, что угодно. Пойму.

[xmoonlight]

logpol32: (я по опыту с SC BroodWar писал)
Выбор, чтобы понять: "сможет ли выбранный герой кого-то победить?" можно определить так: суммарная эффективность (сумма разниц показателей урона выбранного героя с героями противника) выбранных героев должна быть больше нуля.
S=(A1-B1)+(A1-B2)+(A1-B3) > 0

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

[abcd0x00]

xmoonlight:

Маринов ставят за здания полукругом с равным удалением для одновременной атаки перед входом

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

Оффтоп немного, но не смог удержаться.

[Евгений Иванов]

S=(A1-B1)+(A1-B2)+(A1-B3) > 0
Стандартное решение. Я сам предполагал, что для выбора (каждого) героя из своей команды, нужно искать наибольшую сумму - наибольшую эффективность относительно всех героев противника. Просто и логично.

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

Но меня не покидает чувство, что это решение не до конца верно. В рамках указанной задачи, разумеется. Может я и ошибаюсь.

В любом случае, спасибо за ответ.

[xmoonlight]

logpol32: дальше - уже коэффициенты: стоимость, лимиты, скорость атаки и т.д. пока нет этих параметров - эта формула по сути своей - бесполезна и всё верно: ваше чувство Вас не обманывает.

[xmoonlight]

abcd0x00: перечитал 3 раза, затем понял: Вы не так поняли!)))
Уточняю: перед входом в свою базу, а не перед входом на базу противника)
Ну и конечно, перед маринами - строения обязательно, чтобы увеличить длину траектории при атаке маринов с прямой на изогнутую и выиграть таким образом время на продолжительность выстрелов.
Лучше всего - узкий "змеиный" выход с базы)

[abcd0x00]

xmoonlight: до базы противника мы ещё не дошли даже; пока строим оборону. И ты говоришь что-то там выстраивать. Когда волна пойдёт, там такая канитель начнётся, что тебе не до кружков будет. Ты не можешь взять и сказать им "выстройтесь в кружок", ты даже их в линию не построишь (во всяких Age of Empires можно порядки делать сразу и линии, и клин). У тебя, короче, кучки, а кучки привязаны к клавишам (группы). И вот группы можно поставить типа кружком, но это всё равно неудобно. У тебя сами бункеры должны правильно стоять, а не солдатики. Потому что солдатики - сейчас они есть, через пять минут их завалили, три осталось из каких-нибудь 15.

[xmoonlight]

abcd0x00: в этом и есть искусство и одновременно сложность игры, когда RTS превращается в RPG, можно расставлять мышкой, но надо это делать на полном автомате и быстро. И точки выхода из бараков правильно должны быть спланированы сразу, чтобы не искать при расстановке.
При игре в стратегию - мышь и клавиатура (hot-keys) должны работать синхронно и без остановки. (а не только на группы)
Иногда даже применяют комбо-hot-keys, которые сразу делают несколько действий с клавой и мышью. (но это, разумеется, запрещено на соревнованиях)

[abcd0x00]

xmoonlight:

И точки выхода из бараков правильно должны быть спланированы сразу

Хаха, у тебя ещё точки выхода, у меня бараки вообще используются для удара часто. То есть ты их перемещаешь - бам-бам-бам - потом опять перемещаешь. Видал такое? Подвёл бараки, нагенерил людей, увёл бараки, там тут же бункер ставится. А пока стройка идёт, люди защищают строителя, который после постройки сразу в бункер залазит.

[xmoonlight]

abcd0x00: ну как режим смены цели для врага - да. конечно делаю так. пока по нему стреляют - можно чинить и таким образом долго отвлекать огонь от своих юнитов.

[abcd0x00]

xmoonlight: а против человека не играл? А то режим цели для врага - это только для компа сработает. Человек проскочит такой финт.

[xmoonlight]

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

[abcd0x00]

xmoonlight: да человек тем и отличается, что он не заводит солдат, а потом они там сами стреляют, а он может атаковать вручную всей группой сначала одного, потом второго, пока всех не перещёлкает. То же самое касается строителей, я подошёл 15 солдатами застрелил одного и всё. Даже если его чинят, он всё равно не выдержит. А комп - да, он будет атаковать их вразброс и задержится.