Несовершенная информация: информационные множества и совершенство по подыграм

Важность для курса: высокая — даёт точный язык для главного инструмента дизайнера: что каждый игрок видит и чего не видит.

Суть простыми словами

Важно не только, кто ходит раньше, но и что каждый видит. Если ты не видишь хода соперника, это всё равно что ходить одновременно. Одна спрятанная деталь может поменять лучшую тактику. А хороший план годится для любой ситуации, даже той, что не случилась.

Что было на лекции

• Игр в этот день не было, только определения: как соединить одновременные и пошаговые игры.
• Пример. Игрок 1 выбирает «вверх», «середину» или «вниз», игрок 2 видит выбор и отвечает. После выбора «вверх» или «середина» игрок 2 «давит» игрока 1 (себе 4, ему 0), после «вниз» игрок 1 получает 1. Значит, игрок 1 идёт «вниз».
• Теперь игрок 2 не различает «вверх» и «середину». На дереве эти узлы соединяют пунктиром: это одно информационное множество. Игрок 1 может наугад, 50 на 50, выбирать «вверх» или «середину» и получать в среднем 2 вместо 1.
• Два запрета. В узлах одного множества набор действий одинаков, иначе игрок догадается, где он. И игрок помнит свои ходы (идеальная память). В жизни память подводит: Полак иногда сворачивает не на том светофоре по дороге домой.
• Дилемма заключённого рисуется деревом, где игрок 2 не видит хода игрока 1. Та же таблица выходит, если первым ходит игрок 2, а игрок 1 его хода не видит. Это одна игра. Вывод Полака: «важна информация, а не время».
• Пример с тремя равновесиями Нэша: (Uu, L), (Du, R), (Dd, R). Студент Патрик решил дерево с конца: разумно только (Dd, R). Два других держатся на ходе, которого игрок 1 не сделал бы, если бы до него дошло.
• Пример с тремя игроками. После хода B игроков 2 и 3 ждёт маленькая игра, где у игрока 3 есть доминирующая стратегия. Набор (A, вверх, влево) формально равновесие Нэша, но в маленькой игре предписывает неравновесные ходы. Разумно (B, вниз, вправо): игрок 1 получает 2 вместо 1.
• Подыгра: начинается в одном узле, включает всех его потомков и не разрезает информационные множества. Совершенное по подыграм равновесие: равновесие Нэша, которое даёт равновесие Нэша в каждой подыгре.

Главные понятия

• Информационное множество (information set) — узлы, между которыми игрок не может различить, где он.
• Совершенная и несовершенная информация (perfect / imperfect information) — в первой каждое множество из одного узла, во второй нет.
• Идеальная память (perfect recall) — игрок помнит всё, что сам делал и знал раньше.
• Развёрнутая и нормальная форма (extensive / normal form) — дерево и таблица. Одна таблица может прийти от разных деревьев.
• Подыгра (subgame) — часть дерева, которая сама по себе игра.
• Совершенное по подыграм равновесие (subgame perfect equilibrium, SPE) — равновесие Нэша, разумное в каждой подыгре, даже в той, куда не дошли.

Зерно для создателя игр

• Нарисуй, чего игрок не видит: какие ситуации он не может различить? Это его информационные множества. Туман войны, карты рубашкой вверх, одинаковое начало анимации у ударов сверху и снизу в файтинге превращают реакцию в угадывание.
• Одна скрытая деталь меняет лучшую тактику. В примере лекции безопасный ход за 1 очко уступил риску со средним 2. Если все играют скучно и безопасно, спрячь один бит.
• Ищи утечки. Правило об одинаковых действиях значит: если кнопка «обезвредить» появляется только у настоящей ловушки, тайны нет. Звук, задержка сети, подсветка интерфейса тоже выдают скрытый выбор, особенно в онлайне, где «одновременные» ходы приходят по очереди.
• Память игрока не идеальна. Длинным играм нужны журнал заданий и история ходов. А можно сделать забывание механикой, как в «Мемори».
• Проверяй игру по подыграм. Разбей её на самостоятельные части (схватка, раунд, финал) и разбери каждую, начиная с последней. Разумно ли там поступают ИИ и персонажи, даже если туда «никто не пойдёт»? Игроки пойдут.

Мини-игра для урока

«Монетка в кулаке» (по первому примеру лекции). 2 игрока, монетка, 10 минут.

• Игрок 1 выбирает: открыться (положить монетку на стол) или спрятать её в левой или правой руке.
• Открылся: игроку 1 одно очко, игроку 2 два.
• Спрятал: игрок 2 называет руку. Угадал, ему 4 очка. Не угадал, 4 очка игроку 1.
• Версия А: ладони открыты, игрок 2 видит монетку. Версия Б: кулаки закрыты. По 10 ходов в каждой, считай очки.
• Что заметить: ходы и очки те же, изменилось только то, что видит игрок 2. В версии А выгодно открываться: спрятанную монету всё равно найдут. В версии Б выгодно прятать, причём случайно (тайком подбрось вторую монетку): в среднем 2 очка за ход. Закономерность или выражение лица выдают тайну.
• В браузере: компьютер-угадчик ищет закономерности в выборе ученика.

Ошибки и заблуждения

• «Одновременно значит в одну секунду». Нет, это значит «не зная хода другого».
• «План может учитывать всё, что было». Только то, что игрок знает. Нельзя поступить по-разному в ситуациях, которые ты не различаешь.
• «Игрок всё помнит». Это допущение. Люди и организации забывают.

Для продвинутых

• Дерево игры с информационными множествами ввели фон Нейман и Моргенштерн (1944), развил Гарольд Кун (1953). Теорема Куна: при идеальной памяти смешанные и «поведенческие» стратегии равносильны.
• Нарушение идеальной памяти: парадокс «рассеянного водителя» (Piccione и Rubinstein, 1997), очень похожий на рассказ Полака про светофоры.
• Совершенное по подыграм равновесие ввёл Райнхард Зельтен (1965).
• Не путай: несовершенная информация значит «не видишь ходов», неполная значит «не знаешь выигрышей или типа соперника» (Джон Харсаньи, 1967–1968).