Сможет ли квантовый компьютер окончательно "решить" шахматы?

Правильно ли я понял из статьи, что время работы алгоритма будет O(N1/2) где N - количество листьев. Если да, то это не сильно поможет.

"Федя, переводчика надо бы..." ©

Любой гроссмейстер проиграет 1000 партий из 1000 - программе играющей по обычным 32-фигурным базам. И мы это уже обсуждали. На самом деле если даже позиция ничейна, то к ничьей будут чаще всего, из большинства позиций - вести всего 1-3 хода, а все остальные будут проигрывать. И отгадывать их всегда гроссмейстер не сможет. Где-нибудь, да ошибется. А после этого уже стопроцентный проигрыш.

Как-то кажется маловероятным...Можно привести обратный пример-в хорошо известных позициях компьютер выбирает пусть и немного совсем, но все же лучшие продолжения.Вчера была партия Накамура-Карлсен. Норвежец хорошо играл окончание, но все же перевеса не добился, так как этот самый перевес был скрыт за маятниковым многоходовым движением ферзя. Можно возразить,что это слишком частный случай. Но все же,думаю, из 1000 партий с 32-фигурными таблицами тот же карлсон в данный момент возьмет 0...

Все же, если опытный гроссмейстер поработает с этими таблицами (пока несуществующими) и выйдет со знанием, что на 1.e4 ответ 1...с7-с5 проигрывает,а 2... Nf6 делает ничью, то думаю результат будет совсем не сухим для ДНК)


Мой пример перекликается во второй части с предыдущим постом, но все же решился это напечатать...

думаю.тут только практика ответит на этот вопрос((

Мне кажется, что даже 1. e4 a6 будет ничья

Есть такое понятие, прямая положительная связь. В шахматах это означает, то, что получив малейшее преимущество, мы можем его НАРАЩИВАТЬ. Например, на доске материальное и позиционное равенство, но вот есть какое то преимущество у одной из сторон - например, проходная пешка. Это малейшее преимущество наращивается, и вскоре мы имеем уже большее преимущество, сначала позиционное, а потом оно наращивается до материального. Если в позиции невозможно ничего "нарастить", например в эндшпиле "король и ладья против короля и ладьи" то из ничейной позиции большинство ходов ведут к ничейной позиции. Но чем больше фигур на доске, тем больше возможностей и тем меньшего преимущества достаточно для выигрыша. Вот например в эндшпиле KQR-KQR, т.е. "ферзь и ладья против ферзя и ладьи" материальное равенство, но 87% позиции выигрышны для стороны, у которой право первого хода.

Или эндшпиль KRB-KR, т.е. "ладья и слон против ладьи". Большинство позиций ничейны, хотя преимущество в целую фигуру. А в 6-фигурном эндшпиле KRB-KNN, т.е. "ладья и слон против 2-х коней" преимущество - качество (а это меньше чем преимущество в целую фигуру), но почти из всех позиций сильнейшая сторона уже выигрывает. Хотя гроссмейстер не сможет выиграть - там вообще человек неспособен понять, на основании чего сильнейшая сторона добивается победы, и есть маты в 240 ходов.

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

Потому когда много фигур на доске, даже если позиция ничейна, то очень мало ходов будут вести к ничьей - всего скажем, в среднем 3 хода, из 30-40 возможных. Дальше после ошибки, одна из сторон, сможет НАРАЩИВАТЬ свое преимущество, т.е. получение преимущества ведет к получению еще большего преимущества. Это и есть "прямая положительная связь". Это как монетка стоящая на ребре. Если она начала заваливаться в одну из сторон, то дальше она будет падать со все возрастающей скоростью. Потому подавляющее большинство позиций - выигрышны для одной из сторон, и только очень узкое множество позиций - ничейны. Это узкое множество лежит как бы между множеством позиций, выигрышных для белых, и множеством позиций, выигрышных для черных.

Пусть, в среднем, гроссмейстер, рассматривает 4 возможных хода, которые кажутся ему ЛУЧШИМИ из каждой позиции. И один из этих ходов - и есть - неуловимая ошибка, после которой он проиграет. Выбрав один из этих ходов, гроссмейстер с вероятностью 75% попадает в ничейную позицию и далее. Но с вероятностью 25% он попадает в проигрышную для него позицию (после чего проигрыш будет неизбежен).

Точные цифры конечно, неизвестны, но приблизительно можно расценивать шансы так. Если гроссмейстеры (Морозевич, Свидлер и др.) не научились выигрывать даже из позиции "ферзь против ладьи" где перевес ОГРОМЕН и он материальный, то неуловимые для человека ошибки всегда будут встречаться.

Значит, сделав среднестатистически 1 ход, гроссмейстер остается в ничейной позиции с вероятностью 0.75. А сделав 40 ходов, вероятность того, что он останется в ничейной позиции 0.75 в 40-й степени. Пусть первые 15 дебютных ходов он не будет делать ошибок. Но дальше, с 15-го по 55-й ход в партии, гроссмейстер получается, окажется в проигрышной для него позиции с вероятностью 1 минус 0.75 в сороковой степени, точнее, 0.99998.

Проще говоря. гроссмейстер наберет 1 очко, не из 1000 партий, а из 50 тысяч! И это будут 2 ничьи, а выиграть он вообще не сможет против программы, играющей по 32-фигурным базам.

Уж как ни силен был когда то Дип Блю, который обыграл в матче Каспарова, и казалось, куда там уже сильнее
можно играть, а если сейчас его стравить с сильнейшей программой Гудини - и проиграть этот Дип Блю с треском 8 или 9 партий из 10-и. Вот такой парадокс, в шахматах. Такая игра.

Не надо подменять понятия. Если их посадить играть новую партию из этой позиции, они выиграют 100 раз из 100. А то, что они не выиграли на исходе многочасовой партии в цейтноте - ни о чем не говорит.

Не было там жесткого цейтнота, я читал.
А на 1. e4 a6 (потеря темпа) - уверен, что черные проигрывают. Хотя доказать это сейчас нельзя - будем ждать квантовых компьютеров

Интересная у вас статистика. Во первых например даже в начальной позиции все 100% ходов скорей всего ничейны, а во вторых мне казалось что Гроссмейстер выбирает ход в позиции не случайным образом.

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

Идея понятна, но неверна:1)Во многих позициях не проигрывать может например 1 ход, но настолько очевидный, что гроссмейстер его легко найдет и сделает.2)После, к примеру, 35-го хода может получиться эндшпиль, который гроссмейстер не проиграет ни при каких обстоятельствах, 55 ходов-это много, позиция находятся в состоянии неопределенности до 55-го хода крайне редко.3)Во многих позициях не проигрывает не 4 а 10 ходов.

В общем, думаю гроссмейстер 2800 будет набирать 1 очко в 20-50 партиях против идеальной игры. :wall:

Вы уже не первый раз приводите этот пример, так я давно хотел спросить: вы эту базу как-нибудь исследовали, так сказать, руками крутили, или эти 87% —- просто то что выдал генератор?
Мне кажется, бОльшая часть этих выигрышей —- за счет банального отбора незащищеной ладьи после серии шахов. Ну или мат форсированный. Ведь понятно, что в позиции с раскрытым королем и кучей тяжелых фигур право первого шаха —- большое преимущество. А для проверки ничейности шахмат лучше смотреть более нормальные позиции, с пешками.

Много и таких. Но (если фигуры и защищены) часто сторона, делающая первый ход, способна создать такую серию шахов, после которой удается обменять ферзя противника на свою... ладью! И после этого попадаем в 4-фигурный эндшпиль "ферзь против ладьи".

Я думаю, наиболее вероятно, все таки не 1 очко из 50 тысяч партий, а 1 очко из 1000 партий (но никак не из 20-50! ). Хотя доказать это можно будет только после того, как появятся квантовые компьютеры, и шахматы будут полностью решены.

Я анализировал многие партии гроссмейстеров, в которых было 6 (и менее) фигур на доске, ошибки которые они совершают, просто ужасные с точки зрения ЭБ. Доходит до того, что сильнейшая сторона, которая изначально может выиграть, умудряется 3 раза (!!!) упустить свой выигрыш, но слабейшая сторона 3 раза неспособна удержать и довести до ничьей. Когда на доске 32 фигуры, все будет намного сложнее.

Вот например, моя версия такая. После 1.e4, ход 1...с5 ведет к поражению! Таким образом, в очень многих партиях гроссмейстеры проиграют только из-за этого, первого хода. Математики меня поймут, с какой вероятностью проиграет человек, сделав 40 ходов

Дополню еще... Самое интересное, что они НЕ ПОЙМУТ этого. Конечно, если 32-фигурные базы станут достоянием общественности, тогда на первые 10-15 ходов удастся построить дебютную теорию, по которой ошибок в этой части партии не будет. Но если это будет оставаться неизвестным, то уже первых 40 ходов будет достаточно, что человек проиграет 1000 партий из 1000. Это пока всего лишь версия, которая основана на статистическом анализе ошибок, которые способен сделать человек, будь он самый крутой гроссмейстер. Очень хотелось бы, чтобы квантовые компьютеры создали при нашей жизни, чтобы убедиться в этом, насколько человек все-таки несовершенен

Во первых:даже для 10-фигурников(хотя их не должно хватать до решения шахмат)будет нужно астрономическое число памяти,20 Нортонбайт(20000 терабайт )а то и больше Во вторых:их смогут разработать только благодаря глубочайшему анализу и достаточному уровню развития техники,так что будут они лишь к 2128 году.Будем ждать!

Господа,которые сторонники того, что человек может набрать 1 очко против идеальной игры, опубликуйте,пожалуйста,здесь ИДЕАЛЬНУЮ (на Ваш взгляд,конечно) партию)))Посмотрим-можно ли ее улучшить. И не будем забывать, что 32-фигурные таблицы найдут это улучшение.

Партии Слюсарчука.

Подтвержденный факт.
Слюсарчук сумел усилить игру в 6 фигурных таблицах Налимова

На самом деле идеальную партию привести невозможно на мой взгляд. Поскольку уже первый ход может оказаться "не самым лучшим". К примеру что сильнее e4 или d4? Как это определить? По статистике, по оценкам, которые дают движки? А после какой глубины заканчивать исследование? :wall:

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

Идеальную партию привести не смогу, но уверен, что Карлсен сделает из 100 партий ничью с Гудини. Но при этом он должен использовать антикомпьютерную тактику. К примеру сыграть d4, e4, f4, c3. Вот такую структуру, запереть позицию. Компы все еще тупят в подобных позах (могу дать примеры, даже своих партий ).