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

[bin]

В Википедии утверждается, что

Цитата:

«Для любой детерминированной игры с полной информацией [нпр., шахматы, го], теоретически, можно просчитать всё дерево возможных ходов игроков и определить последовательность ходов, которая гарантированно приведёт по крайней мере одного из них к выигрышу или ничьей, то есть всегда может быть построен алгоритм выигрыша или сведения игры вничью по крайней мере для одной из сторон.»

Верно ли это? Есть ли авторитетные источники, где доказывают этот это утверждение? Как его доказать строго? И как понимать: если «по крайней мере для одной из сторон», то для другой никаких гарантий? Т.е. в шахматах белым гарантирован непроигрыш, а черным гарантирован только невыигрыш?

[Xaositect]

Это теорема Цермело. Либо у белых есть выигрышная стратегия, либо у черных есть выигрышная стратегия, либо и у белых, и у черных есть ничейная.

[longstreet]

Xaositect в сообщении #580397 писал(а):

Либо у белых есть выигрышная стратегия, либо у черных есть выигрышная стратегия, либо и у белых, и у черных есть ничейная.

Как? Из любой позиции? Понятное дело, что нет. Тогда как это обговаривается (ведь нельзя равенства условий потребовать, всё равно кто-то первый ходит, кто-то второй)?

[shwedka]

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

Как? Из любой позиции? Понятное дело, что нет. Тогда как это обговаривается (ведь нельзя равенства условий потребовать, всё равно кто-то первый ходит, кто-то второй)?

Не нужно ничего обговаривать. В шахматах первыми ходят белые.

[longstreet]

Там было сказано

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

Для любой детерминированной игры с полной информацией

Чем шахматы с какой-нибудь неклассической расстановкой не подходят под это указание? Это будет детерминированная игра с полной информацией.

-- 04.06.2012, 11:32 --

А, понял, извиняюсь. Либо кто-то один выигрывает, либо ничья. Но это же и есть все возможные варианты, исходя из шахматных правил. Зачем тогда эта теорема Цермело? Что она даёт нетривиального?

[Sonic86]

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

А, понял, извиняюсь. Либо кто-то один выигрывает, либо ничья. Но это же и есть все возможные варианты, исходя из шахматных правил. Зачем тогда эта теорема Цермело? Что она даёт нетривиального?

Не, Вы редуцировали информацию: не просто либо кто-то выигрывает, либо ничья (этак и в дураке то же самое), а именно существует стратегия - в худшем случае очень длинный список правил вида if() then{}else{}, с помощью которого без мозгов можно не проиграть хоть Каспарову, хоть DeepBlue.
Надеюсь, не наврал

[longstreet]

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

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

(Оффтоп)

Я недавно Каспарова видел Чемпионат мира по шахматам в Москве проходил.

[Sonic86]

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

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

Видимо, никак, т.к. это не нужно, достаточно детерминированности.

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

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

Не из любой. Но из любой ситуации либо существует беспроигрышная стратегия у Вас, либо - у Каспарова, либо у Вас существует способ не проиграть.

Вообще, скачайте книжку Крушевский Теория игр. Там этот вопрос разбирается не позже 70-й страницы, читается хорошо. А то боюсь, что совру.

-- Пн июн 04, 2012 11:25:10 --

(Оффтоп)

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

Я недавно Каспарова видел Чемпионат мира по шахматам в Москве проходил.

Везет! Поздравляю!

[longstreet]

Sonic86 в сообщении #580705 писал(а):

Но из любой ситуации либо существует беспроигрышная стратегия у Вас, либо - у Каспарова, либо у Вас существует способ не проиграть.

Не понял. А какие ещё возможны-то исходы?! Либо я выигрываю, либо Каспаров, либо ничья. То, что есть алгоритм, приводящий хотя бы к одному из этих исходов $-$ это же очевидно.

Книжку скачал, посмотрю, спасибо!

[bin]

Sonic86 в сообщении #580705 писал(а):

Но из любой ситуации либо существует беспроигрышная стратегия у Вас, либо - у Каспарова, либо у Вас существует способ не проиграть.

Вообще, скачайте книжку Крушевский Теория игр. Там этот вопрос разбирается не позже 70-й страницы, читается хорошо. А то боюсь, что совру.

Книгу скачал, посмотрю. Спасибо!
Пример ситуации, в которой нет способа не проиграть (если противник не будет делать очень грубых ошибок): белые: король; черные: король, две ладьи на одной горизонтали. Белым есть куда ходить.

[longstreet]

Так ситуаций полно.

[bin]

Sonic86 в сообщении #580692 писал(а):

существует стратегия - в худшем случае очень длинный список правил вида if() then{}else{}, с помощью которого без мозгов можно не проиграть хоть Каспарову, хоть DeepBlue.

Возникает интересный доп. вопрос: а как получить такой список правил, имея программу, играющую по оптимальной стратегии? Например, для крестиков и ноликов 3 на 3, простенькая программа реализует классический альфа-бета алгоритм без ограничений глубины просмотра. Выиграть у такой программы невозможно, но вот как список правил получить?

[longstreet]

Это не список правил. Это именно список (алгоритм) шагов if () then () else() для всевозможных ходов противника.

[bin]

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

Это не список правил. Это именно список (алгоритм) шагов if () then () else() для всевозможных ходов противника.

Ok! Согласен: алгоритм вида if () then () else(). Как его получить из программы, реализующей оптимальную стратегию? Возможно ли это в принципе?

-- Пн июн 04, 2012 16:59:01 --

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

Так ситуаций полно.

Вот я и не понял формулировки: "Но из любой ситуации либо существует беспроигрышная стратегия у Вас, либо - у Каспарова, либо у Вас существует способ не проиграть". Игры двух противников, о которых здесь речь, нпр., шахматы по своему определению (т.е. по своим правилам) имеют два исхода: 1) один из противников выигрывает, а второй проигрывает; 2) ничья. Третьего не дано. Для того, чтобы отметить этот факт из правил игры, теория игр не нужна.

[longstreet]

Я пока только понял то, что есть только эти три варианта (что понятно и начинающему), но существует стратегия в виде алгоритма, как к этому придти, а не на авось рандомно фигуры передвигать. Но я сам не до конца понимаю, это то, что мне ответил Sonic86.