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

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

  1. TopicStarter Overlay

    dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    И если он реально поможет в этом нелегком деле, то как будут выглядить квантовые алгоритмы? Там какое-то специальное будет программирование или теже минимакс и прочие прунинги?)
  2. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    Вопрос не в том, сможет или не сможет. Вопрос - захочет ли...
  3. TopicStarter Overlay

    dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Убыстрение не означает автоматически ИИ)
  4. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.497
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Недавно в журнале "В Мире Науки" была статья, где утверждают, что квантовые компы приведут к существенному убыстрению решения лишь небольшого класса подходящих задач :( . Шахматы как-будто выпадают из этого класса... :|
  5. GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    чтобы "решить" шахматы, нужны 32-фигурные эндшпильные таблицы )))
    даже если какие-то новые суперкомпы смогут их просчитать (что очень сомнительно), то такой огромный объем базы просто негде будет хранить - современные технологии плотности записи не позволят этого сделать

    а любые игровые аналитические "алгоритмы" шахмат решают их лишь приближенно, не во всех вариантах... возможно, программа будет способна не проигрывать никогда, но это не будет означать "решения шахмат"
  6. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    46.412
    Симпатии:
    7.534
    Репутация:
    292
    Адрес:
    Москва, Россия
    Оффлайн
    Да, до 32-фигурных еще далеко.

    А интересно, есть ли примерные оценки, сколько места будут занимать (при нынешнем способе записи) 7-фигурные базы, 8-фигурные базы и так далее? Примерные...
  7. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    Я могу абсолютно безошибочно играть в крестики-нолики на доске 3х3. При этом я не должен держать в памяти всё дерево из нескольких сотен позиций (с учётом симметрий - из 50-ти).

    Возможно, для идеальной игры в шахматы квантовому компу понадобится рабочей памяти существенно меньше, чем надо под полные 32-фигурные таблицы. Просто ответ будет каждый раз вычисляться на лету, а не браться из базы данных.
  8. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    46.412
    Симпатии:
    7.534
    Репутация:
    292
    Адрес:
    Москва, Россия
    Оффлайн
    Подразумевается то, что в незнакомых позициях достаточно будет просто не допускать грубых ошибок.

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

    Думаю, это ограничение сократит объем на 70-80 процентов.
  9. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Решение английских шашек командой Chinook не использует 24-фигурные таблицы, а обходится всего лишь 10-фигурными. Думаю, и в шахматах 10-12 фигурные таблицы должны быть достаточны.

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

    Для примера - график зависимости числа ничьих от рейтинга в турнире движков KCEC:
    [​IMG]
    Каждая точка представляет матч, обычно из 32 партий. На горизонтальной оси - усреднённый рейтинг двух движков в матче (Ra+Rb)/2. На вертикальной оси - процент ничьих в матче. (0 на оси X соответствует 2000 пунктам Эло).

    Видно, что сильные движки делают больше ничьих.

    Линейная регрессия: Процент ничьих = −37.83712 [±4.52885] + 0.02562 [±0.00181] * A
    Где A - среднее арифметическое рейтингов двух движков, играющих матч.

    Для сравнения, в шашках этот момент уже наступил, процент ничьих в партиях сильнейших движков близок к 100.
  10. GlazAlmaz Max

    • Участник
    Рег.:
    12.01.2009
    Сообщения:
    216
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Russia
    Оффлайн
    6-фигурные 1,2 ТБ
    7-и фигурные будут занимать ориентировочно 300-400 ТБ (что вполне реально хранить)
    а дальше рост такой же резкий, еще в тысячу раз может

    в реальность даже 8-фигурных баз как-то верится с трудом в обозримом будущем, а уж тем более 10х и выше вообще кажутся нереальными...

    дак вроде эти шашки имеют слабое решение - просто найден беспроигрышный алгоритм, да и то не во всех позициях - это же разные вещи...
  11. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    То есть, если погрешности упрутся в одну сторону, получим для стопроцентных показателей ничьих:
    2000 + A = 2000 + (100 + 37.8 + 4.5) / (0.0256 - 0.0018) = 5979
    а если в другую, то
    2000 + A = 2000 + (100 + 37.8 - 4.5) / (0.0256 + 0.0018) = 6864

    Интервал "абсолютного игрока" выходит в диапазоне 6000-7000 Эло.
    Как-то странно. Наверное, линейную модель применять нельзя.
  12. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Это да, но ведь и в шахматах мы обсуждаем возможность слабого решения?

    В шахматах в настоящий момент у нас нет даже полной шестифигурки: не хватает таблиц "5-1". До семифигурки - как до луны. Генератора нет и некому сделать: Задача требует совокупности ресурсов (времени, энтузиазма, умения), которых ни у кого нет.

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

    Шашки решали 15 лет, вбухали кучу ресурсов, решили наконец (слабо). Но за это время программы и так перестали (почти) проигрывать. Мне кажется это неплохая оценка сроков - реально о любом решении шахмат можно будет говорить, когда шахматные программы перестанут проигрывать.

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

    Но есть и хорошие новости. Мигель Балликора (автор движка "Gaviota") недавно выпустил генератор 5-фигурных таблиц, и собирается делать 6-фигурку. (обсуждение). Особенно ценно намерение автора выпустить исходник под лицензией BSD. (Код доступа к таблицам Налимова, как известно, не свободен).

    Для оценки реальности "сильного" решения шахмат, их можно сравнить с шахматами 3х4, где сильное решение потребовало построения 59 ГБ таблиц в сжатом виде. (167 ГБ в несжатом). (ссылка) :)
  13. vasa Опытный перворазрядник

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    25.298
    Симпатии:
    5.702
    Репутация:
    264
    Адрес:
    Ростов-на-Дону
    Оффлайн
    В общем, пока можно спать спокойно :)
  14. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    У меня получается интервал:
    от (100+37.83712-4.5288)/(0.02562+0.00181) = 4860
    до (100+37.83712+4.5288)/(0.02562-0.00181) = 5979
    Посередине: (100+37.83712)/(0.02562) = 5380 - идеальный игрок.

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    Коэффициенты в линейной регресии - независимые случайные величины, поэтому никто не обещал, что погрешность у них будет синхронно в одну сторону качаться. Так что я взял по максимуму: наибольший числитель при наименьшем знаменателе, и наоборот. Но не суть, на самом деле. А вот то, что прогибаться он начнёт - это наверняка! По моему
    субъективному ощущению, абсолютный игрок живёт где-то в районе 3500.

    Любопытно было бы для шашечных движков такой график нарисовать.
  16. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Я сделал то же самое, только без ошибок. ;)
  17. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Это да, а так же для людей. :) (Где живёт идеальный белковый шахматист).
  18. Crest Админ, МГ

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    46.412
    Симпатии:
    7.534
    Репутация:
    292
    Адрес:
    Москва, Россия
    Оффлайн
    А я реагирую иначе - нервно. Зябко становится, когда вижу, насколько серьезно люди и машины подходят к процессу - об этом можно судить по последним десяти постам.
    Островок людей-шахматистов, мыслящих обобщенными критериями, уменьшается год от года - и все быстрее, как та самая шагреневая кожа, о которой все говорят, но никто не знает, что это такое.

    Лет через 15-20 (оптимистический прогноз) в анализе все станут супермастерами, в адвансе все станут звездами, даже самую сложную позицию раскусят в пять минут, большую часть дебютов закроют, так как основные линии пробьются до эндшпильных баз. Информационные базы станут настолько мощныцми и удобными, что любой пользователь сможет быстро и по любому вопросу выступать как гроссмейстер экстра-класса.

    Одно радует! И через 20 лет все эти компьютерные мастера, посаженные напротив старенького меня за доску - с обычными деревянными фигурками и без компьютерных костылей - будут выглядеть очень бледно. :)
  19. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    В некоторых вещах я человек занудный :)

    И если прибавить сдвиг по оси A, равный 2000, получаем мой (aka правильный) результат ~= 6860.
  20. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    Белковые, разгильдяи, слишком мало играют. Ну что это такое - матч на первенство мира из 14-16, ну хотя бы и 24 партий? Смех один. Если даже при 600 партиях погрешность Эло получается плюс-минус 20 пунктов...
  21. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Я извиняюсь если всех запутал. Сдвиг на 2000 это дефект маркировки оси графика, в формуле 2000 прибавлять не нужно. (Но, (занудства ради) к второму числу - 5979 - вы 2000 всё ж не прибавили). :)
  22. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.159
    Симпатии:
    1.533
    Репутация:
    58
    Адрес:
    Москва
    Оффлайн
    Ну вот, все ошибки нашли - теперь ответ совсем какой-то огромный получается :)
  23. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    365
    Симпатии:
    283
    Репутация:
    9
    Оффлайн
    Ужос!
    Когда смотришь на это звездное небо точек, через которое проведена прямая линия, то остается просто удивляться.
    Kirr, когда вы перестанете дурить народ своей недостоверной статистикой?
    Попробуйте для начала почитать элементарную теорию регрессионного анализа, особенно в части проверки значимости коэффициентов регрессии.
  24. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Юрий, попробуйте яснее изложить свою мысль, пожалуйста! Что не так с коэффициентами?
  25. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Kirr.

    У меня готов 7-фигурный генератор, 3-я версия, который может построить ЛЮБУЮ 7-фигурную базу используя не более 10-11 гигабайт оперативной памяти и без свопа. Это уже не заоблачная цифра, многие материнки поддерживают до 16 гигабайт. А винчестеров тоже должно хватить, т.к. можно соединять их в RAID.

    Но чтобы за приемлемое время построить все 7-фигурные (их сотни), несколько лет, нужно скажем 100 компов! Т.е. параллельно запустить. У меня таких средств нету, нужны спонсоры либо ждать 10 лет удешевления компов.

    А генератор свой я выложу в интернете предположительно в апреле. Могу и сейчас, но решил сначала провести до конца полномасштабное тестирование.
  26. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Неправильно пишет этот Мир науки. Очень мало людей реально понимающих принципы квантовой механики и квантовых компьютеров, чтобы говорить о реальных возможностях таких компьютеров.
  27. Perepelkin_Konstant Учаcтник

    • Участник
    Рег.:
    13.07.2009
    Сообщения:
    102
    Симпатии:
    7
    Репутация:
    0
    Адрес:
    Великий Новгород
    Оффлайн
    А что собственно неправильно написано в "Мире Науки"? Цитата "квантовые компы приведут к существенному убыстрению решения лишь небольшого класса подходящих задач" весьма четка с точки зрения логики, как математической, так и житейской.
    Что касается показательного класса задач, то таким является класс задач факторизации (разложения на множетели) чисел. Разработаны алгоритмы, которые существенно быстрее (если слова экспоненциальный и полиномиальный рост о чем-нибудь говорят :) ) на квантовых (в будущем) компьютерах, чем на современных классических (в настоящем или в будущем). Правда пока те квантовые "счеты" :), которые уже созданы смогли разложить только 15 :)
  28. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    квантовые компы приведут к существенному убыстрению решения БОЛЬШОГО класса подходящих задач
  29. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Супер! Жду апреля!

    Логичным планом был бы набор добровольцев для генерации 7-фигурных таблиц.
  30. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Логично конечно, но организатор из меня не очень... :) где искать добровольцев? Компьютеры способные генерировать 7-фигурные хотя собрать и легко, но они недешевые, обычно у народа компы похуже. Такие, которые нужны, есть разве что у энтузиастов-оверклокеров. Через несколько лет были бы такие у многих, но не сейчас. Сейчас построить за 2-3 года все 7-фигурные базы способен только миллионер (в долларовом понимании) :)
  31. TopicStarter Overlay

    dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    А может у кого то есть доступ к крутым компам?)
  32. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.465
    Симпатии:
    119
    Репутация:
    1
    Оффлайн
    А куда спешить. 5 лет пролетят не заметите. А там и с компами проблемы не будет. Ведь 8-ми фигурки вряд ли в обозримом будущем посчитают. Так что 7-ми фигурок хватит на долгие годы.
  33. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    1
    Репутация:
    0
    Оффлайн
    Да, 8-фигурки никто не осмелится считать я думаю, до 2050-2080 года. Закон Мура по увеличению производительности компов перестанет действовать в 2017-м. Значит по стоимости на единицу мощности - тоже.
  34. Кузьмич Никита

    • Участник
    Рег.:
    29.12.2009
    Сообщения:
    217
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Санкт-Петербург
    Оффлайн
    а почему вдруг именно в 2017-м? :)

    к тому же данный закон является пока работающим, но чисто эмпирическим предположением/наблюдением
  35. vasa Опытный перворазрядник

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    25.298
    Симпатии:
    5.702
    Репутация:
    264
    Адрес:
    Ростов-на-Дону
    Оффлайн
    В честь столетия октябрьской революции? :D

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