Отвечаю VKB -читайте с начала, там я чётко сказал что Теорема Неша!!!, во-вторых книга кого-то из указанных людей, а НЕ теорема!!! Кроме того про конечную игру - это не аргумент, а теорема, которую раньше я даже мог доказать, а про своего профессора я написал шутки ради - Вы вообще как читаете?????

Хотел бы ответить уважаемому Деду_В_Очках! Могу Вас заверить что я получил сведения по теории игр тоже не из фильмов (хотя фильм неплохой), я также не профессор, и даже не шахматист, но имея диплом по специальности математик - системный программист считаю, что имею право говорить об алгоритмах. По поводу сложности разработки алгоритма - согласен - я и не говорю что есть аналитическое решение - но метод перебора можно значительно улучшить. По поводу принципиальной невозможности решения - математика - это наука точная, теорема доказана и, следовательно, вопрос закрыт - задача решается. И просвещу по поводу стратегии - имеется в виду не чистая, а смешанная стратегия (с вариантами), т.е. существует такой лес стратегий, которые приводят к ничьей, это утверждение логично, математически верно, а потому бесспорно. По поводу ограниченности ЭВМ - замечу, что многопотоковое распределенное вычисление вкупе с декомпозицией задачи ставит ограниченность под сомнение. Вариант примерно таков - каждому пользователю дается скринсейвер, который считает варианты и отсылает в центр - синхронизировать не сложно - проблема с постулатом Эйнштейна решена!

с уважением, Дмитрий

Шахматы сравнивали не с крестиками-ноликами 3х3, а с крестиками-ноликами 2х2. Вот я например вижу более принципиальное отличие между играми в крестики-нолики 2х2 и 3х3, чем между игрой в крестики-нолики 3х3 и шахматами. Причём с именно с точки зрения человека, а не компьютера! крестиками в 2х2 невозможно не выиграть, а 3х3 - уже игра, требующая раздумий по крайней мере для того, кто первый раз играет в неё. Конечно шахматы сложнее и конечно количество переходит в качество. Но между 2х2 и 3х3 сразу уже есть качество...
А какая может быть ответственность за фразу "РЕШИТЬ ШАХМАТЫ ПРИНЦИПИАЛЬНО НЕВОЗМОЖНО"? Для меня как раз таки принципиально возможно. Но практически пока нельзя, и может быть долго будет нельзя, может быть никогда будет нельзя, но это ничего не меняет. Это уже эмоции. "люди, чужие шахматам". О чём это вообще? В игре го программы пока достигли гораздо меньше успехов, чем в шахматах. Даже близко их уровень не приближается к уровню сильнейших игроков. Можно сказать, что пока он на уровне начинающих. И это не потому, что программы для го пишут бездарные программисты, а для шахмат - гениальные. Просто го намного сложнее шахмат. И всё равно я не понимаю, как можно утверждать, что "принципиально невозможно решить го". Откуда мы знаем? А тем более шахматы. Это лишь эмоции...

Ага, то есть 10**120 - это уже оценка СНИЗУ? а сверху - 10**123? А можно тогда ещё немного продолжить ликбез и поподробнее остановиться на обосновании? Сразу же отвечаю BAD`у - тут, и во многих других местах, речь шла именно о числе позиций. Понятно, что число партий больше, чем позиций.

Опять же интересно почему? Снова эмоции? Как это можно доказать? То, что пока такие принципы, законы не обнаружены, ещё не доказывает, что их нет.

Кто может знать, какие технологии откроют в будущем? Но уже сейчас можно возразить хотя бы тем, что для решения задачи перебора всех вариантов можно распараллеливать вычисления. Кто сказал, что идеальный компьютер для шахмат должен состоять только из одного процессора? Хотя конечно признаю, что даже миллиард одновременно работающих компьютеров сократит итоговую цифру максимум на 9 порядков, что не очень-то обнадёживает.

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

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

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

Это сообщение отредактировал zenker - 5/12/2006, 02:13

[QUOTE]
Шахматы сравнивали не с крестиками-ноликами 3х3, а с крестиками-ноликами 2х2. Вот я например вижу более принципиальное отличие между играми в крестики-нолики 2х2 и 3х3, чем между игрой в крестики-нолики 3х3 и шахматами. Причём с именно с точки зрения человека, а не компьютера! крестиками в 2х2 невозможно не выиграть, а 3х3 - уже игра, требующая раздумий по крайней мере для того, кто первый раз играет в неё. Конечно шахматы сложнее и конечно количество переходит в качество. Но между 2х2 и 3х3 сразу уже есть качество...
[/QUOTE]

Полностью согласен. Между крестиками-ноликами 2x2 и 3x3 различие принципиальное: одна "игра" заканчивается победой, другая - ничьей.

[QUOTE]
А какая может быть ответственность за фразу "РЕШИТЬ ШАХМАТЫ ПРИНЦИПИАЛЬНО НЕВОЗМОЖНО"? Для меня как раз таки принципиально возможно. Но практически пока нельзя, и может быть долго будет нельзя, может быть никогда будет нельзя, но это ничего не меняет. Это уже эмоции. "люди, чужие шахматам". О чём это вообще?
[/QUOTE]

Ответственность человека, посвятившего шахматам жизнь.
Согласен, принципиально возможно - но в других физических условиях (только так!). А в объективной реальности этому препятствует запрет на передачу информации быстрее скорости света, - и это меняет всё. Шахматы остаются в живых! Конечно, это эмоции, и вполне естественные. Я очень люблю шахматы и радуюсь, что эта великая игра не умрёт. А "чужие" - просто не почувствовали красоты в шахматном искусстве, и смотрят на шахматы либо как на задачу, которую нужно решить, либо как на средство достижения спортивных успехов, либо ещё что-то, но увы, не видят в шахматах собственно искусства.

[QUOTE]
И всё равно я не понимаю, как можно утверждать, что "принципиально невозможно решить го". Откуда мы знаем? А тем более шахматы. Это лишь эмоции...
[/QUOTE]

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

[QUOTE]
Любая, будь то человеческая или компьютерная, оценка является приближённой, потому что не существует принципов, законов, которые всегда выполнялись бы одинаково во всех типах позиций. Точно оценить любую позицию можно, только построив полный граф игры с данной позиции до конечной.[/QUOTE]
[/QUOTE]
Опять же интересно почему? Снова эмоции? Как это можно доказать? То, что пока такие принципы, законы не обнаружены, ещё не доказывает, что их нет.
[QUOTE]

Интуитивно это очевидно. Без расчёта вариантов играть в шахматы невозможно. Общие принципы существуют, их очень много, но полагаться только на них было бы самоубийственно. Простейший пример. Как правило, хорошо сдвоить ладьи по открытой линии - но если вы следующим ходом получаете мат, линия вам не поможет. А чтобы понять, получаете вы его или нет, надо в уме (в оперативной памяти) просмотреть возможные шахи противника и попробовать найти от них защиту. Это уже перебор вариантов... Разумеется, мало-мальски опытный шахматист в приведённом случае ничего не считает, а просто "видит", есть мат или нет. Но если ту же линию можно захватить не сразу, а через два - три хода, расчёт встречных возможностей противника уже жизненно необходим. Помимо этого, есть просто позиции-исключения, и их очень много, где принципы не срабатывают или входят в противоречия друг с другом. Профессиональный шахматист тем и отличается от любителя, что чувствует (интуитивно - на основе накопленного опыта), когда можно проигнорировать тот или иной общий шахматный постулат, т. е. подходит к каждой позиции конкретно.

[/QUOTE]
Кто может знать, какие технологии откроют в будущем? Но уже сейчас можно возразить хотя бы тем, что для решения задачи перебора всех вариантов можно распараллеливать вычисления. Кто сказал, что идеальный компьютер для шахмат должен состоять только из одного процессора? Хотя конечно признаю, что даже миллиард одновременно работающих компьютеров сократит итоговую цифру максимум на 9 порядков, что не очень-то обнадёживает.
[QUOTE]

Напротив, это как раз весьма обнадёживает :)

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

Это сообщение отредактировал Дед_в_очках - 5/12/2006, 09:18

Нет. 10 в 120-й степени - это именно количество позиций. Все же возможные партии исчисляются уже совершенно невообразимым числом 10 в степени 10 в степени (четырёхзначная цифра, не помню).

Будучи по образованию не математиком, а шахматистом-практиком, изложу лишь в общих чертах, откуда берётся число 10^120. К сожалению, на лекциях в институте физкультуры нам об этом не рассказывали... Как я понимаю, это результат решения 31-й комбинаторной задачи, сложение количества расстановок на 64-х полях 32-х фигур, затем 31-й, 30-ти и т. д. до двух королей. Сама цифра абсолютно достоверна и указана, например, в книге Пушкина "Эвристика и кибернетика" (М., "Знание", 1965, - к вопросу о неизвестном творчестве великого поэта).

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

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

Это сообщение отредактировал stone_evil - 5/12/2006, 10:25

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

--------------------

Гамблер - это всегда загадка... (С) kgenius
___________________________________________
А крысы пусть уходят с корабля ... (В. Высоцкий)

НЕЛЬЗЯ.

Распараллеливание вычислений на миллиард (условно) компьютеров, во-первых, не даст прироста скорости в миллиард раз из-за потерь времени на синхронизацию и других технических сложностей (с этим - к специалистам). Во-вторых, пусть даже мы будем перебирать варианты в миллиард раз быстрее. Насколько дальше мы продвинемся? Известно, что расчёт вариантов на глубину D+1 требует в современной программе приблизительно в восемь раз больше времени, чем расчёт на глубину D. Пусть программа на одном мощном процессоре просчитывает варианты на глубину 10 полуходов за 10 секунд. (Замечу, что это не полный перебор всех вариантов, а селективный, выбрасывающий из рассмотрения львиную долю ходов по результатам оценки. Причём не благодаря безопасной альфа-бета-процедуре, а благодаря всевозможным эвристическим приёмам, принципиально не исключающим ошибку. Полный перебор программы производят только при решении задач, и здесь затраты времени с ростом глубины увеличиваются экспоненциально, т. к. эвристические приёмы, использующие оценку позиций как основу для отсечения вариантов, становятся бесполезными.) Но допустим, что разница между D и D+1 составляет не N^D+1 против N^D, а всего лишь восемь раз. Чтобы углубиться не на 10, а на 15 полуходов, потребуется уже 91 час, а на двадцать (десять ходов селективного перебора) - 345 лет. Если увеличить скорость перебора в миллиард раз, то этой же глубины мы достигнем за 10,7 секунды, и уже сотни лет потребуются, чтобы добраться до 30 полуходов. Что такое 15 ходов в шахматной партии? Это только-только наметившийся переход в миттельшпиль...

Вывод: если даже повысить скорость вычислений не в миллиард, а в миллиард миллиардов (1 секстиллион, 10^18) раз, то максимум, что удастся сделать, это получить через несколько сот лет приближённую (!) оценку всех дебютных вариантов на глубине до 20 ходов. Вопросы организации хранения и использования транспозиционных таблиц (а без них о всего лишь восьмикратном увеличении затрат времени придётся забыть) при таких объёмах вычислений оставим на совести программистов...