Тория игр. Читые стратегии в крестиках-ноликах.

[Wombat]

Г.Оуэн в учебнике "Теория игр" разбирает игру крестики-нолики и говорит, что:
1. На первом ходу у игрока I 9 альтернатив.
2. На второму ходу у игрока I по 7 ответов на каждый из 8 возможных ответов игрока II (симметрией принебрегается).
После этого, Оуэн говорит, что игрок I на втором ходу имеет 9*7^8чистых стратегий.

У меня получается 9*7*8 чистых стратегий для первого игрока.

Вопрос, собственно, в том какой нюанс я не улавливаю.

[Brukvalub]

Wombat писал(а):

Вопрос, собственно, в том какой нюанс я не улавливаю.

Думаю, что в книге опечатка. Понятно, что всего возможно не более 9! разных партий, поэтому столько стратегий, сколько написано в книге, набрать невозможно.

[Macavity]

Brukvalub писал(а):

Wombat писал(а):

Вопрос, собственно, в том какой нюанс я не улавливаю.

Думаю, что в книге опечатка. Понятно, что всего возможно не более 9! разных партий, поэтому столько стратегий, сколько написано в книге, набрать невозможно.

Не всё так просто, мало того, что там указано 9*7^8, так там ещё и в лоб написано - 51 883 209, что равно значению "опечатки". То есть опечатка там двукратная.

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

[antbez]

Мне тоже это странно. А что значит "информационные множества"?

[tolstopuz]

Видимо, автор книги считает стратегией полный набор "на первом ходу я пойду так, если противник ответит так, то я пойду так, а если так, то я пойду так". То есть первый игрок должен перед началом игры приготовить как первый ход, так и варианты второго хода на каждый возможный ответ второго игрока. А таких комбинаций действительно $9\cdot 7^8$.

[antbez]

На первом ходу у второго 8 стратегий. А сколько по этой логике у 2-ого стратегий на втором ходу(пока не очень понимаю)?

Добавлено спустя 1 час 22 минуты 13 секунд:

Ой, не то пишу. Не 8, а 72. Но вот потом... Степень в комбинаторике возникает в формулах без повторения, но разве здесь подобный случай?

[Wombat]

Brukvalub я бы принял это объяснение, если бы не то, что он затем строит на этом выводе дальнейшие рассуждения. Как заметил Macavity автор действительно говорит об информационных множествах и далее говорит, что если в игре существует N информационных множеств, в каждом из которых k вариантов хода, то число чистых стратегий будет k^N. Почему - я не понимаю абсолютно.

Причем у меня есть и русское и английское издания книги - в обоих одно и тоже.

Еще один большой вопрос: как он получил 8 информационных множеств.

Цитата:

Видимо, автор книги считает стратегией полный набор "на первом ходу я пойду так, если противник ответит так, то я пойду так, а если так, то я пойду так". То есть первый игрок должен перед началом игры приготовить как первый ход, так и варианты второго хода на каждый возможный ответ второго игрока. А таких комбинаций действительно 7^8

tolstopuz если рассмотреть более простую игру где каждый игрок выбирает из 4-х возможных цифр (а не из 9-ти как в Х-0) то получается:
Я рассматриваю только одну ветку, когда игрок I выбрал 1.
Для этой ветке чистые стратегии первого игрока на втором ходу:
I - II - I
1 - 2 - 3
1 - 2 - 4
1 - 3 - 2
1 - 3 - 4
1 - 4 - 2
1 - 4 - 3
Итого 6 стратегий (2*3). Если рассуждать как Оуэн, то должно получиться 2^3. Каким образом это возможно?

[Macavity]

Мне кажется tolstopuz близок к тому, что хотел сказать автор.

Похоже Wombat, что в Ваших построениях "...где каждый игрок выбирает из 4-х возможных цифр...", надо рассматривать случаи
1 - 2 - 2
1 - 3 - 3
...

То есть Вы считаете, что цифры не должны повторяться, но на самом деле Ваше предположение это некоторое семантическое знание ("бизнес-правила" ), которое, возможно, по задумке автора нельзя применять к этим информационным множествам.

[Wombat]

Непонятно тогда отчего он ограничивает игрока II выбором всего 8-ми возможных ходов - куда делся 9-й?

[tolstopuz]

Wombat писал(а):

Для этой ветке чистые стратегии первого игрока на втором ходу:
I - II - I
1 - 2 - 3
1 - 2 - 4
1 - 3 - 2
1 - 3 - 4
1 - 4 - 2
1 - 4 - 3

Автор, похоже, считает стратегией дерево вариантов, в котором есть ответ на любой возможный ход противника:
1 - 2 - 3 (- 3 - 2, - 4 - 2)
1 - 2 - 3 (- 3 - 2, - 4 - 3)
1 - 2 - 3 (- 3 - 4, - 4 - 2)
1 - 2 - 3 (- 3 - 4, - 4 - 3)
1 - 2 - 4 (- 3 - 2, - 4 - 2)
1 - 2 - 4 (- 3 - 2, - 4 - 3)
1 - 2 - 4 (- 3 - 4, - 4 - 2)
1 - 2 - 4 (- 3 - 4, - 4 - 3)

[Wombat]

tolstopuz, похоже, что вы правы. Большое спасибо.