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

Тема в разделе "Машинное отделение", создана пользователем vasa, 25 июл 2007.

  1. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Несогласен. Квантовый комп тут не при чем. Проблемы не в быстродействии, а в алгоритмах.
  2. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Практическая ценность игры 6х6 - обучение начинающих.
    См. например прекрасный самоучитель Ильи Ветрова: http://okruzhor.chat.ru/AGA_66/index.htm
  3. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    После появления квантового компа её съедят именно быстродействием. Как и алгоритм RSA.
  4. romm KMC

    • Заслуженный
    • Участник
    Рег.:
    21.02.2006
    Сообщения:
    2.267
    Симпатии:
    14
    Репутация:
    0
    Адрес:
    Сан-Хозе, Калифорния
    Оффлайн
    В резерве есть еще канадские (12х12)
  5. immortal223 Вячеслав

    • Участник
    Рег.:
    22.02.2006
    Сообщения:
    2.412
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Надо же - не знал. :) Правда я от шашек (с чеккерсами) так же далёк, как Фомальгаут от Альдебарана, но будем знать!
  6. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Ну а я внёс свой очень скромный вклад в дело прогресса, решив шахматы на доске 3x3 :) Всё собираюсь закончить решение 3х4, но никак нет времени.. Если удастся выкроить время, хочу ещё порешать варианты Шоги, это ещё интереснее шахмат.
  7. VolMike Учаcтник

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

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

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

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

    Одним из преимуществ именно такого подхода в криптографии, является использование недорогих диодов в качестве источника света. Максимальная тактовая частота теоретически достигает 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/
  9. Quantrinas Учаcтник

    • Участник
    Рег.:
    13.02.2007
    Сообщения:
    3.371
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Как специалист по квантовым точкам, ответственно заявляю, после этого бредового определения дальше можно не читать. :D
  10. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Спасибо, хотя про алгоритм Шора (а также Гровера и Дойча) я в курсе, и один из них могу даже "на пальцах" объяснить. Хотя лучше попросить Quantrinas как специалиста провести нам тут краткий ликбез по квантовым вычислениям. Ибо он назвался груздем :)

    Речь о том, что именно применение этих алгоритмов даст эффективное увеличение быстродействия на много-много порядков. А то, что каждое конкретное "железо" требует своё специфическое матобеспечение - факт, в общем-то, давно известный :)
  11. Quantrinas Учаcтник

    • Участник
    Рег.:
    13.02.2007
    Сообщения:
    3.371
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Я специалист по физике квантовых систем, а не по алгоритмам квантовых вычислений, что является скорее разделом математики. И хотя я в курсе общих вещей, сам не берусь объяснять.
  12. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    Так может и не стоило выпендряться? :)
  13. Quantrinas Учаcтник

    • Участник
    Рег.:
    13.02.2007
    Сообщения:
    3.371
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Я комментировал именно физику.
    А Вы что хотите (можете) прокомментировать?
  14. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
  15. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    А какая разница что я могу? Если даже я НИЧЕГО не могу, это что дает Вам повод повыпендриваться ? :)
  16. Quantrinas Учаcтник

    • Участник
    Рег.:
    13.02.2007
    Сообщения:
    3.371
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Если НИЧЕГО не можете, тогда не встревайте в разговор.
  17. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    Опять же, заявление типичного выпендрёжника. Я же сказал ЕСЛИ НИЧЕГО. А что я могу можно посмотреть в теме "Меряемся производительностью перфт". Я смог практически с нуля сделать генератор ходов на уровне того же всем известного WildCat. Кроме того, и это главное, мои действия в этом направлении стимулировали работу других программистов. Например Шарк, по его утверждению, благодаря гонке перфтов увеличил скорость своего генератора в 4 раза. Пух задумался о переделке кода на мейлбоксы увидев их эффективность. А теперь ответьте каким боком здесь квантовые точки в физическом смысле к теме "Шашки (чекерс) и другие игры-кандидаты на полное решение"? И слепому видно что чистый выпендрёж. Не могу по теме то хоть то что знаю скажу. :)
  18. Quantrinas Учаcтник

    • Участник
    Рег.:
    13.02.2007
    Сообщения:
    3.371
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Поздравляю и желаю дальнейших успехов.

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

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    122
    Репутация:
    1
    Оффлайн
    Ладно, проехали.
  20. Mustitz Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    Попробовал алгоритм MCTS в русских шашках (alpha).
    Попробовать можно тут http://35.204.55.174/
    Надо нажать “New Game White” или “New Game Black” и играть

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

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

    Исходники чуть подправлю и выложу, если будет кому интересно.
    WinPooh, Rom, Pied_Piper и ещё 1-му нравится это.
  21. Pied_Piper Крысолов

    • Участник
    Рег.:
    28.08.2016
    Сообщения:
    776
    Симпатии:
    686
    Репутация:
    37
    Нарушения:
    22
    Оффлайн
    Исходники это всегда хорошо
  22. Rom Учаcтник

    • Участник
    Рег.:
    12.02.2012
    Сообщения:
    499
    Симпатии:
    182
    Репутация:
    21
    Онлайн
    Погонял немного. Играет ориентировочно в районе 1-2 разряда, или примерно на равных с 5-6 уровнем программы Чекерсленд. Иногда зевает простую тактику. Но редко. В последней партии просто отдала две шашки.

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

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    Вот исходники: 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, шашки это просто учебный пример для себя. В шахматах большая конкуренция, требуются больше ресурсы. В шашках, я думаю, ситуация будет попроще, плюс можно будет обкатать решения на железе сравнительно небольшой мощности.
  24. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Как прекрасно читать собственные предсказания через каких-то одиннадцать лет. Вырабатывает смирение и самокритичность.
    grizly, sovaz1997 и Zayats нравится это.
  25. sovaz1997 Учаcтник

    • Участник
    Рег.:
    30.08.2016
    Сообщения:
    419
    Симпатии:
    57
    Репутация:
    3
    Онлайн
    Я сначала не понял: а как же AlphaGo Zero? Но потом до меня дошло))
  26. Mustitz Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    Сыграл турнир с целью определить оптимальный параметр 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), но где-то напутал...
  27. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Рейтинг можно считать методом итераций. Присвоить всем одно и то же стартовое значение, посчитать для каждого средний рейтинг соперников, вычислить ожидаемое число очков. И добавить к рейтингу прибавку или штраф за перебор или недобор очков до этого матожидания. Затем снова посчитать ожидаемые результаты, и новые штрафы и прибавки. Повторять, пока не устаканится.
    Так работает программа bayeselo.
    https://www.remi-coulom.fr/Bayesian-Elo/
    Mustitz и sovaz1997 нравится это.
  28. Mustitz Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    Да, я думал об этом. Не мне хотелось решить аналитически. Ну и я довёл это до ума.

    Итак, если записать математическое ожидание каждого игрока, то мы получим
    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))
  29. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Так в том то и дело, что при любом подходе нам придётся решать задачу оптимизации. Либо для суммы квадратов отклонения набранных очков, либо для суммы квадратов отклонения присвоенных рейтингов.
    Просто другой базис. Конечно, из спортивного интереса можно для этой задачи оптимизации найти аналитическое решение...
    Интересно ещё посмотреть, насколько эти схемы дают близкий результат с системами игровых серверов, когда после каждой партии у обоих соперников слегка меняется рейтинг.
  30. Mustitz Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    http://35.204.55.174/
    Немного пофиксил без в игре перед ETB.
    Теперь сила игры определяется числом просмотренных узлов (поэтому время расходуется более-менее равномерно).
    Добавил эвристику выбирать ход в rollout-е не случайно из всех узлов, в которых не было доигрывания (раньше было из всех узлов), что дало примерно +15-20 ELO.
  31. grizly Новичок

    • Новичок
    Рег.:
    10.05.2015
    Сообщения:
    39
    Симпатии:
    148
    Репутация:
    10
    Оффлайн
    Тоже сейчас прочитал. Наверно даже не произошло ничего настолько революционного за последние 10 лет. Увеличились компьютерные мощности, и задачи ранее недоступные стало возможно решать методами, для которых этих мощностей не хватало.
  32. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.706
    Симпатии:
    1.951
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Главное, догадались соединить нейронные сети и поиск Монте-Карло. С эффектом взаимного усиления.
  33. grizly Новичок

    • Новичок
    Рег.:
    10.05.2015
    Сообщения:
    39
    Симпатии:
    148
    Репутация:
    10
    Оффлайн
    А разве нейронная сеть вместе с мктс не использовалась до Гугла в го? Мне казалось, что использовалась, но сети были маленькими, фичи в сети задавались явно. И веса подбирались либо вручную, и как-то оптимизировались, либо было обучение с учителем. Мне казалось именно большие вычислительные мощности Гугла позволили использовать большие сети, дип лернинг, и только тогда программа заиграла на уровне человека. Не так было?
  34. Mustitz Заслуженный

    • Заслуженный
    • Участник
    Рег.:
    30.09.2006
    Сообщения:
    2.851
    Симпатии:
    311
    Репутация:
    21
    Адрес:
    Киев
    Оффлайн
    MCTS дал заметное усиление в игре го-программ. Но нейронные сети не привлекали, писали больше свои эвристики. Точно так же нейронная сеть может использоваться и в alpha-beta переборе, но... это целый ворох проблем, проще написать свою эвристическую оценку. Точно так же вот есть Komodo MCTS, играет на 200 ELO слабее оригинальной версии, но при этом сколько времени тратилось на разработку и доводку до ума? Думаю не сравнить с оригинальной Alpha-Beta.

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

    • Участник
    Рег.:
    12.02.2012
    Сообщения:
    499
    Симпатии:
    182
    Репутация:
    21
    Онлайн
    Насколько я знаю, именно в сочетании, они не использовались. До 2006 года оба подхода считались альтернативными, разрабатывались считанными энтузиастами по отдельности и давали плохие результаты. С 2007 года MCTS оказался на пике популярности, результаты быстро росли, поэтому все внимание было направлено на него. Нейросети до 2012 года были не особо популярны. Но в 2012 году многослойные нейросети вдруг начали показывать отличные результаты в других областях, поэтому необходимость попробовать их в го стала достаточно очевидной. С новыми знаниями и мощностями.

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

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

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