Ball Sort Puzzle — это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.

Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался — насколько бы глубоко я ни пытался продумать свою стратегию. В итоге — с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.

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

Ну это ни в какие ворота — против нас играет коварный ИИ. Нужно действовать соответственно!

Под катом мы:

• Придумаем алгоритм, решающий эту головоломку (Python)

• Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)

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

• Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции

Погнали!

Алгоритмическое решение задачи

Решать такую задачу было весьма занимательно. Поэтому предлагаю заинтересованному читателю попробовать решить её самостоятельно.

Я же в первую очередь решил побить проблему на сущности. Это сделает алгоритм чуть более элегантным, а также поможет в будущем парсить скриншоты игры:

class Color

class Color:
    def __init__(self, symbol, verbose_name, emoji):
        self.symbol = symbol
        self.verbose_name = verbose_name
        self.emoji = emoji

    def __repr__(self) -> str:
        return f'Color({self})'

    def __str__(self) -> str:
        return self.emoji

class Ball:
    def __init__(self, color: Color):
        self.color = color

    def __eq__(self, other: 'Ball'):
        return self.color is other.color

    def __repr__(self):
        return f'Ball({self.color.verbose_name})'

    def __str__(self) -> str:
        return str(self.color)

class Flask:
    def __init__(self, column: List[Color], num: int, max_size: int):
        self.num = num
        self.balls = [Ball(color) for color in column]
        self.max_size = max_size

    @property
    def is_full(self):
        return len(self.balls) == self.max_size

    @property
    def is_empty(self) -> bool:
        return not self.balls

    def pop(self) -> Ball:
        return self.balls.pop(-1)

    def push(self, ball: Ball):
        self.balls.append(ball)

    def __iter__(self):
        return iter(self.balls)

    def __getitem__(self, item: int) -> Ball:
        return self.balls[item]

    def __len__(self) -> int:
        return len(self.balls)

    def __str__(self) -> str:
        return str(self.balls)

class Move:
    def __init__(self, i, j, i_color: Color):
        self.i = i
        self.j = j
        self.emoji = i_color.emoji

    def __eq__(self, other: 'Move') -> bool:
        return (self.i, self.j) == (other.i, other.j)

    def __repr__(self) -> str:
        return f'Ball({self})'

    def __str__(self) -> str:
        return f'{self.i} -> {self.j}'

Для решения будем использовать метод поиска с возвратом (Backtracking).

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

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

• Либо нас не выкинет наш критерий остановки — решённый пазл

• Либо в нашем хранилище состояний (states) не будет всех возможных перестановок — в таком случае решения нет

    def solve(self) -> bool:
        if self.is_solved:
            return True

        for move in self.get_possible_moves():
            new_state = self.commit_move(move)
            if new_state in self.states:  # Cycle!
                self.rollback_move(move)
                continue

            self.states.add(new_state)
            if self.solve():
                return True
            self.rollback_move(move)

        return False

Алгоритм достаточно прямолинейный и далеко не всегда выдаёт оптимальное решение. Тем не менее он справляется с решением большинства задачек из игры за 1 сек.

Проверим алгоритм на чём-нибудь попроще:

def test_3x3():
    data_in = [
        [color.RED, color.GREEN, color.RED],
        [color.GREEN, color.RED, color.GREEN],
        [],
    ]

    puzzle = BallSortPuzzle(data_in)
    result = puzzle.solve()
    assert result is True
    play_moves(data_in, puzzle.moves)

Полная версия программы доступна на github.

Распознавание скриншотов игры

Мы будем работать с .jpg картинками двух видов

Каждый чётный раунд игры состоит из 11 колб и 36 шариков, а нечётный — 14 колб и 48 шариков. Чётные и нечётные раунды отличаются расположением колб, но на счастье всё остальное у них одинаковое — по 4 шарика в колбе, 2 колбы пустые, цвета используются одни и те же.

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

class ImageParser:
    def __init__(self, file_bytes: np.ndarray, debug=False):
        self.image_orig = cv2.imdecode(file_bytes, cv2.IMREAD_COLOR)
        self.image_cropped = self.get_cropped_image(self.image_orig)

    @staticmethod
    def get_cropped_image(image):
        height, width, _ = image.shape
        quarter = int(height / 4)
        cropped_img = image[quarter : height - quarter]
        return cropped_img

Теперь будем искать кружочки. В библиотеке OpenCV ровно для этих целей существует метод HoughCircles. Чтобы его использовать нужно перевести изображение в чёрно-белый вид, а также "эмпирически подобрать" параметры поиска. Чтобы найденные кружочки потом расфасовать по колбам, нормализуем и отсортируем их.

    @staticmethod
    def normalize_circles(circles):
        last_y = 0
        for circle in circles:
            if math.isclose(circle[1], last_y, abs_tol=3):
                circle[1] = last_y
            else:
                last_y = circle[1]
        return circles

    def get_normalized_circles(self) -> List[Any]:
        image_cropped_gray = cv2.cvtColor(self.image_cropped, cv2.COLOR_BGR2GRAY)
        circles = cv2.HoughCircles(image_cropped_gray, cv2.HOUGH_GRADIENT, 2, 20, maxRadius=27)
        if circles is None:
            raise ImageParserError("No circles :shrug:")

        circles = np.round(circles[0, :]).astype("int16")
        ind = np.lexsort((circles[:, 0], circles[:, 1]))
        circles = circles[ind]
        circles = self.normalize_circles(circles)
        ind = np.lexsort((circles[:, 0], circles[:, 1]))
        circles = circles[ind]
        return circles

Дальше будем определять цвет шарика.

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

    @staticmethod
    def get_dominant_color(circle) -> Color:
        colors, count = np.unique(circle.reshape(-1, circle.shape[-1]), axis=0, return_counts=True)
        dominant = colors[count.argmax()]
        return dominant

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

Посчитаем такое расстояние до каждого из изначально заданных цветов и найдём минимальное

RBG_TO_COLOR = {
    (147, 42, 115): VIOLET,
    (8, 74, 125): BROWN,
    (229, 163, 85): L_BLUE,
    (68, 140, 234): ORANGE,
    (196, 46, 59): BLUE,
    (51, 100, 18): GREEN,
    (35, 43, 197): RED,
    (87, 216, 241): YELLOW,
    (125, 214, 97): L_GREEN,
    (123, 94, 234): PINK,
    (16, 150, 120): LIME,
    (102, 100, 99): GRAY,
}
COLORS = np.array(list(RBG_TO_COLOR.keys()))

def get_closest_color(color: np.ndarray) -> Color:
    distances = np.sqrt(np.sum((COLORS - color) ** 2, axis=1))
    index_of_smallest = np.where(distances == np.amin(distances))
    smallest_distance = COLORS[index_of_smallest].flat
    return RBG_TO_COLOR[tuple(smallest_distance)]  # type: ignore

Далее нам остаётся только распределить шарики по колбам. Итоговый class ImageParser доступен на github.

Преобразуем программу в Telegram Bot

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

Так как наш бот хоститься на Яндекс.Функции — триггером к его запуску будет запрос на заданный нами webhook.

Whenever there is an update for the bot, we will send an HTTPS POST request to the specified url, containing a JSON-serialized Update.

Если в сообщении есть массив photo, то можно увеличить вероятность распознавания шариков выбрав фотографию с максимальным весом:

if photos := message.get('photo'):
    # here photos is an array with same photo of different sizes
    # get one with the highest resolution
    hd_photo = max(photos, key=lambda x: x['file_size'])

Чтобы скачать картинку, придётся сделать 2 запроса к Telegram API

# Получение данных о файле, нас интересует ключ ответа file_path
GET https://api.telegram.org/bot{BOT_TOKEN}/getFile?file_id={file_id}
# Получение самого файла
GET https://api.telegram.org/file/bot{BOT_TOKEN}/{file_path}

В остальном же всё просто — получаем картинку, скармливаем её парсеру и затем алгоритму-решателю.

def handler(event: Optional[dict], context: Optional[dict]):
    body = json.loads(event['body'])  # type: ignore
    print(body)
    message = body['message']
    chat_id = message['chat']['id']

    if photos := message.get('photo'):
        # here photos is an array with same photo of different sizes
        hd_photo = max(photos, key=lambda x: x['file_size'])  # get one with the highest resolution
        try:
            file = telegram_client.download_file(hd_photo['file_id'])
        except TelegramClientError:
            text = "Cant download the image from TG :("
        else:
            file_bytes = np.asarray(bytearray(file.read()), dtype=np.uint8)
            try:
                image_parser = ImageParser(file_bytes)
                colors = image_parser.to_colors()
            except ImageParserError as exp:
                text = f"Cant parse image: {exp}"
            else:
                puzzle = BallSortPuzzle(colors)  # type: ignore
                solved = puzzle.solve()
                if solved:
                    text = get_telegram_repr(puzzle)
                else:
                    text = "This lvl don't have a solution"
    else:
        return {
            'statusCode': 200,
            'headers': {'Content-Type': 'application/json'},
            'body': '',
            'isBase64Encoded': False,
        }

    msg = {
        'method': 'sendMessage',
        'chat_id': chat_id,
        'text': text,
        'parse_mode': 'Markdown',
        'reply_to_message_id': message['message_id'],
    }

    return {
        'statusCode': 200,
        'headers': {'Content-Type': 'application/json'},
        'body': json.dumps(msg, ensure_ascii=False),
        'isBase64Encoded': False,
    }

Отмечу ещё один нюанс: телеграм очень строго следует политике экранирования спецсимволов. Для Markdown это:

To escape characters '_', '*', '`', '[' outside of an entity, prepend the characters '\' before them.

Любой такой неэкранированный символ — и вы не увидите ответа в телеграм-чате. И останется только гадать — является ли это ошибка интеграции или вот такой коварный баг. Будьте осторожны.

Деплой бота в Яндекс.Функцию

Про создание Я.Функции также есть отличная статья от @mzaharov. Там подробно описан процесс заведения функции, а также установки вебхука для телеграмм бота.

Я расскажу как сделал Continuous Delivery при помощи GitHub Actions. Каждая сборка мастера увенчивается деплоем новой версии функции. Такой подход заставляет придерживаться модели разработки GithubFlow с его главным манифестом

Anything in the master branch is always deployable.

Каждая сборка мастера состоит из 3ёх этапов

• lint (black, flake8, isort, mypy) — проверка кода на соответствие всем стандартам Python 2020

• test — тестируем программу с помощью pytest, поддерживая качество и покрытие кода

• deploy — непосредственно заливаем новую версию приложения в облако

Деплоить будем с помощью Yandex-Serveless-Action — уже готового Action для использования в своих пайплайнах

  deploy:
    name: deploy
    needs: pytest
    runs-on: ubuntu-latest
    if: github.ref == 'refs/heads/master'
    steps:
      - uses: actions/checkout@master
      - uses: goodsmileduck/yandex-serverless-action@v1
        with:
          token: ${{ secrets.YC_TOKEN }}
          function_id: ${{ secrets.YC_FUNCTION_ID }}
          runtime: 'python38'
          memory: '256'
          execution_timeout: "120"
          entrypoint: 'main.handler'
          environment: "            TELEGRAM_BOT_TOKEN=${{ secrets.TELEGRAM_BOT_TOKEN }}"
          source: 'app'

Переменные окружения программы и сборки спрячем в GitHub Secrets на уровне репозитория.

Результат

Бота можно найти в telegram по позывному @ballsortpuzzlebot.

Все исходники — на Github.

Присоединяйтесь к маленькому community любителей этой игры в telegram. Бот был добавлен в группу и внимательно следит за всеми отправленными картинками.

Бонус! Уровни, у которых нет решения

Мой алгоритм умывает руки — говорит что перебрал все возможные комбинации и решения нет. Возможно это баг алгоритма.. или QA-отдел мобильной игры просто забил на эти уровни, так как не предполагал, что кто-то так далеко зайдёт)

Заключение

Для меня это был интересный опыт скрещивания технологий (Telegram API + Python + OpenCV + Lambda). Надеюсь он окажется полезен кому-нибудь ещё.

Найденные баги, предложения по оптимизации алгоритма, или даже PR в репозиторий крайне приветствуются

С новым годом!