Стратегические игры. Доступный учебник по теории игр - стр. 65
Однако большинство из вас знают, как в худшем случае добиться хотя бы ничьей в игре в крестики-нолики на поле три на три. Так что есть простое решение этой игры, которое можно найти посредством обратных рассуждений, и истинный стратег способен существенно снизить сложность игры в ходе его поисков. Оказывается, как и в версии игры «два на два», многие возможные пути на дереве игры со стратегической точки зрения идентичны. В частности, девять начальных ходов могут быть только трех типов: вы ставите крестик на угловую позицию (четыре возможных варианта), на боковую позицию (также четыре возможных варианта) и на центральную позицию (один вариант). Использование этого метода для упрощения дерева игры поможет снизить уровень сложности задачи и приведет вас к описанию оптимальной равновесной стратегии, полученной методом обратных рассуждений. К примеру, мы могли бы показать, что игрок, который ходит вторым, может гарантированно добиться как минимум ничьей, сделав надлежащий первый ход и постоянно блокируя в дальнейшем попытки первого игрока выставить три символа в ряд[24].
Хотя сравнительно простые игры, такие как крестики-нолики, решаемы методом обратных рассуждений, выше мы показали, насколько быстро повышается сложность дерева игры даже в играх с двумя участниками. Поэтому при анализе более сложных игр вроде шахмат находить полное решение становится гораздо труднее.
В шахматах в распоряжении игроков (условно называемых «белые» и «черные») имеются наборы из 16 фигур разной формы, которые передвигаются по шахматной доске восемь на восемь клеток (рис. 3.8) в соответствии с заданными правилами[25]. Белые ходят первыми, черные – вторыми, и так далее по очереди. Все ходы видны другому игроку, и ничего не оставлено на волю случая, как в карточных играх, где карты перетасовываются и сдаются. Кроме того, шахматная партия должна заканчиваться за конечное число ходов. Согласно правилам, при троекратном повторении одной и той же позиции в течение игры объявляется ничья. Ввиду наличия конечного количества способов разместить 32 фигуры (или меньше, если некоторые фигуры побиты) на 64 клетках шахматной доски, партия не может продолжаться бесконечно долго без возникновения подобной ситуации. Поэтому в принципе шахматы поддаются полному анализу методом обратных рассуждений.
Рис. 3.8. Шахматная доска
Однако этот анализ так и не проведен. Шахматы не «решены» так, как в свое время крестики-нолики, а причина в том, что, несмотря на простоту правил, шахматы – чрезвычайно сложная игра. Из начальной позиции набора фигур, показанных на рис. 3.8, белые могут сделать любой из 20 ходов