Статистика улья:

Число моделей (из них покрашено): 267 (246); Турнирные игры (Победы - Ничьи - Поражения): 34 - 16 - 13

среда, 18 июля 2012 г.

Теория командных турниров – Расчёт минимаксной стратегии

По многочисленным просьбам попробую наглядно продемонстрировать что же такое минимаксная стратегия. Возьмём игру 3 на 3 игрока для простоты. Всего в такой игре получается 3*3*2*2 = 36 вариантов исходов. Но не все они удовлетворяют нас и нашего соперника. Рассмотрим таблицу ожиданий:


BA GK SB
IG 3 10 11
DE 16 8 2
Tyr 6 4 15



В нашей команде IG, DE, Tyr. У оппонента BA, GK, SB. Мы ходим первыми. Построим дерево вариантов хотя бы для одной ветки:


Начнём не сверху вниз, а снизу-вверх. От листочков к корням дерева, так сказать.

3rd attacker. Выбор третьего атакера очевиден. Всегда просто выбрать 1 вариант из 1. В крайней левой ветке выбор такого атакера противником принесёт нам 15 очков!

3rd defender. Выбор нами третьего дефендера такой же как и третьего атакера. Он единственный возможный и принесёт нам 15 очков.

2nd attacker. Выбор второго атакера за нами. Противник поставил в защиту ГК. Мы будем выбирать тот вариант который принесёт нам больше очков. Мы знаем, что если мы выберем ДЭ, то получим 15+8=23 очка. Если выберем Тиранидов, то получим 4+7=11 очков. Выбираем ДЭ!

2nd defender. Противник думает, что у него есть выбор. На самом деле легко увидеть что от выбора второго защитника противником ничего не зависит. Если он выберет ГК, то дальше мы пойдём по левой ветке и получим 15+8 очков. Легко увидеть что если он выберет СБ, то мы получим те же самые 15+8 очков. Ну, предположим, что он выберет ГК в таком случае.

1st attacker. Вот, впервые наш соперник хоть что-то выбирает и от его решения что-то зависит. Мы знаем, что если он выберет БА, то далее по какой бы он ветке ни пошёл мы получим 15+8+3 очка. Аналогично идя от конца к началу можно посчитать количество набранных очков для вариантов ГК и СБ - цифры приведены на рисунке. Противник делает свой выбор в пользу наименьшего числа - чем меньше наберём мы, тем больше возьмёт он! Выбирает БА!

1st defender. Итак, мы знаем, что если выберем ИГ, то противник выберет БА чтобы дать нам не больше чем 15+8+3 очка. Аналогичным образом просчитываются очки для ДЭ и Тиранидов и раз уж тут решение принимаем мы, то выбираем максимальное число - 15+8+3=26 очков.

Таким образом данная игра при нашем первом ходе приносит нам 26 очков и имеет два варианта стратегии:

1. IG-BA-GK-DE-TYR-SB
2. IG-BA-SB-TYR-DE-GK

Предоставляю вам самим возможность посчитать минимаксную стратегию для варианта, когда первым ходит наш оппонент и убедиться, что мы наберём МЕНЬШЕ очков, чем если будем ходить первыми сами.

Комментариев нет:

Отправить комментарий