Игра в развернутой форме с несовершенной информацией

Каждой вершине в развернутой форме игры соответствует единственная предыстория-то есть последовательность действий, которая приводит из начальной вершины в данную вершину. Особенностью рассматриваемых в предыдущей главе игр с совершенной информацией является то, что каждый игрок перед тем, как сделать ход, полностью знает предысторию игры — действия, выбранные ранее им и другими игроками. Другими словами, игрок знает, в какой вершине дерева он оказался. В этом разделе мы рассмотрим класс игр, называемых играми с несовершенной информацией, в которых игроки могут не знать полностью предысторию игры.

Чтобы отобразить ограниченность информации на дереве игры, используют так называемые информационные множества. Информационное множество отображает тот факт, что игрок не знает, в какой вершине дерева находится (т.е. не знает точно, какова была предыстория игры). Если игрок не может отличить две вершины дерева, то они принадлежат одному и тому же информационному множеству. Используя понятие информационного множества, мы можем дать формальное определение игр с совершенной (и полной) информацией: в играх с совершенной информацией в каждом информационном множестве находится только одна вершина.

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

По сравнению с развернутой формой игр с совершенной (и полной) информацией, в развернутой форме игр с несовершенной информацией появляется еще один элемент — информационное множество. Какие требования накладываются на дерево игры, содержащее информационные множества с более чем одной вершиной? Во-первых, каждая вершина дерева игры (кроме конечных) должна принадлежать одному и только одному информационному множеству. Во-вторых, по смыслу определения информационного множества, в каждой вершине информационного множества ход должен принадлежать одному и тому же игроку. В-третьих, множества возможных действий во всех вершинах одного и того же информационного множества должны быть одинаковыми (в противном случае игрок мог бы по тому, какие альтернативы ему доступны, определить, в какой именно вершине он находится).

Еще один вид требований к дереву игры появляется, если предположить, что игроки не забывают ту информацию, которой они обладают. Это так называемые игры с идеальной памятью. Игра в развернутой форме называется игрой с идеальной памятью, если игроки всегда помнят то, что они ранее знали, и то, что они ранее делали.