От NV
К Rom
Дата 26.07.2004 17:04:14
Рубрики WWII;

См. Дональда Кнута, Искусство программирования

том 1 стр.314. Как раз про тот самый алгоритм который неизвестен.


>Шахматы – это игра с полной информацией. Поскольку в шахматах имеется конечное число состояний (позиций) то, согласно теореме Цермело, в любой позиции существует лучший ход (возможно, не единственный). Тем самым исход игры из любой позиции, в том числе и начальной, предопределен.
>Обращаю Ваше внимание на то, что вышеупомянутая теорема ничего не говорит о том, каким должен быть этот исход - чтобы это выяснить, нужно решить позицию...

Вот еще на эту тему немножко

http://rain.ifmo.ru/~korotkov/mainb.pdf

Виталий


От Rom
К NV (26.07.2004 17:04:14)
Дата 26.07.2004 17:41:37

Дело не в конкретном алгоритме: его существование как раз гарантируется теоремой

>>Шахматы – это игра с полной информацией. Поскольку в шахматах имеется конечное число состояний (позиций) то, согласно теореме Цермело, в любой позиции существует лучший ход (возможно, не единственный). Тем самым исход игры из любой позиции, в том числе и начальной, предопределен.
>>Обращаю Ваше внимание на то, что вышеупомянутая теорема ничего не говорит о том, каким должен быть этот исход - чтобы это выяснить, нужно решить позицию...
>
>Вот еще на эту тему немножко

> http://rain.ifmo.ru/~korotkov/mainb.pdf

Вот здесь - http://vif2ne.ru/nvk/forum/2/co/835836.htm - Вы уже говорите примерно то же, что и я: "...зависит от игры. Но в детерминированных играх всегда побеждает кто-то один и тот же (в смысле порядка ходов) - или гарантированно сводит вничью (зависит от правил).".
Соответственно если рассматривать шахматы как набор правил, то при оптимальной стратегии исход определяется позицией; если же рассматривать шахматы как совокупность набора правил и начальной позиции, то исход предопределён - но, не зная оптимальной стратегии, мы не можем сказать, какой это исход...
От NV
К Rom (26.07.2004 17:41:37)
Дата 26.07.2004 18:04:38

В работе Кнута утверждается что приведенный алгоритм

>>>Шахматы – это игра с полной информацией. Поскольку в шахматах имеется конечное число состояний (позиций) то, согласно теореме Цермело, в любой позиции существует лучший ход (возможно, не единственный). Тем самым исход игры из любой позиции, в том числе и начальной, предопределен.
>>>Обращаю Ваше внимание на то, что вышеупомянутая теорема ничего не говорит о том, каким должен быть этот исход - чтобы это выяснить, нужно решить позицию...
>>
>>Вот еще на эту тему немножко
>
>> http://rain.ifmo.ru/~korotkov/mainb.pdf
>
>Вот здесь - http://vif2ne.ru/nvk/forum/2/co/835836.htm - Вы уже говорите примерно то же, что и я: "...зависит от игры. Но в детерминированных играх всегда побеждает кто-то один и тот же (в смысле порядка ходов) - или гарантированно сводит вничью (зависит от правил).".
>Соответственно если рассматривать шахматы как набор правил, то при оптимальной стратегии исход определяется позицией; если же рассматривать шахматы как совокупность набора правил и начальной позиции, то исход предопределён - но, не зная оптимальной стратегии, мы не можем сказать, какой это исход...

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


От Rom
К NV (26.07.2004 18:04:38)
Дата 27.07.2004 11:18:05

К сожалению, мой экземпляр "Искусства программирования" сейчас не у меня...:-(

Связаться с человеком, у которого он находится, мне также не удалось. Тем не менее...

>>>>Шахматы – это игра с полной информацией. Поскольку в шахматах имеется конечное число состояний (позиций) то, согласно теореме Цермело, в любой позиции существует лучший ход (возможно, не единственный). Тем самым исход игры из любой позиции, в том числе и начальной, предопределен.
>>>>Обращаю Ваше внимание на то, что вышеупомянутая теорема ничего не говорит о том, каким должен быть этот исход - чтобы это выяснить, нужно решить позицию...
>>Вот здесь - http://vif2ne.ru/nvk/forum/2/co/835836.htm - Вы уже говорите примерно то же, что и я: "...зависит от игры. Но в детерминированных играх всегда побеждает кто-то один и тот же (в смысле порядка ходов) - или гарантированно сводит вничью (зависит от правил).".
>>Соответственно если рассматривать шахматы как набор правил, то при оптимальной стратегии исход определяется позицией; если же рассматривать шахматы как совокупность набора правил и начальной позиции, то исход предопределён - но, не зная оптимальной стратегии, мы не можем сказать, какой это исход...
>
>В работе Кнута утверждается что приведенный алгоритм именно дает гарантированный выигрыш белым. При естественно соблюдении правил игры. Не вижу в данном случае причины не доверять классику. Другое дело, что практической пользы от такого алгоритма нет. Но это уже другой вопрос.

Возможны разные варианты...
Возможно, Вы всё же что-то не так поняли.
Возможно (если Вы пользуетесь переводным вариантом) была допущена ошибка при переводе.
Возможно, наконец, что в данном случае Дональд Кнут высказал необоснованное утверждение. Во-первых, он не является авторитетом в этом вопросе - он не специалист по теории игр, а проверить результат работы приводимого им алгоритма он не мог (имеющихся вычислительных мошностей явно недостаточно и вряд ли будет достаточно в обозримом будущем - на что Вы и сами указываете: http://vif2ne.ru/nvk/forum/co/835827.htm ). Во-вторых - что существенно важнее - в математике (в отличие от, скажем, теологии) ссылка на авторитет не может служить обоснованием верности утверждения; требуется доказательство или ссылка на доказательство. Мы даже не можем принять утверждение о выигрыше белых за аксиому - поскольку из теоремы Цермело нам совершенно точно известно, что утверждение об исходе шахматной партии при следовании оптимальной стратегии разрешимо в рамках аксиоматики теории игр (несмотря на то, что получение самого решения лежит за пределами имеющихся вычислительных возможностей).
Для некоторых игр можно утверждать что-то определённое об исходе, не располагая оптимальной стратегией - за счёт привлечения дополнительных соображений. Так, для игры "крестики-нолики n в ряд" предположение о наличии выигрышной стратегии для "ноликов" приводит к противоречию: "крестики" могли бы сделать произвольный ход в начале, а далее следовать той же стратегии, делая опять-таки произвольный ход, если нужное поле занято - поскольку наличие лишнего "крестика" не может препятствовать выигрышу "крестиков". К рэндзю это рассуждение уже неприменимо - в силу несимметричности правил и наличия ограничений на построение "вилок". Для шахмат оно, конечно, тоже неприменимо - и пока вообще нет никаких оснований утверждать что-либо определённое о том, каким должен быть исход шахматной партии при оптимальной стратегии (хотя оптимальная стратегия существует - и даже есть алгоритм, позволяющий её получить).
От Игорь Куртуков
К NV (26.07.2004 18:04:38)
Дата 26.07.2004 18:49:34

Ре: В работе...

>именно дает гарантированный выигрыш белым.

Где же там гарантия именно выигрыша?

> Не вижу в данном случае причины не доверять классику.

Не вижу причины доверять вашему пониманию классика. Приложите этот алгоритм к игре в крестики-нолики на поле 3x3. Дает нам гарантированный вигрыш крестиков?
От Alpaka
К Игорь Куртуков (26.07.2004 18:49:34)
Дата 26.07.2004 22:23:31

Ре: В работе...


>Не вижу причины доверять вашему пониманию классика. Приложите этот алгоритм к игре в крестики-нолики на поле 3x3. Дает нам гарантированный вигрыш крестиков?
***
Вы будете смеяться (С), но таки в крестики-нолики есть выигрышная стратегия, и таки для первоходящего. :)))
Алпака
От Игорь Куртуков
К Alpaka (26.07.2004 22:23:31)
Дата 26.07.2004 22:37:31

Конечно буду смеятся.

>Вы будете смеяться (С), но таки в крестики-нолики есть выигрышная стратегия

Крестики-нолики 3x3 ? Вы либо чукча-не-читатель, либо просто ошибаетесь. При правильной игре "нолики" сводят в ничью.
От Alpaka
К Игорь Куртуков (26.07.2004 22:37:31)
Дата 27.07.2004 01:04:04

Моя ошибка, Вы правы (0)

Алпака