По многочисленным просьбам попробую наглядно продемонстрировать что же такое минимаксная стратегия. Возьмём игру 3 на 3 игрока для простоты. Всего в такой игре получается 3*3*2*2 = 36 вариантов исходов. Но не все они удовлетворяют нас и нашего соперника. Рассмотрим таблицу ожиданий:
В нашей команде 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
Предоставляю вам самим возможность посчитать минимаксную стратегию для варианта, когда первым ходит наш оппонент и убедиться, что мы наберём МЕНЬШЕ очков, чем если будем ходить первыми сами.
| 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
Предоставляю вам самим возможность посчитать минимаксную стратегию для варианта, когда первым ходит наш оппонент и убедиться, что мы наберём МЕНЬШЕ очков, чем если будем ходить первыми сами.
No comments:
Post a Comment