Есть кто-нибудь, кто сможет на пальцах объяснить принцип работы AlphaZero, которая вынесла даже Стокфиш?? Как я понял, там используются обучающиеся нейронные сети и не используется классический Шенноновский метод создания дерева перебора вариантов с минимаксом.

https://habr.com/post/343590/

используется метод поиска монте-карло
https://habr.com/post/282522/

Стокфиш, на сколько знаю, последний раз играл версией 8.
Потом, достаточно сомнительно, что АльфаЗиро нашла все начала, которые в Рыбке заложены как библиотека дебютов.

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

Во-первых, почему не с 10й версией играла, во-вторых дебюты. Шипов говорил, что некоторые идеи прямо вот-вот, последние разработки теории.
Т.е. допустим, что Альфа играет сильнее. Он сам додумал всю библиотеку?! Если бы он это сделал, имхо, он бы не проиграл ни разу. А он проигрывал, 6 поражений, 839 ничьих

> Во-первых, почему не с 10й версией играла

насколько я понял новая версия играла то ли с 9 то ли с 10-й версией.

кстати у меня антивирус находит вирус на офиц.сайте стокфиша для 10-й версии

не, в декабре матч из 1000 партий против 8й версии был
Шипов еще говорил, что 10-ка некоторые моменты Альфы разгадала, когда он давал подумать ей

https://www.chess.com/ru/news/view/novaia-versiia-alphazero-razgromila-stockfish-v-matche-iz-1-000-partii
"В дополнительных матчах новая AlphaZero победила "последнюю разрабатываемую версию" Stockfish почти с тем же результатом, что и в матче со Stockfish 8. В окончательной версии статьи указано, что AlphaZero играла против последней разрабатываемой версии Stockfish на 13 января 2018, то есть, Stockfish 9."

вот написано что было сыграно сколько то партий с 9-ой версией с тем же результатом почти, правда без подробностей

и там же

Партия 2 с анализом Stockfish 10:
Stockfish 8 vs. AlphaZero

Че пишут..

> Че пишут..

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

6 дек. 2018 - разгромила Stockfish8

AlphaZero играла против последней разрабатываемой версии Stockfish на 13 января 2018, то есть, Stockfish 9

- > 13 января 2018 - Stockfish 9

Что-то мне подсказывает, что январь идет перед декабрем.
т.е. разгромив в январе 9ку, в декабре стала играть с 8кой?

Сдается мне, что писатель статьи путается в показаниях. На кол, собаку!

> Сдается мне, что писатель статьи путается в показаниях

не принципиально, главное играла и с ней

смотря как смотря )
Нейросеть это, конечно, гуд. Но без банального перебора и дебютов - о-оочень сомневаюсь что обошлось.
Еще раз, уточню: Не сомневаюсь, что AZ побил бы 8,9 и даже 10. Очень может быть. Почему бы и нет.
Но заявить, что перебор и дебюты не юзаются .. ну.. не знаю.

> что перебор и дебюты не юзаются

почему? перебор есть и алгоритм Monte-Carlo Tree Search они вроде как декларируют.
А дебюты выводятся нейросетью самообучением с нуля.
Почему это невозможно?

Ну раз перебор есть, то ладно )
Не внимательно читал, значит

Дебюты.. черт его знает, на самом деле. Может и можно вывести. Я только сомневаюсь, что они будут похожи на "человеческие". Но, в принципе, они и не показали базу дебютов AZ, которую он сам вывел (якобы)

Одно из сомнений породил тот факт, что компьютер довольно часто ломал знаменитые задачи на мат в 4 и более ходов. Опровергал их, находил защиту.
По идее, он должен опровергнуть и дебют. На каком-нибудь 7-8-9 ходе наказать противника своей "новинкой". Ну, если он сам это все вывел, такое должно быть у него.

> По идее, он должен опровергнуть и дебют

не ну согласись в дебюте у людей сотни лет игр и всем понятные схемы
быстрейшего развития и атаки уже понятны любому кмс,
одной из "новинок" альфазеро на грани дебюта-миттельшпиля стала
активация чернопольного слона белых на диагонали а1-h8  и одновременная жертва пешки g2 с открытием вертикали g для ладьи и долговременным давлением на пункт g7
Эта тема во многих играх со стокфишем проскальзывает...

> одной из "новинок" альфазеро

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

> любит задвигать крайние пешки

ага, смотрел )

> ага, смотрел )

думаю если пересмотреть все партии альфазеро можно еще что-то найти -
так что новинки есть и стратегические в том числе

> новинки есть и стратегические в том числе

Прям на 5-6-7 ходе не видал. Конечно, видал только те, которые Шипов показывал. Может и есть новинки, конечно.
Там предлагают скачать архив, вроде.. Но, боюсь, нашей квалификации не хватит оценить )
С др. стороны, думаю, что кто-то скачивал, смотрел.. Но не видал отзывов о новинках

имхо большинство новинок в миттельшпиле и игра в дебюте на ограничение,
так сказать сначала зажимает - потом добивание с огоньком :)

Когда объясняют - да ). Становится понятно, как ловко зажимает )

> Становится понятно, как ловко зажимает

может через сто лет появиться программа которая нынешние в одном потоке будет
черными побеждать без особого напряга, вот тогда мы будем говорить ловко :)
Движки за последние годы сильно эволюционировали, но это не означает конец -
скорей только начало чего-то бОльшего. Существование такой программы как альфазеро
это только подтверждает. К тому же уже сейчас есть нейросеть для "обычного железа" -
http://lczero.org/ и она тоже не слабо прогрессирует. А что будет через 10 лет? 50? 100?

Я думаю человек на пороге создания искусственной жизни - не меньше.
Я не знаю как насчет души у этой всей машинерии, но факт остается фактом -
программы развиваются и пока конечно не дошли до полностью автономного саморазвития,
но все предпосылки к этому имеются... Я боюсь за то, что разработчик такой программы в
конечном счете ошибётся в постановке цели для машины и тогда возможны нехорошие
сценарии или более того такой разработчик сможет запрограммировать так что, цели
будут выбираться динамически и абстрактно, тогда уже такую программу можно будет
назвать разумной, а это проблема... Проблема отношений между искусственным и естественным.
На эту тему у человечество огромное количество фантастических книг, чаще с апокалиптическим
сюжетом. И на этом будет учиться машина? Человек сейчас мало что может дать своему ребенку,
тому приходится все постигать на собственном опыте. А что человек может дать машине?
В большинстве только негативную информацию, коей на просторах интернета достаточно.
Другой вопрос что целью должно стать поиск чего-то положительного, но сие сложно
запрограммировать динамической постановкой целей, если вообще такая задача будет стоять...

> xayam ©   (07.01.19 19:23) [21]


не.. как-то ты мрачен ))
Изобретатель топора примерно так же, наверное, был. Можно хату срубить, а можно и соседу по черепушке двинуть.
Смотря в чьи руки попадет..

Кстати, надо глянуть прогноз производительности железа. Гугл легко может позволить себе Альфу, никаких сомнений. Но, вроде, это экстенсивный путь. Они там нагородили кучу серверов, конечно, у них все будет ok..
А вот такое, что бы под столом стояло и было сравнимой мощности?
Пока, на сколько опять же помню, достигнут предел (практически). Ждем революцию )

> Смотря в чьи руки попадет..

проблема в том что в данном случае у нас разумный (читай неконтролируемый) топор

ну.. у  этого умника есть розетка )

> ну.. у  этого умника есть розетка )

ключевое слово - ПОКА есть :)

тем более проблемой может стать не сама розетка,
а то что она охраняема самим ИИ и его
сподвижниками :)

> xayam ©   (07.01.19 20:20) [26]
> > ну.. у  этого умника есть розетка )
> ключевое слово - ПОКА есть :)

или более того розеток может быть миллион и отключение всех
будет равносильна отказу от электричества для всего человечества :)

SkyNet? )
Далеко нам до этого, все же. Не разделяю оптимизма про ИИ. Создадут максимум эксперта в одном направлении. Картинки распознавать, в шахматы играть.
Ну да, или планировать ядерные удары максимальной эффективности

могут соединить несколько направлений.

Но вот что бы прям вот такой разум, который бы начал розетки защищать и Т-800 печатать для поиска и убийства Била Гейтса 2.0 - не, для такого мы еще долго не будем готовы, имхо
хотя.. для некоторых Т-800 надо вызвать, 100%% ))

> SkyNet? )

а что не веришь? Но всё к этому идёт...
Не знаю сколько на это понадобиться лет, но если вектор развития сохранится,
то я оцениваю максимально - 100 лет и если человечество к тому времени
не погибнет во вспышке ядерного взрыва, то будет и такая проблема как дополнение к
остальным...

Опасность есть. Но больше, думаю, опасность в ошибке в коде, чем, что ИИ САМ решит поработить всех.
Т.е. скорее кто-то посадит AV и он запустит все ракеты, чем он осознанно запустит все ракеты. Еще и потому, что человечество было бы идиотами, если бы отдало под контроль ИИ все, без возможности остановить в любой момент через какой-нить бэкдор

> если бы отдало под контроль ИИ все, без возможности остановить
> в любой момент через какой-нить бэкдор

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

> xayam ©   (08.01.19 00:57) [32]

Защелку ему тогда, как на дискетке )
Пока пимку не отодвинешь, фиг тебе а не запись. И все это в ядре. И граната привязана к пимпке, что бы не сдвинуть )

а копии делать тоже запретить? Где-то записывать должно быть разрешено,
иначе как творить :)

На отдельный носитель творить будет. А ядро для модификации для самого ИИ закрыто

Зацени )
Только что получилось сыграть на личесс )) (https://lichess.org)

https://cloud.mail.ru/public/N7kQ/qxZFNY25W
мат в 4 хода

> мат в 4 хода

это называется  - спертый мат

> На отдельный носитель творить будет

а если это будет программа? Можно будет запустить с носителя?

Ну конечно
Как раньше дискеты работали, 3.5 которые
http://www.delphiplus.org/images/dvip02/dvip02-131.png
все читается, а писать нельзя пока защелку не сдвинешь. Вот ядро будет на таком носителе, а остальное на другом - там пусть переписывает

> Как раньше дискеты работали

да, но всегда можно перенести на другой носитель пишущий и такого ограничения не будет

оно возьмет контроль над роботом, который передвинет защелку )

> xayam ©  

кстати, про обман или действительно ИИ )

Недавно статейка попалась, как нейронка из фотки со спутника и карты улиц  строила 3d вид этих улиц
Так эта коза построила такие мелочи, что ее проверили тут же.
И выяснилось, что она (или программист?) пользовались доп.данными ) Что-то там тихо ей рисовали, незаметно, заранее.
Потому что она там в одном месте столб нарисовала. А на корте его нет, и со спутника не видать, что это столб. В общем, спалилась на мелочи.
Вот что-то мне подсказывает, что Альфе тоже немного помогли )

> оно возьмет контроль над роботом, который передвинет защелку
> )


Все ходы записаны!
>> граната привязана к пимпке

т.е. растяжка стоит.
Отключить нельзя, граната выведена во внутрь. Как ядро переписывать.. хм.. придумал! -  Никак! )

> ВладОшин ©   (09.01.19 22:48) [42]

оно возьмет контроль над пылесосом,
которым удаляют пыль в системном блоке,
он обезвредит гранату и передвинет защелку

или аккуратно распилит корпус

или дырочку просверлит

или или

> Sha

хотел услышать твое мнение об этом -
http://pda.delphimaster.net/?id=1546676061&n=3

твоя вторая гипотеза равносильна проблеме Гольдбаха, так что извиняй

> Sha ©   (10.01.19 13:14) [45]
> твоя вторая гипотеза равносильна проблеме Гольдбаха, так
> что извиняй

то что равносильна я и сам понимаю.
А почему график такой возрастающий?

чисто умозрительно: чем больше K, тем больше у него вариантов оказаться точно посередине между двумя простыми

> чисто умозрительно

вопрос как это доказать?
я думаю ответ никто не знает конечно :)

никто не знает, как доказать, что есть хотя бы 1 вариант )

> никто не знает, как доказать, что есть хотя бы 1 вариант
> )

ну если доказать что есть асимптота снизу существует, то хотя один вариант существует :)

> xayam ©   (10.01.19 12:08) [44]


xayam ©   (08.01.19 02:03) [16]
вот "остается" доказать что нижняя граница стремиться к какой-то возрастающей ассимптоте и считай гипотеза доказана.


Как все просто на самом деле! А матерые математики всего мира чешут репу годами )))

BTW, на TCEC LeelaZero (open source реализация по идеям AlphaZero) тоже обыгрывает Stockfish 8:
https://tcec.chessdom.com/

> Mystic ©   (17.01.19 14:39) [52]

думаешь уже stockfish 10 обыграет?

по очкам пока отстает

> думаешь уже stockfish 10 обыграет?


Сейчас там кубок, скоро суперфинал SF - Lc0. Посмотрим, но вряд ли.




KomodoMCTS дисквалифицировали за крэши и его результаты аннулировали, так что Lc0 на втором месте. В остальном пока что SF10 пока что ведёт и в личной встрече, и по очкам, и по рейтингу. Но посмотрим, какую сетку выберут для суперфинала.

> скоро суперфинал SF - Lc0

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

> Конечно, у lc0 шанс есть, но думаю не в этом сезоне - она
> пока не готова,
> не полностью обучена


Дык и SF тоже развивается (можно сравнить хотя бы с восьмой версией). Lc0 как раз может подсказать как его улучшить :)

> Дык и SF тоже развивается

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

что интересно - в разработке обоих движков участвует один человек - Гэри Линскотт,
поэтому развитие одного - это развитие и второго :)
lc0 сейчас фактически только обкатывают, когда там пройдет серьезное обучение и
уберут детские болезни - у sf нет шансов в перспективе, самообучение его убьет, хотя
я думаю будущее за гибридной системой lc0+sf

SF уже давно не развивается вручную (да и другие топовые движки тоже). Большинство коэффициентов тюняться в результате большого количество тренировочных партий между собой/другими движками. Прирост силы SF результат одного китйца, который предоставил большие мощности для наигрывания этих партий (плюс и для TCEC). Сейчас появиться возможность задействовать и Lc0 для обучения SF.

Гибридные системы не очень приживаются в живом мире и в технике. Например, бомбардировщик B-36 имел 6 винтовых и 4 реактивных двигателя, но удачным не был. Хотя ансамблевые модели сейчас дают прирост в несколько процентов в Deep Learning.

Lc0 немного останавливает общность концепции — один алгоритм для всех игр. Думаю, если завести на вход NN несколько дополнительных параметров, она играла бы сильнее. Например, я предлагал считать белопольных и чернопольных слонов разными фигурами.

Убрать детские болезни тоже непросто. Что считать детской болезнью? По сути нужна ещё одна NN сеть-гипервизор.

Опять же, железо разное, и сравнивать SF vs Lc0 нечестно. Надо проводить турнир в одинаковых условиях, например ограничить потребление энергии от блока питания в 1 kW. А там используюй что хочешь :)

> Опять же, железо разное, и сравнивать SF vs Lc0 нечестно.
>  Надо проводить турнир в одинаковых условиях, например ограничить
> потребление энергии от блока питания в 1 kW. А там используюй
> что хочешь :)

а lc0 на gpu играет? тогда может быть и так

> а lc0 на gpu играет? тогда может быть и так


На TCEC Lc0 Да, на GPU, причём достаточно топовая конфигурация. А так играет  и на CPU, но очень слабо.

> А так играет  и на CPU, но очень слабо

то есть фактически gpu vs cpu? И что больше энергии жрет?

> SF уже давно не развивается вручную (да и другие топовые
> движки тоже). Большинство коэффициентов тюняться в результате
> большого количество тренировочных партий между собой/другими
> движками

не ну сам коэффициент вносится вручную же?
а у lc0 динамически определяется

> не ну сам коэффициент вносится вручную же?

я так понимаю в sf реализовано что-то типа этого только больше коэффициентов
https://habr.com/ru/post/305604/
но вот чтобы иметь новый коэффициент - его нужно явно определить

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

> то есть фактически gpu vs cpu? И что больше энергии жрет?


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


> не ну сам коэффициент вносится вручную же?
> а у lc0 динамически определяется


Вот поэтому у SF коэффициентов тысячи, а у Lc0 миллионы. Но в целом аналогично SF, в случае надо ещё задать модель нейронной сети. Тут тоже возможны нюансы — неправильно задашь — не обучишь ничему.

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

> Подход SF: давай подумаем какие коэффициенты и эвристики
> будут полезны. Запрограммируем их.
> Подход Lc0: создадим сеть с десятью миллионам коэффициентов,
>  а сеть сама решит, какие из них чему надо присвоить.

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

когда вообще суперфинал начинается?

Закончится кубок, начнёться...


> и я думаю что есть вероятность пропустить что-то новое,
> lc0 же это новое усиленно ищет.


Ну... это неправильный взгляд на вещи. Найти что-то новое это немного неправильно. Даже если Lc0 уйдёт в отрыв, то человек всё равно не сможет понять, что же именно нашла Lc0.

Повторяю, у SF 1000 коэффициентов, которые добавили люди исходя из понимания работы движка. У Lc0 миллионы коэффициентов, которые добавили исходя из понимания работы нейросети. Понятно, что миллион коэффициентов дадут более точное понимание позиции, но это дополнительное время на выбор хода.

Есть ещё интересный движок Komodo MCTS, который исползует технику случайных доигрываний Monte Carlo, как и Lc0, но у него ходы кандидаты выбираются исходя из анализа позиции по alpha-beta. Движок достаточно интересный, за год развития уже практически вошёл в TOP-5. В перспективе ставлю на него :)

> Есть ещё интересный движок Komodo MCTS, который исползует
> технику случайных доигрываний Monte Carlo, как и Lc0, но
> у него ходы кандидаты выбираются исходя из анализа позиции
> по alpha-beta. Движок достаточно интересный, за год развития
> уже практически вошёл в TOP-5. В перспективе ставлю на него

так вот получается что он гибридный :) А говорил что это плохо

> так вот получается что он гибридный


Гибридный, это когда мы берём два движка, которые играют одинаково сильно, и строим из них третий. Тут же alpha-beta специфический, его задача получить не только оценку, но и достоверность. Сам по себе этот alpha-beta хорошо играть не умеет.

> Гибридный, это когда мы берём два движка, которые играют
> одинаково сильно, и строим из них третий

при чем здесь сила движков.
Тут речь об идеях. Берем две идеи сильных движков и получаем третий движок.
А как ты говоришь (я не знаю) KomodoMCST как раз использует и alpha-beta и mcst,
это как раз две разные идеи, которые используются в современных движках...

MCTS состоит из двух частей. Первая — надо каждому ходу прописать начальные вероятности. Вторая — доигрывания. Собственно говоря, прописать вероятности можно при помощи разных техник, A0 делала это при помощи нейросети, и то, в общем от этого они отошли, поэтому их перебор сложно назвать MCTS сейчас. Можно прописывать вероятности рандомом (так я делал в шашках), можно при помощи alpha-beta можно ещё как. Это не гибридность, мотому что алгоритм MCTS мы не меняем. Мы просто изпользует разные запасные части.

Гибридность когда у нас есть два движка, и мы пытаемся их искусственно объединить. Например, у нас есть Lc0, и есть SF10. Мы пытаемся из объединить, оцениваем позицию двумя движками параллельно, а потом пытаемся принять решение. Например, выбираем ход нейросетью только из ходов, которые SF10 оценивает не более чем минус пешка от оптимального. Ну и тут куча вопросов, в ряде позиций это предотвратит зевки, в ряде позиций это заставит пройти мимо выигрыша...

> Mystic

не хочешь матч по шахматам устроить?

> не хочешь матч по шахматам устроить?


Между кем?

> Между кем?

как хочешь можно со мной блиц 1+5, 1+7 или 3+5.
Можно адванс с движками тоже интересно будет.

Я больше 3+2, но сложно предугадать, когда бывает свободное время.

> сложно предугадать, когда бывает свободное время

ну ты дай знать, когда будешь готов
у тебя скайп или телеграм есть?

Telegram: mustitz

> Mystic ©  


а вы смогли бы сделать самообучающуюся шашечную программу типа lczero?

> а вы смогли бы сделать самообучающуюся шашечную программу
> типа lczero?


Я думаю в этом направлении, но нету времени. В принципе план действий пока что такой:

☐ реализовать сервер на основе MCTS, который бы раздавал задания клиентам (доиграть с такой-то позиции) и хранил статы и базу возникающих позиций
☐ реализовать клиенты, которые бы брали задание у сервера и доигрывали партию

Потом уже можно обучать нейронную сеть, но лично мне было бы интересно дополнительно

☐ кластеризовать позиции; и для каждого кластера подобрать оптимальные значения параметров Propability, Ngames, чтобы оптимальный ход находился как можно быстрее для кластера (оптимизационная задача)

☐ Обучить нейросеть на этом наборе, чтобы вместе с вероятностью каждого хода шёл дополнительный параметр Ngames, который будет характеризовать достоверность оценки (чем меньше Ngames, тем больше MCTS будет стараться его дополнительно проверить).

Ну и кроме нейросети мне было бы интересно посмотреть на CLONALG и попытаться построить распознавание паттернов на его основе тоже

> Mystic ©  

а как сами партии разыгрываются? случайными ходами?

У меня сейчас MCTS а доигрывание случайными ходами.

https://github.com/mustitz/checkers

Собственно говоря, вполне можно использовать это для первой итерации. Потом веса будет возвращать натренированная нейросеть.

> Потом веса будет возвращать натренированная нейросеть.


веса для чего? для оценочной функции?

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

это получается, она сама находили позиционные признаки и вычисляла для них коэффициенты? (веса)

> веса для чего? для оценочной функции?

там же нейросеть, значит для нейронов,
то что обозначается в англ. литературе как w (weight)

> веса для чего? для оценочной функции?


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

В общем случае ситуация такая: для каждой позиции у нас есть статистика доигрываний, а именно сколько раз встрелилась позиция и какой процент набранных очков. Например, позиция после e2-e4 встретилась 42 раза, из них белые набирали 60.7% очков.

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

Но что делать в случае, когда мы только начали анализ, и никакой статистики у нас нет? В моих шашках сейчас мы пробуем сделать каждый ход, и только потом уже пользуемся формулой, когда хотя-бы одно доигрывание есть. Ещё есть опция считать, что изначально у нас была 1 симуляция, где мы набрали 50% очков (ничья).

Но... есть ещё вариант, чтобы некий Оракул посмотрел на позицию и заранее проставил желательно оба параметра (число симуляций и оценку). Чем эта оценка лучше рандома, тем адекватнее ходы попадут в симуляции, и тем будут сильнее играть программа. На крайняк Оракул может возвращать только оценку, а число симуляций проставим какой-нить константе (например 1). Вот эта оценка возникающей позиции и есть вес хода.

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

Как настроить коэффициенты этой нейросети? Ну... один из вариантов примерно такой. Допустим, у нас уже заданы некоторые коэффициенты нейросети (рандом). Наша задача усилить нейросеть. Отлично, играем со старыми коэффициентами много разных партий. Ну а дальше если ход привёл к победе, то заносим его в обучающий набор с коэффициентов 1, если к поражению — с нулём. Как только такой статистики много, делаем обучение новой нейросети.

> Mystic ©

но возможных позиций в шахматах - безумное число (в стоклеточных шашках, наверное, тоже велико), а мы можем сохранить лишь небольшое подмножество.

как сеть поведет, когда встретится незнакомая позиция? как она сопоставляет ее с той, что есть уже в базе?

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

Так и тут, если позиция незнакомая, то нейросеть постарается оценить её на основании схожести со знакомыми.

а как схожесть установить? вот в чем вопрос

Суперфинал в 17-00 по МСК

> а как схожесть установить? вот в чем вопрос


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

Мистик, а как вы собираетесь определять схожесть? Это сложная математика?

> В остальном пока что SF10 пока что ведёт и в личной встрече,
>  и по очкам, и по рейтингу. Но посмотрим, какую сетку выберут
> для суперфинала.

В чате говорят, что лила проигрывает из-за перегрева gpu,
в остальных случаях на двух gpu со стокфишем ничья

мда, lc0 стабильно проигрывает только черными

> Мистик, а как вы собираетесь определять схожесть? Это сложная
> математика?


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

похоже стокфиш проигрывает черными,
пока +2 в пользу sf но если проиграет то будет +1
а там бы продержаться lc0 черными

Ну... там с раздачи тяжёлый вариант во французской, а игра чёрными SF по французской против AlphaZero это боль.

она выиграла белыми. Теперь нужно защитить черными :)

> игра чёрными SF по французской

вообще этот вариант с ходом Nc6 кажется некорректным,
весь смысл французской защиты в ходе c5, а конь блокирует эту пешку

> Mystic ©   (06.02.19 13:32) [95]
>
> > Мистик, а как вы собираетесь определять схожесть? Это
> сложная
> > математика?
>
>
> Нет, не сложная. В принципе, можно выбрать много метрик
> оценки позиции (например, наименьшее расстояние до общей
> позиции в партии). Или разность в количестве шашек, штрафы
> на общие ходы, ... А дальше кластеризация. Потом можно прикрутить
> автокодировщик, и смотреть расстояние уже в том векторном
> пространстве, в котором он работает.


Я всё равно не представляю, как это может работать. В шахматах сдвинь пешку на одну клетку, и всё может перевернуться, а тут на схожесть какие-то расстояния проверяются)

она еще выиграла :) счет равный :)

Интервью с одним из разработчиков Lc0:
http://www.chessdom.com/interview-with-alexander-lyashuk-about-the-recent-success-of-lc0/

> Я всё равно не представляю, как это может работать. В шахматах
> сдвинь пешку на одну клетку, и всё может перевернуться,


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

> Mystic ©   (07.02.19 12:49) [103]


А не подскажете простенький проект на github-е, который показывал как нейросетью (или еще как-нибудь) подогнать веса для оценочной функции?

Вообще, по работе с нейросетями (Python + keras) можно почитать Шолле, хорошая книга без большого погрудения в математику.

Чисто что-то простенькое для шахмат/шашек — не знаю...

SF выиграл трикряду, в одной из партий Leela зевнула достаточно простую тактику:

> Mystic ©   (08.02.19 11:19) [105]


кстати, а почему так получилось, что большинство таких проектов пишется на Python?

> кстати, а почему так получилось, что большинство таких проектов
> пишется на Python?


Ну... Я вижу следующие преимущества.

(1) У Python есть консоль, где можно вводить команды по одной и видеть результаты. Все компилируемые языки типа Java идут лесом, потому как 90% кода это R&D, который запускается часто один раз в жизни. Например, принесли новый набор данных в CSV-формате. Мы хотим его посмотреть, немного преобразовать. Вот это я могу делать пошагово в консоле. Если где ошибусь, то выполню ещё одну праивльную команду — всё осталось жить в памяти. Никаких тебе циклов компиляция/запуск с перечитыванием всего и вся в память.

(2) Python исторически оказался инструментом, который понравился сишникам (embedding). Поэтому там хорошая интеграция с C, что позволяет на нем реализовывать участки кода, которые критичны к производительности или которые требуют доступа к двайверам/железу. На Python есть много таких библиотек, посему умножать матрицы на Python жутко тормознуто, то несли это делает numpy, то это делает C-код со сравнимой скоростью. У многих динамических языков программирования (особенно заточенных под web) интеграция с C/C++ несколько нетривиальна. Имхо, Ruby долгое время мешала заточненность под web (львиная доля всех проектов). Javascript имеет тяжёлое наследие. В качестве клея они использовались мало.

(3) Python это бесплатный язык программирования общего назначения. Который достаточно просто устнановить и настроить в Linux. Если я натренировал нейронную сети, я могу тут же в Python по месту на Amazon-сервере тут же развернуть микросервис с простым JSON-интерфейсом. Если брать тоже популяные в среду машинного обучения языки, такие как R и MATLAB, то MATLAB достаточно монстроуозен,  и поставить его на Amazon под docker как-то вот тяжеловато... Если брать R, то он затачивался больше под R&D и там мало библиотек общего назначения, и они развиваются медленнее.

Если брать по мелочи, то очень помогли такие две фишки:
a. индексация слайсов через двоеточие, по аналогии с математическими языками R и MATLAB успрощает реализацию математики

;
b. генераторы позволяют писать код так, что со стороны выглядит, что создаётся большое количество временных объектов. Это проще и нагляднее, а привыполнении кода циклы вкладываются и экономится память:


разворачивается в

Мистик, а представьте: есть детерминированная игра с полной информацией, но не ясно, как писать оценочную функцию. Сможет ли нейросеть, играя сама с собой, вычленить позиционные признаки и найти веса для них?

AlphaZero и LeelaZero так и обучается, в этом их фишка. 10 часов обучения и AlphaZero играет примерно на одном уровне со SF в шахматы и бьёт всех с большим отрывом в го :)

Оценочная функция это атрибут alpha-beta перебора (вширь). Соответственно, если движок не основан на alpha-beta переборе, то оценочная функция ему вообще ни в красную армию. Например, вот мои шашки на основе MCTS:
http://mustitz.host.funtoo.org:2201/
В них нет никакой оценочной функции.

Вот только вряд ли речь идёт о позиционных признаках. Нейросеть скорее тут выступает как сжатая ассоциативная база.

Симпатично сделали. На чем писали?

https://gitlab.com/mustitz/rus-checkers
Или на github
https://github.com/mustitz/checkers
но там нет одного подмодуля.

И у вас партии разыгрываются случайным образом?

> И у вас партии разыгрываются случайным образом?


Там MCTS с использование формулы UCB1, вот цикл симуляции:
https://github.com/mustitz/checkers/blob/master/source/ai-mcts.c#L531

А вот в случае, когда в позиции не все ходы исследованы, то есть два варианта: либо мы ход выбираем случайно (smooth=0), либо мы считаем, что в каждой позиции уже как минимум один раз встречался каждый ход, и в результате получилась рыба (smooth). Параметр smooth можно настроить в консоли.

Это мердж логики со smooth:
https://github.com/mustitz/checkers/commit/f384304c5818ff3c6720c813cc66fdb757dc9d99
там же можно посмотреть на статы (не повлияло на силу, особенно при длинных контролях)

на удивление счет в суперфинале равный.
Lc0 была постоянно в роли догоняющего, стокфиш не смог уйти в отрыв.
Больше трети матча позади, посмотрим что будет интересно же :)

Уже Lc0 впереди

> Mystic ©   (14.02.19 12:18) [116]
> Уже Lc0 впереди

ха-ха, а мы говорили невозможно - она видимо еще выиграет одну партию -
сейчас оценка стокфиша 3.3 в пользу lc0

Мистик, а каково по вашему мнению будущее компьютерных шахмат?

> Мистик, а каково по вашему мнению будущее компьютерных шахмат?
>
>


100% рыба, а так проги будут играть сильнее, сильнее и сильнее. Со своими нюансами. Т. е. чемпионат между программами можно будет проводить в формате TCEC, только позиции будут всё более разбалансированы.

> 100% рыба

ты же вроде за комодомцст болел?

а что значит "позиции будут всё более разбалансированы"?

> ты же вроде за комодомцст болел?


Да, мне Komodo MCTS представляется более интересным.


> позиции будут всё более разбалансированы


Например, королевский гамбит. Удержат ли белые ничью или проиграют? Вот, SF удержал ничью, а Lc0 нет.

Мистик, а вот такой вопрос. Я лет 7-8 назад увлекался немного темой MCTS with UCT.
И я помню две вещи:

1. Монте-Карло хорош для игр, где оценочную функцию трудно написать (го, например). В шахматах ОФ давно получена хорошая. По идее шахматам не нужен MCTS, главное хорошо дерево вариантов резать. То есть Stockfish рано хоронить и там еще не всё сказано

2. У MCTS, как известно, четыре стадии (selection, expansion, playout, backpropagation). Самая интересная часть - playout. И тут вопрос: как проиграть партию? Если чисто случайными ходами, то сила программы, основанной на Монте-Карло, будет невысока. Желательно сыграть максимально безошибочную партию, тогда и оценки узлов будут корректными.

1. Скорее наоборот, Alpha-beta хороша для игр, где позволяет ветвистость игры и можно написать оценочную функцию. Поэтому для шахмат такой подход следует рассмотреть. А вот лучший это подход или нет надо экспериментировать. MCTS же хорошо подходит для многих игр. Как показывает пример Komodo MCTS, результаты можно сравнивать.

Если сравнивать вообще алгоритмы MCTS и alpha-beta, то... alpha-beta имеет проблему горизонта, и сейчас в чистом виде у сильных движков почти не встречается. Даже тот же Stockfish делает случайные доигрывания. Проблемой для alpha-beta являются крепости (по мнению SF у белых есть лишняя ладья, но в силу замкнутости пешечных цепей её не реализовать). Ну и разные долгоиграющие факторы, например, оценка долгосрочной инициативы соперника. MCTS имеет тот недостаток, что может пропустить тактику (меньше узлов в поиске).

2. Komodo MCTS доигрывает при помощи усечённой alpha-beta со специфической оценочной функцией. При этом оценка Komodo в окончаниях часто точнее SF, потому что хорошо понимает, что такое крепость (нулевой процент побед при доигрывании). AlphaZero доигрывала в первых версиях на основании предложения нейросети. Потом от этого отказались, там сейчас нейросеть возвращает оценку и на основании температуры выбирается узел для последующего рассмотрения. Оценка в окончании часто не соответствует действительности при таком подходе. Мои шашки — чистый рандом. Ну а так playout + инициализация начальных оценок ходов — простор для творчества.

А как вам такая идея?
Играет движок сам с собой методом MCTS, строится дерево Монте-Карло, playout-ы при этом играются так: смотрятся все первые ходы, делаются, возвращается оценка и выбирается ход с лучшей оценкой. То есть никакого рандома.
По итогам определенного количества партий выбирается  лучший набор параметров для ОФ и идет дальше коррекция весов для ОФ.

похоже сбой в железе случился

да похоже лиле засчитали падение, она пока на очко впереди.
А партия будет переигрываться?

> А партия будет переигрываться?


Дали переиграть. По правилам, крэш считается поражением, дисконнект переигрывается.


> А как вам такая идея?


Хотите — пробуйте. Пока описано нечётко, но я вижу две возможные проблемы: №1 позиции после разных ходов будут похожи, и сложно придумать ОФ, чтобы на это реагировала; №2 непонятно на каких данных обучать ОФ?

Мистик, а вы смотрели исходный код Lc0?

Я вот не могу понять, что на выходе получается после кучи сыгранных партий самообучения? какой-то файл с trained data?

> что на выходе получается после кучи сыгранных партий самообучения?
>  какой-то файл с trained data?

вот же ссылка http://lczero.org/networks/

xayam, спасибо за ссылку

> xayam, спасибо за ссылку

вообще первая ссылка в гугле по запросу "Lc0" ведёт на этот сайт :)

А Leela Chess во время игры использует шахматные знания?  Дебютную библиотеку? Таблицы Налимова, Sygyzy? Или только свое?

> А Leela Chess во время игры использует шахматные знания?
>   Дебютную библиотеку? Таблицы Налимова, Sygyzy? Или только
> свое?

ну вот сейчас идет tcec на сайте chessdom и там все это используется,
но а так это по желанию - можно отключить

И насколько пунктов ЭЛО меньше, если отключить?

> java_guy ©   (19.02.19 11:23) [135]
> И насколько пунктов ЭЛО меньше, если отключить?

трудно сказать, но если у противника lc0 тоже отключить,
то я думаю для lc0 это преимущество.
Думаю, до 100 Эло не больше, если противник будет иметь дебютные и эндшпильные базы

> Я вот не могу понять, что на выходе получается после кучи
> сыгранных партий самообучения? какой-то файл с trained data?
>


Не знаю, не смотрел. Но логично, чтобы в обучающей выборке была позиция, ход который приводил к набору очков (½, 1). Плюс оценка результата доигрывания (статистика).

Как думаете, почему после публикации материалов от разработчиков Alpha Zero шахматная программа на этом принципе появилась почти сразу,  а для го по-прежнему нет?

> появилась почти сразу,  а для го по-прежнему нет?

вообще то го раньше появилась. Первоначальный автор
https://en.wikipedia.org/wiki/Leela_Zero
LeelaZero назвал программу в го
и только потом из нее сделали LeelaChessZero или Lc0

> Alpha Zero шахматная программа на этом принципе появилась
> почти сразу,  а для го по-прежнему нет?


Го программа появилась раньше, и при написании шахматной программы использовался опыт го-программы.

Вот интересное в википедии прочитал: "In early 2018, another team branched Leela Chess Zero from the same code base, also to verify the methods in the AlphaZero paper as applied to the game of chess. AlphaZero's use of Google TPUs was replaced by a crowd-sourcing infrastructure and the ability to use graphics card GPUs via the OpenCL library. Even so, it is expected to take a year of crowd-sourced training to make up for the dozen hours that AlphaZero was allowed to train for its chess match in the paper"

Мистик, а если бы вы решили написать свою шашечную программу на принципах AlphaZero/LeelaZero, то как бы вы тренировали ее? Сколько миллиардов партий должен сыграть движок, чтобы сильно заиграть? Вряд ли это получится с одним домашним ноутбуком

Ну... 1600 TPU умножить на 10 часов... Эквивалентно работе одного GPU в течение 10 * 1600 * 3 = 48 000 часов = 2000 дней = 5½ лет

в  чате сказали, исторический момент - стокфиш выигрывает tcec в последний раз :)

> Мистик, а если бы вы решили написать свою шашечную программу
> на принципах AlphaZero/LeelaZero, то как бы вы тренировали
> ее? Сколько миллиардов партий должен сыграть движок, чтобы
> сильно заиграть?


Ну... AlphaZero это 6 миллионов партий вроде. Для шашек, я думаю, хватит одного миллиона с головой. А если добавить базы окончаний, то ещё на порядок меньше.

Мистик, смотрите, что я нашел:
In Komodo's MCTS mode the search tree is expanded in best-first manner based on winning probabilities determined neither by random playouts nor by a neural network, but a tiny alpha-beta searchplus quiescence and static evaluation, also similar to UCT, dealing with the crucial trade-off between exploration and exploitation. While playing strength is lower with MCTS, positional play and judgement may well be better in many positions, not to mention a more risky and entertaining playing style.

Комодо не играет партии до конца случайным образом, а оценивает узлы в MCTS-дереве маленькой альфа-бетой.

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

И судя по адекватности оценок в окончаниях (0.00 в случае крепости) Komodo MCTS таки доигрывает.

determined neither by random playouts 

В классическом MCTS нужно сыграть партию для каждого созданного узла. Просто времени не хватит для построения дерева с приемлемым Depth. Может только в эндшпиле

Вот здесь Ларри Кауфман всё объясняет: http://www.talkchess.com/forum3/viewtopic.php?f=2&t=67441

Большая ветка. Поражен, как агрессивно на него нападают. Думал, только у нас так

Правильно, Komodo MCTS доигрывает партию до конца, но не случайными ходами. Если узел неизвестный, в нём запускается alpha-beta перебор, который выдаёт ожидаемый процент очкой для каждого хода. А дальше работает UTC.