Пишем игрового бота на примере решения «Цветочной клумбы»

Зачем это нужно?

На вопрос «Зачем?» всегда есть красивый ответ: “Science isn’t about why, it’s about why not”. Хотя, в целом, вы можете получить определенные навыки при написании этого бота, познакомиться с новыми штуками и т.п., но в первую очередь это “just for fun”.

Хорошо, давайте писать бота. С чего начать?

Для начала нужно определиться самому, что именно должен делать бот вместо вас. У нас есть клумба, которая состоит из семи уровней. На каждом уровне нужно каким-то хитрым способом добиться того, чтобы вся клумба 4х6 была засажена цветами. Т.е. алгоритм прохождения игры следующий:

Начать новый уровень/игру;
Понять, по какому принципу один клик мышки изменяет состояние клумбы;
Придумать, как такими манипуляциями засадить всю клумбу;
Проделать рутинную техническую работу по многократному механическому воздействию указательным пальцем на левую кнопку компьютерной мыши;
Нажать кнопку «Ок» в сообщении о том, что уровень пройден (эй, это таки реально важно!);
Перейти на шаг 1, если это не последний уровень. Если же последний…
Ввести имя, включить “We are the champions” Квинов и на радостях выплеснуть пол бутылки шампанского на клавиатуру.

Если хорошо потрудиться – бот может выполнять все эти шаги самостоятельно, один за другим. Степень его самостоятельности будет зависеть только от вашего желания и времени, которое вы убьете на эту штуку.

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

Начало новой игры

Чтобы начать игру, достаточно пройти по ссылке.

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

Правила уровней

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

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

Придумать алгоритм решения уровня

Решений может быть много, но на быстрое меня натолкнул Твердохлеб Ярослав. Каждая клетка рассматривается как переменная в кольце по модулю 2, всего таких переменных 24 штуки. Строится система линейных алгебраических уравнений (в зависимости от правил, по которым решается уровень). Дальше она решается, скажем, методом Гаусса (но не общий случай, а случай для кольца по модулю). И если решение существует – программа его найдет.

Эта часть бота должна работать быстро. По сути, для решения системы размерности 24 требуется порядка операций, и такие системы будут решаться моментально на любой исправной ЭВМ, которой не больше, наверное, 20 лет. Для решения этой задачи я по привычке взял С++.

Хорошо, мы знаем, как решать уровень. Осталось его получить...

Для автоматизации этого этапа я использовал Python. Он напрямую взаимодействовал с браузером, сохранял страницу на жесткий диск, и запускал скомпилированную С++-программу, которая эту страницу парсила, определяла уровень, и отправляла результат (о чем рассказано ниже). При этом удобно было использовать библиотеку win32api, которая позволяет отправлять системе сообщения о нажатии клавиш, т.п. Если конкретно, то:

Запустил хром, открыл игру, почистил куки;
Запустил скрипт на питоне, который 7 раз подряд:

Нажимает F5 чтобы обновить страницу (после очистки куки таймер включится только тогда, когда сервер отправить новые куки – т.е. после обновления страницы);
Нажимает Ctrl+S («Сохранить как…»), Enter (подтвердить указанную директорию), кнопку «левая стрелка» (в выпрыгнувшем окошке «Заменить файл с таким же именем?» переместиться на кнопку «Да»), Enter (нажать ее).
Запускает скомпилированную С++-решалку, ждет ее завершения;
Нажимает Enter («Ок» в «Поздравляем, вы прошли уровень!»);

Как отправить решение на сервер

Тут все просто. Если вы заметили, что происходит, когда вы нажимаете на клетку левой кнопкой мышки – браузер переходит по адресу, в котором в виде параметров передается номер строки и столбика, клетка которых была нажата. Таким образом, программа определяет, какие клетки нужно нажать, и через тот же win32api, только в моем случае для С++, открывает новые вкладки в хроме. Порядок не имеет значения. Нужно лишь обратить внимание на то, что сообщение «Поздравляем! …» выпрыгнет в последней открытой вкладке, что нам, собственно говоря, только на руку.

В чем могут быть затычки

Главная затычка в том, что графический интерфейс браузера или операционной системы может просто не успевать за вашими махинациями. Решение простое: перед всеми системными сообщениями о нажатиях клавиш, открытиях страниц и т.п. нужно расставить паузы. Их сложно оценить – их легче подобрать экспериментально. К слову, именно на этой части можно значительно сократить время прохождения игры, поскольку back-end программы (решалка на плюсах) работает моментально. Все время уходит на взаимодействие с браузером, и чем больше вы этого времени сэкономите – тем лучше.

Самый крутой вариант

Еще круче – сделать без графического интерфейса. На питоне это делается весьма несложно при помощи библиотеки urllib2. Алгоритм примерно такой:

Отправляем первый запрос, получаем ответ, сохраняем куки (называется PHPSESSID). Отлично, сессия открыта;
Генерируем новые запросы (запросы страниц-уровней, ссылки-клики) с передачей полученного куки, чтобы оставаться в пределах одной сессии.

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

Я решил проблему так: на самом последнем уровне я делаю все клики, кроме одного. Потом я открываю в браузере клумбу, с помощью плагина для любимого браузера меняю куки на тот, что использовался в программе, и обновляю страничку. В итоге получаю последний уровень, который находится за 1 клик до победы – и в глаза само собой бросается, какой именно клик нужно сделать.

История написания и результат

Первая версия бота была чисто на плюсах, и не умела сохранять вкладки. Приходилось руками сохранять страницу, и на это уходило время. Кроме того, изначально я решал ее на через СЛАР и Гаусса, а через анализ графа игры, и последние уровни решались в среднем секунд по 10. Но, приловчившись, мне удалось войти в минуту.

Далее мне подсказали идею СЛАР. Решался уровень моментально, но ручная работа забирала около 25-30 секунд.

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

А потом я сделал пересылку пакетов в текстовом режиме, и просто делал последний ход в браузере, куда копировал куки после работы программы. Программа-решение работает на всех 7 уровнях (с учетом обмена информацией с сервером) порядка 0.5 секунды, еще около 1.5-2 секунд (если потренироваться) уходит на ручную вставку куки, обновление страницы и совершение последнего клика. Итого – честных 3 секунды.

Чмоки всем в этом чате,

Башук Саша, 2012г.