? AI для игры Threes!. ?

Репозиторий GitHub:Halfrost-Field

Follow: полурост · GitHub

Source: GitHub.com/HAL мороз/dayhou…

источник вдохновения

Месяц назад я участвовал в соревновании по искусственному интеллекту с двумя другими друзьями. Хотя результаты конкурса не были идеальными, по крайней мере, я получил удовольствие от процесса программирования. Из этого конкурса я понял, что Go хорош не только в написании серверов, написании игровых симуляторов и написании ИИ. В последнее время поддержка WeChat Jump и Jump, а также поддержка конференции на высшем уровне в основном написаны на Go. Так что я больше не мог сидеть на месте и написал одну в память о нашей игре.

Поскольку я тоже клиент, этот ИИ также должен иметь возможность набирать очки на мобильных телефонах. Итак, ищем мобильную игру, в которую могут играть трое или со словом «три» в названии, вот:

Threes preson join one AI competition ---> Threes-AI

"Показные" баллы

В настоящее время эта версия ИИ для Go имеет точки запуска в 3 местах, и в каждом из них было проведено 200 игр. Процент получения высокого балла составляет около 20%. Поэтому я также надеюсь, что на втором этапе проекта, этапе машинного обучения, скорость достижения высоких результатов может быть увеличена до 100%.

1. играйте в тройки на официальном сайте

Этот сайт является веб-версией официальной игры.

Видео рекордов здесь,Ссылка на видео Тенсент

2. тройка Android-клиент

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

3. веб-сайт, созданный самостоятельно

Чтобы обучить модель с помощью машинного обучения и публично продемонстрировать силу этого ИИ, согласно официальным правилам игры, веб-версия была перегравирована в первоначальный вид.

Видео рекордов здесь,Ссылка на видео Тенсент

В интернете ходит такой "слух": когда будет синтезировано 12288 кирпичей, то есть будет объединено 2 6144 кирпича, игра завершится и будет разыгран список производителей игр. На этом сайте такого правила нет, и кирпичи можно делать как можно выше. Оценки не отображаются онлайн, чтобы можно было полностью проверить мудрость ИИ.

Конечно, для первых 2-х официальных игровых адресов автор ни разу не синтезировал 12288 кирпичей, поэтому проверить достоверность "слуха" невозможно. 100% синтез 12288 кирпичей также является целью этого ИИ.цель еще не достигнута.

метод запуска

1. веб-сайт, созданный самостоятельно

Docker


// 先把 go 服务端跑起来，端口是 9000
docker container run --rm -p 9000:9000 -it halfrost/threes-ai:go-0.0.1

// 再把 web 前端跑起来，http://127.0.0.1:9888
docker container run --rm -p 9888:9888 -it halfrost/threes-ai:web-0.0.1

Local

Локальная сборка немного более хлопотная, и она также выполняется в два этапа: сначала создается сервер go, а затем — веб.

Сначала создайте сервер go:


// 回到项目主目录
cd threes-ai
go run main.go

Приведенная выше команда создаст сервер go, и сервер будет прослушивать информацию с порта 9000.

Создайте сеть снова:

Поскольку проект основан на метеоре, сначала настройте локальную среду метеора и установите метеор.Ручная ссылка


// 进入 threes! web 主目录
cd threes-ai/threes!
meteor

Вышеупомянутая команда запустит веб на http://localhost:3000.

Сюда уже подбежал местный.

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

Сначала упакуйте сервер go.Поскольку докер внутри Linux, обратите внимание на кросс-компиляцию при упаковке, иначе конечный докер не может быть выполнен. Для конкретных шагов по упаковке, пожалуйста, обратитесь к шагам в файле Dockerfile_go.


docker image build -t threes_go:0.0.1 .
docker container run --rm -p 9000:9000 -it threes_go:0.0.1

Переупаковать веб:


cd threes-ai/threes!
meteor build ./dist

После выполнения вышеуказанной команды в текущем каталоге будет создана папка dist, и она будет содержатьthrees!.tar.gzАрхив. Разархивируйте этот сжатый пакет, вы получите пакетный файл, этот файл нам нужен для развертывания.

В настоящее время вы также можете запускать сеть этой производственной среды локально. Используйте следующую команду:


cd dist/bundle
ROOT_URL=http://127.0.0.1 PORT=9888 node main.js

В это время Интернет также будет работать по адресу http://127.0.0.1:9888. Обратите внимание, что версия узла должна быть 8.9.4. Требования к версии для узла — это требования к версии для метеора. метеор 1.6 соответствует узлу 8.9.4. Автор также ограничил информацию о версии узла в файле .nvmrc. Ближе к дому, вернемся к вопросу упаковки образов веб-докеров.

После этого просмотрите шаги в файле Dockerfile_web, чтобы узнать, как упаковать его в образ Docker.


docker image build -t threes_web:0.0.1 .
docker container run --rm -p 9888:9888 -it threes_web:0.0.1

Сначала запустите образ docker сервера go, а затем запустите образ docker сети.

2. играйте в тройки на официальном сайте

Первый шаг — упаковать программу go в динамическую библиотеку, которую удобно вызывать python.


go build -buildmode=c-shared -o threes.so main.go

Приведенные выше пакеты команд входят в динамическую библиотеку threes.so.

Затем вам нужно использовать режим удаленной отладки Chrome, чтобы установить соединение ws.threes_ai_web.pyЧто он делает, так это передает цифровую информацию о шахматной доске в сеть, чтобы идти.После того, как функция перехода обработана, она возвращается к направлению, в котором нужно двигаться на следующем шаге. Наконец, вернитесь на веб-страницу через ws, чтобы имитировать движение.


sudo /Applications/Google\ Chrome.app/Contents/MacOS/Google\ Chrome --remote-debugging-port=9162

python threes_ai_web.py -b chrome -p 9162

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


已在现有的浏览器会话中创建新的窗口。
[29819:45571:0225/225036.004108:ERROR:browser_gpu_channel_host_factory.cc(121)] Failed to launch GPU process.

Столкнувшись с вышеуказанной ошибкой, полностью закройте Chrome, а затем выполните--remote-debugging-port=9162Вот и все. Обычно устанавливается новое соединение через веб-сокет, например:


DevTools listening on ws://127.0.0.1:9162/devtools/browser/86c6deb3-3fc1-4833-98ab-0177ec50f1fa

threes_ai_web.pyС этим скриптом все еще есть некоторые проблемы, иногда ошибки приводят к прерыванию соединения ws. Это будет отредактировано позже и опубликовано.

3. FAQ

1. Образ halfrost/three-ai:web-0.0.1 имеет версию 0.0.2, почему в приведенной выше команде используется версия 0.0.1?

Эта проблема связана с проблемой сервера развертывания. В текущем исходном кодеthrees-ai/threes!/client/js/game.jsВ строке 367 порт в версии 0.0.1 — 9000, а в версии 0.0.2 — 8999.

Почему существует разница в номере порта между двумя версиями? Из-за ssl. Развертывание на сервере осуществляется по протоколу https, поэтому ws становится соединением wss. Неважно, работает ли он локально, в любом случае это локальный хост или 127.0.0.1, оба из которых являются http. Поскольку на стороне сервера необходимо добавить ssl, необходимо использовать nginx для добавления слоя обратного прокси для поддержки wss. Nginx прослушивает порт 8999 веб-сервера и перенаправляет его на порт 9000 сервера после добавления ssl. Это завершает взаимодействие wss между web и go. Если вы запускаете его локально, вам не нужно быть таким хлопотным, просто используйте порт 9000. Веб-сервер напрямую подключается к порту 9000 сервера go через порт 9000 для связи ws.

2. В процессе развертывания сервера произошла ошибка`WebSocket connection to 'wss://XXXX' failed: Error in connection establishment: net::ERR_CONNECTION_REFUSED`ошибка, как решить?

Вышеупомянутая ошибка CONNECTION_REFUSED обычно возникает по следующим трем причинам:

1. Возможно, сервер iptables блокирует порт
2. IP или порт могут быть неправильными или протокол не поддерживается
3. Сервер не запущен

Вышеупомянутая проблема возникла при развертывании автором.Во-первых, с помощью обнаружения iptables было обнаружено, что проблемы нет. Вторая возможность заключается в том, что wss не поддерживается, а порт определяется командой openssl:


openssl s_client [-connect host:port>] [-verify depth] [-cert filename] [-key filename] 
 [-CApath directory] [-CAfile filename][-reconnect] [-pause] [-showcerts] [-debug] [-msg] 
 [-nbio_test] [-state] [-nbio] [-crlf] [-ign_eof] [-quiet]

Путем обнаружения было обнаружено, что порт не поддерживает ssl, поэтому добавление слоя ssl под прокси nginx решило указанную выше проблему.

Анализ игры

Трудность с Тройками в том, что этодолжен проигратьигра. Когда игра доходит до второй половины, после синтеза 6144, положение кирпича нельзя перемещать большую часть времени, что эквивалентно 4 * 4 = 16 сеткам минус одна для него. Кирпичи на поле не могут быть объединены все сразу на более позднем этапе, поэтому остается очень мало места.Часто из-за того, что оборот не может быть открыт или 1 или 2 идут подряд, его нельзя синтезировать в 3, и это "зажали" заживо.

В процессе проектирования веб-версии мы не учитывали режим «перескакивания уровней», как у клиента, то есть появляющиеся кирпичи могут появляться кратно 3, например 3, 6, 12, 24, 96, 192. , 384... Это большое количество кирпичей. Так что игровой процесс на веб-версии может быть немного проще, чем на клиенте.

Почему будет проще? Потому что хотя больших кирпичей не будет (большие кирпичи имеют высокий балл), время игры будет больше, но и выживаемость тоже немного выше. Если он выпадает последовательно, 96, 384, 768, все приходят по отдельности, из-за чего на шахматной доске появляется много несочетаемых кубиков.Хотя счет будет стремительно расти, он также не сможет двигаться, потому что его нельзя комбинировать. игра быстро.

В клиенте есть настройка «уровня перехода», и эти кирпичи могут появляться в течение определенного периода времени. Я также обнаружил эту проблему при тестировании ИИ.Шанс быть принужденным к смерти от одной 1 или одной 2 подряд невелик, но есть много случаев принуждения к смерти от больших кирпичей с большим количеством очков, что приводит к долгому времени выживания.Долго, и оценка не так высока, как веб-версия.

В игровой схеме действительно есть хитрости.

Раскладка игры монотонна, так как оптимальную раскладку смотрите на следующих двух картинках:

Видно, что компоновка этих двух изображений является наилучшей, потому что соседние кирпичи могут продолжать синтезироваться на более высоком уровне после синтеза, так что скорость синтеза также самая высокая. Может добиться самого быстрого устранения кирпичей на доске. Если раскладка не строится на такой монотонности, то часто из-за хаотичности самой раскладки некоторые кирпичики не могут быть синтезированы, и в конце концов они «принуждаются к смерти» сами по себе.

Алгоритмическое мышление

Это репо реализовано с Expectimax Search.Конечно, есть и другие решения этой проблемы.Здесь также упоминаются идеи алгоритмов.Соответствующие алгоритмы - это алгоритм два и алгоритм три, но они реализованы без кода.

1. Деревья поиска Expectimax

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

1. Вытягивая покерную карту, вы никогда не знаете, какая карта будет вытянута следующей.Как получение этой неизвестной карты повлияет на игру?
1. В игре "Сапер" в любое время щелкните по квадрату. Это может быть мина или число. Случайное положение мины будет напрямую влиять на то, будет ли раунд прямо над игрой.
1. В игре Pac-Man местоположение призрака появляется случайным образом, что напрямую приводит к следующему планированию маршрута.
1. Тройки! В игре блоки 1 и 2 появляются случайным образом, что влияет на то, как мы перемещаем блоки.

Все вышеперечисленные ситуации можно решить с помощью Expectimax Search Trees. Эти типы вопросов связаны с поиском максимального значения (оценки). Основная идея заключается в следующем:

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

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

1. Некоторые особенности максимального ожидаемого значения Expectimax

Другие узлы не являются враждебными узлами и не находятся под нашим контролем. Причина в их неизвестной природе. Мы не знаем, что вызывают эти узлы.

Каждое состояние также имеет максимальное ожидаемое значение. Мы также не можем слепо выбрать максимальное ожидаемое значение expectimax, потому что оно не является на 100% безопасным и может привести к тому, что все наше дерево «освободится».

Узлы возможности управляются средневзвешенной вероятностью, а не слепым выбором минимального значения.

2. Об обрезке

В expectimax нет концепции обрезки.

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

3. Функция вероятности

В Expectimax Search у нас есть вероятностная модель поведения противника в любом состоянии. Эта модель может представлять собой простое равномерное распределение (например, бросание игральной кости) или сложную, требующую большого количества вычислений для получения вероятности.

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

Пример: расчет времени до аэропорта. Вес багажа повлияет на время в пути.


L（无）= 20，L（轻）= 30，L（重）= 60

В трех случаях распределение вероятностей таково:


P（T）= {none：0.25，light：0.5，heavy：0.25}

Затем расчетное время вождения записывается как


E [L（T）] =  L（无）* P（无）+ L（轻）* P（轻）+ L（重）* P (重)
E [L（T）] =  20 * 0.25）+（30 * 0.5）+（60 * 0.25）= 35

4. Математическая теория

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

Важно отметить, что ожидания не обязательно совпадают с «ожиданиями» в обычном смысле — «ожидания» могут не совпадать с каждым результатом. Ожидаемое значение — это среднее значение выходных значений для этой переменной. Ожидаемое значение не обязательно включается в набор выходных значений переменной.

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

5. Конкретный

О конкретных идеях поговорим ниже.

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

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

Следующий кирпич 2 . Так где он появится? Всего 16 дел.

Если вы переместите операцию ВВЕРХ, 2 кирпича появятся в 4 разных позициях. Если вы переместите операцию ВНИЗ вниз, есть 4 вида позиций, в которых появляются 2 кирпича. Если вы переместите ВЛЕВО влево, 2 кирпича появятся в 4 разных позициях. Если вы переместите ВПРАВО вправо, 2 кирпича появятся в 4 разных позициях.

Получив эти 16 случаев, продолжайте рекурсию вниз. Рекурсивная формула выглядит следующим образом:

Приведенная выше формула предназначена для непрерывного расчета ожидаемого значения.

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

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

Приведенная выше формула является формулой расчета ожидаемого значения при условии рекурсивной сходимости.

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

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

Однако в реальном рекурсивном процессе могут возникнуть следующие ситуации:

Большая площадь пустого пространства требует много рекурсии, что косвенно приводит к большому объему вычислений и большему времени ИИ, чтобы один раз подумать. Решение этой проблемы заключается в ограничении глубины рекурсии.

Используйте выборочную дисперсию, чтобы оценить среднее значение:

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

Reference:

[1]:ExpectimaxSearch

[2]:What is the optimal algorithm for the game 2048?

[3]:2048 ИИ – интеллектуальный бот

2. Минимаксный поиск Минимаксный поиск

Теория минимакса (minimax), предложенная фон Нейманом в 1928 году, проложила путь для состязательных методов поиска по дереву, которые стали основой теории принятия решений на заре информатики и искусственного интеллекта.

Подробнее см. в следующем репо:

GitHub.com/day от охотника/…

3. Поиск по дереву Монте-Карло

Методы Монте-Карло решают задачи путем случайной выборки, а впоследствии, в 1940-х годах, как способ решения нечетко определенных задач, непригодных для прямого поиска по дереву. Реми Кулон объединил эти два метода в 2006 году, чтобы предоставить новый метод планирования ходов в Go, известный сегодня как поиск по дереву Монте-Карло (MCTS). Теоретически MCTS можно применять к любой области, которую можно описать в виде {состояние, действие}, а результат можно предсказать с помощью моделирования.

Монте-Карло — это метод решения задач обучения с подкреплением, основанный на средней доходности выборки. AlphaGo использует поиск по дереву Монте-Карло, чтобы быстро оценить значение позиции доски. Мы также можем использовать этот метод для оценки вероятности того, что текущий ход Тройки наберет наибольшее количество очков.

Доска для го состоит из 19 линий по горизонтали и вертикали, а общее количество ходов равно 361. Две стороны делают ходы попеременно, а это означает, что всего в го может быть 10^171 (171 ноль после 1) возможностей. Это превышает общее количество атомов во Вселенной, равное 10^80 (1 с последующими 80 нулями)!

Традиционный ИИ обычно использует метод поиска методом перебора (это то, что делает Deep Blue) и строит дерево для всех возможных методов. Из-за огромного пространства состояний невозможно перечислить все состояния методом полного перебора.

Поиск по дереву Монте-Карло можно условно разделить на четыре этапа. Выбор, Расширение, Моделирование, Обратное распространение.

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

Выбор: начните с корня R и выберите последовательных дочерних элементов до листовых узлов L. В следующем разделе объясняется больше о способе выбора дочерних элементов, чтобы позволить игровому дереву расшириться до наиболее многообещающего хода, что является сущностью поиска по дереву Монте-Карло.

Расширение: если L не заканчивает игру беспроигрышной для любой из сторон, создайте один (или несколько) дочерних узлов и выберите из них узел C.

Моделирование: воспроизведение в случайном порядке с узла C. Этот шаг также иногда называют воспроизведением или развертыванием.

Обратное распространение: используйте результаты воспроизведения для обновления информации в узлах на пути от C к R.

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

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

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

Отсюда мы можем видеть, что поиск по дереву Монте-Карло - это эвристическая стратегия поиска, которая использует частоту для оценки вероятности, Когда частота выборок собрана достаточно, частота приближается к вероятности. Это эквивалентно случайному подбрасыванию монеты: пока количество подбрасываний достаточно, частота выпадения орла будет бесконечно близка к 0,5.

Reference:

[1]:Browne C B, Powley E, Whitehouse D, et al. A Survey of Monte Carlo Tree Search Methods[J]. IEEE Transactions on Computational Intelligence & Ai in Games, 2012, 4:1(1):1-43.

[2]: П. Ауэр, Н. Чеза-Бьянки, П. Фишер, "Конечный анализ проблемы многорукого бандита", Mach.Learn., т. 47, № 2, стр. 235–256, 2002.

To-Do

Я думал, что этот проект так и закончится, но после того, как Али выпустил «Желтую книгу» в последние дни, я вдруг почувствовал, что у меня появилась новая идея, и решил продолжить использовать обучение с подкреплением, чтобы закончить второе издание. Надеюсь, что более умный ИИ сможет на 100% выполнить высшее достижение 12288. После завершения обучения я вернусь и продолжу доделывать следующую статью.