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

Мне кажется к шахматам больше подходит определение устойчивого и неустойчивого равновесия из физики. Т.е. небольшие отклонения не ведут к выходу позиции из равновесия - она возвращается к равенству. Но как только будет пересечен определенный предел (+0,3 или +0,5 - не суть), то позиция покатится по наклонной.

Bulldozer, вам математегам не понять отличие теории от практики.

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

Число позиций в шахматах не больше чем (10 ** 42) десять в сороквторой степени. Сейчас решены все 7-и фигурки (2012г),
это 4 * (10 ** 14). Осталось 20-24 порядка.

Количество просчитаных позиций увеличивается
в 10 раз примерно за 3-5 лет. Это "правило" выполняется на протяжении послндних 20 лет, и полностью соответствует "Закону Мура".

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

Вашими устами да мёд пить. Что-то я сомневаюсь что через 2 года восьмифигурки решат. Во-первых, не так много энтузиастов этим занимаются, во-вторых, каждые 5 лет нужен новый суперкомпьютер, который этим будет заниматься , а кто его даст бедным шахматистам?

Закон Мура говорит о конкретной технологии, которая изживет себя через 10-15 лет максимум. Какой прогресс будет дальше - неизвестно. Есть возможность, что и никакого.

Закон Мура (количество транзисторов, размещаемых на кристалле интегральной схемы, удваивается каждые 24 месяца) выполнялся до недавнего времени. Сейчас пожалуй срок увеличился до 2.5 лет, но это не так принципиально. То, что вы не видите увеличивающейся производительности процессоров объясняется просто - она не нужна. Обычному пользователю хватит максимум i3 для всех его нужд. Вот и работают над энергопотреблением, интегрированным видео и т.д.
HDD на 10Тб в 2015 сделали, SSD вообще невероятными темпами растут в объемах, тоже не совсем понятно о какой стагнации идет речь.

Мы ж говорим о суперкомпьютерах (не дома ж вы десятифигурки считать будете).

Возможно последние два года есть некоторое замедление роста, но он все еще экспоненциальный.

2Тб ИМХО вполне солидно

Первый терабайтник появился в 2007, первый 10-терабайтник в 2015. В 10 раз за 8 лет по вашему это не рост?

Суперкомпьютеры растут за счёт многих вещей. Например, быстрая связь (40gb InfiniBand) или GPGPU.
Да, скорее всего, экспоненциальный рост близок к своему концу, но говорить о его окончании еще преждевременно. Intel не зря 16 миллиардов в год на R&D тратит. Авось что нибудь придумают.

Вы манипулируете числами. Можно взять 5(2013) - 10(2015). Ровно в два раза, прям по Муру.

Позвольте защитить свою позицию. Про 8-и фигурки за два года я не говорил.
Было сказано
- обьем посчитанных позиций растет в 10 раз за 3-5 лет.
- Ссылаясь на стабильность "Закона Мура" (50 лет) предположил что шахматы решат через 60-100 лет.

Это так скажем "интегральная" оценка без подробностей. Хотите чуть поподробнее? Пожалуйста.

7-фигурки это 4*(10**14)позиций. решены 2012г.
8-фигурки это 4*(10**16)позиций. И у нас получается что они будут решены не через 2 года,
а где-то 2018-2022 годах. Так что ждать осталось не так долго.


Теперь еще поподробнее, и с примерами попытаюсь показать, что так скорее всего и будет.
Сегодняшная ситуация не уникальна за примерами далеко ходить не надо.
В 2011 году, на этом же сайте, обсуждалось создание 7-фигурок. Кстати, очень интересные
были разговоры, кто интересуется может перечитать и узнать много полезного про Эндшпильные
таблицы.
В общем предполагалось таблицы будут строится также как и таблицы "Налимова".
Ожидалось, что построены они будут 2015 году и займут 200 Тб.
Реальным фаворитом была программа Skipper_NORTON-а, и она вполне бы справилась с задачей
году 2015 или даже в 2014.

У 6-ти фиг "Налимова" 1 таблица считалась в RAM-е одного "компа" и потом несколько "компов"
сливали результаты в общий котел всего получалось 1.2 Тб.
7-фигурки не лезли в 32-битные вычисления и Skipper_NORTON-у пришлось перейти на 64-битные
он очень сильно оптимизитовал работу с RAM, в последней версии все вычисления помещались в
8 Gb, что было внолне достижимо для многих. Итого получилось что ~100 "компов" с 64-битной
операционкой, 8 Gb RAM и 2 Tb HDD решили бы эту задачу где-то за год.

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

Но создатели "Ломоносовских" таблиц пошли другим путем, одна таблица считалась на нескольких
узлах (по сути "компах"), да еще получили для вычислений огромные ресурсы.
И вот результат 2012 году 7-фигурки были посчитаны, они заняли 140 Tb.
2013 любой желающий мог купить "Soft" за разумные деньги и получить доступ к этим таблицам.
После этого интерес к генератору Skipper_NORTON-а упал.

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

Боюсь быть многословным, но если есть интерес то можно поговорить на этк тему поподробнее...

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

Далее. 7-фигурки посчитали на суперкомпьютере. В таких условиях можно посчитать и восьмифигурки, были бы деньги. Топовый супер компьютер мира в 30 раз мощнее ломоносова. Мало? Можно взять все суперкомпьтеры из топ500 и посчитать восьмифигурки очень быстро.
Поэтому имхо считать надо возможность посчитать на мощном потребительском компе, или на среднем сервере + возможность скачать. И в этом отношении думаю семифигурки станут доступны в районе 2020. Захочет ли ктото потратить деньги на расчет восьмифигурок? Не знаю. Не уверен.

EvgeniyZh почти во всем могу согласится с вами. Но. Количество транзисторов лежит в основе производительности. Да каждый транзистор работает все менее эффективно и "клацает" все больше в холостую. Но, несмотря на все "ужасы" и "тупики" быстродействие "процов" выросло за последние 30 лет гдето в 1000 раз. Каждый транзистор стал удельно во много раз дешевле и "компы" становятся все доступнее. Все эти плюсы и минусы друг друга во многом компенсируют.
И рост до сих пор экспоненциальный. В дальнейшем он может немного ускорится или замедлится но думаю останется экспоненциальным. (Конечно всемирные катаклизмы в расчет не берем.)

Кстати не обязательно 8-фигурки будут посчитаны на супер компьютере. 5-ти были посчитаны на супер компьютере, 6-ти на персоналках, 7-ми на супер компьютере, 8-ми ???. Что там произойдет в будущем никто не знает.

Да топовый супер "комп" мира в 30 раз мощнее "Ломоносова", а что-бы сделать шаг от 7-ми к 8-фигуркам нужно 100

Совершенно уверен, что технических проблем посчитать 7-фигурки на "мощном потребительском компе" нет. Главная причина почему этого до сих пор нет, отсутствие серьезного интереса.

Всё-таки "квантовый компьютер" это совсем не то же самое, что просто "очень быстрый обычный компьютер". Так что все эти графики имеют к теме косвенное отношение.

Закон Мура не может выполняться еще 100 лет, потому что в 2^50 (то есть примерно 10^15) больше транзисторов чем сейчас никак разместить не получится чисто физически.

Ну так я сказал, разделите работу между 500 топовымы суперкомпами, заполгода максимум будут восьмифигурки.

Сами говорили, что надо 100 компов на год или один комп на 100 лет. Самыми перспективными тут выглядят Syzygy и занимать места будут поменьше, и считаются быстро.Но на них минимум терабайт оперативы нужен. Так что 2020+

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

Т.е. удвоение скорости происходит за три года. Поскольку увеличение количества транзисторов, миниатюризация технологий и все прочее для конечного пользователя несущественно, то надо отталкиваться от этой цифры. Которая весьма правдоподобна: мой Athlon 2001 года дает на Stockfish'е 2.2 порядка 0.2 MN/s, какой-то 64-битный Intel 2011 года - около 2, а сегодняшние четырехядерники средней линейки - около 6. Топовые персоналки всегда были на пол-порядка быстрее, т.е. опережают заурядные лет на пять. Телефоны же отстают примерно на 10 лет, мой S2 выдает те же 0.2 и на равных катает с ветераном-Athlon'ом. А S5 показывает ожидаемые 0.6 MN/s.

Думаю, и с top-500 та же история, если просто и честно запустить движок, а не спец. заточенные тесты проводить с идеально распараллеливаемыми процессами. И, конечно, период удвоения в три года закончился, теперь темпы будут скромнее.

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

вопрос не в том решит или не решит, вопрос в том сможем ли мы его создать.

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

это псевдоквантовые компьютеры.

это не то.

Есть что-то указывающее на то, что нет? Один кубит смогли же

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

Ух ты, у вас уже есть квантовый алгоритм решения шахмат и вы знаете какие у него выходные данные?

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

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

Тем, что с помощью КК вы просто будете знать ответ (выигрыш, ничья или проигрыш) для каждой позиции. То есть вы знаете правильную оценку -каждой позиции. Скажем, вы будете знать, что при ходе d4 в начальной позиции, белые выигрывают, а при е4 -ничья. Ну, и что, какая вам "радость" от такого знания?

Это не является решением игры. Точнее является, но ультра-слабым. Даже слабое решение требует стратегию для победы/ничьи в начальной позиции.

Кроме того, с 32-фигурками WDL комп никогда даже на ничью не уйдет.

Другого решения с помощью КК у меня для вас нет.

Увас для меня никакого решения нет. Вот создадите квантовый алгоритм решения шахмат и докажите, что лучшего нет, тогда и поговорим. А пока это все пустые слова.

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

Вы можете предоставить доказательство этого?

—- добавлено: 16 Jan 2016 —-

Кроме того, чем плох всегда выигрывающий компьютер?

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

А на кой шахматистам все более и более сильные движки, да и движки вообще?

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

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