Написание программы для воспроизведения Google Semantris

Автоматика - это хорошо, если вы точно знаете, где поставить машину. - Элиягу Голдратт

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

В игре доступно 2 режима.

АРКАДА

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

БЛОКИ

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

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

Оказывается, это может быть

Semantris-Solver использует следующую процедуру для игры:

  • Сохраняйте текущее состояние игры с помощью методов компьютерного зрения
  • Определите слово, которое нужно ввести, чтобы получить более высокую награду / более длительный игровой процесс
  • Найдите связанное слово с помощью встраивания слов

В следующих разделах мы собираемся погрузиться в работу Semantris-Solver для обоих режимов игры.

АРКАДА

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

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

Кроме того, в аркадном режиме есть три типа цветов темы.

Вы поймете, что цвет темы здесь не играет никакой роли - игровой механизм останется прежним, если мы изменим цвет темы. Что меняется, так это определение выделенного слова.

Слово выделяется, если слева от него есть указатель (▶ Корабль).

Преобразование цветового пространства

Режим ARCADE программы Semantris-Solver начинается со снятия снимка экрана с экрана ноутбука и его преобразования в полутоновое изображение, независимо от фактического цвета.

Соответствие шаблонов

Нашим следующим шагом будет поиск выделенного слова на захваченном изображении. OpenCV предоставляет метод под названием Соответствие шаблонов для поиска и определения местоположения изображения шаблона на большом изображении.

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

Оптическое распознавание символов (OCR)

В зависимости от положения указателя рядом с ним обрезается раздел с выделенным словом.

Обрезанное изображение преобразуется в текст с помощью Tesseract OCR; в этом случае мы получим Корабль.

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

Выделение связанного слова (с использованием вложений слов)

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

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

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

БЛОКИ

В этом режиме есть блоки слов с четырьмя возможными цветами для данной темы. Блоки слов могут содержать или не содержать слово.

Ввод связанного слова для блока слов удалит связанные с ним блоки такого же цвета, как старый добрый Тетрис.

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

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

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

Кроме того, в режиме блоков есть три типа цветов темы.

Генерация цветовой палитры

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

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

Обнаружение контура

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

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

Контур - это кривая, соединяющая все непрерывные точки вдоль границы, имеющая одинаковый цвет или интенсивность.

Группу блоков слов можно рассматривать как контур этого цвета; если он связан с несколькими блоками одного цвета, площадь контура будет суммой связанных блоков слов.

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

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

Обнаружение слов (с использованием Tesseract и Word2Vec)

Контурное изображение преобразуется в текст с помощью Tesseract OCR; в этом случае он предоставит нам Сад.

Подобно аркадному режиму, мы будем использовать Word2Vec, чтобы найти наиболее похожее на него слово, на этот раз это будет Цветочные клумбы.

Улучшения

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

Например, для этого контура будет возвращено «Eloctrlclty» вместо «Электричество».

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

Здесь может помочь модель коррекции орфографии, в которой Eloctrlclty заменяется на Электричество.

Я создал проблему в репозитории GitHub для того же самого, не стесняйтесь вносить свой вклад, если хотите. 😄

Исходный код

Семантрис-Решатель (GitHub)

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

Зависимости

Было невозможно построить Semantris-Solver без следующих программных инструментов.

  • OpenCV
  • Word2Vec (gensim)
  • pyautogui (создание снимка экрана и ввод связанных слов)
  • Тессеракт (OCR)

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

Следуйте за мной в Twitter Правендра Сингх или посетите мой личный сайт hackpravj.com.