gt_lec4_dyn

Динамические игры

    Отличаются от статических ("камень-ножницы-бумага").
    
    Пример. Выбор градоначальника, четыре кандидата -- A, B, C, D.
    Есть три коммуны, и в силу традиций они делают выбор по очереди.
    Сначала представители первой вычёркивают одного из кандидатов, потом второй, потом третьей, оставшийся кандидат считается выбранным.
    У каждой коммуны есть предпочтения:
    
    I   II   III
    A   C    D
    B   A    B
    C   B    С
    D   D    A
    
    Наивный вариант поведения: считать, что никто не просчитывает ходы других игроков. Тогда стратегия -- вычёркивать наименее предпочтительного кандидата из оставшихся.
    
    Стратегический вариант поведения учитывает последствия того или иного выбора. Предположим, что I планирует свой ход. Пусть она вычеркнет самого желанного кандидата A. Вторая вычеркнет D, а третья -- C. Тогда для первой и третьей получится более предпочтительный вариант.
    
    Обычно рассмотрение динамических игр подразумевает построение дерева:
             
             AB
             AC          
             BC
         ABC AB
    ABCD ABD AD
         ACD BD
         BCD AC
             AD
             CD
             BC
             BD
             CD
             
    Очевидно, один и тот же результат игрок может получить разными последовательностями ходов.
    
    Такие игры решаются с помощью принципа Цермело -- рассмотрением всех вариантов за один ход до окончания игры.
    
             B
             C          
             B
         ABC B
    ABCD ABD D
         ACD D
         BCD C
             D
             D
             B
             D
             D

         C
    ABCD B
         C
         B
         
    Пример: пираты и золотые слитки. На корабле есть семь пиратов, у каждого есть ранг 1..7, самый сильный с рангом 1. Они сходили в рейд и получили 50 золотых слитков. Дележ происходит так: самый старший пират предлагает свой вариант [a1, a2, ..., a7]. Если хотя бы половина оставшихся согласна, то такой вариант и выбирается, иначе старшего пирата убивают, и продолжается то же самое со следующим по старшинству -- [a2, .., a7]. Если остались только 6-й и 7-й, то будет выбран вариант [50, 0]. 
    
        Тут тоже используется принцип Цермело, но дерево не строят, оно большое.
        
        Пятый может предложить [49, 0, 1].
        
        Четвёртый тогда должен предложить [47, 0, 1, 2]
        
        Третий: [47, 0, 1, 2, 0].
        
        Второй: [46, 0, 1, 2, 0, 1].
        
        У первого уже есть варианты:
            [46, 0, 1, 2, 0, 1, 0]
            [46, 0, 1, 0, 0, 1, 2]
            
        Если бы пиратов было восемь, то у первого была бы неопределённость.
        
        Немного упростим правила. Предположим, что если остаётся двое, то они делят добычу пополам [25, 25].
        Тогда уже у пятого есть выбор:
            [24, 26, 0]
            [24, 0, 26]
            
        И у четвёртого:
            [24, 25, 0, 1]
            [24, 25, 1, 0]
            , и ни один из вариантов не даёт гарантированного выигрыша.
            
        Хотя решения пятого пирата симметричны, само наличие у него вариантов не даёт четвёртому игроку сделать выигрышный ход. Это открытая проблема игр с множеством равновесий.
    
    Рассмотрим сначала динамические игры с полной (совершенной) информацией.
    
        Для формализации задаётся список игроков (N) и дерево игры (Г).
        
        Обычно обозначают A множество всех рёбер, A(x) -- рёбра, идущие вниз из х. Множество терминальных вершин T = { x in X | A(x) = 0 }.
        Каждой терминальной игре сопоставляется некоторый выигрыш: u: T -> R^n.
        u(t) = (u1t, ..., unt) in R^n.
        
        И ещё есть отображение I: X\T -> N,
        Xi = I^(-1)(i) = { x in X | в x ходит игрок i }.
        
        Решение такой игры всегда находится с конца согласно принципу Цермело.
        И получается, что каждую вершину можно заменить на одну из терминальных.
        
        Для разрешения неопределённостей рассматриваются все варианты.

        Класс бинарных игр -- игры для двух игроков, в которых выигрывает не более чем один.
        Шашки к таким не относятся, потому что допускается ничья с бесконечным повторением ходов.
        В любой бинарной игре победитель известен заранее.
        
    "Детские игры" или кто выигрывает при правильной игре
    
        Выигрышная стратегия часто не показывается в явном виде. Но в некоторых играх -- "детских" -- теория игр может дать ещё и способ выиграть.
        
        N камней, два игрока берут по очереди количество камней, равное степень двойки. Игрок, забравший последний камень, выигрывает.
        Здесь проигрывает игрок, в позиции которого количество камней делится на три.
        
        Игра "Ним". Дано конечное число кучек с камнями, в каждой конечное количество камней. Каждый по очереди берёт из одной кучки любое количество камней. Проигрывает тот, кто берёт последний камень. 
        
        Рассмотрим частный случай:
        
        (3, 2, 1)  (0, 2, 1)  (0, 1, 1)
                              (0, 0, 1)
                              (0, 2, 0)
                   (1, 2, 1)  (0, 2, 1)
                              (1, 1, 1)
                              (1, 0, 1)
                              (1, 2, 0)
                   (2, 2, 1)  ...
                   (3, 0, 1)  ...
                   (3, 1, 1)  ...
                   (3, 2, 0)  ...
                   
        Игра "Гексагон"
            
            Игровое поле -- ромбическая область из шестиугольных полей.
            С нижнего левого и верхнего правого края ромба -- территория первого игрока, с двух других сторон -- второго. Игроки выкладывают на гексы фишки, и цель -- построить путь между своими двумя сторонами.
            Очевидно, что оба победить не могут.
            
            Предположим, что выигрышная стратегия есть у второго игрока. Если так, то первый игрок может начать копировать стратегию второго игрока зеркально, считая, что первый ход совершён в какое-то ещё не занятое поле.
            
            Но на данный момент способа получить выигрышную стратегию для первого игрока в общем случае нет.