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

Тема в разделе "Машинное отделение", создана пользователем dan77790, 4 дек 2009.

  1. Rom Учаcтник

    • Участник
    Рег.:
    12.02.2012
    Сообщения:
    472
    Симпатии:
    165
    Репутация:
    21
    Оффлайн
    Мне кажется к шахматам больше подходит определение устойчивого и неустойчивого равновесия из физики. Т.е. небольшие отклонения не ведут к выходу позиции из равновесия - она возвращается к равенству. Но как только будет пересечен определенный предел (+0,3 или +0,5 - не суть), то позиция покатится по наклонной.
  2. Camon14 магистр

    • Заслуженный
    • Ветеран
    Рег.:
    28.05.2012
    Сообщения:
    14.378
    Симпатии:
    6.471
    Репутация:
    457
    Нарушения:
    10
    Оффлайн
    Bulldozer, вам математегам не понять отличие теории от практики.

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

    • Новичок
    Рег.:
    17.06.2011
    Сообщения:
    16
    Симпатии:
    3
    Репутация:
    0
    Оффлайн
    Число позиций в шахматах не больше чем (10 ** 42) десять в сороквторой степени. Сейчас решены все 7-и фигурки (2012г),
    это 4 * (10 ** 14). Осталось 20-24 порядка.
    :(
    Количество просчитаных позиций увеличивается
    в 10 раз примерно за 3-5 лет. Это "правило" выполняется на протяжении послндних 20 лет, и полностью соответствует "Закону Мура".
    :clap:
    В компьютерной области этот закон выполняется последние 50 лет.
    Если все так пойдет и дальше, то лет через 60-100 шахматы как матиматическая задача будут решены. А как будет называтся этот "комп" квантовым или по другому, неважно.
    :)
    Любитель_ и Camon14 нравится это.
  4. Camon14 магистр

    • Заслуженный
    • Ветеран
    Рег.:
    28.05.2012
    Сообщения:
    14.378
    Симпатии:
    6.471
    Репутация:
    457
    Нарушения:
    10
    Оффлайн
    Вашими устами да мёд пить. Что-то я сомневаюсь что через 2 года восьмифигурки решат. Во-первых, не так много энтузиастов этим занимаются, во-вторых, каждые 5 лет нужен новый суперкомпьютер, который этим будет заниматься , а кто его даст бедным шахматистам?
  5. Challenger Spy Технический специалист

    • Команда форума
    Рег.:
    29.01.2011
    Сообщения:
    3.510
    Симпатии:
    2.044
    Репутация:
    190
    Оффлайн
    Если под законом Мура вы подразумеваете вычислительную мощность, то он давно мертв. Уже довольно давно (по компьютерным меркам) процессорная отрасль находится в глубочайшем тупике, и выхода оттуда пока не видно даже в отдаленной перспективе (т.н. квантовые компьютеры пока оставим в области фантастическиж проЖектов). Про стагнацию в области роста объемов носителей я уже и говорить не буду - там точно такое же болото. Так что график просчета шахмат неуклонно загибается к горизонтали ;)
  6. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Закон Мура говорит о конкретной технологии, которая изживет себя через 10-15 лет максимум. Какой прогресс будет дальше - неизвестно. Есть возможность, что и никакого.

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

    • Команда форума
    Рег.:
    29.01.2011
    Сообщения:
    3.510
    Симпатии:
    2.044
    Репутация:
    190
    Оффлайн
    EvgeniyZh, Проснитесь, дружище! Мощности мы не видим потому, что полупроповодниковая отрасль уже очень давно уперлась в квантовые эффекты, и рост частот отдыхает на курортах микромира :) Обеспечивавший в последние 5-8 лет хоть какое-то подобие (впрочем, уже страшно далекое от народа муровских темпов) роста костыль многоядерности тоже уже практически выработал свой ресурс (курим закон Амдала).
    В смартфонах, где шахты техпроцессов еще не выработаны до дна - сумасшедшая гонка мегагерцев/ядер/ppi рвет и мечет (хотя тоже осталось уже недолго фраеру маркетологам танцевать).
    То, что подавляющему большинству обычных пользователей хватает и того, что уже имеется - в большей части верно. Но ведь и разработчики П/О не совсем уже дураки, они просто подстраиваются под текущие процессорные возможности :) Да и многие стандартные задачи уже вышли к своему пределу (обработка текста, прослушивание музыки) или близки к этому (кино-видео).
    SDD от солидных объемов и разумных цен еще очень далеки. Кстати, развиваются оч-чень быстро несмотря на то, что среднестатистическому пользователю и обычного винта хватает за глаза ;)
    А что касается "роста" объемов - винчестер на 1 терабайт за 100$ я брал в 2008, а сейчас мейнстрим - 3 tb за 120...
    --- добавлено: 14 янв 2016 ---
    Ах да...к чему я все это?! Компьютерная отрасль в тупике. Есть мнение, что, например, десятифигурки вообще никогда просчитаны не будут ;)
  8. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Мы ж говорим о суперкомпьютерах (не дома ж вы десятифигурки считать будете).
    [​IMG]
    Возможно последние два года есть некоторое замедление роста, но он все еще экспоненциальный.
    2Тб ИМХО вполне солидно
    Первый терабайтник появился в 2007, первый 10-терабайтник в 2015. В 10 раз за 8 лет по вашему это не рост?
  9. Challenger Spy Технический специалист

    • Команда форума
    Рег.:
    29.01.2011
    Сообщения:
    3.510
    Симпатии:
    2.044
    Репутация:
    190
    Оффлайн
    Суперкомпьютеры еще растут вопреки застое в процессорах, за счет масштабируемости. Но и она не вечна!
    Насчет SSD вы правы. 2tb - это солидно )
    По винтам предлагаю сделать другую, более характерную отсечку: не 1(2007) - 10(2015), а 3(2010) - 10(2015) :)
  10. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Суперкомпьютеры растут за счёт многих вещей. Например, быстрая связь (40gb InfiniBand) или GPGPU.
    Да, скорее всего, экспоненциальный рост близок к своему концу, но говорить о его окончании еще преждевременно. Intel не зря 16 миллиардов в год на R&D тратит. Авось что нибудь придумают.

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

    • Новичок
    Рег.:
    17.06.2011
    Сообщения:
    16
    Симпатии:
    3
    Репутация:
    0
    Оффлайн
    Позвольте защитить свою позицию. Про 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-фигурками. Пусть кажется что уперлись в стену и дальше пути
    нет. Но прогресс не остановить какая-нибкдь идея сделает возможным то что невозможно сейчас.

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

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Во первых, рассчитывать на еще 100 лет экспоненциального роста несколько наивно. Более того, напомню, что закон Мура говорит о количестве транзисторов, а не вычислительным мощностях. Такое количество транзистров физически невозможно. Вы конечно имели ввиду производительность, но нет никаких гарантий что закон продолжит выполнятся даже относительно кремния, а уж на новой технологии все будет совсем по другому.

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

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

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

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

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

    • Заслуженный
    • Участник
    Рег.:
    10.05.2006
    Сообщения:
    2.947
    Симпатии:
    677
    Репутация:
    28
    Оффлайн
    Всё-таки "квантовый компьютер" это совсем не то же самое, что просто "очень быстрый обычный компьютер". Так что все эти графики имеют к теме косвенное отношение.
  15. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Закон Мура не может выполняться еще 100 лет, потому что в 2^50 (то есть примерно 10^15) больше транзисторов чем сейчас никак разместить не получится чисто физически.

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

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

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

    • Ветеран
    Рег.:
    08.01.2007
    Сообщения:
    2.007
    Симпатии:
    1.000
    Репутация:
    109
    Оффлайн
    Т.е. удвоение скорости происходит за три года. Поскольку увеличение количества транзисторов, миниатюризация технологий и все прочее для конечного пользователя несущественно, то надо отталкиваться от этой цифры. Которая весьма правдоподобна: мой 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 та же история, если просто и честно запустить движок, а не спец. заточенные тесты проводить с идеально распараллеливаемыми процессами. И, конечно, период удвоения в три года закончился, теперь темпы будут скромнее.
    Challenger Spy нравится это.
  17. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    У супекомпьютеров тысячи ядер, причем с нефиговыми затратами на коммуникацию. На них нет смысла "тупо запускать движок". На них вообще нет смысла запускать задачи у которых распараллеливаемость далека от идеальной.
  18. Eugene_K Учаcтник

    • Участник
    Рег.:
    14.12.2014
    Сообщения:
    829
    Симпатии:
    133
    Репутация:
    3
    Оффлайн
    вопрос не в том решит или не решит, вопрос в том сможем ли мы его создать.
  19. Scaramuccia Учаcтник

    • Участник
    Рег.:
    12.01.2012
    Сообщения:
    1.699
    Симпатии:
    600
    Репутация:
    24
    Оффлайн
    Вопрос не в сможем ли мы его создать, а сможем ли мы его создать достаточно мощный. Квантовые компьютеры со смешной памятью (порядка десятка кубитов) созданы уже давно.
  20. Eugene_K Учаcтник

    • Участник
    Рег.:
    14.12.2014
    Сообщения:
    829
    Симпатии:
    133
    Репутация:
    3
    Оффлайн
    это псевдоквантовые компьютеры.

    это не то.
  21. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Есть что-то указывающее на то, что нет? Один кубит смогли же
  22. FIBM Учаcтник

    • Участник
    Рег.:
    27.05.2011
    Сообщения:
    362
    Симпатии:
    192
    Репутация:
    5
    Оффлайн
    Квантовый компьютер (КК) к шахматам вообще имеет достаточно косвенное отношение. Ну, какая польза будет людям от того, что в каждой позиции КК будет давать точный окончательный ответ (выигрыш, ничья или проигрыш), а на следующем ходу будет давать новый ответ. Главное-почему так, а не по-другому, вы все равно не узнаете.
    Ситуация кардинально отличается от, например, "взлома банковского кода", где вам важно знать ответ и больше ничего.
  23. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Ух ты, у вас уже есть квантовый алгоритм решения шахмат и вы знаете какие у него выходные данные?
    Scaramuccia нравится это.
  24. FIBM Учаcтник

    • Участник
    Рег.:
    27.05.2011
    Сообщения:
    362
    Симпатии:
    192
    Репутация:
    5
    Оффлайн
    Принципы работы КК и построения квантовых алгоритмов известны, и этого достаточно, чтобы скептически оценивать пользу КК для шахмат.
  25. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Решение игры подразумевает что в любой позиции можно получить лучший ход. Чем квантовый компьютер в этом смысле отличается от традиционного?
  26. FIBM Учаcтник

    • Участник
    Рег.:
    27.05.2011
    Сообщения:
    362
    Симпатии:
    192
    Репутация:
    5
    Оффлайн
    Тем, что с помощью КК вы просто будете знать ответ (выигрыш, ничья или проигрыш) для каждой позиции. То есть вы знаете правильную оценку -каждой позиции. Скажем, вы будете знать, что при ходе d4 в начальной позиции, белые выигрывают, а при е4 -ничья. Ну, и что, какая вам "радость" от такого знания?
  27. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Это не является решением игры. Точнее является, но ультра-слабым. Даже слабое решение требует стратегию для победы/ничьи в начальной позиции.

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

    • Участник
    Рег.:
    27.05.2011
    Сообщения:
    362
    Симпатии:
    192
    Репутация:
    5
    Оффлайн
    Другого решения с помощью КК у меня для вас нет.
  29. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Увас для меня никакого решения нет. Вот создадите квантовый алгоритм решения шахмат и докажите, что лучшего нет, тогда и поговорим. А пока это все пустые слова.
  30. FIBM Учаcтник

    • Участник
    Рег.:
    27.05.2011
    Сообщения:
    362
    Симпатии:
    192
    Репутация:
    5
    Оффлайн
    Грубить не нужно. Объясняю еще раз. Квантовый компьютер позволит получить только готовый ответ в любой шахматной позиции. Никаких шахматных вариантов у вас не будет. Не устраивает-придумывайте что-нибудь другое, но КК вам в этом деле не сильный помощник.
  31. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    Вы можете предоставить доказательство этого?
    --- добавлено: 15 янв 2016 ---
    Кроме того, чем плох всегда выигрывающий компьютер?
  32. Camon14 магистр

    • Заслуженный
    • Ветеран
    Рег.:
    28.05.2012
    Сообщения:
    14.378
    Симпатии:
    6.471
    Репутация:
    457
    Нарушения:
    10
    Оффлайн
    Для чего учёным полный просчёт шахмат понятно. Но шахматистам это на кой? У меня вопрос ко всем, вы бы хотели чтобы при вашей жизни шахматы просчитали до конца? Имхо даже полный просчёт шахмат не убьёт игру, потому что в подавляющем числе позиций каждая из сторон имеет несколько приемлемых ходов, которые не проигрывают. Но придётся серьёзно усиливать борьбу с подсказками.
  33. EvgeniyZh Учаcтник

    • Участник
    Рег.:
    07.02.2014
    Сообщения:
    487
    Симпатии:
    110
    Репутация:
    15
    Адрес:
    Ришон ле Цион, Израиль
    Оффлайн
    А на кой шахматистам все более и более сильные движки, да и движки вообще?
  34. Camon14 магистр

    • Заслуженный
    • Ветеран
    Рег.:
    28.05.2012
    Сообщения:
    14.378
    Симпатии:
    6.471
    Репутация:
    457
    Нарушения:
    10
    Оффлайн
    Проклятые ученые-алхимики наделали движки и базы партий. Я бы только приветствовал, если бы на законодательном уровне это все запретили. Романтику убивают хады.
  35. Jadn Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    10.05.2006
    Сообщения:
    2.947
    Симпатии:
    677
    Репутация:
    28
    Оффлайн
    Уже сейчас средний движок на среднем телефоне играет сильнее чемпиона мира. Так что будут или не будут просчитаны шахматы до конца, на ситуацию с подсказками это никак не повлияет. Вот переписку добьёт, это да.

Поделиться этой страницей