Задачка про двухходовые шахматы.

← →
McSimm (2003-12-12 15:22) [0]

Предположим игроки делают по два хода подряд. Сначала два хода белые, затем черные и т.д.
(Если одномy из коpолей объявлен шах (допyстим, чеpномy), то в этом слyчае ход сpазy же пеpеходит к чеpным, но они имеют пpаво только на один ход, чтобы yйти от шаха, если yйти за один ход невозможно, то, как обычно, мат.)

Требуется доказать, что при такой игре белым пpи наилyчшей игpе гаpантиpована как минимyм ничья.

← →
Mystic (2003-12-12 16:04) [1]

Правила нечестные... Пусть сначала белые делаютодин ход. А потом уже пусть делают по два...

Ответ знаю (кажеться у Гика приводился).

← →
}|{yk (2003-12-12 16:17) [2]

А что тут доказывать, взять книгу Карпова и Гика 80 какого-то года и прочитать все доказательство. он там рассматривал машинные шахматы и алгоритмы их игры. Так что не надо изобретать велосипед

← →
nikkie (2003-12-12 16:33) [3]

>А что тут доказывать, взять книгу Карпова и Гика 80 какого-то года и прочитать все доказательство.

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

← →
McSimm (2003-12-12 16:41) [4]

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

← →
Igorek (2003-12-12 17:20) [5]

первый ход - конем вперед-назад...

← →
aimsyslv (2003-12-12 21:10) [6]

Igorek ответил. Доказываем от противного. Пусть белые всегда проигрывают. Делают ход конём туда-сюда. Чёрные оказываются в ситуации белых. Противоречие. чтд

← →
Bel (2003-12-12 21:22) [7]

> aimsyslv © (12.12.03 21:10) [6]
> Igorek ответил. Доказываем от противного. Пусть белые всегда проигрывают. Делают ход конём туда-сюда. Чёрные оказываются в ситуации белых. Противоречие. чтд

В условии было: > Требуется доказать, что при такой игре белым пpи наилyчшей игpе гаpантиpована как минимyм ничья. Т. е. игра в поддавки исключается.

← →
Fantasist (2003-12-12 21:22) [8]

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

Нифига не понял.

← →
nikkie (2003-12-12 21:28) [9]

>Bel, Fantasist
предположим противное - при наилучшей игре черные побеждают. сделаем ход конем Kg1-f3-g1. возникает исходная позиция с переменой цвета. согласно предположению, теперь при наилучшей игре должны выиграть белые. противоречие.

← →
aimsyslv (2003-12-12 21:29) [10]

Объясняю попу - лярно .
Предположим, что белые при наилучшей игре проигрывают. Тогда они делают первый ход конём туда-сюда(kf3-kg1). Теперь чёрные оказались в пололжении белых перед их ходом. По нашему предположению черные должны проиграть. Противоречие, т.к обе стороны проиграть одновременно не могут. Показательно то, что мы
не находим метод беспрогйгрышной игры, а лишь доказываем, что он
есть.

← →
nikkie (2003-12-12 21:31) [11]

на самом деле в этом рассуждении есть небольшая логическая дырка.

← →
aimsyslv (2003-12-12 21:34) [12]

Где????

← →
nikkie (2003-12-12 21:41) [13]

интересующимся предлагается ее найти.

← →
Fantasist (2003-12-12 21:55) [14]

> предположим противное - при наилучшей игре черные побеждают.
> сделаем ход конем Kg1-f3-g1. возникает исходная позиция
> с переменой цвета. согласно предположению, теперь при наилучшей
> игре должны выиграть белые. противоречие.

Вот это доказательство! То есть предполагается, что существует такая "наилучшая" игра для одной из сторон, обеспечивающая выйгрыш. Мне кажеться, что это доказательство как раз показывает обратное, что такой игры не существует.

Вот:

предположим что для черных "наилучшая" игра при которой они выигрывают. Сделаем ход конем Kg1-f3-g1. возникает исходная позиция с переменой цвета. Теперь, согласно предположению, существует "наилучшая" игра при которой выигрывают белые. Противоречие. Следовательно не существует такой игры для черных.

Правда, для белых это, к стати говоря, не доказывается.

← →
nikkie (2003-12-12 22:12) [15]

>Fantasist
из твоего поста я ничего не понял. может ты просто ни разу доказательств от противного не видел? если совсем непонятно, могу расшифровать, что имеется вид под "наилучшей" игрой.

← →
Fantasist (2003-12-12 23:11) [16]

> может ты просто ни разу доказательств от противного не видел

Ничего себе заявление! :)

> что имеется вид под "наилучшей" игрой.

Да. Это пожалуй представляет наибольший интерес.

← →
Fantasist (2003-12-12 23:19) [17]

> из твоего поста я ничего не понял

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

← →
nikkie (2003-12-12 23:53) [18]

>Своим доказательством я и показал, что для черных такого алгоритма не существует.
а что тогда доказывалось в [9] и [10]? и чем твое доказательство от них отличаются? и чем вызвано такое возмущение
>Вот это доказательство!
?

по поводу того, что такое "наилучшая" игра. в каждой позиции существует конечное число возможных ходов. далее, благодаря некоторым правилам шахматная партия не может продолжаться бесконечно. значит мы можем построить полное дерево партий. "листья" этого дерева - позиции с известным результатом: 1, 1/2 или 0. поднимаемся по дереву с помощью минимаксной процедуры. каждая позиция получает одну из трех оценок. "наилучшая" игра - игра, которая на каждом ходу не ухудшает эту оценку. то есть исходный вопрос состоит в том, какая оценка у начальной позиции. просят доказать, что для двухходовых шахмат эта оценка не может быть 0.

← →
nikkie (2003-12-12 23:56) [19]

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

← →
Fantasist (2003-12-13 02:16) [20]

> и чем вызвано такое возмущение

Да это как раз не возмущение - скорее удивление что ли.

> а что тогда доказывалось в [9] и [10]?

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

← →
aimsyslv (2003-12-13 10:32) [21]

шахматная партия не может продолжаться бесконечно
Вообще-то может, но в этом случае результат не определён.

← →
aimsyslv (2003-12-13 10:39) [22]

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

← →
SergP (2003-12-13 10:40) [23]

> aimsyslv © (13.12.03 10:32) [21]
> шахматная партия не может продолжаться бесконечно
> Вообще-то может, но в этом случае результат не определён.

Если под словом бесконечно - понимать то что оно обозначает, то партия продолжаться бесконечно не может. Так как в таком случае рано или поздно возникнет троекратное повторение позиции и ничья.

← →
eukar (2003-12-13 10:40) [24]

Как шахматная партия может продолжаться бесконечно?

← →
aimsyslv (2003-12-13 10:41) [25]

Обожаю логику!!!!

← →
aimsyslv (2003-12-13 10:43) [26]

Согласен, это - в классику, а скажем в блиц и быстрые правила о троекпатном повторении не действую( хотя там решает судья, так что объективно все может быть)

← →
nikkie (2003-12-13 14:07) [27]

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

так кто скажет, где дыра в рассуждениях [9],[10],[14]?

← →
Diablo (2003-12-13 14:52) [28]

nikkie
ну чего ты докопался. Естесственно, что черные тоже могут сделать ход туда-обратно. И мы опять приходим к начальным условиям.

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

← →
SergP (2003-12-13 15:36) [29]

> Diablo (13.12.03 14:52) [28]
> nikkie
> ну чего ты докопался. Естесственно, что черные тоже могут
> сделать ход туда-обратно. И мы опять приходим к начальным
> условиям.

Если черные так же сделают, то белые могут снова сделать это же.
А если так и будет продолжаться то будет троекратное повторение позиции и ничья. А ничья нас тоже устраивает....

← →
aimsyslv (2003-12-14 15:36) [30]

nikkie
Может быть в том, что начальная позиция чёрных строго говоря не эквивалентна позиции белых?

← →
SergP (2003-12-14 16:55) [31]

> Может быть в том, что начальная позиция чёрных строго говоря
> не эквивалентна позиции белых?

И чем же она не эквивалентна?

← →
Diablo (2003-12-14 20:12) [32]

>И чем же она не эквивалентна?

Ну типа противоположные фигуры стоят на клеточках другого цвета :)

← →
nikkie (2003-12-15 23:34) [33]

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

позиция действительно неэквивалентна начальной. разница в том, что после Kg1-f3-g1 позиция такая же, но уже сделан 1 полуход. а это означает, что некоторый выигрышная для черных партия при разыгрывании ее с переменой цвета после Kg1-f3-g1 может неожиданно завершиться вничью - если сработает троекратное повторение позиции или правило 50 ходов.

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

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

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

Задачка про двухходовые шахматы. Найти похожие ветки