Эта книга Доминика Кляйна 19 Май года 2023
Перевод нейросетей.
PS Мне сложно перевести всю книгу целиком, поэтому буду переводить частями.
Предисловие
Эта книга представляет собой краткое введение в современные компьютерные шахматы.
Шахматные движки, использующие искусственный интеллект на основе глубокого обучения, оказали значительное влияние на шахматное сообщество. AlphaZero, шахматный монстр, разработанный дочерней компанией Google DeepMind, внезапно оказался способным играть в красивые, почти человеческие шахматы. Некоторые партии демонстрировали жертвы фигур без немедленного тактического выигрыша, но с позиционными долгосрочными преимуществами, которые обычные шахматные движки не могли найти.
Некоторые даже в шутку провозгласили возвращение эпохи романтических шахмат. С точки зрения шахматиста, внутренняя работа шахматного движка часто остается загадкой. Под ними обычно понимают черные ящики, в которых могут разобраться только гениальные программисты и исследователи.
В знаменитом матче DeepBlue против Гарри Каспарова в 1997 году, где чемпион мира по шахматам Каспаров проиграл суперкомпьютеру, разработанному IBM под названием DeepBlue, он выдвинул обвинения в том, что команда DeepBlue жульничала. Он намекнул, что конкретный ход в позиции во второй партии матча не был результатом компьютерного расчета, а был результатом вмешательства человека. Он заявил, что кажется очень маловероятным, что шахматный компьютер мог сделать именно этот ход. Его аргумент заключался в том, что компьютер воздержался от выигрыша пешки, чтобы вместо этого получить лучшую расстановку фигуры. В то время он просто не мог понять, что шахматный движок способен на такой ход.
С некоторой отдаленностью Каспаров рассказывает о матче со своей точки зрения и несколько поправляет свои заблуждения. В отличие от этого, технически подробный рассказ разработчика DeepBlue Фэн-сюн Сюй о событиях рисует совершенно иную историю . Обе книги очень интересны для чтения, и я рекомендую попробовать их оба. Тем не менее, одно следует четко заявить: нет никаких оснований полагать, что DeepBlue не смогла найти рассматриваемый ход в этой позиции. Это признает даже Каспаров в своей книге, где он заявляет, что был неправ и должен извиниться перед командой DeepBlue. Он отмечает, что современные компьютеры находят лучший ход за считанные секунды. Требуется большое мужество, чтобы признать свои ошибки. Но даже движки, выпущенные в 1997 году, смогли найти правильный ход, как мы увидим вглаве 3.
Каспаров доминировал в шахматах на протяжении десятилетий. Как же так получилось, что такой шахматный гений совершенно неправильно оценил ситуацию? Мы можем только догадываться, но, похоже, он оценивал шахматный движок исключительно с точки зрения шахматиста, пренебрегая его внутренней технической работой. Более того, он, по-видимому, полагался на шахматную программу Fritz для обучения и оценки шахматных компьютеров , хотя Фриц в то время был известен как своего рода «захватчик пешек» с высоким тактическим видением, но менее качественной позиционной оценкой по сравнению с другими движками. Обладая более глубоким техническим пониманием и принимая во внимание инженерную перспективу, мы можем задаться вопросом, смог бы Каспаров продлить неизбежное поражение людей от шахматных компьютеров еще на некоторое время. Можно только догадываться, но не стоит недооценивать психологическую сторону дела, а именно удивление и ошеломление от движений двигателя: после пятой партии Каспаров сказал, что у него не было настроения играть, а когда его попросили подробнее рассказать о своих перспективах, он сказал: «Я человек. [...]Когда я вижу что-то, что выходит далеко за рамки моего понимания, я боюсь». Якобы Каспаров недоумевал после 44... Rd1 в первой игре матча-реванша 1997 года, и он и его команда глубоко проанализировали, почему DeepBlue предпочла именно его. 44...Rf5; придя к выводу, что DeepBlue должен был видеть спаривание в 20 или более . По словам Сюй , это была просто ошибка в программе. С другим взглядом на технические проблемы, связанные с проектированием и программированием массово-параллельной системы с пользовательским оборудованием, команда Каспарова могла бы придать этой возможности гораздо большую вероятность.
Эта книга не о матче Каспарова против DeepBlue. Но эта история наглядно показывает, что интересно и, возможно, даже стоит заглянуть за кулисы и разобраться во внутренней работе шахматных движков, даже если вы не компьютерщик, а просто шахматист, получающий удовольствие от игры. Одно дело смотреть с благоговением и восхищаться AlphaZero, меняющим правила игры, но совсем другое — выяснить, как работают AlphaZero и подобные движки, и лучше понять, на что они способны.
Шахматное программирование – это довольно техническая область. Начать работу сложно, и входной барьер кажется высоким. Известный писатель-фантаст Артур Кларк писал, что «любая достаточно продвинутая технология неотличима от магии» . Здесь мы хотим раскрыть эту магию: эта книга для всех тех, кто не хочет мириться с поверхностными объяснениями, такими как «Этот движок работает лучше, потому что теперь у него есть искусственный интеллект». Эта книга для тех, кто хочет заглянуть глубже, любит разбирать вещи на части и копаться в них, чтобы разобраться, как все это работает. Мы совершим путешествие в компьютерные шахматы. В этой книге вы узнаете, что такое нейронная сеть и как она обучается, как работают классические альфа-бета поисковики и как все это было объединено для создания сильнейшего шахматного движка, доступного на сегодняшний день, Stockfish NNUE. Смущены всем этим жаргоном? Это нормально, так как мы все разберемся с этим шаг за шагом. Тем не менее, эта книга не является учебником для выпускников. Мы рассмотрим все основные идеи с большим количеством примеров, но постарайтесь абстрагироваться от ненужных деталей и убедиться, что вы (надеюсь) не заблудитесь в математических деталях.
Действительно, для понимания нейронных сетей требуется математика, но на самом деле это не так уж и много. Кроме того, на удивление мало предварительных технических знаний.
На самом деле, есть только два основных математических понятия, которые вы должны знать. Во-первых, это базовое исчисление, а именно то, как вычислить производную. Во-вторых, вам нужно разобраться в умножении матриц. Вы, скорее всего, помните эти вещи из средней школы, а если нет, я предлагаю вам откопать свой старый школьный учебник математики и быстро освежить в памяти. Но, к счастью, это в основном все, на самом деле. Эта книга содержит примеры программирования на языке Python. Это действительно дружественный к новичкам и простой язык программирования. Но не заблуждайтесь — ни в коем случае не обязательно пользоваться этими примерами программирования или становиться программистом, чтобы разобраться в понятиях, описанных в этой книге. Чтобы проиллюстрировать это, вы можете думать об этом как о работе архитектора: это помогает, если вы знакомы с каменной кладкой и, возможно, даже работали в строительстве, но это ни в коем случае не является обязательным для понимания того, как проектируются дома. Если вам нравится программирование, эти примеры помогут вам изучить представленные концепции и послужат отправной точкой для ваших собственных экспериментов. Весь исходный код, представленный в этой книге, также доступен в Интернете по адресу
Если вы шахматист и внимательно проработаете эту книгу, вы лучше поймете, как работают шахматные движки, каковы их ограничения и как интерпретировать их результаты. Если появятся новые движки и подходы, вы будете лучше понимать, что их достижения означают для игры. Вы также сможете оценить маркетинговый жаргон коммерческих поставщиков. И если вы столкнетесь с очередной газетной статьей о «революциях искусственного интеллекта и глубокого обучения», у вас будет гораздо больше возможностей для суждения о том, являются ли сделанные в ней утверждения верными или в лучшем случае сомнительной научно-фантастической фантазией. Получайте массу удовольствия!
Я думаю, что мы все должны что-то говорить, но притворяться,
что это сказали другие, очень умные люди, а мы просто цитируем их
Аристотель
Шахматы состоят из тактики и стратегии. Для тактики вы просчитываете ходы и ответы и смотрите, приводит ли какая-либо из последовательностей ходов к вынужденному преимуществу или невыгоде. По сути, вы ищете среди всех возможных вариантов. Для стратегии вы оцениваете позицию без особых расчетов. Мой отец научил меня правилам шахмат, наверное, в возрасте восьми или девяти лет, но позже я потерял интерес к игре. Я заново открыл для себя шахматы во время чемпионата мира по шахматам 2014 года между Карлсеном и Анандом, начал играть и искал высококачественные учебные материалы. Затем я наткнулся на книгу Джереми Силмана «ReappessYour Chess» [Sil10]. Вот и все — перечисленные и объясненные все аспекты оценки позиции: пешечные структуры, сильные и слабые поля, открытые линии, хорошие и плохие поля для своих фигур, безопасность короля — все было там и сформулировано так, чтобы любитель мог это понять. Сильман объясняет, как характеризовать позицию по дисбалансам, т.е. преимуществам и недостаткам, которые характеризуют должность. Он выступает за использование такого рода техники оценки для поиска хороших ходов в позиции.
Позже я наткнулся на книгу Вилли Хендрикса «Сначала двигайся, думай потом» . Хендрикс очень критично относится к методу Сильмана по оценке дисбалансов. Его аргумент заключается в том, что мы редко находим хорошие ходы, просто глядя на позицию, и что вместо этого мы должны немедленно искать и применять ходы, которые приходят нам в голову — отсюда и название — чтобы прийти к пониманию текущей позиции и найти лучший следующий ход.
С точки зрения специалиста в области информатики, это, однако, псевдоспор: конечно, нам нужны и поиск, и оценка.
Давайте посмотрим на знаменитое греческое жертвоприношение, показанное на рисунке 1.1.
rnbq1rk1/pppn1ppp/4p3/3pP3/1b1P4/2NB1N2/PPP2PPP/R1BQK2R w KQ - 0 1
Как мы оцениваем эту позицию? Конечно, есть и равный материал. У белых, возможно, небольшое преимущество в пространстве. Таким образом, без поисков мы оценим позицию с небольшим преимуществом в пользу белых. Но после поиска нескольких кандидатов ходов, мы быстро находим последовательность 1.Bxh7+! Kxh7 2.Ng5+. Теперь нам нужно глубже искать все возможные ответы после каждого хода и обнаруживать, что в полученных позициях белые либо ставят мат, либо выигрывают материал. Другими словами, полученные позиции очень легко оценить с высокой степенью уверенности. Основываясь на этих оценках, мы пересматриваем исходную позицию как «У белых значительное преимущество». Однако часто при расчетах мы не можем достичь точки мата или позиции, в которой оценка проста из-за значительных материальных преимуществ. Конечно, каждая шахматная партия рано или поздно заканчивается финальной позицией, но так глубоко искать вообще невозможно. Таким образом, мы должны остановиться после определенного количества ходов, а затем оценить полученную позицию по структурным особенностям, таким как дисбалансы Сильмана. Например, взгляните на рисунок 1.22. Мы можем пройтись по нескольким последовательностям ходов, в частности d5! и все последующие ответы Блэка; рассматривать особенно Ne7, за которым следует e5. Только используя критерии дисбаланса Сильмана и без какого-либо дальнейшего поиска, мы можем оценить результирующую позицию (позиции): во всех последующих вариациях белых существует значительное позиционное преимущество, но нет немедленного материального выигрыша или последовательности матов. Затем мы можем использовать оценки результирующих позиций для (повторной) оценки исходного положения на рисунке 1.2.
r1bqk2r/pppp1ppp/1bn2n2/8/2BPP3/5N2/PP3PPP/RNBQK2R w KQkq - 0 1
Другими словами, белые имеют значительное преимущество на текущей позиции, благодаря своему преимуществу в пространстве в центре. Я полагаю, что основная мысль Вилли Хендрикса заключается в том, что люди редко делают это структурным способом, которому часто учат, т.е.
• Найдите ряд возможных ходов. Затем для каждого из них последовательно...
• рассчитать все последующие позиции и деревья вариаций, которые получаются в результате этих ходов-кандидатов как можно глубже
• оценить все полученные позиции
• Наконец, на основе всех этих оценок (пере)оцените текущую позицию и выберите лучший ход.
Люди, вероятно, прыгают туда-сюда, забывают о возможных ходах, сосредотачиваются на одной конкретной линии, затем принимают решение, руководствуясь инстинктом, а не рациональным мышлением, и злятся, когда понимают, что фигура только что была потеряна. По крайней мере, так я это делаю. В конечном итоге, однако, все сводится к поиску (кандидатских) ходов и оценке позиций. А поскольку мы не всегда можем копать настолько глубоко, чтобы оказаться в конечном состоянии игры, нам нужно остановиться после нескольких ходов и оценить неокончательную позицию. В течение долгого времени люди всегда были лучше в оценке позиций и хуже в поиске. Особенно это касалось шахматных позиций, которые трудно оценить, т.е. где нет конкретных критериев, чтобы мы могли рассчитать или доказать преимущество. Типичными примерами являются очень закрытые позиции, как на рисунке 1.3.
1b6/5p2/p1p1k1p1/Pp1p1nPp/1PPPpP1P/4P2R/2K5/1R6 w - - 0 1
Здесь у белых есть материальное преимущество. Рыбка хочет избежать ничьей путем повторения в позиции с материальным преимуществом, и в итоге сделает неудачный ход,неправильная оценка соответствующего позиционного недостатка. В конце концов черные выиграли партию. Именно специфическая пешечная структура приведет к тому, что белые в конечном итоге проиграют, если они попытаются форсировать победу, а ладьи не могут этому помешать. Преимущество компьютеров в поиске совершенно очевидно: компьютеры просто лучше справляются с обработкой чисел. Любой карманный калькулятор умножает числа быстрее, чем человек. Слабость в оценке позиций — это то, что долгое время преследовало компьютеры. Люди учатся судить о положении с помощью интуиции. Часто бывает сложно выразить словами, почему позиция лучше или хуже. Стефан Мейер-Кален, автор шахматной программы Shredder, однажды рассказал такую историю: 3 В некоторых позициях Shredder делал особенно плохой позиционный ход. Он спросил сильного игрока, в чем была проблема, чтобы найти потенциальное решение, т.е. он должен был выяснить, в чем именно заключалась проблема. Но он получил только ответ: «Нет, ты просто так не играешь».
Революция, которую принесла AlphaZero, по-настоящему изменила правила игры, вызвав способность интуитивно оценивать шахматную позицию, как человек, и не полагаться на фиксированный набор правил, как, например, подсчет пешек. Технически шахматные движки используют нейронные сети для создания абстрактной модели человеческого мозга, чтобы обрабатывать и оценивать шахматную позицию.
Но как хорошие игроки становятся такими хорошими в шахматах? Если прислушаться к советам гроссмейстера, то часто упоминается следующая стратегия:
• Посмотрите на свои собственные игры без движка. Внимательно смотрите на ошибки, которые допустили вы и ваш соперник, и учитесь на этих ошибках, чтобы играть лучше в следующий раз.
• Внимательно присматривайтесь к партиям гроссмейстеров. Совершенствуйтесь, глядя на их подходы и планы на различных типах должностей.
Интересно, что следование этой стратегии — это именно то, что компьютерные шахматные программы делают в настоящее время, чтобы получить (сверх)человеческое понимание шахматных позиций. Либо взяв большие базы данных партий шахматных гроссмейстеров, либо просматривая и учась на их собственных играх.
Для первого шага нам, очевидно, нужно сыграть много игр. В знаменитом романе Стефана Цвейга «Schachnovelle» шахматист становится очень хорошим в шахматах (и почти сумасшедшим), разделяя свою личность и играя в бесконечные шахматные партии между этими двумя личностями. У компьютеров нет проблем с безумием (пока), и, следовательно, обучение самостоятельной игрой стало стандартом де-факто в обучающих шахматных программах или, скорее, в базовых нейронных сетях. Кроме того, этот подход в основном предпочтительнее по сравнению с просмотром больших баз данных игр игроков-людей.
Можно также сказать, что компьютеры наконец-то поняли, как люди учатся и играют, и именно поэтому они становятся такими сильными. Что может быть более комплиментом для нас, простых смертных?
Глава 2 полностью посвящена нейронным сетям. Здесь мы обсудим математические концепции и заложим основу для всех последующих дискуссий о последних улучшениях, основанных на искусственном интеллекте. Если это слишком утомительно для чтения из-за сложной математики, вы также можете просто выбрать понимание нейронной сети как черного ящика, который при наличии шахматной позиции отвечает позиционной оценкой; Пропустите эту главу и вернитесь к ней позже. Если вы решите использовать эту технологию, вы научитесь аппроксимировать неизвестные, сложные функции, обнаруживать Байкинмана на изображениях и создавать причудливые сложные нейронные сети, для которых вам, к сожалению, скорее всего, не хватит вычислительной мощности для их обучения.
В главе 3 мы рассмотрим методы поиска, которые используют шахматные движки. Мы узнаем, как «классические» шахматные движки используют альфа-бета поиск, и как поиск по методу Монте-Карлотри предлагает альтернативу шахматам, а также другим, более сложным играм, таким как Сёги или Го. В качестве примера мы также реализуем альфа-бета-поиск и поиск по дереву Монте-Карло и протестируем его с простой шахматной позицией. Глава 4 — это место, где все сходится воедино. Мы подробно рассмотрим, как AlphaZero и Leela Chess Zero работают технически и как они развились из AlphaGo. Мы также рассмотрим последнюю революцию в компьютерных шахматах, а именно комбинацию классических альфа-бета-поисковиков в шахматах и сёги с более простыми нейронными сетями. Они являются современными и способны обыграть LeelaChess Zero. И они могут работать даже на стандартном домашнем компьютере!
В главе 5 мы реализуем наш собственный игровой движок на основе нейронной сети, аналогичный AlphaZero или Leela Chess Zero. Поскольку игра в шахматы слишком сложна для эффективного обучения на стандартном ПК, мы ограничимся более простым вариантом шахмат под названием Hexapawn. Тем не менее, поскольку все методы существуют, а подход AlphaZero довольно агностически привязан к конкретным правилам игры, эта реализация может быть легко распространена на более сложные задачи, включая шахматы, при условии наличия огромных необходимых вычислительных ресурсов. Наконец,
в главе 6 мы подводим итоги последних событий и строим догадки о том, что нас ждет.
Как же тогда читать эту книгу? Если вы
• в основном интересуется AlphaZero, затем прочтите главу 2 до многослойных персептронов, чтобы получить краткое представление о нейронных сетях. Затем перейдите к главе 3 и прочтите раздел о поиске деревьев по методу Монте-Карло, а затем перейдите к главе 4. Пропустите раздел об AlphaGo и перейдите непосредственно к разделам о AlphaGo Zero и AlphaZero.
• в основном интересуетесь эффективно обновляемыми нейронными сетями, то также прочтите главу 2 до многослойных персептронов, чтобы получить краткое представление о нейронных сетях, прочтите раздел об альфа-бета-поиске в главе 3 и раздел о NNUE в главе 4.
• в основном заинтересованы в реализации собственной версии AlphaZero и имеете точку зрения программиста, тогда просто перейдите к главе 5 и взгляните на HexapawnZero. Затем ищите все на ходу, пока вы пробираетесь через код.
В идеале, однако, вы внимательно прочитаете эту книгу от начала и до конца!
Здесь должен быть какой-то выход Сказал шутник вору
Слишком много запутанности
Я не могу получить облегчения
Ян Лекун
В фильме «Пи» (1998) математический гений и энтузиаст го Макс Коэн убежден, что все в мире можно понять через числа. Чем больше он углубляется в свои теории, тем больше он оказывается на грани безумия.
Теперь наша задача — изучить математические и программные концепции нейронных сетей, на которых работают современные мощные движки Го и шахматы. Поскольку мы не хотим сойти с ума, очевидно, что мы должны проявлять большую осторожность и не должны относиться к этой задаче легкомысленно.
Макс Коэн, кстати, не дал себе сойти с ума, самостоятельно исполнив импровизированную трепанацию. Или, может быть, эта сцена просто должна была быть шуткой.
Я не уверен. В любом случае, на всякий случай, возьмите себе отвертку, положите ее рядом с этой книгой, и теперь давайте начнем!
2.1 Перцептрон
Линия [tex] y=-x+\frac{5}{3}[/tex]
Нейронные сети предназначены для обучения функций, в частности, сложных, нелинейных функций. Грубо говоря, функция — это описание того, как сопоставить каждое значение из одного набора со значением из другого набора. Возможно, вы помните из средней школы линейные уравнения вида
y=ax+b
где x — переменная, а a и b — фиксированные константы.
Например, две точки (0, [tex]\frac{5}{3}[/tex]) и (1, [tex]\frac{2}{3}[/tex])
Чтобы найти подходящие a и b, чтобы линия проходила через эти две точки, мы просто подставим две точки как x и y в y=ax+b и получим два уравнения:
[tex]\frac{5}{3}=a*0+b[/tex] и [tex]\frac{2}{3}=a*1+b[/tex]
По первому уравнению мы получаем b = [tex]\frac{5}{3}[/tex] , а второе уравнение приводит к [tex]a=\frac{2}{3}-b=\frac{2}{3}-\frac{5}{3}=-1[/tex] . Эта линия показана на рисунке 2.1.Учитывая некоторые пары значений, конечно, легко определить базовую функцию, если заранее знать форму функции - например, y=ax+b. Но выучить функцию сложно, если вы вообще не знаете форму функции, и если функция сложная.
Рассмотрим следующие примеры:
• Учитывая доход человека, его возраст, его профессиональное образование, место жительства и, вероятно, другие переменные, какова наиболее вероятная сумма кредитного долга, которую он может погасить?
• Если есть два изображения лица, показывают ли они одного и того же человека или нет?
• Учитывая произвольную шахматную позицию и предполагая идеальную игру, выиграют ли белые в конечном итоге партию, выиграют ли черные в конечном итоге или это будет ничья?
Обратите внимание, что все эти вопросы могут быть выражены в виде математических функций, наложенных числами. В первом случае все входные переменные являются числами, и кредитный долг также является числом.
Во втором примере вы можете рассматривать изображения как состоящие из пикселей, где каждый пиксель представляет собой тройку красных, зеленых и синих значений в диапазоне от 0.0 до 1.0, и функция отображается на единицу, если у нас один и тот же человек, и на ноль в противном случае.
В третьем примере вы можете закодировать шахматную позицию в виде числа — мы увидим позже, как это можно сделать — и функция выведет 1, если выиграют белые, −1, если выиграют черные, и 0, если у нас ничья.
Теперь цель состоит в том, чтобы найти формы функций, которые являются достаточно общими и могут быть скорректированы для моделирования других, очень сложных функций, истинное определение которых мы не знаем — как в вышеупомянутых примерах. Для этого исследователи черпали вдохновение в мозге. Мозг состоит из сети нейронов, которые связаны между собой через так называемые синапсы. В зависимости от Сигналов, которые посылают синапсы, нейрон затем сам посылает сигналы другим людям. Математическое приближение такого нейрона, получившего название персептрон, изображено на рисунке 2.2.
Он имеет n + 1 входов, однако первый вход x0 всегда установлен в 1. С каждым входом связан вес.
Затем нейрон выполняет вычисления
После этого к v применяется функция активации a(v).
Персептрон — это простейшая форма нейронной сети.
Давайте рассмотрим небольшой пример и попробуем смоделировать очень простую функцию, логическое И.
Чтобы сделать это более доступным, представьте, что вы симпатичный шахматист1 и предположим, что есть два условия. В зависимости от этих условий функция подсказывает, выиграете вы игру или нет.
Условие одно из них заключается в том, что вы королева.
Условие второе заключается в том, что ваш враг довольно плохой игрок.
Мы запишем 1, если условие истинно, и 0 в противном случае. Функция выводит 1, если вы выиграете, и 0 в противном случае.
В таблице 2.1 перечислены все возможные комбинации. Другими словами, вы выиграете только в том случае, если вы дама, а ваш враг довольно слаб. Во всех остальных случаях вы в конечном итоге испортите игру
Теперь рассмотрим перцептрон на рисунке 2.3.
У него есть три входа, но Первый параметр x0 всегда устанавливается в 1, как упоминалось выше.
Таким образом, переменные x1 и x2 соответствуют нашим входным параметрам: queen up, а противник довольно слабый. Давайте проверим, действительно ли выход персептрона вычисляет нашу функцию, т.е. когда и выиграем ли мы игру:
Оказывается, этот перцептрон не имитирует нашу желаемую функцию. Но это близко:Всякий раз, когда мы хотим, чтобы выход функции И был равен 1, выход нашей симуляции является положительным значением. С другой стороны, когда мы хотим, чтобы выход функции И был равен 0, результат нашего моделирования строго меньше нуля. Итак, давайте определим нашу функцию активации как простое пороговое значение:
[tex]a(v)=\left\{\frac{0:v< 0 }{1:v\geq 0 }\right\}[/tex]
Теперь у нас есть
Отлично – наш персептрон успешно имитирует функцию И! Причина, по которой это моделирование работает и перцептрон вычисляет И, очевидно, кроется в тщательно подобранных весах w0 = −10, w1 = 6 и w2 = 6.
Но откуда они берутся? Оказывается, мы можем автоматически узнать подходящие веса, рассматривая множество примеров или короткие выборки. Алгоритм для этого называется обратным распространением на основе градиентного спуска; И вот тут-то и происходит вся магия нейронных сетей.
Эта книга представляет собой краткое введение в современные компьютерные шахматы.
Шахматные движки, использующие искусственный интеллект на основе глубокого обучения, оказали значительное влияние на шахматное сообщество. AlphaZero, шахматный монстр, разработанный дочерней компанией Google DeepMind, внезапно оказался способным играть в красивые, почти человеческие шахматы. Некоторые партии демонстрировали жертвы фигур без немедленного тактического выигрыша, но с позиционными долгосрочными преимуществами, которые обычные шахматные движки не могли найти
судя по этому пассажу, автор не шахматист... или очень невнимательный
Глава 2 полностью посвящена нейронным сетям. Здесь мы обсудим математические концепции и заложим основу для всех последующих дискуссий о последних улучшениях, основанных на искусственном интеллекте. Если это слишком утомительно для чтения из-за сложной математики, вы также можете просто выбрать понимание нейронной сети как черного ящика, который при наличии шахматной позиции отвечает позиционной оценкой; Пропустите эту главу и вернитесь к ней позже.
Обратное распространение и градиентный спуск
Жесткие пороговые значения легко и быстро реализовать, но во многих сценариях требуется более детальный подход.
Рассмотрим вышеупомянутый пример сравнения изображений двух лиц.
Изображают ли они одного и того же человека?
Если сеть, например, выводит значение 0,001, это может указывать на то, что маловероятно, что на этих двух изображениях изображен один и тот же человек. Или, по крайней мере, существует сравнительно высокий уровень сомнений.
Однако использование жесткого порогового значения в качестве функции активации, как мы делали для логического И, приведет к получению значения 1. Это может ввести в заблуждение.
Вместо этого мы будем использовать функцию сигмоиды, которая определена как
Важным свойством сигмоидальной функции является то, что независимо от того, каково входное значение, выходное значение всегда находится в диапазоне 0...1.
Для задачи сравнения изображений лица снова представим себе выход сети 0.001. У нас есть sigmoid(0.001) ≈ 0.5. Поскольку у нас есть диапазон от 0 до 1, мы можем думать об этом как о некотором проценте или вероятности, т.е. это 50-процентная вероятность того, что это совпадение.
Тогда, вероятно, этого недостаточно, чтобы назвать это безопасным решением и, следовательно, результатом, который мы ожидали.
Вернемся к вопросу о том, как найти подходящие веса для сети.
Давайте вернемся к сети И из предыдущего раздела и просто инициализируем ее случайным образом, скажем, весами w0 = 1, w1 = 2 и w2 = 3, и оценим производительность сети для двух примеров ( x 1 = 1 , x 2 = 0 ) и (x1 = 1, x2 = 1). Эти два примера должны дать 0 и 1 соответственно.
Интуитивно это кажется довольно плохим: для (x1 = 1, x2 = 1) у нас есть 0,99, что почти равно 1, и таким образом это правильный результат.
Для (x1 = 1, x2 = 0) у нас есть 0.95, что тоже почти 1, но правильный результат равен 0.
Как мы можем объективно измерить текущую производительность сети с помощью выбранных весов?
Очевидный способ — взять разницу между выходом сети и ожидаемым результатом.
Давайте запишем outi для вывода сети примера i и давайте напишем ri для ожидаемого результата примера i.
Тогда одним из способов измерения ошибки сети является взятие квадрата разности, т.е. ( outi − ri )2 .
Для второго примера (x1 = 1, x2 = 1) у нас есть ожидаемый результат r2 = 1, т.е. при заданном out2 сети ошибка равна (out2 − 1)2.
Эта функция изображена на рисунке 2.5.
Рисунок 2.5: Квадратная функция ошибки для ожидаемого результата 1
Как можно видеть, квадрат различий делает акцент на больших ошибках: маленькая разница 0,1 между outi и ri приводит к значению ошибки 0,01, в то время как большая разница 2 результата приводит к значению ошибки 4.
Наша сеть успешно имитирует предполагаемую функцию, если ошибка сети минимальна.
Таким образом, на примере мы хотели бы свести к минимуму погрешность работы сети.
В идеале мы должны иметь ошибку 0. Взглянув на рисунок 2.5 или на выражение (out2 − 1)2, нетрудно увидеть, что функция error имеет (глобальный) минимум для out2 = 1.
Итак, как мы находим минимум функции? Возможно, вы помните следующие три шага из средней школы:
1. Вычислите первую производную и проверьте, где она обнуляется
2. Вычислите вторую производную и проверьте, действительно ли вы нашли локальный минимум, а не максимум.
3. Теперь у нас есть один или несколько локальных минимумов.
Теперь сравните значение функции для всех локальных минимумов, определенных на первых двух шагах, чтобы получить глобальный минимум.
Это правильный подход, но его трудно реализовать на практике.
При заданном значении x0 гораздо более простой подход, особенно если мы имеем дело с очень сложными функциями, заключается в следующем:
чтобы найти (локальный) минимум функции f(x), мы
• Вычислить первую производную f'(x)
• Оцените первую производную в точке x0.
Если f'(x0)> 0, то f(x) уменьшается, если мы уменьшаем x0.
Если f'(x0)< 0, то f(x) уменьшается, если мы увеличиваем x0.
Если f'(x0) = 0 или если f(x0) ≈ 0, мы нашли локальный минимум.
• Просто надеемся, что этот локальный минимум является глобальным.
Это проиллюстрировано на рисунке 2.6.
Давайте рассмотрим примеры x1 = 1 и x2 = 0.
Это имеет ожидаемый результат 0, но сеть выводит 0,95, что является нашим начальным значением для x0.
Для x0 = 0.95 мы имеем ошибку (0.95 − 0)2 = 0.9025 — крайняя правая точка, отмеченная на рисунке 2.6.
Взяв производную, мы имеем (x2)'= 2x.
Но для этой конкретной точки производная предоставляет информацию о наклоне линии.
Идея теперь состоит в том, чтобы посмотреть на уклон и двигаться в направлении, которое минимизирует ошибку, т.е. здесь, влево.
В количественном отношении мы имеем (x2)'(0.95) = 2 ∗ 0.95 = 1.9.
Поскольку первая производная на этом этапе положительна, нам нужно уменьшить входной аргумент, чтобы достичь минимума.
Вычтем из x0 какое-то маленькое значение, скажем, 0.5.
Наше новое значение x0 = 0,95 − 0,5 = 0,45;
снова отмечено на рисунке 2.6. Ошибка для этого нового значения x0 равна (0.45 − 0)2 ≈ 0.2, поэтому мы уже значительно уменьшили ошибку.
Мы можем повторить это в другой раз, снова рассматривая уклон на этом этапе:
(x2)'(0.45) = 0.9, т.е. производная снова положительная, и нам нужно уменьшить x0, чтобы двигаться в направлении минимума.
Теперь у нас 0,45 − 0,5 = −0,05. Это крайняя левая точка, отмеченная на рисунке 2.6. Тогда ошибка равна (−0,05−0)2 = 0,0025.
Мы немного превысили глобальный минимум x0 = 0, но мы очень близки к минимуму, так как ошибка почти равна нулю.
Теперь у нас есть простой метод для вычисления локального минимума функции error.
Но как это связано с сетью?
Конечно, мы можем минимизировать функцию ошибки, но входом для функции ошибки является выход сети, т.е. выход, который мы не можем напрямую изменить - мы можем только настроить веса сети!
Чтобы свести ошибку к минимуму, давайте рассмотрим определение входных данных функции error, а именно выходных данных сети. Это согласно определению:
out = sigmoid ( 1 ∗ w0 + x1 ∗ w1 + x2 ∗ w2 )
Чтобы оценить, как изменится ошибка, если мы внесем небольшие изменения в w1, предположим, что все остальное в этой функции постоянно, включая w0 и w2.
Но это как раз и есть частная производная w.r.t. w1.
Частная производная отвечает на вопрос: предполагая, что все постоянно, следует ли нам немного увеличивать или уменьшать w1, чтобы уменьшить глобальную общую ошибку?
А для w2 на тот же вопрос можно ответить с помощью частной производной w.r.t. w2.
Теперь у нас есть план по обучению нейронной сети:
1. Инициализируйте сеть случайными весами
2. Возьмите пример (или группу примеров) и вычислите погрешность сети с этими примерами
3. Вычислите глобальную ошибку путем усреднения по всем отдельным ошибкам
4. Для всех весов wi вычислим частную производную W.R.T. wi
5. В зависимости от частной производной, немного увеличиваем или уменьшаем каждый вес wi
Давайте применим это на практике для нашего примера.
Ограничимся весами без смещения w1 и w2, а в качестве значения ошибки запишем E.
Для простоты рассмотрим случай, когда мы обновляем нашу сеть с помощью всего одного примера, и таким образом опускаем индексы i. Используя определение сети вместе с функциями активации и ошибки, мы вычисляем для нашей сети следующее:
и мы хотим вычислить dE/dw1 и dE/dw2.
Обратите внимание, что E может быть выражено как композиция из нескольких функций.
Мы будем дублировать их для части, которая вычисляет значение выходного узла (функция активации), а net — для части, которая умножает входные данные с весами и суммирует их. Мы также опускаем аргументы функции слева для лучшей читаемости:
Теперь вспомним правило цепи для вычисления производных.
Правило дифференцирования сложной функции — это способ нахождения производной от составных функций . Это одно из основных правил, используемых в математике для решения дифференциальных задач. Оно помогает нам находить производные от составных функций, таких как (3x2 + 1)4 , (sin 4x), e3 x, (ln x)2 и других.
С помощью правила дифференцирования сложной функции находятся только производные составных функций.
У нас есть
Давайте вычислим E'(w1) с правилом цепочки и используем (x1 = 1, x2 = 0) с ожидаемым выходом 0 в качестве обучающих данных:
Обратите внимание, что 1 во второй строке справа происходит от внутренней производной out.
Иногда (r − out)2 используется для функции ошибки.
Тогда мы получим −1 для внутренней производной, и конечный результат будет таким же.Давайте разберемся со следующей производной из цепочки.
Производная сигмоидной функции является сложной, но обратите внимание, что
где для нашего обучающего примера мы имеем x1 = 1.
Сложив все это вместе, мы получим dE/dw1 = 1,9 ∗ 0,48 ∗ 1 ≈ 0,086.
Частная производная положительна, поэтому следует немного уменьшить w1.
На сколько? Это сложный вопрос. Если вы помните рисунок 2.6, вы заметили, что если мы предпримем слишком большие шаги, мы можем переступить минимум. Если мы будем делать очень маленькие шаги, этого не должно происходить, но может потребоваться довольно много итераций, пока мы не приблизимся к минимуму.
Общее эмпирическое правило состоит в том, чтобы обновлять вес как
где n (ню) — это просто некоторый эвристически выбранный положительный постоянный фактор, называемый скоростью обучения.
Обратите внимание, как частная производная заботится о правильном знаке.
Здесь производная положительна, таким образом, n(dE/dw1) также положительна, и мы вычитаем из w1.
Давайте возьмем n= 0.5, и у нас будет w1 = 2 − (0.5 ∗ 0.86) = 1.57.
Тогда для dE/dw0 (обратите внимание, что x0 = 1 по определению веса смещения) и dE/dw2 мы можем выполнить те же вычисления.
Получаем обновленные веса
w0= 0.96, w1= 1.96, w2= 3.0
С обновленными весовыми коэффициентами наша сеть вычисляет для двух примеров
Как мы видим, сеть оценивает выборку x1 = 1, x2= 1 все еще почти на 1, но немного снижает выход выборки x1= 1, x2 = 0 в сторону желаемого результата 0.
Можно ожидать, что после еще нескольких итераций сеть выдаст веса, которые правильно имитируют желаемую функцию И.
Мы увидим его реализацию в следующем разделе.
Остается еще один открытый вопрос: Что делать, если в нашей сети не один слой, а несколько (скрытых) слоев.
В этом случае мы выражаем сеть как цепочку еще большего количества функций и применяем правило
цепочки для обновления весов.
В приведенном выше примере вместо dnet/dw1 мы можем, например, иметь dnet1/dout0 для некоторого out0, который затем состоит из некоторой net0,
Из всего этого можно понять только одно - сеть обучается методом научного тыка
Поэтому оставим этот раздел математики на будущее и перейдем к следующему разделу.
Из всего этого можно понять только одно - сеть обучается методом научного тыка
Поэтому оставим этот раздел математики на будущее и перейдем к следующему разделу.
Насколько я могу судить, разделы выше это довольно частная штука.
Сути вещей она не объясняет и как связано с шахматами тоже
Примечание.
В дальнейшем все примеры идут на языке Python.
Я подумал и решил, а почему бы не установить Python, чтобы пользоваться примерами.
Установил, хотя я не знаю этого языка, но это не важно Python 3.8.0
Поставте галочку - "Add Python 3.8 to PATH"
Проверка установки
Откройте командную строку (нажмите Win + R, введите cmd и нажмите Enter). Введите команду:
python --version
Установка библиотеки Python Chess
Прежде чем погрузиться в кодирование, нам нужно установить библиотеку Python Chess. Python, будучи языком с открытым исходным кодом, предлагает широкий спектр бесплатных библиотек, и библиотека Python Chess — одна из них. Чтобы установить ее, просто выполните команду
pip install chess
Установка редактора кода
Для работы нам понадобится редактор кода (IDE)
Ты, Достопочтенный,
действительно можешь быть
ищущим, ибо, стремясь к своей
цели, ты не видишь многого, что
было бы прямо перед тобой.
Матиас Файста
В основополагающей работе «Думай как гроссмейстер» Александр Котов учит простому и прямолинейному методу мышления как гроссмейстер. Его метод
поиска наилучшего хода в позиции основан на следующих простых шагах:
• учитывать все интересные ходы в заданной позиции
• Затем для каждого из этих ходов рассчитайте все полученные вариации.
Однако, как только вы рассчитали линию, никогда не возвращайтесь к этой линии, просто обязательно проведите свой первоначальный анализ.
• просчитывать все линии для соперника
• используя это «дерево анализа» вариаций, окончательно оценить позицию и выбрать наиболее перспективный ход.
Но, может быть, основная причина в том, что я вообще не знаю ни одного гроссмейстера.
Тем не менее, это звучит как стратегия, которую может реализовать компьютер.
Во-первых, обратите внимание, что некоторые вещи здесь немного расплывчаты.
В частности, на какую глубину мы будем рассчитывать? Если мы не находимся в эндшпиле, где некоторые линии на самом деле оказываются в конечной позиции, т.е. мате, патовой или ничьей, нам придется где-то остановиться и оценить текущую позицию:
равна ли она?
Или у одной из сторон есть преимущество?
В предыдущей главе мы видели, как создать чрезвычайно мощную и сложную функцию оценки с помощью глубокой нейронной сети с различными слоями.
Однако такая функция оценки не была доступна на заре компьютерных шахмат.
И на данный момент нет способа совместить функцию оценки на основе глубокой нейронной сети с минимаксным или альфа-бета-поиском — но об этом позже.
Итак, давайте начнем с того, чему учат каждого ребенка, когда начинают играть в шахматы: подсчет пешек.
И немного подправьте это, учитывая расположение фигур, т.е. убедившись, что элементы, размещенные в центре, считаются более ценными, чем элементы, размещенные на краю.
В качестве основы мы будем использовать цифры из таблицы 3.1.
Если дать слону на десять очков больше, чем коню, функция оценки будет в пользу пары слонов.
Кроме того, две ладьи оцениваются выше, чем один ферзь.
Все это, конечно, спорно, но опять же: это всего лишь очень грубая оценка.
Мы можем немного изменить это, добавив или вычитая очки в зависимости от того, где размещена фигура.
Это показано в таблице 3.2.
Например, конь, поставленный на e4, будет оценен не 310 очками, а 310 + 20 = 330 очками.
Опять же, это спорно, особенно когда речь идет о сложных миттельшпилях или эндшпилях, но этого достаточно в качестве грубой эвристики.
Конечно, есть и более качественные функции оценки.
Например, вы можете попытаться определить, находится ли игра в начале, в середине игры или есть эндшпильная позиция. В зависимости от этого, возможно, будет лучше переместить короля за пределы центра в безопасное место или ближе к центру. В позициях миттельшпиля вы можете оценить безопасность короля,т.е. рокировался ли король? Пешки перед королем? Двигались ли эти пешки? Есть ли пешки на седьмой или второй горизонтали?
В идеале, конечно, мы должны использовать для оценки глубокую нейронную сеть, т.е. сеть, как она была представлена в предыдущей главе.
Однако, чтобы понять классический поиск минимакса и альфа-бета, с этого момента мы просто предположим, что у нас есть функция оценки,
которую можно быстро вычислить, как тривиальная функция выше.
Реализация функции оценки
Существует отличная и простая в использовании шахматная библиотека, получившая название python-chess forPython. С его помощью легко реализовать функцию оценки, которую мы описали выше.
Во-первых, мы определяем массив со значениями квадрата в листинге 3.1.
Центральной структурой данных python-chess является доска, на которой закодирована шахматная позиция. Имея доску, мы просто перебираем все
возможные квадраты и, в зависимости от фигуры, которая размещена на квадрате, мы суммируем значение фигуры вместе со значением из таблицы с фигурой в квадрате, чтобы получить общее количество очков.
Мы делаем это как для Белых, так и для Черных. Наконец, мы возвращаем разницу в общем счете за белых и черных.
Это показано в листинге 3.2.
Мы можем быстро протестировать функцию оценки.
На рисунке 3.1 показана позиция, в которой белые могут сделать ход и поставить мат.
r1bqkb1r/pppp1ppp/2n2n2/4p2Q/2B1P3/8/PPPP1PPP/RNB1K1NR w KQkq - 4 4
Функция оценки, конечно, не будет учитывать мат и просто рассчитает оценку на основе подсчета фигур и их расстановки.
Давайте вернемся к предложению Котова о том, как считать или как шахматисты должны считать вообще, но определим вещи более формально и без какой-либо двусмысленности — чтобы компьютер мог понять и реализовать подход алгоритмически. Но прежде давайте рассмотрим конкретный пример, чтобы понять общий принцип. Для этого мы рассматриваем эндшпиль с тремя противоборствующими пешками, изображенный на рисунке 3.2.
8/5pp1/6p1/5P1P/8/K7/8/k7 w - -
Чтобы упростить задачу, мы рассмотрим только правый верхний угол позиции и забудем про позицию короля. Также немного изменим условия выигрыша: белый выигрывает, если сможет поставить пешку на третью горизонталь. Черные выиграют, если смогут заблокировать или захватить все
пешки белых.
Обратите внимание, что черные не выигрывают при достижении пятой горизонтали, мы рассматриваем только исходы «белые выигрывают» или «черные блокируют или захватывают всех». Понятно, что ничьи невозможны. Мы также предположим, что у нас есть функция оценки, которая может оценить любую позицию, и которая выведет 10, если белые выиграют, и 0, если выиграют черные. Нет никаких объяснений, как работает эта функция оценки; Мы просто предположим, что он есть. Все это просто для того, чтобы получить пример с меньшим количеством возможных ходов и вариаций, чтобы все еще можно было рассчитать вручную все варианты.
Прежде чем мы начнем, еще несколько определений.
При иллюстрировании последовательности ходов и результирующих позиций мы делаем это с помощью дерева.
Пример показан на рисунке 3.3.
Сверху находится корневой узел. От корневого узла есть разные ответвления, по которым мы можем проследить, которые ведут к другим узлам, дочерним узлам корневого узла. Внизу находятся узлы, которые не имеют преемников. Они называются листовыми узлами. Оно имеет некоторое сходство с настоящим деревом, если рассматривать его вверх ногами.
Начнем с позиции (1) на рисунке 3.3. Ход белым.
Есть четыре возможных хода:
• Белые могут продвинуть левую пешку вперед.
• Белые могут взять левой пешкой черную.
• Белые могут взять правой пешкой черную.
• Белые могут продвинуть правую пешку вперед.
Теперь нам нужно рассмотреть каждый из них.
Мы начинаем с реализации первого варианта и переместите левую белую пешку вперед.
Теперь настала очередь черных. У них есть три варианта:
взять белую пешку справа с результатом позиции (4), продвинуться вперед средней пешкой с результатом позиции (5) или взять левую пешку в результате позиции (6).
Мы могли бы пойти дальше и рассмотреть все возможные ответы белых на каждый из этих ходов, но давайте предположим, что мы остановимся на этом и вызовем нашу функцию оценки.
Поскольку в позициях (4), (5) и (6) белые всегда будут иметь свободную пешку и, таким образом, смогут дойти до третьей горизонтали, оценка даст оценку 10 для каждой из этих позиций.
Как уже упоминалось, мы оставим открытым вопрос о том, как функция оценки приходит к этому выводу, мы просто предположим, что она есть. То же самое мы можем сделать и для других возможных ходов.
Например, если правая белая пешка в начальной позиции берут черную пешку, а мы рассматриваем все возможные ответы черных, то оказываемся в позициях (7) и (8). Они оцениваются как 0, так как белые больше не могут прорваться.
Как же мы можем использовать эту информацию для оценки положения листовых узлов?
Предположим, мы хотим вычислить оценку узла (2). Здесь ход черных. Мы всегда будем считать, что черные делают наилучший возможный ход (с оценкой дочерних узлов). Другими словами, черные пытаются свести к минимуму результат оценки. Он выберет ход, который приведет
к дочернему узлу с наименьшей оценкой. Здесь он может выбрать между тремя узлами, однако все они дают оценку 10. Однако минимальное число 10, 10 и 10 равно 10. Аналогично для вычисления узла (3), все ходы приводят к позиции,которая оценивается как 0. Здесь минимум 0.
Пока что все это не очень интересно. Итак, давайте рассмотрим, как эти оценки узлов (2) и (3) помогают нам получить более точную оценку корневого узла. В корневом узле играют белые.
Белые, конечно, выберут тот ход, который приведет к максимально возможной оценке, т.е. они хотят максимизировать свой результат.
Для узла (2) теперь он знает, что если черные играют идеально, то позиция оцениваетсяв 10 баллов..
Для узла (3) позиция оценивалась как 0.
Мы его не вычисляли, но предполагаем, что для всех остальных ходов из корневого узла мы также получим оценки 0.
Белые выбирают максимум из всех возможных вариантов, т.е. они будут играть левой пешкой вперед, ведущей к узлу с оценочным значением 10. Так как это максимум, то мы считаем корневой узел также оцениваемым со значением 10, т.е. выигрыш для белых.
Сформулируем этот подход в виде алгоритма:
• Сначала создаем дерево поиска. Имея позицию, мы рассматриваем все ходы для той стороны, чей ход, скажем, у белых.
Для каждого хода мы учитываем все ответы черных. Опять же, для каждого из этих ходов черных есть ряд ходов белых и так далее.
• В какой-то момент мы должны остановиться. Либо потому, что больше нет разрешенных ходов (т.е. игра закончена матом или ничьей), либо просто потому, что у нас не хватило времени и места, так как дерево растет очень быстро. Простой способ ограничить размер дерева поиска — всегда останавливаться на фиксированном расстоянии от корня, т.е. на фиксированной глубине дерева.
• Для каждого листового узла сгенерированного дерева мы должны оценить положение вашей функции оценки. Это может быть функция
подсчета пешек, которую мы представили ранее. Мы дополняем эту функцию оценки для позиций, где белые выиграли матом, оценкой позиции как ∞, снятых позиций как 0 и с позиций, где черные выиграли матом с −∞.
• Теперь мы шаг за шагом распространяем результаты обратно на корневой узел. При данном подходе, где все дочерние узлы имеют оценки, мы – берем максимальное значение всех дочерних узлов, если это очередь белых, берем минимальное значение всех дочерних узлов, если это очередь черных.
Эта процедура известна как минимакс.
Обратите внимание,что минимакс является довольно независимым от шахмат. В частности, он может быть применен ко всем играм с двумя игроками, подобно шахматам, при условии, что существует функция оценки, которая, учитывая позицию в игре, может дать числовую оценку позиции.
Используя python-chess, minimax имеет прямолинейную реализацию, показанную в листинге 3.4.
Listing 3.4: The minimax algorithm
Функция bestmove принимает три параметра: доску, которую следует оценить,текущую глубину (для ограничения глубины поиска) и логический параметр, который указывает, следует ли нам максимизировать или минимизировать оценку текущей доски.
Если у нас есть мат, то вместо того, чтобы возвращать бесконечность, мы возвращаем очень большое положительное (или отрицательное) целое число, в зависимости от того, поставили ли белые мат черным или наоборот.
Если игра закончилась вничью, мы возвращаем 0.
Во всех остальных случаях мы генерируем все допустимые ходы текущей позиции. Для каждого хода мы применяем этот ход для достижения следующей позиции. Затем остается определить, наступила ли очередь белых, и мы хотим получить максимальный результат в этой позиции на доске, или
это очередь черных, и мы хотим взять минимальный результат для этой позиции.
Рассмотрев все допустимые ходы, мы эффективно вычислили оценку текущей доски и вернули эту оценку, которая была сохранена в переменной best_value.
По сути, мы уже реализовали шахматный движок, пусть и очень простой.
Имея позицию, мы можем использовать минимакс, чтобы получить следующий лучший ход
Listing 3.5: Compute Best Move in Position
def getNextMove (depth , board , maximize):
legals = board. legal_moves
bestMove = None
bestValue = -99999
if(not maximize):
bestValue = 99999
for move in legals:
board.push(move)
value = minimax(board , depth - 1, (not maximize))
board.pop ()
if maximize:
if value > bestValue:
bestValue = value
bestMove = move
else:
if value < bestValue:
bestValue = value
bestMove = move
return (bestMove , bestValue)
Сначала мы генерируем все возможные легальные ходы в текущей позиции.
Если наступает очередь белых, мы ищем ход с наибольшим количеством очков и инициализируем оценку для лучшего хода в переменной bestValue с очень маленьким числом, так что любой ход, возвращаемый minimax, будет лучше этого значения по умолчанию. Если наступает очередь черных, мы стремимся минимизировать счет и таким образом инициализируем bestValue с очень большим числом. Далее мы перебираем все разрешенные ходы и сравниваем счет с лучшим из найденных на данный момент. Если мы нашли более удачный ход, то запоминаем его в переменной bestMove.
После перебора всех ходов мы, наконец, возвращаем лучший ход, найденный на данный момент.
import chess
pieceSquareTable = [
[ -50,-40,-30,-30,-30,-30,-40,-50 ],
[ -40,-20, 0, 0, 0, 0,-20,-40 ],
[ -30, 0, 10, 15, 15, 10, 0,-30 ],
[ -30, 5, 15, 20, 20, 15, 5,-30 ],
[ -30, 0, 15, 20, 20, 15, 0,-30 ],
[ -30, 5, 10, 15, 15, 10, 5,-30 ],
[ -40,-20, 0, 5, 5, 0,-20,-40 ],
[ -50,-40,-30,-30,-30,-30,-40,-50 ] ]
def eval(board):
scoreWhite = 0
scoreBlack = 0
for i in range (0 ,8):
for j in range (0 ,8):
squareIJ = chess.square(i,j)
pieceIJ = board.piece_at(squareIJ)
if str(pieceIJ) == "P":
scoreWhite += (100 + pieceSquareTable [i][j])
if str(pieceIJ) == "N":
scoreWhite += (310 + pieceSquareTable [i][j])
if str(pieceIJ) == "B":
scoreWhite += (320 + pieceSquareTable [i][j])
if str(pieceIJ) == "R":
scoreWhite += (500 + pieceSquareTable [i][j])
if str(pieceIJ) == "Q":
scoreWhite += (900 + pieceSquareTable [i][j])
if str(pieceIJ) == "p":
scoreBlack += (100 + pieceSquareTable [i][j])
if str(pieceIJ) == "n":
scoreBlack += (310 + pieceSquareTable [i][j])
if str(pieceIJ) == "b":
scoreBlack += (320 + pieceSquareTable [i][j])
if str(pieceIJ) == "r":
scoreBlack += (500 + pieceSquareTable [i][j])
if str(pieceIJ) == "q":
scoreBlack += (900 + pieceSquareTable [i][j])
return scoreWhite - scoreBlack
NODECOUNT = 0
def minimax(board, depth, maximize):
global NODECOUNT
if(board.is_checkmate()):
if(board.turn == chess.WHITE):
return -100000
else:
return 1000000
if(board.is_stalemate()) or board.is_insufficient_material():
return 0
if depth == 0:
return eval(board)
legals = board.legal_moves
if(maximize):
bestVal = -9999
for move in legals:
board.push(move)
NODECOUNT += 1
bestVal = max(bestVal, minimax(board, depth - 1, (not maximize)))
board.pop()
return bestVal
else:
bestVal = 9999
for move in legals:
board.push(move)
NODECOUNT += 1
bestVal = min(bestVal, minimax(board, depth - 1, (not maximize)))
board.pop()
return bestVal
def getNextMove (depth , board , maximize):
legals = board. legal_moves
bestMove = None
bestValue = -99999
if(not maximize):
bestValue = 99999
for move in legals:
board.push(move)
value = minimax(board , depth - 1, (not maximize))
board.pop ()
if maximize:
if value > bestValue:
bestValue = value
bestMove = move
else:
if value < bestValue:
bestValue = value
bestMove = move
return (bestMove , bestValue)
board = chess.Board (" r1bqkb1r/pppp1ppp/2n2n2/4p2Q/2B1P3/8/PPPP1PPP/RNB1K1NR w KQkq - 4 4")
print (" current evaluation ")
print(eval(board))
print(getNextMove(2, board , True))
В основополагающей работе «Думай как гроссмейстер» Александр Котов учит простому и прямолинейному методу мышления как гроссмейстер. Его метод
поиска наилучшего хода в позиции основан на следующих простых шагах:
• учитывать все интересные ходы в заданной позиции
• Затем для каждого из этих ходов рассчитайте все полученные вариации.
Однако, как только вы рассчитали линию, никогда не возвращайтесь к этой линии, просто обязательно проведите свой первоначальный анализ.
• просчитывать все линии для соперника
• используя это «дерево анализа» вариаций, окончательно оценить позицию и выбрать наиболее перспективный ход.
Надо сказать, что хоть Котов и гроссмейстер, изложил он метод довольно непедагогично
И судя по всему, автор книги его еще и дополнительно извратил.
С помощью минимаксного алгоритма нам нужно посетить множество узлов в дереве, т.е. найти и оценить множество позиций. Сколько?
Приступим к небольшому эксперименту. Рассмотрим еще раз положение на рисунке 3.1.
Мы можем использовать эту позицию для двух целей.
Во-первых, давайте посмотрим, действительно ли работает наша реализация минимакса и находит ли (очевидный) мат Qxf7.
Во-вторых, давайте посмотрим, сколько узлов нужно посетить, чтобы найти мат.
Используя нашу реализацию getNextMove, это очень просто.
Для начала зафиксируем глубину полуходов d для поиска дерева. Затем нам нужно создать объект board с позицией и вызвать getNextMove.
В Python он состоит всего из двух строк, показанных в листинге
Listing 3.6: Alpha-Beta Position Evaluation
Для рисунка 3.1 и глубины 3 это на самом деле занимает несколько минут на моем компьютере. Опять же, это Python, и он далек от эффективной реализации шахматного движка. Матовый ход Qxf7 в конце концов найден. Добавление счетчика дает нам посещенные узлы — в этом примере нам нужно было посетить 46828 узлов.
(Move.from_uci('h5f7'), 1000000)
46828
[Finished in 6.8s]
Можем ли мы сделать лучше и уменьшить количество узлов, которые мы посещаем,но при этом быть уверенными в том, что мы найдем мат?
Давайте еще раз посмотрим на пример, который был представлен в minimax, изображенном на рисунке 3.4.
Начинаем с корня, затем посещаем узел (2), и далее расширяемся до узлов (6), (7) и (8). На этом наше разложение заканчивается, мы вызываем нашу функцию оценки и распространяем результат обратно в узел (2).
Здесь мы берем минимум из трех дочерних узлов, что приводит к вычислению 10 для узла (2).
Затем мы возвращаемся к корневому узлу и начинаем разворачивать следующий возможный ход, что приводит к посещению узла (3).
В узле (3) доступны два возможных хода. Мы начинаем с обратного захвата пешкой, посещаем узел (9), где мы достигаем нашего предела глубины поиска, и оцениваем позицию, чтобы получить оценочное значение, 0.
В этот момент давайте немного остановимся перед дальнейшим действием и рассмотрим информацию, которая нам доступна в данный момент.
В узле (3) играют черные. Левый ребенок поставил ему 0. Если другой дочерний узел больше 0, черный выберет лучший (минимальный) узел ниже, и
это именно тот дочерний узел с 0. Если другой ребенок даже меньше 0, черные, конечно, выберут его.
Другими словами, у черных есть как минимум узел со значением 0, возможно даже меньше. Теперь давайте поднимемся дальше по дереву, вернемся к корневому узлу (1). Здесь ход белых. Белые стараются максимизировать исход партии.
Мы знаем, что черные могут получить как минимум 0, если белые выберут дочерний узел (3). Но из нашей предыдущей оценки мы уже знаем, что
узел (2) получит у белых 10, поэтому он всегда предпочтет узел (2) узлу (3).
Другими словами, выбор белых больше не зависит от оценки узла (10). Мы можем прекратить любое дальнейшее исследование ниже узла (3) и вместо
этого сразу перейти к узлу (4).
Оценив узел (11), мы также знаем, что черные могут получить здесь значение 0. Таким же образом мы можем прекратить любое дальнейшее исследование и перейти к узлу (5).
В итоге мы сэкономили на посещении большого количества узлов.
На самом деле, мы полностью посетили только крайнюю левую ветвь дерева, т.е. все узлы ниже точки (2), пока не достигли предела глубины поиска.
Для всех остальных узлов мы пропустили поиск и оценку нескольких частей дерева.
Мы сделали это, всегда записывая текущую оценку bestevaluation с текущим поддеревом для White (Black), и мы называем это значением alpha
(beta).
Если мы можем отрезать ветвь и пропустить посещение ее узлов, мы говорим, что мы сделали альфа (бета) отсечку.
Отсюда и название алгоритма:
альфа-бета поиск.
Алгоритм показан в листинге 3.7.
import chess
# P = 100
# N = 310
# B = 320
# R = 500
# Q = 900
# position table
pieceSquareTable = [
[ -50,-40,-30,-30,-30,-30,-40,-50 ],
[ -40,-20, 0, 0, 0, 0,-20,-40 ],
[ -30, 0, 10, 15, 15, 10, 0,-30 ],
[ -30, 5, 15, 20, 20, 15, 5,-30 ],
[ -30, 0, 15, 20, 20, 15, 0,-30 ],
[ -30, 5, 10, 15, 15, 10, 5,-30 ],
[ -40,-20, 0, 5, 5, 0,-20,-40 ],
[ -50,-40,-30,-30,-30,-30,-40,-50 ] ]
def eval(board):
scoreWhite = 0
scoreBlack = 0
for i in range(0,8):
for j in range(0,8):
squareIJ = chess.square(i,j)
pieceIJ = board.piece_at(squareIJ)
if str(pieceIJ) == "P":
scoreWhite += (100 + pieceSquareTable[i][j])
if str(pieceIJ) == "N":
scoreWhite += (310 + pieceSquareTable[i][j])
if str(pieceIJ) == "B":
scoreWhite += (320 + pieceSquareTable[i][j])
if str(pieceIJ) == "R":
scoreWhite += (500 + pieceSquareTable[i][j])
if str(pieceIJ) == "Q":
scoreWhite += (900 + pieceSquareTable[i][j])
if str(pieceIJ) == "p":
scoreBlack += (100 + pieceSquareTable[i][j])
if str(pieceIJ) == "n":
scoreBlack += (310 + pieceSquareTable[i][j])
if str(pieceIJ) == "b":
scoreBlack += (320 + pieceSquareTable[i][j])
if str(pieceIJ) == "r":
scoreBlack += (500 + pieceSquareTable[i][j])
if str(pieceIJ) == "q":
scoreBlack += (900 + pieceSquareTable[i][j])
return scoreWhite - scoreBlack
NODECOUNT = 0
def alphaBeta(board, depth, alpha, beta, maximize):
global NODECOUNT
if(board.is_checkmate()):
if(board.turn == chess.WHITE):
return -100000
else:
return 1000000
if depth == 0:
return eval(board)
legals = board.legal_moves
if(maximize):
bestVal = -9999
for move in legals:
board.push(move)
NODECOUNT += 1
bestVal = max(bestVal, alphaBeta(board, depth-1, alpha, beta, (not maximize)))
board.pop()
alpha = max(alpha, bestVal)
if alpha >= beta:
return bestVal
return bestVal
else:
bestVal = 9999
for move in legals:
board.push(move)
NODECOUNT += 1
bestVal = min(bestVal, alphaBeta(board, depth - 1, alpha, beta, (not maximize)))
board.pop()
beta = min(beta, bestVal)
if beta <= alpha:
return bestVal
return bestVal
def getNextMove(depth, board, maximize):
legals = board.legal_moves
bestMove = None
bestValue = -9999
if(not maximize):
bestValue = 9999
for move in legals:
board.push(move)
value = alphaBeta(board, depth-1, -10000, 10000, (not maximize))
board.pop()
if maximize:
if value > bestValue:
bestValue = value
bestMove = move
else:
if value < bestValue:
bestValue = value
bestMove = move
return (bestMove, bestValue)
board = chess.Board ("r1bqkb1r/pppp1ppp/2n2n2/4p2Q/2B1P3/8/PPPP1PPP/RNB1K1NR w KQkq - 4 4")
print(getNextMove(3, board , True))
print(NODECOUNT)
(Move.from_uci('h5f7'), 1000000)
8050
[Finished in 8.1s]
Здесь мы повторно используем функцию вычисления из реализации minimax.
Расчет наилучшего хода в текущей позиции также такой же, как и раньше.
Мы лишь заменяем сам алгоритм поиска.
Давайте сопоставим пример с реализацией.
Мы инициализируем алгоритм с очень маленьким значением для alpha и очень большим значением для beta, что указывает на то, что мы не можем вырезать какую-либо ветвь в начале без поиска.
Теперь сосредоточимся на строках кода 12-19 и узле (1). Для каждого хода мы вычисляем оценку поддерева, сравниваем ее с нашим текущим значением альфа и берем максимум обоих.
Выполнение поиска альфа-бета на узле (2) дает нам наилучшее значение 10, которое является нашим новым значением альфа.
Теперь мы начинаем посещение узла (3) со значением альфа10. После посещения узла (9) и возвращения к узлу (3) мы имеем значение бета 0
— по нашей текущей информации, это лучшее, что могут сделать черные.
В этот момент значение бета — значение 0 — меньше, чем значение альфа — значение 10— (строка 17).
Вместо того, чтобы завершать цикл for, который начинается в строке 12, мы немедленно возвращаем нашу оценку, тем самым отсекая узел (10).
Выполнение альфа-бета поиска с той же глубиной, что и minimax, в позиции, показанной на рисунке 3.1, возвращает результат в несколько раз меньше по сравнению с minimax.
Количество узлов уменьшилось с 46828 до 9050. Прим.(У меня 8050, скорее всего опечатка)
Альфа-бета-поиск позволил нам пропустить множество узлов. Для более глубоких поисков эффект становится еще более важным!
Прим. предыдущая часть раздела пропущена т.к. - это просто вода
3.5 Поиск дерева по методу Монте-Карло
3.5.1 Игра в Го
В предыдущих разделах мы видели, что альфа-бета поиск является очень мощным алгоритмом, с помощью которого мы можем создавать мощные шахматные движки.
Так почему же мы должны искать альтернативные подходы к поиску?
Давайте посмотрим на игру Го.
Го выглядит интригующе простым на первый взгляд, но невероятно глубокой игрой.
Для тех, кто не знаком с Го, давайте очень кратко повторим основные понятия и правила Го.
Вместо квадратов на доске печатаются 19 на 19 линий, а на пересечениях расставляются фигуры, называемые точками.
Существует только один вид фигур – камень.
Игроки ходят поочередно (в отличие от шахмат, у черных первый ход) и кладут камни на доску.
После установки камни больше не перемещаются, но их можно захватить.
Цель игры – занять как можно больше территории.
Территория защищена, если есть группа камней, которые окружают территорию. Вражеские камни можно захватывать, окружив их своими камнями.
Чтобы сохранить территорию и убедиться, что камни, окружающие территорию, не захвачены вражескими камнями, должно быть определенное количество незанятых точек. Камни, окружающие территорию, называются группами.
Рассмотрим следующие примеры:
• На рисунке 3.8 черные окружили территорию. Но эту территорию атакуют белые камни, которые сами окружают черных.
На территории черных есть только одна свободная точка — глаз.
Если настанет очередь белых, она просто поставит один камень на последнюю незанятую точку, тем самым захватив все черные камни сразу.
Следовательно, черная группа не жива, так как территория не может быть сохранена.
• На рисунке 3.7 у черных есть группа с двумя глазами. Если белые положат камень в один из глаз, это не приведет к захвату, так как у черных остается еще один глаз. Однако белый камень, помещенный в глаз, сам будет окружен черными камнями. Это было бы своего рода самоубийственным
ходом, что запрещено в Го. Следовательно, черная группа на рисунке живая.
• На рисунке 3.9 с первого взгляда можно подумать, что черная группа жива. Но рассмотрим размещение белыми камня в верхней правой
свободной точке. Эта свободная точка не является настоящим глазом:
если белые положат туда камень, это приведет к захвату камня прямо рядом с острием, что не будет самоубийственным ходом. Оставшаяся
черная группа имеет только один глаз и не жива. Поэтому вся группа не жива.
• Точно так же глаз на самом деле является всего лишь одной свободной точкой. Например, на рисунке 3.10 черная группа не жива. Вы можете попытаться разобраться сами, почему это так.
Естественно, есть несколько пограничных случаев и много тактической теории о том, как двигаться, чтобы убедиться, что группы живы, или как убивать ходы.
Этого достаточно, чтобы получить представление о сложности, связанной с Go.
Существуют тактики, такие как вся теория групп и как обводить камни, как упоминалось выше.
Однако, по сравнению с шахматами, кажется, что гораздо больше внимания уделяется пониманию позиции и распознаванию образов из-за огромного размера доски.
Камни могут быть размещены в, казалось бы, не связанных друг с другом местах на доске, и позже, когда камней становится все больше и больше, их связь внезапно приобретает значение.
Это подводит нас к первому важному наблюдению, когда мы сравниваем шахматы и Го:
в отличие от шахмат, здесь нет простой функции оценки, чтобы оценить произвольное положение.
Любители борются с этим, и требуются годы практики и таланта, чтобы развить позиционное понимание игры.
В шахматах мы умеем считать фигуры.
В Го это не имеет особого смысла, потому что вы можете разместить гораздо больше камней на доске, создавая группу, но позже в игре все эти камни будут захвачены сразу, потому что окажется, что вы не сможете сохранить группу в живых, то эти камни ничего не стоят.
Создание подходящих функций оценки — это то, над чем разработчики компьютерных систем бились веками.
До революции, которая произошла с AlphaGo, использовались сложные вычислительные функции, включающие в себя множество эвристических функций обнаружениям шаблонов.
Однако их вычисления были дорогостоящими.
Помните, что для работы альфа-бета поиска нам нужна быстрая и разумная функция точной оценки. Если функция вычисления настолько медленна, что на практике мы можем искать только на один ход вперед, мы в основном не ищем вообще, а в основном полагаемся только на функцию оценки для определения следующего хода. Еще одним осложняющим фактором является сложность игры.
Как уже упоминалось, Goр азмещается на доске в формате 19 умножить на 19.
Следовательно, у начинающего игрока (черных) есть 19 ∗ 19 + 1 = 362 хода на выбор — в Го можно пасовать, отсюда и лишний ход.
Когда ставится один камень, у соперника есть 362 − 1 = 361 возможный ход и так далее.
Захват камней и построение групп, конечно, ограничивает количество возможных ходов, но это все равно довольно много.
Сравните это с количеством возможных дебютных ходов в шахматах.
В исходной позиции белые могут сделать по два возможных хода каждой пешкой, в результате чего получается 16 возможных ходов.
Кроме того, есть четыре возможных хода белыми конями, в результате чего в общей сложности 20 возможных дебютных ходов для белых.
У черных есть 20 возможных ответов.
После хода нескольких пешек количество возможных ходов, конечно, увеличивается, но мы все равно видим, что количество возможных ходов в
шахматной позиции на несколько величин меньше, чем в Го.
Согласно Мацубаре и др., мы можем оценить коэффициент ветвления (т.е. среднее количество возможных ходов в данной позиции) для Го в 250 и для шахмат в 35.
Обратите внимание, что в шахматах часто встречаются бессмысленные ходы, которые легко заметить — вспомните предыдущий раздел и поиск покоя, где мы можем заметить бессмысленные взятия.
В то время как в Го все не так просто. Кроме того, в Го игры просто имеют гораздо больше ходов до конца игры из-за размера доски.
Также интересно сравнить разветвляющиеся множители шахмат и Го с Сёги, японским вариантом шахмат.
Он отличается от западных шахмат тем, что имеет немного большую доску (9 на 9) и тем, что захваченные фигуры могут быть возвращены в игру – подобно шахматам Crazyhouse или Bughouse. Интуитивно это создает еще большую сложность, и коэффициент ветвления оценивается примерно в 80. Интересно, что поиск альфа-бета работает (с трудом) для Сёги, а Сёги программы только недавно достигли гроссмейстерской силы.
Для сравнения, их сила всегда уступала компьютерным шахматам, и,несмотря на все новые и революционные методы, сегодня они все еще далеко не так сильны, как их шахматные коллеги.
Мы рассмотрим эти революционные техники, которые также были перенесены обратно в текущие шахматные программы, в главе о NNUE.
Подводя итог: Alpha-Beta не работает для Go, потому что
• высокий коэффициент ветвления игры
• Отсутствие быстрой и хорошей функции оценки.
Поэтому имеет смысл взглянуть на методы поиска, которые работают даже при высоком разветвлении и не полагаются на ручные функции оценки.
Чтобы решить задачу создания алгоритма, который может обрабатывать игры с большим коэффициентом ветвления и не полагается на функцию оценки, мы будем черпать вдохновение из теории шахматного дебюта.
Когда профессиональные шахматисты готовят дебюты, они полагаются на свой собственный анализ, а также на статистику.
Вы наверняка уже видели открытые баз данных. В таких базах данных хранится и накапливается информация о сыгранных играх.
Например, при открытии браузера Lichess.org с начальной позицией мы получаем следующую информацию для ходов 1.e4 и 1.a3.
Информация аккумулируется по играм топовых игроков.
• Для 1.e4 мы знаем, что этот ход был использован более чем в миллионе партий. Около 33 процентов всех партий были выиграны белыми, 42 процента были ничейными, а 25 процентов были выиграны черными.
• В версии 1.a3 только 574 партии были сыграны лучшими игроками.
Здесь 29 процентов были выиграны белыми, около 40 процентов были ничейными, а 32 процента были выиграны черными.
Кажется естественным думать, что 1.e4 лучше, чем 1.a3, глядя на статистику.
Возможно, мы немного опасаемся, чтобы быть уверенными в этом, так как было сыграно так мало игр с 1.a3.
Может случиться так, что 1.a3 - отличный ход, и маленький размер выборки не является репрезентативным.
Еще один аспект, который следует учитывать здесь, заключается в том, что по умолчанию начальная книга Lichess.org учитывает только игры игроков с более высоким рейтингом.
Очевидно, что хорошие игроки в среднем выбирают лучшие ходы, и поэтому это должно дать лучшее представление о том, что хорошо, а что плохо. Но что делать, если у нас нет такой базы данных? Как насчет игры в случайные игры?
Подумайте о следующей ситуации.
Вы находитесь в позиции, в которой есть только два хода; один ход выигрывает ферзя, а другой позволяет противнику переместить своего ферзя в безопасное место.
Мы могли бы выполнить каждый ход, а затем для обеих полученных позиций сыграть несколько тысяч случайных игр.
Под этим я подразумеваю просто случайный выбор правильных ходов в каждой последующей позиции, пока игра не закончится победой белых, ничьей или победой черных. \
Затем мы могли бы собрать статистику для этих случайных попыток.
Мы ожидаем, что для хода, который выигрывает ферзя, в среднем у нас должен быть более высокий коэффициент выигрыша.
И в этом вся идея поиска дерева Монте-Карло.
Чтобы определить следующий ход, просто выполните каждый правильный ход, сыграйте несколько случайных партий, соберите статистику для этих случайных попыток и сравните результаты, чтобы определить следующий лучший ход.
Такой подход имеет ряд преимуществ:
• Нет необходимости в функции оценки. Мы просто играем в случайные игры, пока игра не закончится.
Это также означает, что поиск по дереву Монте-Карло полностью независим от каких-либо знаний,специфичных для предметной области, и, таким образом, может быть использован для любого вида полноинформационной детерминированной игры для двух игроков.
• Потенциально мы можем работать с играми с большим коэффициентом ветвления.
Мы просто фиксируем несколько случайных выходов и не исследуем все последующие ответы каждого игрока.
Конечно, это может привести к неудаче:
предположим, вы белые, находитесь в сложной позиции в эндшпиле и пытаетесь найти следующий ход.
Предположим далее, что есть два хода.
На первом ходу белых почти все ответы черных приводят к победе белых, но есть только один конкретный ответ, в котором черные сохраняют
ничью.
На другом ходу белые всегда выигрывают при идеальной игре (все еще могут быть ничьи (если белые случайно зайдут в тупик).
Затем, полагаясь на случайные игры, вы можете пропустить один конкретный ответ на первый ход и заявить, что два хода статистически равны, или даже ложно заявить, что первый ход лучше.
С другой стороны, конкретный ответ черных также может быть пропущен игроком-человеком, и даже с такой несовершенной статистикой такой подход все равно может стать сильным компьютерным противником.
• Мы не полагаемся на огромную базу данных, но все же можем создавать достоверную статистику — за исключением упомянутых выше проблем —
поскольку случайные игры часто выполняются быстро. Таким образом, мы можем быстро играть и генерировать множество игр для каждой позиции дерева.
Чтобы более формально описать поиск дерева Монте-Карло, мы можем разбить алгоритм на четыре основные операции:
выбор, расширение,моделирование и обратное распространение.
• Выбор:
На этом шаге мы выбираем узел в дереве поиска в соответствии с некоторыми правилами. Изначально мы начинаем с текущей позиции в качестве корневого узла дерева поиска.
Пройдя через несколько итераций, мы создадим более крупное дерево поиска.
В этом случае мы движемся вниз по дереву игры до тех пор, пока не найдем и не зафиксируем листовой узел.
Конечно, нам нужно будет найти стратегию выбора хода на каждом шаге. Такая стратегия должна подбирать ходы таким образом, чтобы были выбраны наиболее перспективные ходы и чтобы мы не проводили слишком много времени в бесперспективных узлах.
Позже мы увидим, как можно построить такую стратегию вне зависимости от каких-либо знаний об игре, просто используя статистику. Пока что мы просто предположим, что такая стратегия существует.
• Расширение:
На этом шаге мы создаем новый узел, применяя ходы в узле, выбранном на шаге выбора.
В самом простом варианте алгоритма мы просто добавляем ровно один ход и добавляем полученный одноузловой узел.
Этот ход может быть выбран случайным образом или в соответствии с какой-либо другой стратегией.
Мы будем придерживаться простого варианта, когда здесь просто добавлен один узел.
• Моделирование:
На этом шаге мы выполняем вычисления для получения статистической информации о новом узле.
Самый простой способ — играть в определенное количество случайных игр, т.е. выбирать случайные ходы до тех пор, пока игра не закончится победой, ничьей или поражением.
• Обратное распространение:
На этом шаге мы берем статистическую информацию, которую мы вычислили, выполняя случайные игры, и распространяем ее обратно к корню игрового дерева.
Мы обязательно храним статистическую информацию в каждом узле о статистике выигрышей, которую мы получили для нового узла.
Мы можем визуализировать эти операции следующим образом:
мы начинаем с корневого узла, а затем выбираем ходы, пока не достигнем конечного узла (рис. 3.11).
Здесь мы расширяем листовой узел, применяя (случайное) перемещение, и создаем новый дочерний узел (рис. 3.12).
Из этого дочернего узла мы играем в случайные игры (рис. 3.13)
и, наконец, распространить результаты через все родительские узлы обратно к корневому узлу (рис. 3.14).
Есть одна важная формулировка, которую мы должны здесь прояснить. Обычно слово лист в игровом дереве обозначает точки, в которых ход невозможен.
Для шахмат это позиции, в которых игра выиграна, сыграна вничью или проиграна.
Здесь мы обозначим такие узлы как терминальные узлы.
С другой стороны, листовые узлы — это узлы, в которых не все возможные дочерние узлы были развернуты (и посещены).
...
Рассмотрим рисунок 3.15:
На первый взгляд, можно рассматривать только узлы,помеченные как 1/1 и 3/5 как листовые узлы. Ведь для узла с отметкой 2/5 у нас уже развернули дочернюю часть. Но есть и другие действия, которые возможны из узла с маркировкой 2/5, которые еще не были выполнены, поэтому все еще есть неразвернутые дочерние узлы. Следовательно, это листовой узел.
Давайте проверим небольшой пример с вещественными числами, чтобы понять, как четыре операции работают на практике.
Изначально мы начинаем с текущей позиции в качестве корневого узла.
Для каждого узла мы записываем два параметра:
а)текущую оценку узла и б) количество посещений узла.
Взгляните на рисунок 3.16.
Здесь уже были проведены некоторые итерации, и в каждом узле есть значения для двух чисел.
В левой части рисунка выбираем крайний левый узел и применяем шаг расширения.
Затем мы запускаем одну симуляцию на этом узле.
Предположим, что эта симуляция состоит только из одной сыгранной игры, и предположим далее, что мы играли в игру (не в шахматы), где исход игры либо выиграл (1), либо проиграл (0).
Итак, мы записываем 1/1 для этого недавно расширенного узла: это была одна победа, и мы посетили только что расширенный узел ровно один раз.
В правой части рисунка мы используем обратное распространение для обновления всех родительских узлов до корня этого вновь расширенного узла. Здесь имеется только один узел.
Обновляем счетчик посещений, меняя его с 5 на 6, а также обновляем оценку (добавляем один win). Прим. с 2 на 3
Затем мы продолжим выбор узла, расширим ранее непосещенный узел, запустим моделирование и обновим все родительские узлы.
Здесь мы немного упростили ситуацию. Не все игры имеют бинарный исход.
Например, либо белые выигрывают, либо происходит ничья, либо белые проигрывают партию.
Глядя на произвольные игры, мы получим некую оценку, которую генерирует наша симуляция. Обратите внимание, что ее не следует путать с функцией оценки, например, для поиска альфа-бета.
Там функция оценки оценивает неитоговые позиции игры.
Здесь мы применяем симуляцию случайного воспроизведения, и наш результат оценки основан на результате этого воспроизведения.
Например, для шахмат мы можем закодировать победу/ничью/поражение как (1, 0, −1) или как (1.0,
0.5, 0.0).
При обратном распространении родительские узлы до корневого узла затем обновляются в соответствии со следующей формулой.
Учитывая новую оценку E, среднюю оценку M и количество посещений узла V, обновления определяются как
Рассмотрим, например, рисунок 3.17.
Как и в предыдущем примере, у нас есть выделение и расширение с левой стороны.
Результатом моделирования является оценка 0.1. Родительский узел затем обновляется как
Остаются еще два основных вопроса, о которых вы, вероятно, задаетесь вопросом на данный момент.
Первый: Как определяется операция выбора?
Очевидно, что отбор оказывает огромное влияние на исход MCTS.
Второй: Как только мы закончим поиск MCT, как мы выбираем ход?
Для первого вопроса есть две естественные стратегии:
• Исследование:
Мы должны попытаться посетить все узлы и постараться не искать слишком избирательно. В противном случае мы можем пропустить отличный ход, потому что мы никогда не выделяем и не разворачиваем соответствующий узел.
• Использование:
Если мы определили перспективный узел, мы должны возвращаться к нему и анализировать его как можно чаще, так как это может быть лучшим ходом в данной позиции.
Возвращаясь к этому узлу, мы получаем большую степень уверенности в том, что это действительно хороший шаг.
Эти две стратегии противоречат друг другу по своей природе.
Приведенная ниже формула обозначена как UCT (Upper Confidence bounds applied to Trees) и основана на задаче о многоруком бандите, которая является тщательно анализируемой проблемой в теории вероятностей.
Значение UCT для узла i со средним значением Mi, который был посещен Vi раз, определяется как:
Здесь Vparent — количество посещений родительского узла узла i, а c — небольшое эмпирически выбранное значение смещения.
Всякий раз, когда мы находимся в точке ветвления в дереве, мы вычисляем значение UCT для всех дочерних узлов, а затем выбираем дочерний узел с наибольшим значением UCT.
Мы пропустим математические детали о том, как вывести формулу UCT.
Достаточно сказать, что он обеспечивает баланс между разведкой и эксплуатацией.
Более подробно см. [ACF02], где дается подробный анализ проблемы многорукого бандита.
Возможно, существуют более разумные способы выполнения операции выбора.
Если бы у нас был какой-то оракул, который мог бы дать нам оценку, какие ходы более перспективны в данной позиции, чтобы мы могли сразу направить выбор и расширение узлов в нужном направлении и пропустить бесперспективные узлы.
Как причудливая нейронная сеть, которая может дать нам быструю оценку вероятности выигрыша каждого дочернего узла...
Не вдаваясь в подробности, скажу, что именно эта интуиция лежит в основе большинства нейронных сетей,
которые мы рассмотрим в следующей главе.
Второй открытый вопрос касался того, как выбрать ход после того, как мы закончим поиск MCT.
Существуют различные стратегии.
Мы могли бы выбрать прямого потомка корневого узла с самой высокой средней оценкой.
С другой стороны, UCT обеспечивает нам хорошее соотношение между разведкой и эксплуатацией. Это означает, что если конечный узел выбирается снова и снова, то на этапе выбора уже определен лучший дочерний узел, учитывающее значение UCT, которое в свою очередь основано на M, средней
оценке узла.
Поэтому наиболее распространенной и несколько неинтуитивной стратегией является выбор прямого потомка корневого узла, который посещался чаще всего, т.е. узла с наибольшим значением V.
Теперь мы рассмотрели базовый алгоритм MCTS/UCT.
Давайте немного позабавимся и реализуем это в Python, чтобы создать простую шахматную программу на основе MCTS.
Поскольку он на Python, он будет очень медленным и неэффективным, но простым в реализации.
Более того, он практически иллюстрирует алгоритм и лежащую в его основе концепцию.
...
Основная структура данных здесь представляет собой узел дерева, см.
Листинг 3.8: MCTS - Tree
class TreeNode():
def __init__(self, board):
self.M = 0
self.V = 0
self.visitedMovesAndNodes = []
self.nonVisitedLegalMoves = []
self.board = board
self.parent = None
for m in self.board.legal_moves:
self.nonVisitedLegalMoves.append(m)
def isMCTSLeafNode(self):
return len(self.nonVisitedLegalMoves) != 0
def isTerminalNode(self):
return len(self.nonVisitedLegalMoves) == 0 and len(self.visitedMovesAndNodes) == 0
В узле дерева мы сохраняем текущую оценку в переменной M, а также количество посещений V.
Мы также поддерживаем два списка: один, в котором хранятся все ходы, которые мы уже развернули по крайней мере один раз, и соответствующие дочерние узлы.
В другом списке хранятся все ходы, которые мы еще не развернули, но могли бы развернуть позже.
Тогда тривиально проверить, является ли древовидный узел листовым (если возможны, но неразвернутые ходы это листовой узел) и является ли он конечным узлом (возможных ходов больше нет, потому что, например, это мат).
В листинге 3.9 показаны четыре операции MCTS, т.е. выбор, расширение, симуляция и обратное распространение.
Листинг 3.9: MCTS - Operations1
На этапе выбора мы сначала проверяем, является ли узел листовым.
Если это так, то возвращаем нод — это выбор нашего выбора.
В противном случае мы перебираем все дочерние узлы, вычисляем uct-значение для каждого узла и выбираем тот, у которого наибольшее uct-значение.
На шаге расширения мы удаляем один ход из списка тех ходов, которые мы еще не рассмотрели.
Мы создаем новый дочерний узел и устанавливаем все значения элементов дочернего узла соответственно.
Наконец, мы добавляем перемещение, а также вновь сгенерированный дочерний узел в список узлов, где мы поддерживаем посещенных детей.
Мы возвращаем дочерний узел в качестве развернутого узла.
На этапе моделирования мы продолжаем случайным образом выбирать допустимые ходы текущей позиции на доске и применять их к доске до тех пор, пока игра не закончится победой, ничьей или поражением.
В зависимости от исхода мы возвращаем выплату в размере 1,0 (победа), 0,5 (ничья) или 0 (проигрыш).
На этапе обратного распространения мы обновляем среднюю оценку,а также количество узлов в соответствии с ранее определенной формулой.
Затем мы рекурсивно применяем этот шаг ко всем родительским узлам вплоть до корневого узла.
Мы можем протестировать реализацию с помощью примера с матом, показанного на рисунке 3.1,
r1bqkb1r/pppp1ppp/2n2n2/4p2Q/2B1P3/8/PPPP1PPP/RNB1K1NR w KQkq - 4 4
как показано в листинге 3.10.
Listing 3.10: MCTS - Checkmate
import random
import chess
import math
random.seed(42)
PLAYER = chess.WHITE
OPPONENT = chess.BLACK
class TreeNode():
def __init__(self, board):
self.M = 0
self.V = 0
self.visitedMovesAndNodes = []
self.nonVisitedLegalMoves = []
self.board = board
self.parent = None
for m in self.board.legal_moves:
self.nonVisitedLegalMoves.append(m)
def isMCTSLeafNode(self):
return len(self.nonVisitedLegalMoves) != 0
def isTerminalNode(self):
return len(self.nonVisitedLegalMoves) == 0 and len(self.visitedMovesAndNodes) == 0
def uctValue(node, parent):
val = (node.M/node.V) + 1.4142 * math.sqrt(math.log(parent.V) / node.V)
#print(val)
return val
def select(node):
if(node.isMCTSLeafNode() or node.isTerminalNode()):
return node
else:
#print(node.board)
#print(node.visitedMovesAndNodes)
#print(node.nonVisitedLegalMoves)
maxUctChild = None
maxUctValue = -1000000.
for move, child in node.visitedMovesAndNodes:
uctValChild = uctValue(child, node)
if(uctValChild > maxUctValue):
maxUctChild = child
maxUctValue = uctValChild
if(maxUctChild == None):
raise ValueError("could not identify child with best uct value")
else:
return select(maxUctChild)
def expand(node):
moveToExpand = node.nonVisitedLegalMoves.pop()
board = node.board.copy()
board.push(moveToExpand)
childNode = TreeNode(board)
childNode.parent = node
node.visitedMovesAndNodes.append((moveToExpand, childNode))
return childNode
def simulate(node):
board = node.board.copy()
while(board.outcome(claim_draw = True) == None):
ls = []
for m in board.legal_moves:
ls.append(m)
move = random.choice(ls)
board.push(move)
#print("---------------start-----------")
#print(board)
payout = 0.5
o = board.outcome(claim_draw = True)
#print("winner: " + str(o.winner))
#print()
if(o.winner == PLAYER):
payout = 1
if(o.winner == OPPONENT):
payout = 0.5
if(o.winner == None):
payout = 0
return payout
def backpropagate(node, payout):
#node.M = ((node.M * node.V) + payout) / (node.V + 1)
node.M = node.M + payout
node.V = node.V + 1
# not at the root node yet
if(node.parent != None):
return backpropagate(node.parent, payout)
import chess
board = chess.Board (" r1bqkb1r/pppp1ppp/2n2n2/4p2Q/2B1P3/8/PPPP1PPP/RNB1K1NR w KQkq - 4 4")
root = TreeNode(board)
for i in range (0 ,200):
node = select(root)
# if the selected node is a terminal , we cannot expand
# any child node. in this case , count this as a win/draw/loss
if(not node. isTerminalNode ()):
node = expand(node)
payout = simulate(node)
backpropagate (node , payout)
root. visitedMovesAndNodes .sort(key=lambda x:x[1].V, reverse=True)
print ([ (m.uci (), child.M, child.V) for m, child in root.visitedMovesAndNodes [0:10]])
Сначала мы создаем позицию на доске и корень дерева.
Затем мы применяем ряд итераций MCTS (здесь 200).
Здесь нам нужно убедиться, что мы случайно не попытаемся расширить узлы, которые являются конечными, т.е. там, где закончилась игра.
Например, при взгляде на дочерний узел после применения хода Qxf7, очевидно, что больше нет ходов для расширения. Затем моделирование начинается непосредственно в этом узле.
Сама симуляция тогда просто определяет, что игра находится в финальном состоянии, и немедленно вычисляет выигрыш. После применения MCTS мы смотрим на корневой узел, чтобы определить лучший следующий шаг. Мы сортируем все ходы в соответствии с количеством посещений этого узла.
А как насчет более сложных позиций?
Давайте попробуем мат Легаля, показанную на диаграмме
r2qkbnr/ppp2ppp/2np4/4p2b/4P3/1BN2N1P/PPPP1PP1/R1BQ1RK1 w kq -
Здесь 1.Nxe5 выигрывает пешку, и после 1...Bxd1? 2.Bxf7+ Ke7 3.Nd5++ мат.
Лучший ответ черных после хода 1.Nxe5 - 1...Nxe5, после этого белые отвечают 2.Qxh5 и остаются с лишней пешкой.
r2qkbnr/ppp2ppp/3p4/4n2Q/4P3/1BN4P/PPPP1PP1/R1B2RK1 b kq -
Обратите внимание, что здесь белый слон расположен на b3, в то время как позиция обычно представлена слоном на c4.
Причина в том, что обмен становится немного более глубоким, пока не материализуется преимущество, т.е. нам нужно проверить последовательность глубиной в пять полуходов.
Здесь мы стараемся сократить время поиска.
К сожалению, MCTS не может определить преимущество с 2000 итераций.
Так ли это сложно?
Как насчет поиска альфа-бета. Когда мы применяем наш упрощенный альфа-бета поисковик с getNextMove(5, board, True)), правильный ход Nxe5
обнаруживается с оценкой 280.
(Move.from_uci('f3e5'), 280)
2121700
[Finished in 2425.0s]
Почему MCTS здесь не работает?
Первая проблема заключается в том, что после игры в Nxe5 мы замечаем, что это, казалось бы, очень плохой ход.
Если мы проводим случайные игры с этой позиции, и черные захватывают белого ферзя, то остается только одна очень специфическая комбинация, которая позволяет белым выиграть игру.
Чтобы обнаружить это, а также убедиться в том, что шаг выбора движется в правильном направлении вдоль этой последовательности ходов, нам нужно много итераций.
Всего несколько случайных розыгрышей не подхватят эту последовательность ходов и, вероятно, закончатся в пользу черных, особенно если ферзь захвачен, а белые не ответят соответственно.
Это особенность шахмат, где часто встречаются весьма специфические тактики, которые намного перевешивают любые позиционные аспекты.
Это отличается от других игр, таких как Го, например.
Вторая проблема заключается в том, что нам нужно много матчей подряд.
Однако генерация ходов в шахматах требует значительных вычислительных затрат. Шахматные ходы кажутся интуитивно понятными для опытного игрока, но правила на самом деле довольно сложны:
• в игре много разных фигур, и у каждой свои правила
• ход фигур может быть запрещен, если это ставит под удар собственного короля
• конь может перепрыгивать через другие фигуры, в то время как другие фигуры не могут
• у пешек невероятно сложные правила. Они могут переместить два поля в исходное положение, но только одно поле в противном случае. За исключением случаев захвата. И прохождения. А затем, когда они достигают последнего ряда, они становятся другой фигурой
• рокировка - это особый ход, при котором две фигуры перемещаются одновременно.
Перед рокировкой и после ее выполнения необходимо выполнить несколько сложных условий.
Все это должно быть вычислено, и быстрая генерация ходов на самом деле очень важна при создании мощных шахматных движков. В дополнение к вышеупомянутым проблемам , Python — очень медленный язык, в нем простота программирования сочетается соскоростью выполнения. Вот почему примеры движков, показанные в этой книге, работают так медленно.
Если мы сравним это с игрой Го, то увидим, что существует только один вид фигур - камень. Ход заключается в размещении этого камня на свободном кресте на доске.
Тем не менее, выполнение всех допустимых ходов может быть сложным.
Тем не менее, MCTS, по-видимому, является единственным выбором для Go, поскольку на практике для альфа-бета-поиска слишком много азветвлений.
Все это сильно влияет на количество симуляций, которые мы можем сделать за определенный промежуток времени.
И именно поэтому учебник MCTS в том виде, в котором он представлен здесь, на самом деле довольно плохой выбор для компьютерных шахмат. Конечно, есть исключения из этого правила.
Мы вернемся к этому в следующей главе.
3.6 Резюме
Давайте быстро подведем итоги: Alpha-Beta — это мощный алгоритм поиска игровых деревьев. Его недостаток заключается в том, что для выполнения
функции оценки требуются знания, специфичные для предметной области. Кроме того, фактор ветвления игры не должен быть слишком большим — в крайнем случае, альфа-бета будет искать только один уровень вглубь и, по сути, сведется к прямому применению функции оценки только один раз. Monte-Carlo Tree Search не зависит от предметной области и может быть применен к любой детерминированной игре для двух игроков.
Если работают и альфа-бета, и MCTS, обычно альфа-бета более точна и быстра.
Но для игр с очень высоким коэффициентом ветвления и/или отсутствием хорошей функции оценки, MCTS может стать мощной альтернативой альфа-бета-поиску.
Если говорить о независимости домена — это фича или проклятие?
С точки зрения шахмат, мы могли бы использовать много знаний в предметной области. В конце концов, для компьютера гораздо проще оценить позицию в шахматах по сравнению, скажем, с Го.
Что касается хронологии MCTS: Брюгманн [Brü93] впервые применил технологии Монте-Карло, т.е. случайные розыгрыши, к игре Го.
Затем Кулом [Cou06] применил методы Монте-Карло к поиску по дереву и объединил их.
Наконец, Kocsiset al. [KS06] установил связь с проблемой многоруких бандитов и дал определение UCT.
Если вы хотите, чтобы что-то было сделано
хорошо, сделайте это сами!
Харуко Обоката
Для того, чтобы получить интуицию и лучше понять, как работает AlphaZero на практике, стоит реализовать его самостоятельно.
Однако, как мы уже выяснили, обучение соревновательной сети для игры в шахматы требует огромных вычислительных ресурсов, и предполагается, что у вас в подвале нет маленького дата-центра.
Поэтому мы рассмотрим гораздо более простую игру.
Часто для таких экспериментов используют TicTac Toe, но пока он прост, к сожалению, не имеет даже отдаленного сходства с шахматами.
Самая простая игра, которая чем-то похожа на шахматы, вероятно, Hexapawn.It была придумана научно-популярным писателем Мартином Гарднером в 1962 году для демонстрации простых игровых механик и игровых деревьев.
Правила очень просты: в Hexapawn играют на доске 3x3. Каждая сторона имеет по три пешки в первом и третьем рядах соответственно, как показано на рисунке 5.1.
Пешки ходят как обычно, за исключением того, что они не ходят на два шага в начале — и, очевидно, здесь нет en-passent.
Игрок выигрывает, если он может сделать пешку ферзем.
Тут нет патовой ситуации или ничьей:Если настала очередь игрока и у него нет хода, то он проигрывает игру.
Hexapawn – это решенная игра, т.е. мы знаем для каждой позиции, кто выиграет, если он играет оптимально.
На самом деле, нетрудно убедиться, что черные всегда выиграют партию, если будут играть по оптимальной стратегии: Прим. кому интересно найдите стратегию сами
Другими словами, эта игра крайне тривиальна в решении и отлично подходит для наших экспериментов.
В этом разделе мы спроектируем нейронную сеть, похожую на AlphaZero.
Он будет принимать состояния доски в качестве входных параметров и на выходе будет вероятности ходов, которые указывают, насколько
хороши ходы или какой ход должен быть сыгран, а также значение, которое выводит вероятный исход игры от текущего состояния.
Мы будем обучать эту сеть с помощью двух разных подходов и сравнивать их.
Сначала мы будем использовать контролируемое обучение, т.е. будем генерировать обучающие данные. Эти обучающие данные состоят из позиций,
оптимального хода в данной позиции и (рассчитанного) исхода игры в этой позиции — обратите внимание, что такой исход известен.
Во-вторых, мы будем применять подход, подобный "Зеро". То есть мы реализуем обучающий цикл AlphaZero с помощью Monte Carlo Tree Search в сочетании с самостоятельной игрой и обучением с подкреплением.
Мы проверим эффективность нашей тренировки, сравнив силу тренируемой контролируемой и «нулевой» сети против соперника, который делает только случайные ходы.
Хорошо обученная сеть, играющая черными, должна обыгрывать такого соперника в подавляющем большинстве всех случаев.
Начнем с сетевой архитектуры, т.е. самой сети, а также с ввода и вывода сетевой работы.
...
предполагается, что у вас в подвале нет маленького дата-центра.
Я сначала тоже так подумал
Ан нет, я был не прав!
У всех, у кого есть аккаунт Гугл, есть такой дата-центр - Google Colab.
Google Colab (Google Colaboratory) — это бесплатный облачный сервис для программирования на Python.
Google Colab удобен тем, что обеспечивает гибкую настройку конфигурации для каждого проекта. По умолчанию всем пользователям доступен виртуальный процессор Intel Xeon и 13 ГБ оперативной памяти. Для ускорения вычислений Colab открывает доступ к графическим процессорам (GPU) — обычно это NVIDIA Tesla K80, T4 или P100 с видеопамятью до 16 ГБ. Также доступны тензорные процессоры (TPU) для работы с нейросетями, однако они совместимы только с определёнными версиями TensorFlow.
А почему бы не воспользоваться этим маленьким дата-центром
Короче, я им воспользовался
Warning: Spoiler![ Click to expand ][ Click to hide ]
