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

Вопрос не в том, сможет или не сможет. Вопрос - захочет ли...

Да, до 32-фигурных еще далеко.

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

Я могу абсолютно безошибочно играть в крестики-нолики на доске 3х3. При этом я не должен держать в памяти всё дерево из нескольких сотен позиций (с учётом симметрий - из 50-ти).

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

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

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

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

Решение английских шашек командой Chinook не использует 24-фигурные таблицы, а обходится всего лишь 10-фигурными. Думаю, и в шахматах 10-12 фигурные таблицы должны быть достаточны.

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

Для примера - график зависимости числа ничьих от рейтинга в турнире движков KCEC:

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

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

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

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

То есть, если погрешности упрутся в одну сторону, получим для стопроцентных показателей ничьих:
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 Эло.
Как-то странно. Наверное, линейную модель применять нельзя.

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

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

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

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

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

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

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

В общем, пока можно спать спокойно

У меня получается интервал:
от (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 - идеальный игрок.

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

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

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

Я сделал то же самое, только без ошибок.

Это да, а так же для людей. (Где живёт идеальный белковый шахматист).

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

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

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

В некоторых вещах я человек занудный

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

Белковые, разгильдяи, слишком мало играют. Ну что это такое - матч на первенство мира из 14-16, ну хотя бы и 24 партий? Смех один. Если даже при 600 партиях погрешность Эло получается плюс-минус 20 пунктов...

Я извиняюсь если всех запутал. Сдвиг на 2000 это дефект маркировки оси графика, в формуле 2000 прибавлять не нужно. (Но, (занудства ради) к второму числу - 5979 - вы 2000 всё ж не прибавили).

Ну вот, все ошибки нашли - теперь ответ совсем какой-то огромный получается

Юрий, попробуйте яснее изложить свою мысль, пожалуйста! Что не так с коэффициентами?

Супер! Жду апреля!

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

В честь столетия октябрьской революции?