Tuesday, July 17, 2012

Теория командных турниров – Игра в паринги с полной информацией


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


Команда оппонентов
GK
CSM
Eld
Tyr
BA
DE
Наши бойцы
Eld
5
13
10
15
11
6
IG
13
13
16
2
4
16
Dae
15
5
3
2
14
3
GK
9
14
13
14
8
13
SM
6
5
6
9
16
4
SW
6
14
17
16
10
14

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


Если мы играем в паринги без назначения чемпионов и оба капитана одинаково оценивают ожидания игр, то мы можем просчитать все 518400 вариантов парингов для наших команд и, зная, что каждый капитан принимает решения для максимизации своего выйгрыша получим, что:
1. В случае если мы защищаемся первыми, то мы наберём всего 53 очка.
2. В случае если первым выставляет защитника команда оппонентов, то мы наберём 66 очков.
Таким образом, у нас есть минимальное отставание от команды оппонентов на уровне композиции. Можно считать такую игру «игрой с равными композициями».

Попробую пояснить на примере, чем отличается оптимальная минимаксная стратегия от простого назначения «лучшего дефендера и лучшего атакера».

Предположим, что мы проиграли кубовку и должны выставить первого защитника. Попробуем разыграть паринги по принципу «сразу ставим лучшего защитника, потом лучшего атакера на защитника оппонента». Оппонент будет вести себя точно так же.
Итак, первый наш лучший защитник – это ГК. Оппонент не сможет выбить из него больше 12 очков в свою пользу.
Соответственно оппонент ставит в атаку на нашего ГК своих БА, чтобы забрать 12 очков. Мы получаем 8 очков.
Лучший защитник оппонента после этого – CSM. Мы можем набрать максимум 14 очков на таком защитнике. Соответственно, мы ставим в атаку СВ и дальше будем защищаться Эльдарами. В итоге получим вот такую табличку парингов:

1
GK
8
BA
2
4
SW
14
CSM
3
5
Eld
5
GK
6
8
SM
9
Tyr
7
9
IG
16
DE
10
12
Dae
3
Eld
11
=55

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

Сумма всех игр получилась равной 55 очков. С одной стороны это больше, чем то, что мы получили бы, если бы оппонент играл по минимаксной стратегии. Но оппонент допустил ошибку, играя не по оптимальной стратегии.
Давайте попробуем сами сыграть по минимаксной стратегии и, тем самым, выжать максимум из ошибки оппонента.
Я не буду приводить сложные алгоритмы расчёта оптимальной минимаксной стратегии, просто предположим что мой алгоритм правильный:)
1. Итак, согласно оптимальной стратегии, наш первый защитник – ГК. Это совпадает с предыдущим раскладом, что не удивительно в целом.
2. Противник действует так же, как и в прошлом случае и ставит в атаку на ГК лучшего атакера – БА.
3. В защиту противник ставит CSM, как лучшего своего защитника. Это ошибка нашего оппонента, в минимаксной стратегии он должен был выставить в защиту Эльдар или ДЭ. Посмотрим, к чему это приведёт.
4. Пересчитав оптимальную стратегию после хода оппонента мы однозначно выставляем в атаку на CSM наших Эльдар! Это даст нам возможность позже реализовать потенциал наших СВ в атаке!
5. Неожиданно, казалось бы, в защиту выходят SM. Эти парни не много принесут в атаке и не много сольют в защите, пусть они и не кажутся лучшими защитниками, но это оптимальный выбор согласно минимаксной стратегии.
6. Лучший атакер оппонента на СМ это ДЭ.
7. Лучшая защита оппонента на этом ходу это ГК.
8. Мы реализуем нашу отличную атаку Демонами на ГК и остальной розыгрыш уже не важен.

Вот как выглядит итоговая таблица:

1
GK
8
BA
2
4
Eld
13
CSM
3
5
SM
4
DE
6
8
Dae
15
GK
7
9
IG
2
Tyr
10
12
SW
17
Eld
11
=59

Мы набрали на 4 очка больше, чем при прямолинейной игре в лучший дефендер  - лучший атакер. А 4 очка это разница между поражением и ничьей. Кроме того, в сравнении с минимаксной стратегией мы набрали на 6 очков больше!! Тем самым одна ошибка оппонента стоила ему преимущества на уровне композиции после выйгранной кубовки!

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

1 comment:

  1. Если не придираться к приведенным примерам - все три статьи очень хороши. Спасибо.

    Джонни.

    p.s.
    Тулбокс - не обязательно сильный сингловый ростер. Это просто более, или менее all-round ростер.

    ReplyDelete