Теория игр: детерминированные игры с полной информацией

[bin]

Посмотрел рекомендованную книгу, нашел:

Цитата:

Позиционная игра называется игрой с полной информацией, если в любой точке любой ее партии игрок, делающий ход, точно знает, какие выборы были сделаны раньше. […]

Примерами игры с полной информацией могут служить шашки, шахматы, крестики и нолики. Большинство карточных игр не является играми с полной информацией, так как игроки не знают, какие карты были выданы другим игрокам.
Ниже мы покажем, что матрица любой игры двух игроков с нулевой суммой с полной информацией в нормальной форме имеет седловую точку, т. е. в игре с полной информацией существуют оптимальные чистые стратегии. Это означает, что в таких играх, как шашки, шахматы, крестики и нолики, у игрока существуют стратегии, придерживаясь которых он не проиграет. Другими словами, у первого игрока существует такая стратегия, придерживаясь которой он может либо выиграть, если второй игрок будет играть не лучшим образом, либо добиться ничьей, если второй игрок будет играть самым лучшим образом. Аналогичное положение и у второго игрока.

А. В. Крушевский, Теория игр, 1977, С. 84.

Но см. мой пример выше: игра «голый король против двух ладей» (назовем ее, ЛМ – линейный мат), в этой игре белые проиграют (не добиться им ничьей!), если черные будут играть самым лучшим образом, что противоречит цитированному утверждению. Или я что-то пропустил в начале книги, и ЛМ не подходит под это утверждение? Почему?

[longstreet]

Да, я тоже не понимаю:

longstreet в сообщении #580698 писал(а):

Как тут обговаривается какое-то подобие равенство сил в начале партии?

Не из любой же ситуации существует стратегия, с помощью которой можно не проиграть Каспарову или DeepBlue?!

Ну, ситуацию можно и попроще, чем Вы предложили. Скажем, белые четыре ферзя и король против чёрного короля. Что, всегда чёрному королю можно сделать ничью?

[Xaositect]

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

В качестве примера можно рассмотреть такую простую игру: имеется n палочек, каждый игрок своим ходом зачеркивает одну или две, выигрывает тот, кто зачеркнул последнюю. Если $n$ кратно 3, то второй игрок может выиграть, как бы ни ходил первый, а если не кратно - то выигрышная стратегия есть у первого игрока.
Если же разрешить каждому игроку пропустить ход, и взять $n = 3$, то у каждого из игроков есть ничейная стратегия --- ничего не делать, но ни у кого нет ни выигрышной, ни проигрышной.

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

[longstreet]

(Оффтоп)

Мы в эти палочки с зачёркиванием на уроках в школе играли.

[INGELRII]

bin в сообщении #580926 писал(а):

Но см. мой пример выше: игра «голый король против двух ладей» (назовем ее, ЛМ – линейный мат), в этой игре белые проиграют (не добиться им ничьей!), если черные будут играть самым лучшим образом, что противоречит цитированному утверждению. Или я что-то пропустил в начале книги, и ЛМ не подходит под это утверждение? Почему?

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

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

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

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

[longstreet]

(Оффтоп)

INGELRII в сообщении #581047 писал(а):

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

Это да. На недавнем финале чемпионата мира по шахматам из двенадцати классических партий десять ничьих. И это, говорят, ещё мало. Вроде когда по регламенту чемпионата двадцать четыре партии играли, в районе двадцати ничьих иногда было.

[bin]

INGELRII в сообщении #581047 писал(а):

bin в сообщении #580926 писал(а):

Но см. мой пример выше: игра «голый король против двух ладей» (назовем ее, ЛМ – линейный мат), в этой игре белые проиграют (не добиться им ничьей!), если черные будут играть самым лучшим образом, что противоречит цитированному утверждению. Или я что-то пропустил в начале книги, и ЛМ не подходит под это утверждение? Почему?

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

Я говорю не о шахматах, а об игре ЛМ, где стартовой позицией является описанная выше.

-- Вт июн 05, 2012 14:51:48 --

INGELRII в сообщении #581047 писал(а):

Сказано же: для одного из игроков. Не сказано, что для обоих сразу!

Это сказано в Википедии, но не сказано в книге Крушевского (см. цитаты выше)!

-- Вт июн 05, 2012 15:04:48 --

Xaositect, Ваш пример с палочками ИМХО объясняет ситуацию!