Шашки (чекерс) и другие игры-кандидаты на полное решение

Несогласен. Квантовый комп тут не при чем. Проблемы не в быстродействии, а в алгоритмах.

В резерве есть еще канадские (12х12)

Надо же - не знал. Правда я от шашек (с чеккерсами) так же далёк, как Фомальгаут от Альдебарана, но будем знать!

Само по себе создание квантового компьютера не приведет к увеличению скорости вычислений. Не менее важную роль здесь составляют алгоритмы, которые используют всю "нестандартную" мощь квантовых вычислителей.
Например, проблема RSA (суть факторизации) на квантовом компьютере не может быть успешно решена стандартными методами (ECM,QS,NFS). Лишь с помощью алгоритма Шора (созданным им в 1995 г. специально для квантовых машин) можно решить за полиномиальное время проблему разложения больших чисел на простые множители.

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

Техническая сторона данного метода расшифровки заключается во взаимодействии коротких импульсов когерентного светового потока с квантовыми точками. Для большинства людей квантовые точки это мистические частички «научной пыли», так как довольно сложно понять, чем они являются. На самом деле, квантовые точки - это мельчайшие частицы, которые чувствительны к малейшим изменениям. При определенной частоте и фазах, свет образует сложную систему. Луч света сам по себе формирует разновидность «оптической сети» со способностью считывать информацию, по мере перехода от одной квантовой точки к другой.

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

Одним из преимуществ именно такого подхода в криптографии, является использование недорогих диодов в качестве источника света. Максимальная тактовая частота теоретически достигает 100 ГГц. Пока что рабочей частотой в лабораторных условиях является 1,4 ГГц. Для передачи одного бита квантовой информации (кубита) необходим всего лишь один фотон. Энергия, необходимая для передачи 1 кубита, равна 10-18 Дж. Другими словами, чтобы работать на частоте 1 ГГц потребуется всего лишь одна миллиардная ватта. Примечательно, что данная область исследований берет свое начало от ионной ловушки, которая работает в вакууме. Ученые полагали, что ионная ловушка справится с подобной задачей лучше, хотя в итоге оказалось, что ее считывающие способности на несколько порядков ниже, чем у данного подхода. На данный момент конечные продукты с этим решением, по производительности равны процессорам Core 2 Duo или Opteron. Сейчас они уже работают в лаборатории.

Проводящиеся исследования нацелены на будущее использование новой технологии, которая включает в себя лазеры квантовых точек, оптические модуляторы и устройства квантовой логики, которые послужат основой для будущих квантовых компьютеров. Этот проект был основан Агентством национальной безопасности (National Security Agency), Офисом военных исследований (Army Research Office) , Офисом воздушных сил по научным исследованиям (Air Force Office of Scientific Research) и Лабораториями морских исследований (Naval Research Labs). Разработки по данному проекту вел Дункан Стил (Duncan Steel) и три старших исследователя а также около десятка студентов. Университет в Сан Диего занимался теорией, Лаборатории морских исследования занимались физикой квантовых точек, а университет в штате Мичиган занимался вычислительной частью. Годовой бюджет проекта составляет 800000 долларов."
Первоисточник: http://www.3dnews.ru/news/impuls_sveta_vzlamivaet_kodi_bezopasnosti_za_neskolko_sekund-267452/

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

Я специалист по физике квантовых систем, а не по алгоритмам квантовых вычислений, что является скорее разделом математики. И хотя я в курсе общих вещей, сам не берусь объяснять.

Так может и не стоило выпендряться?

Я комментировал именно физику.
А Вы что хотите (можете) прокомментировать?

А какая разница что я могу? Если даже я НИЧЕГО не могу, это что дает Вам повод повыпендриваться ?

Если НИЧЕГО не можете, тогда не встревайте в разговор.

Опять же, заявление типичного выпендрёжника. Я же сказал ЕСЛИ НИЧЕГО. А что я могу можно посмотреть в теме "Меряемся производительностью перфт". Я смог практически с нуля сделать генератор ходов на уровне того же всем известного WildCat. Кроме того, и это главное, мои действия в этом направлении стимулировали работу других программистов. Например Шарк, по его утверждению, благодаря гонке перфтов увеличил скорость своего генератора в 4 раза. Пух задумался о переделке кода на мейлбоксы увидев их эффективность. А теперь ответьте каким боком здесь квантовые точки в физическом смысле к теме "Шашки (чекерс) и другие игры-кандидаты на полное решение"? И слепому видно что чистый выпендрёж. Не могу по теме то хоть то что знаю скажу.

Поздравляю и желаю дальнейших успехов.

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

Оставляю за собой право и далее высказываться по разным вопросам.

Ладно, проехали.

Попробовал алгоритм MCTS в русских шашках (alpha).
Попробовать можно тут http://35.204.55.174/
Надо нажать “New Game White” или “New Game Black” и играть

Сервер слабый (Google Cloud, 1 CPU), так что если тормозит, то лучше играть более вдумчиво
Уровень игры не очень, надо усиливать. Писал для себя, не тестировал сильно. Работает под Chrome для Linux, под Edge 100% можно и не пытаться. Под Android тоже не работает.

Параметры алгоритма: 250 000 симуляций (поэтому в конце игры немного ускоряется), случайное доигрывание, используются шестифигурные таблицы окончаний.

Исходники чуть подправлю и выложу, если будет кому интересно.

Погонял немного. Играет ориентировочно в районе 1-2 разряда, или примерно на равных с 5-6 уровнем программы Чекерсленд. Иногда зевает простую тактику. Но редко. В последней партии просто отдала две шашки.

Нормальных программ в шашках - по пальцам пересчитать. Так что было бы не плохо если выпустите под Винду. Вариативность уже есть, нужно только добавить регулирование силы игры и тогда просто поиграть уже было бы нормально.

Вот исходники: https://gitlab.com/mustitz/rus-checkers (или https://github.com/mustitz/checkers).

Там можно найти:
(1) Генератор ходов на C;
(2) Простой AI на основании тупого полного перебора даже без alpha-beta;
(3) Простой AI на основании алгоритма Monte Carlo Tree Search (MCTS);
(4) Простой Python скрипт для игры между собой;
(5) Алгоритм генерации таблиц окончаний для русских шашек (пока сгенерированы 6-фигурные таблицы полностью 2.7G и 7-фигурные частично, метрика DTC);
(6) Простой web-сервер плюс интерфейс для игры против компьютера.

На самом деле это скорее чистое применение алгоритма MCTS без какого-либо знания о том, что такое шашки. Но даже это уже показывает не самый ужасный результат, плюс субъективно игра программы мне кажется более человечной (те же зевки). Так что человечность игры AlphaZero и LeelaZero мне кажется больше свойством алгоритма MCTS, чем нейросетей. Правда по достижении таблиц окончаний сразу возвращается результат доигрывания, поэтому в конце игра программы достаточно бестолкова — выбирается случайный ход не выпускающий победу. Понятно, что треугольник Петрова на рандоме не построить, ходя большк из рук не выпустит. Надо будет пофиксить

Вообще, в планах было попрактиковаться в Deep Learning, шашки это просто учебный пример для себя. В шахматах большая конкуренция, требуются больше ресурсы. В шашках, я думаю, ситуация будет попроще, плюс можно будет обкатать решения на железе сравнительно небольшой мощности.

Я сначала не понял: а как же AlphaGo Zero? Но потом до меня дошло))

Сыграл турнир с целью определить оптимальный параметр C в Monte Caro Tree Search. По результатам поменял C c 0.5 на 1.3 на http://35.204.55.174/

Код:

 1. mcts-c1.3    ...... ½½½00½ 01½110 ½1½½½½ 1100½½ 1½1½½½ ½½1½1½ ½½1001 011000 1½½½½½ ½½0½½½ ½1½110 ½½0½½1 11½½11 ½1½11½ ½10111 111111 11111½ 111111 111111    75.5
 2. mcts-c1.1    ½½½11½ ...... 0½1½1½ ½½½½½½ ½½0½½1 0½½1½0 ½½½½1½ 001½½0 ½½1½½1 ½10½½½ ½½½½11 ½½½½½½ ½1½½½½ ½½0½1½ 111½1½ 11½1½1 11½111 1111½1 111111 111111    75.0
 3. mcts-c1.5    10½001 1½0½0½ ...... ½1½1½1 ½½½½½½ 1½½0½½ 0½1½½½ ½½0½½½ 1½1½1½ 0½½1½0 ½½1½½½ ½½½½½½ 0½1111 ½½½½0½ ½½½11½ 111½1½ 11½111 ½11111 111½11 111111    73.0
 4. mcts-c1.7    ½0½½½½ ½½½½½½ ½0½0½0 ...... 1½11½½ ½½½½½½ ½½1½01 1½½½1½ 1½½½½1 ½½½0½1 ½½½½11 ½½½½½½ 1½½½1½ ½½½½½½ ½1½½½½ 011½11 ½101½½ 111111 111111 111111    72.5
 5. mcts-c1.9    0011½½ ½½1½½0 ½½½½½½ 0½00½½ ...... ½0½½01 1½½½½½ ½½½0½½ ½0½½½½ ½½½½11 ½½10½½ ½½1½1½ ½1½½½1 1½½½½½ 1½1110 11½1½½ 11111½ 111111 101111 111111    71.5
 6. mcts-c1.4    0½0½½½ 1½½0½1 0½½1½½ ½½½½½½ ½1½½10 ...... ½½½½½0 101½½½ ½½½1½½ ½1½½½1 ½½½½0½ 1½½110 ½110½½ ½½10½0 0½111½ ½01111 111½11 111½11 ½1½111 111111    71.5
 7. mcts-c1.8    ½½0½0½ ½½½½0½ 1½0½½½ ½½0½10 0½½½½½ ½½½½½1 ...... ½1½½½½ ½0½½00 1½½½½1 ½01½½1 ½110½½ 0½0½½½ ½1½11½ 11½½½½ ½1½1½½ 111111 111111 111111 111111    70.5
 8. mcts-c1.2    ½½0110 110½½1 ½½1½½½ 0½½½0½ ½½½1½½ 010½½½ ½0½½½½ ...... 1½½½0½ ½00½½½ ½½½0½½ ½½½1½½ ½½½½1½ 0½½11½ ½½1½½1 ½110½½ 111111 111111 111111 111111    70.5
 9. mcts-c1.0    100111 ½½0½½0 0½0½0½ 0½½½½0 ½1½½½½ ½½½0½½ ½1½½11 0½½½1½ ...... 0½1½½0 ½½½½½1 0½½1½½ 101½½½ ½½½½½½ ½11½11 ½1½1½1 11111½ 11½111 ½11111 101111    69.5
10. mcts-c1.6    0½½½½½ ½01½½½ 1½½0½1 ½½½1½0 ½½½½00 ½0½½½0 0½½½½0 ½11½½½ 1½0½½1 ...... ½1½½½½ ½½½½0½ ½½½1½1 1½½½½½ 1½½1½1 011010 1111½1 ½11111 111111 111111    69.5
11. mcts-c2.0    ½½1½½½ ½½½½00 ½½0½½½ ½½½½00 ½½01½½ ½½½½1½ ½10½½0 ½½½1½½ ½½½½½0 ½0½½½½ ...... ½½½½1½ ½1½110 ½½1111 ½101½½ 1½½11½ 1½½½1½ 111½11 011111 111111    68.5
12. mcts-c0.9    ½0½001 ½½½½½½ ½½½½½½ ½½½½½½ ½½0½0½ 0½½001 ½001½½ ½½½0½½ 1½½0½½ ½½½½1½ ½½½½0½ ...... 11½½½½ ½½½½½1 1½½1½½ ½½11½1 01111½ 111111 111111 111111    67.5
13. mcts-c0.8    ½½1½½0 ½0½½½½ 1½0000 0½½½0½ ½0½½½0 ½001½½ 1½1½½½ ½½½½0½ 010½½½ ½½½0½0 ½0½001 00½½½½ ...... 101½1½ 101½1½ 11½½½½ 111½1½ 1½1111 111111 1½1111    62.5
14. mcts-c0.7    00½½00 ½½1½0½ ½½½½1½ ½½½½½½ 0½½½½½ ½½01½1 ½0½00½ 1½½00½ ½½½½½½ 0½½½½½ ½½0000 ½½½½½0 010½0½ ...... 1011½0 1½1111 1½0111 11½111 1½1110 1111½1    60.5
15. mcts-c0.6    ½0½00½ 000½0½ ½½½00½ ½0½½½½ 0½0001 1½000½ 00½½½½ ½½0½½0 ½00½00 0½½0½0 ½010½½ 0½½0½½ 010½0½ 0100½1 ...... 11001½ 11½½11 111111 11111½ 111111    52.0
16. mcts-c0.5    ½01000 00½0½0 000½0½ 100½00 00½0½½ ½10000 ½0½0½½ ½001½½ ½0½0½0 100101 0½½00½ ½½00½0 00½½½½ 0½0000 00110½ ...... ½011½1 1½1½11 111111 111111    46.0
17. mcts-c0.4    000000 00½000 00½000 ½010½½ 00000½ 000½00 000000 000000 00000½ 0000½0 0½½½0½ 10000½ 000½0½ 0½1000 00½½00 ½100½0 ...... ½11½½½ 111110 111½½1    28.5
18. mcts-c0.3    00000½ 0000½0 ½00000 000000 000000 000½00 000000 000000 00½000 ½00000 000½00 000000 0½0000 00½000 000000 0½0½00 ½00½½½ ...... 01½111 ½11110    16.5
19. mcts-c0.2    000000 000000 000½00 000000 010000 ½0½000 000000 000000 ½00000 000000 100000 000000 000000 0½0001 00000½ 000000 000001 10½000 ...... 0½10½1    11.5
20. mcts-c0.1    000000 000000 000000 000000 000000 000000 000000 000000 010000 000000 000000 000000 0½0000 0000½0 000000 000000 000½½0 ½00001 1½01½0 ......     7.5

Кстати, как можно посчитать рейтинги по результатам турнира? Пробовал из системы линейных уравнений R0 = 0, Ri - Raverage = ExpectedEloDiff(points/maximus), но где-то напутал...

Да, я думал об этом. Не мне хотелось решить аналитически. Ну и я довёл это до ума.

Итак, если записать математическое ожидание каждого игрока, то мы получим
R[i] - Ravr[i] = EloDiff(S[i]),
где R[i] - рейтинг i-го игрока, Ravr[i] - выражение для среднего рейтинга соперников, EloDiff это разница в Эло,котоая соотвествует проценту набранных очков S[i].

Получается вырожденная система линейных уравнений (если сложить все уравнения системы, то получим 0 = Sum(i, EloDiff(S[i])). Она имеет точное решение, если сумма разниц в рейтинге в правой части равна нулю.Мне казалось, что это всегда так (это справедливо для двух игроков, и это случайно совпало в одном из тестовых примеров). В этом случае мы можем присвоить любому игроку произвольный рейтинг, остальные рейтинги можно получить из решения системы.

Вот только в общем случае это не так, и сумма в правой части необязательно нулевая. В этом случае точного решения система не имеет, что означает, что невозможно присовить рейтинги всем игрокам так, чтобы средний результат соответствовал разнице Эло. Но можно найти оптимальное решение, чтобы оптимизировать разность квадратов между левой и правой частью. Задача эта хоро известна, и метод numpy.linalg.lstsq хорошо с этим справляется.

Правда, подозреваю, что оба метода будут давать одинаковые результаты

n = len(estimate_list)
dim = n, n
A = np.zeros(dim)
B = np.zeros(n)

elo_diff = lambda e: -400 * log10(1/e-1)
for player in estimate_list:

i1 = names.index(player['name'])
for k, v in player['stats'].items():

i2 = names.index(k)
A[i1, i2] = 1.0 if i1 == i2 else -v['qgames'] / player['qgames']​

B[i1] = elo_diff(player['nscore'])​

X = np.linalg.lstsq(A, B, rcond=None)
R = X[0]
R = list(R-min(R))

http://35.204.55.174/
Немного пофиксил без в игре перед ETB.
Теперь сила игры определяется числом просмотренных узлов (поэтому время расходуется более-менее равномерно).
Добавил эвристику выбирать ход в rollout-е не случайно из всех узлов, в которых не было доигрывания (раньше было из всех узлов), что дало примерно +15-20 ELO.

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

А разве нейронная сеть вместе с мктс не использовалась до Гугла в го? Мне казалось, что использовалась, но сети были маленькими, фичи в сети задавались явно. И веса подбирались либо вручную, и как-то оптимизировались, либо было обучение с учителем. Мне казалось именно большие вычислительные мощности Гугла позволили использовать большие сети, дип лернинг, и только тогда программа заиграла на уровне человека. Не так было?

MCTS дал заметное усиление в игре го-программ. Но нейронные сети не привлекали, писали больше свои эвристики. Точно так же нейронная сеть может использоваться и в alpha-beta переборе, но... это целый ворох проблем, проще написать свою эвристическую оценку. Точно так же вот есть Komodo MCTS, играет на 200 ELO слабее оригинальной версии, но при этом сколько времени тратилось на разработку и доводку до ума? Думаю не сравнить с оригинальной Alpha-Beta.

А для нейросети надо много ресурсов для обучения. В шахматах первой ласточной был Жираф, и это 2500 ELO (обучение на обычном железе).

Насколько я знаю, именно в сочетании, они не использовались. До 2006 года оба подхода считались альтернативными, разрабатывались считанными энтузиастами по отдельности и давали плохие результаты. С 2007 года MCTS оказался на пике популярности, результаты быстро росли, поэтому все внимание было направлено на него. Нейросети до 2012 года были не особо популярны. Но в 2012 году многослойные нейросети вдруг начали показывать отличные результаты в других областях, поэтому необходимость попробовать их в го стала достаточно очевидной. С новыми знаниями и мощностями.

Долго ждать не пришлось, в 2014 году независимо друг от друга, какие-то студенты из Эдинбурга и Гугл решили потренировать нейросети для го. Результаты получились сносные. Теперь уже скрещивание MCTS и нейросетей прямо-таки напрашивалось. Ну а дальше всё завертелось.

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