Полное описание повторяющихся игр, которые представляют собой большую и важную научную область, выходит за рамки данной книги, но они возникают во многих ситуациях. Например, последовательную игру можно организовать, поместив двух агентов в мир 4x3, показанный на рис. 17.1. Если будет определено, что не должно происходить никакого движения, если два агента пытаются одновременно перейти в один и тот же квадрат (эта проблема часто возникает на многих пересечениях разных направлений дорожного движения), то некоторые чистые стратегии могут привести к бесконечному тупику. Одно из решений состоит в том, чтобы для каждого агента был рандомизирован выбор между движением вперед и остановкой на месте; патовая ситуация будет быстро разрешена и оба агента смогут продолжить свое движение. Именно такой подход применяется при разрешении коллизий между пакетами в сетях Ethernet.

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

Повторяющиеся игры в частично наблюдаемых вариантах среды называются играми с частичной информацией. К примерам таких игр относятся карточные игры наподобие покера и бриджа, в которых каждый игрок видит только некоторое подмножество карт, а также более серьезные "игры", такие как моделирование атомной войны, когда ни одна из сторон не знает местонахождение всех пусковых установок противника. Решения игр с частичной информацией можно найти, рассматривая дерево доверительных состояний, как и в случае задач POMDP (см. раздел 17.4). Одно важное различие между ними состоит в том, что собственное доверительное состояние является наблюдаемым, а доверительное состояние противника — нет. Для таких игр практически применимые алгоритмы были разработаны только недавно. Например, найдено решение для некоторой упрощенной версии покера и доказано, что вариант, в котором игроки блефуют, действительно является рациональным, по крайней мере в составе тщательно сбалансированной смешанной стратегии. В результате этих исследований было сделано одно важное открытие, которое заключается в том, что смешанные стратегии полезны не только для того, чтобы сделать действия игрока непредсказуемыми, но и для минимизации объема информации, которую противник может извлечь из наблюдений за действиями этого игрока. Интересно отметить, что разработчики программ для игры в бридж хорошо понимают важность сбора и сокрытия информации, но ни один из них не предложил использовать рандомизированные стратегии.