поставить крестик. Второй игрок имеет три возможных действия в каждом из четырех узлов принятия решений. Когда первый игрок получает право сделать второй ход, у него есть два варианта действия в каждом из 12 (4 × 3) узлов принятия решений. Как показано на рис. 3.7, даже у этой мини-игры в крестики-нолики очень сложное дерево игры. Хотя на самом деле оно не такое уж сложное, поскольку игра гарантированно закончится, после того как первый игрок сделает второй ход. Тем не менее на этом дереве 24 концевых узла, и их необходимо проанализировать.
.
Рис. 3.7. Сложное дерево простой игры в крестики-нолики на поле два на два
Это дерево служит здесь иллюстрацией того, насколько сложным может быть дерево даже в случае простых (или упрощенных) игр. Как оказалось, применение метода обратных рассуждений к анализу мини-игры в крестики-нолики позволяет быстро найти равновесие. Из такого анализа следует, что любой выбор первого игрока на втором ходе приводит к одному и тому же исходу игры. Здесь нет оптимального действия; любой ход так же хорош, как и остальные. Стало быть, когда второй игрок делает первый ход, он тоже видит, что любой возможный ход даст тот же результат, поэтому может с одинаковым успехом выбрать любой из трех вариантов в каждом из четырех узлов принятия решений. И наконец, то же самое верно и для первого игрока, делающего первый ход: любой вариант выбора равноценен остальным вариантам, а значит, он гарантированно победит в игре.
Хотя у этой версии игры в крестики-нолики весьма занимательное дерево, ее решение не представляет особого интереса. Первый игрок всегда выигрывает, поэтому выбор, сделанный обоими игроками, никак не влияет на конечный результат. Многим из нас больше знакома версия «три на три» игры в крестики-нолики. Для того чтобы проиллюстрировать ее деревом игры, нам пришлось бы показать, что первый игрок имеет девять возможных действий в начальном узле, у второго игрока восемь вариантов действий в каждом из девяти узлов принятия решения. На втором ходе у первого игрока семь возможных действий в каждом из 8 × 9 = 72 узлов, тогда как у второго игрока на втором ходе – шесть возможных действий в каждом из 7 × 8 × 9 = 504 узлов. Эта закономерность продолжается до тех пор, пока дерево не прекратит стремительно разрастаться, поскольку определенные комбинации ходов приводят к победе первого игрока, после чего игра заканчивается. Однако минимум до пятого хода победа невозможна. Для того чтобы нарисовать полное дерево этой игры, понадобится огромный лист бумаги или очень мелкий почерк.
Однако большинство из вас знают, как в худшем случае добиться хотя бы ничьей в игре в крестики-нолики на поле три на три. Так что есть простое решение этой игры, которое можно найти посредством обратных рассуждений, и истинный стратег способен существенно снизить сложность игры в ходе его поисков. Оказывается, как и в версии игры «два на два», многие возможные пути на дереве игры со стратегической точки зрения идентичны. В частности, девять начальных ходов могут быть только трех типов: вы ставите
