От NV
К Паршев
Дата 26.07.2004 15:40:17
Рубрики WWII;

Как неизвестно - известно

>за пределами дебюта и до упрощения - тёмный лес.
>До сих пор неизвестно, чем игра кончается при правильной игре - ничьей или победой белых.

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

Виталий
От Игорь Куртуков
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 18:37:58

Ре: Как неизвестно...

>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой.

Ну что вы такое говорите? Нет такого правила для детерменированных игр.
От NV
К Игорь Куртуков (26.07.2004 18:37:58)
Дата 26.07.2004 18:39:32

Ре: Как неизвестно...

>>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой.
>
>Ну что вы такое говорите? Нет такого правила для детерменированных игр.

http://vif2ne.ru/nvk/forum/0/co/835836.htm
От Rom
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 16:47:18

Так - неизвестно.

>>До сих пор неизвестно, чем игра кончается при правильной игре - ничьей или победой белых.
>
>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой. И даже алгоритм известен. Только толку от него кроме как теоретического нет никакого - вычислительные мощности для него абсолютно нереальны (во всяком случае пока). Увы, экспоненциальная сложность - практически полный перебор вариантов.

Шахматы – это игра с полной информацией. Поскольку в шахматах имеется конечное число состояний (позиций) то, согласно теореме Цермело, в любой позиции существует лучший ход (возможно, не единственный). Тем самым исход игры из любой позиции, в том числе и начальной, предопределен.
Обращаю Ваше внимание на то, что вышеупомянутая теорема ничего не говорит о том, каким должен быть этот исход - чтобы это выяснить, нужно решить позицию...
От NV
К Rom (26.07.2004 16:47:18)
Дата 26.07.2004 17:04:14

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

том 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)

Алпака
От tarasv
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 16:32:35

Re: Вы это, слегка погорячились :))

>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой. И даже алгоритм известен.

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

Орфографический словарь читал - не помогает :)
От NV
К tarasv (26.07.2004 16:32:35)
Дата 26.07.2004 17:21:06

С этим согласен - погорячился

>>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой. И даже алгоритм известен.
>
> Неизвестен, в том то и дело мало того для шахмат не найдена выйгрышная стратегия и неопределено какой везультат. А уж насчет выйгрыша в любой игре начинающего это вобще неправильно в корне - все завиаист от игры.

например игра Баше - выигрывает всегда второй. Так что действительно зависит от игры. Но в детерминированных играх всегда побеждает кто-то один и тот же (в смысле порядка ходов) - или гарантированно сводит вничью (зависит от правил).
От Роман (rvb)
К NV (26.07.2004 17:21:06)
Дата 26.07.2004 17:23:15

Консенсус (-)
От Siberiаn
К tarasv (26.07.2004 16:32:35)
Дата 26.07.2004 16:44:55

Не знаю кто тут горячится, но знаю что вы неправы

>>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой. И даже алгоритм известен.
>
> Неизвестен, в том то и дело мало того для шахмат не найдена выйгрышная стратегия и неопределено какой везультат. А уж насчет выйгрыша в любой игре начинающего это вобще неправильно в корне - все завиаист от игры.

>Орфографический словарь читал - не помогает :)

Надо шахматные учебники почитать лучше. Авербаха например. В шахматах - как уже здесь говорил ваш оппонент - выигрывает КАК ПРАВИЛО тот кто играет белыми, то бишь тот кто ходит первый. Поэтому при одинаковом ВЫСОКОМ классе игроков тот кто играет белыми играет на выигрыш, а тот кто играет черными - на ничью и будет этой ничьеё весьма доволен. Это элементарно

Siberian
От tarasv
К Siberiаn (26.07.2004 16:44:55)
Дата 26.07.2004 17:10:34

Re: Игра людей это одно а математическая теория шахмат это совсем другое

>Надо шахматные учебники почитать лучше. Авербаха например. В шахматах - как уже здесь говорил ваш оппонент - выигрывает КАК ПРАВИЛО тот кто играет белыми, то бишь тот кто ходит первый.

То-то в шахматной литературе до сих пор нет учебника "Как выигрывать играя белыми" и в ближайшее время не предвидится. :)

>Поэтому при одинаковом ВЫСОКОМ классе игроков тот кто играет белыми играет на выигрыш, а тот кто играет черными - на ничью и будет этой ничьеё весьма доволен. Это элементарно

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

Орфографический словарь читал - не помогает :)
От NV
К tarasv (26.07.2004 17:10:34)
Дата 26.07.2004 17:16:30

Еще раз отошлю к Дональду Кнуту

>>Надо шахматные учебники почитать лучше. Авербаха например. В шахматах - как уже здесь говорил ваш оппонент - выигрывает КАК ПРАВИЛО тот кто играет белыми, то бишь тот кто ходит первый.
>
> То-то в шахматной литературе до сих пор нет учебника "Как выигрывать играя белыми" и в ближайшее время не предвидится. :)


http://vif2ne.ru/nvk/forum/0/co/835814.htm

просто практического толку от принципиального существования алгоритма нет никакого - дерево вариантов примерно 10**40.
От Паршев
К NV (26.07.2004 17:16:30)
Дата 26.07.2004 22:07:12

Я Вам лучше анекдот расскажу.

Придумали шахматную машину - все ходы рассчитывает. Посадили играть с ней чемпиона мира, он, естественно, мандражирует. Ему выпало белыми. Он ходит: е2-е4.
Манина: "сдаюсь".
Видите ли, понятие выигрыша нестрогое. как договорились. Если бы в крестики-нолики выигрышем было кто первым поставит 5 знаков, то выигрывали бы всегда крестики.
И в шахматах эти понятия договорные.
От Николай Поникаров
К Паршев (26.07.2004 22:07:12)
Дата 27.07.2004 09:16:35

Крестики-нолики

День добрый.

>Придумали шахматную машину - все ходы рассчитывает. Посадили играть с ней чемпиона мира, он, естественно, мандражирует. Ему выпало белыми. Он ходит: е2-е4.
>Манина: "сдаюсь".

Не так этот анекдот рассказывают :) Попал шахматист-любитель в рай, и стал играть партию с Алехиным. "У нас тут времени много, мы просчитали..." :))

>Если бы в крестики-нолики выигрышем было кто первым поставит 5 знаков, то выигрывали бы всегда крестики.

Хм. У крестиков в свободном рэндзю позиция много сильнее, но выигрышная стратегия не известна.

С уважением, Николай.
От Роман (rvb)
К Siberiаn (26.07.2004 16:44:55)
Дата 26.07.2004 16:48:41

Валера, тут ТЫ не прав :)

"Как правило" - это показатель статистический. "Существует выигрышная стратегия" - совсем другой случай. В шахматах если и существует выигрышная стратегия, то она науке пока неизвестна. Была бы известна - в шахматы бы никто не играл :)

S.Y. Roman ( Холмовцы: http://vif2ne.ru/holmovo/forum/ )
От Вулкан
К Роман (rvb) (26.07.2004 16:48:41)
Дата 27.07.2004 11:06:52

Прав Сайбериан, прав..))

Приветствую!
>"Как правило" - это показатель статистический. "Существует выигрышная стратегия" - совсем другой случай. В шахматах если и существует выигрышная стратегия, то она науке пока неизвестна. Была бы известна - в шахматы бы никто не играл :)
Есть такая "теория игр". Кстати она реализовывается в компьютерных игрушках.
Постулаты:
1) Играющий первым имеет преимущество.
2) Стратегия ходящего вторым - не проиграть.
Если угодно, могу порыться в старых институтских тетрадях и даже формулы нарыть..)
С уважением, Вулкан
От Rom
К Вулкан (27.07.2004 11:06:52)
Дата 27.07.2004 19:04:21

В данном случае - неправ. Как, впрочем, и Вы.

>>"Как правило" - это показатель статистический. "Существует выигрышная стратегия" - совсем другой случай. В шахматах если и существует выигрышная стратегия, то она науке пока неизвестна. Была бы известна - в шахматы бы никто не играл :)
>Есть такая "теория игр".

Раздел математики с таким названием действительно есть.

>Кстати она реализовывается в компьютерных игрушках.
>Постулаты:
>1) Играющий первым имеет преимущество.
>2) Стратегия ходящего вторым - не проиграть.

А всё остальное из вышенаписанного Вами - неверно.

>Если угодно, могу порыться в старых институтских тетрадях и даже формулы нарыть..)

Поройтесь, наройте. Пока что отмечу:
• то, что Вы сформулировали - не постулаты (см., например, http://encycl.yandex.ru/cgi-bin/art.pl?art=bse/00061/88500.htm&encpage=bse );
• применительно к шахматам истинность второго утверждения неизвестна, а первого не определена;
• в обобщении на все игры оба утверждения просто-напросто ложны (легко можно построить пример игры, в которой заведомо выигрывает второй игрок).
От Siberiаn
К Rom (27.07.2004 19:04:21)
Дата 27.07.2004 19:24:18

Я прав во всех случая. А вас я вобще не знаю

Я сказал что в шахматах преимущество у того кто играет белыми.
Это факт известный всем и тот кто его оспаривает - тот просто неумный человек, забалтывающий очевидные вещи

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

Siberian
От Rom
К Siberiаn (27.07.2004 19:24:18)
Дата 27.07.2004 19:58:26

Вы не знаете не только меня (или нас?..:-]) - и в этом Вы также неправы...;-)

>Я сказал что в шахматах преимущество у того кто играет белыми.
>Это факт известный всем

Это факт статистический. Статистика действительно показывает, что при приблизительно равном классе партнёров играющий белыми выигрывает чаще, чем играющий чёрными (а чаще всего игра заканчивается вничью).
Речь же шла ( http://vif2ne.ru/nvk/forum/co/835725.htm , http://vif2ne.ru/nvk/forum/co/835786.htm ) о факте математическом - можно построить дерево всех шахматных партий (оно конечно) и можно таким образом окончательно решить вопрос об исходе шахматной игры при оптимальной стратегии; даже алгоритм известен - только вот вычислительных мощностей заведомо недостаточно...
От Роман (rvb)
К Вулкан (27.07.2004 11:06:52)
Дата 27.07.2004 13:41:38

Неа, не прав :)

>Постулаты:
>1) Играющий первым имеет преимущество.

Далеко не всегда достаточное для выигрыша, хотя бы. Нагляднейший пример - крестики-нолики. Оптимальные стратегии для обоих игроков - ничейные.

S.Y. Roman ( Холмовцы: http://vif2ne.ru/holmovo/forum/ )
От Rom
К Роман (rvb) (26.07.2004 16:48:41)
Дата 26.07.2004 16:52:58

Существует _оптимальная_ стратегия. Ничейная она или выигрышная - неизвестно. (-)
От Роман (rvb)
К Rom (26.07.2004 16:52:58)
Дата 26.07.2004 16:55:12

С уточнением полностью согласен (-)
От Роман (rvb)
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 16:12:47

Re: Как неизвестно...

>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой.

Крестики-нолики - детерминированная игра? Играть пробовали? Ну и как с "победой белых"?

>И даже алгоритм известен.

??

S.Y. Roman ( Холмовцы: http://vif2ne.ru/holmovo/forum/ )
От Нумер
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 16:00:33

Re: Как неизвестно...

>>за пределами дебюта и до упрощения - тёмный лес.
>>До сих пор неизвестно, чем игра кончается при правильной игре - ничьей или победой белых.
>
>при ПРАВИЛЬНОЙ игре в шахматы победа будет как в любой детерминированной игре - за той стороной которая ходит первой. И даже алгоритм известен. Только толку от него кроме как теоретического нет никакого - вычислительные мощности для него абсолютно нереальны (во всяком случае пока). Увы, экспоненциальная сложность - практически полный перебор вариантов.

И всё же, а почему Вы считаете, что именно беые победят? На этот счёт видно что-то теория игр говорит, можно подробнее?
От Паршев
К NV (26.07.2004 15:40:17)
Дата 26.07.2004 15:59:56

В крестики-нолики играть не приходилось? (-)