Привет, хабрахабр!
О чём эта статья?
Эта статья посвящена подробному описанию процесса создания биллиардного бота, который без участия человека играет в игру pool billiard и принимает решения, зарабатывая очки. Статья будет полезна и интересна людям, увлекающимся созданием ботов и программированием.
Предисловие
У всех нас есть любимые игры и виды спорта. Здорово, когда первое совпадает со вторым. Помимо своих увлечений спортом и спортивными проектами, я люблю также и некоторые компьютерные игры. Одна из моих любимейших игр, и вживую, и виртуально — это, конечно же, бильярд. Бильярд, пул, снукер… как угодно, — я люблю их все! Я разделяю мнение многих о том, что, например, снукер — это «недискретные» шахматы. Мало просто забивать последовательность определённых шаров в лузы, там ведётся ещё и невероятная стратегическая борьба. Борьба за снукеры, за позиции… а какой фантастической техникой обладают профессиональные бильярдисты — просто молчу в тряпочку.
Достоинства этой несомненно аристократической игры можно перичислять очень долго. Но перейдём к сути статьи. Моя самая любимая игра в бильярд вот уже пять лет и по сегодняшний день — это «Pool Billiard» на Facebook. Она классно сделана не только эстетически, но и технически. Невооруженным глазом видны классно написаный физический движок, продуманный геймплей, клиент-серверная валидация действий, обработка ошибок, дизайн, система статистики, магазин, чат в конце концов. Игру явно делали профи, да и она в топах. В неё очень приятно играть… и выигрывать!
Я достаточно долго играл в неё, пока в голову не пришла мысль: «Ба! Да она же идеально подходит для создания под неё игрового бота!» Выигрывать приятно, а выигрывать своим роботом, автоматически — вдвойне! Выигрывать у платных игроков, понакупивших систему навигации и подкручивания битка, демонстрируя им фантастические по технике и красоте удары, оставляя их с отвисшими челюстями — втройне приятно! Плюс автоматический набор очков опыта и монет: оставил робота на ночь, под утро ты лучший! Кроме того, я даже как зритель обажаю часами смотреть на игру в бильярд.
В общем, да, я решился! Добро пожаловать под кат! :)
Создание
Перед началом создания я, имея на тот момент уже довольно большой опыт игры в Pool Billiard, всё тщательно продумал с карандашом и листочком в руках. Конечно, всё предугадать невозможно, но «скелет» был создан. Внесите скелет! Для создания бота я использовал C++. Написание и отладка кода в факультативном режиме по вечерам заняли у меня почти четыре месяца. Согласитесь, сложно отлаживать что-то на закрытой системе, особенно когда необходимо оттестировать некоторый редкий или исключительный случай, который случается в одной из ста партий. Я ведь не могу фривольно расставить шары и смоделировать ту или иную ситуацию на столе.
Как робот взаимодействует с игрой?
Я понял, что бот будет взаимодейтсовать с браузером посредством полной имитации человека: распознавания образов и имитации человеческого ввода: мышь, клавиатура. Слава богу, перед каждым ударом не надо вводить капчу ;))) Так я и сделал: люблю системы имитации поведения человека, от которого браузеры так беззащитны!
Значит, нужно уметь находить на экране регион с игрой, уметь взаимодействовать с ним, получать от игры некие сигналы и обрабатывать их, и, что самое сложное, уметь правильно осуществлять удары. Я составил список необходимых действий, которые должен уметь осуществлять бот (например, зайти в определённую игру, отправить в чат определённое сообщение, поставить шар в определённую точку, проверить количество очков, нанести удар определённой силы под определённым углом, разбить пирамиду и так далее) и список определённых сигналов, которые бот должен уметь распознавать (например, начался наш ход, раунд внезапно закончился, противник сдался, денег мало и так далее). Всего получилось около сорока ситуаций; некоторые получились асинхронными, некоторые — нет. Я запрограммировал и насколько это возможно тщательно оттестировал каждую из них (об этом отдельно), после чего строительные кубики бота были готовы.
Какова общая логика работы?
Я решил, что общая логика работы будет, разумеется, state-машина. Вначале бот калибруется на игру, потом вычисляет количество имеющихся денег, потом решает какую ставку сделать. Далее следует сам игровой процесс, после которого бот вновь решает как лучше войти в новую игру. Чем проще логика, тем надёжней и предсказуемей работает система. И проще ловить баги.
Какова детальная логика работы?
Детальная логика сурова и бородата, она содержит целую кучу ветвлений и возможных ситуаций. Начинается всё с того, что запускается игра и сам бот. Игра (окно браузера со стартовым экраном игры) находится на экране. Её координаты записываются и это служит отправной точкой для всех последующих действий ввода мышью и распознавания ситуации.
Далее бот определяет количество моих денег, чтобы понять, какие ставки можно делать. После выбора размера ставки бот заходит в соответствующую комнату и начинается игра. Она может закончиться в любой момент, так как уже с этой секунды оппонент может закрыть браузер, и, спустя некий таймаут, наш раунд признают недействительным. Оппонент может также сам выйти из раунда в любой момент: в этом случае победа будет присуждена мне. Распознавание всех этих ситуаций начинается прямо тут.
Далее сервер случайно определяет, кто начнёт игру: я или оппонент. Бот ожидает начала своего хода. На весь ход даётся только 20 секунд. За это время надо успеть определить, что ход уже мой, считать со стола шары, очки, правильно их распознать, найти нужный удар и успеть его осуществить.
Бот сам определяет, будет ли он разбивать пирамиду, и на этот случай у него припасена парочка просто отпадных вариантов. Если разбивать пирамиду не надо, бот распознаёт координаты шаров на столе, какие шары он может забивать (цветные или полосатые или любые_кроме_чёрного или только_чёрный (судя по ситуации в игре)), количество очков и всю-всю-всю остальную канитель.
После этого бот рассчитывает и наносит удар. (самый короткий, но самый важный абзац)
Бот, помимо основных занятий и не в ущерб игре, любит также початиться с оппонентами. Обычно, такое временное окошко возникает сразу после осуществелния удара. Вот тут-то бот и пишет некоторое чат-сообщение оппоненту.
После проведения удара либо ход переходит к сопернику, либо продолжаем играть, либо мы победили, либо мы проиграли. Бот ждёт признак одной из этих ситуаций.
В случае поражения либо победы бот закрывает текущее окно игры и сводное окно результатов и переходит вновь к распознаванию количества денег.
State-машина в общем примерно такая.
Как игра находится на экране?
Я читаю контекст всего экрана в C++. Игра находится на экране очень просто. Так как дизайн игры не «резиновый» (она не тянется), а фиксированный, то все элементы постоянно находятся на одном и том же расстоянии друг от друга. Значит, необходимо найти на экране с игрой некий статичный элемент, который никогда визуально (графически) не меняется, и вычислить координаты начала и конца окна относительно него. Сделав пару скриншотов и обработав всё в фотошопе, я так и сделал. Я сделал простой и надёжный маркер распознавания стола. Я решил отказаться от идеи распознавать координаты окна перед каждым ударом. Это напряжно и отнимает драгоценные моменты рассчёта идеального удара. Поэтому бот определяет позицию игры только один раз — при запуске. После того, как бот нашёл окно игры, двигать окно браузера даже на один пиксель строго запрещено: в процессе игры на бильярдном столе неточность даже в один пиксель при длинных ударах накапливает чудовищно огромную погрешность. Отсюда все удары будут неверными.
Маркер игры — это неизменяемая часть изображения игрового окна.
Как определяется количество денег?
Тут мне просто повезло. Мне не пришлось ставить снифер на браузер и слушать трансляцию игры для определения количества денег или распознавать символы с экрана. Всё прозаично: дело в том, что в игре не всё сделано на флеше. Сам элемент с суммой моих монет — простое текстовое поле, легко выделяемое мышью. Я просто имитирую следующее: подвожу мышь к началу поля, зажимаю ЛКМ, провожу вправо до конца поля, отпускаю ЛКМ. В результате бот попросту выделяет поле с деньгами. Потом я копирую его в буфер обмена, удаляю спецсимволы типа пробелов, запятых и точек… и всё! Сумма монет у меня в кармане ;)
Игровые монеты — это просто выделяемое поле.
Как выбирается комната для игры?
Есть несколько комнат для игры, каждая из которых содержит определённую ставку (плату за вход). Два оппонента заходят в комнату, ставя каждый, например, по 100 монет. Победитель получает выигрыш в 140 монет (не 200, как это можно было ожидать (это сделано гейм-дизайнерами для того, чтобы постоянно из игры утекала масса денег, и люди были вынуждены пользоваться магазином и докупать себе монет за реальные деньги и играть, либо ждать пока ежедневное колесо фортуны не принесёт им монет для игры)). Проигравший уходит ни с чем. Логика проста.
В дешёвых комнатах тусуется вечно всякий сброд: новички, лузеры и так далее. Ради прикола туда иногда заходят и профи. Вероятность выиграть там очень высока.
В комнатах подороже можно встретить игроков средней руки, иногда новички заходят туда по глупости, иногда суперпрофи спускаются туда (видимо, чтобы порвать в клочья кого-то). Вероятность выиграть там примерно 50%.
В дорогих комнатах тусуется элита: либо суперпрофи, либо платники с купленной системой навигации, подсказок и так далее. Скорей всего, там светит проигрыш.
У бота есть несколько режимов выбора ставки: принудительные режимы (когда бот всегда ставит ту сумму, которую я ему указал) и авторежим. Авторежим сделан очень интересным образом. Я собрал статистику выигрыша ботом в комнатах разных ставок и на её основе написал весьма интересную программу. Она всего лишь выдаёт на выход несколько чисел, но очень важных чисел. Это так называемые пороговые количества монет. Например, если у нас 300 монет, бот имеет право играть только в первой комнате, а вот после преодоления порогового количества в 740 монет бот уже имеет право играть в первой и во второй комнате. Разумеется, бот стремится играть в самой дорогой комнате.
Так вот, программа интересна тем, что она автоматически подбирает эти самые пороговые значения по некоторому алгоритму, который она же сама дальше и использует для предсказания рисков последующего проигрыша. Она имитирует миллионы партий и принятий решения об игре в той или иной комнате (обстрел Монте-Карло) и выдаёт правильные пограничные количества монет. Причём, я заметил, алгоритм — сходящийся!
Непосредственно вход в комнату осуществляется нажатием на определённый фрагмент экрана, где расположена кнопка входа и осуществления определённой ставки.
После выбора комнаты жмём на соответствующую кнопку.
Как определяется возможность хода?
Тут на помощь вновь приходят маркеры. На игровом экране всё так же статично, как и на главном, и все элементы находятся всегда на одних и тех же местах. Это панацея. Аватарка моего оппонента, а также статистика, окно сообщений и прочие элементы, всегда находятся слева. Мои — справа. Я так же создал простой и надёжный маркер определения моего хода. Как только бот читает его, он переходит к следующей фазе.
Как распознаются шары?
Вот тут целая эпопея в трёх актах. Не буду описывать всех своих двухмесячных страданий по этому вопросу, опишу происходящее только в кратце. Из сфотографированного на момент распознавания шаров изображения стола вычитается изображение чистого стола, тщательно подготовленного мною в фотошопе. Далее находятся высококонтрастные зоны, на которых находятся пятна шаров. По определённым специфическим световым маркерам с учётом недопустимости overlap'a находятся центры шаров. Далее они сортируются по контрастности ярковыраженности, чтобы не допустить попадание мусора с экрана (кий, надписи на столе). После чего положение шаров уточняется проверкой тени вокруг них. Наконец, получили список нужного количества центров шаров на изображении.
Как только я не пытался по-другому искать шары! И с помощью определения теней, и с помощью метода границ Канни, и с помощью хитроумных классификаторов: все эти и многие другие методы были очень низкорезультативны и неточны по сравнению с методом, написанным лично мной. Я даже натравливал на статистику Wolfram Mathematica, но особо чёткого ответа это мне не дало. Может, плохо натравливал.
Но мало узнать центры шаров, надо ещё определить где полосатый, где сплошной, где белый (биток), а где — чёрный (восьмёрка) шары. Тут безграничной фантазии не было границ, потому что надо было унифицированно решить целую кучу проблем. Например, зелёный шар очень сильно сливается с сукном, а если полосатый жёлтый шар остановится так, что его белый полюс будет направлен строго в камеру, то он будет почти настолько же белый, насколько таковым является биток. Тонкостей всплыло целый миллиард, и со всеми ними я вынужден был бороться.
Я перебрал целое море решений, отбрасывая их из-за недостаточной точности, и, наконец, сам написал самый точный из них. У меня получилось решающее дерево, в каждом узле которого — самописный классификатор. Для каждого найденного шара я определяю цветовые характеристики: средний {R, G, B}, средний {H, S, B}, самый яркий и самый тёмный цвет без учёта цветовых пятен. Потом я однозначно нахожу биток как самый белый шар. Далее пытаюсь определить восьмёрку как самый тёмный шар. После всего, необходимо разделить цветные от полосатых. Но непросто ларчик открывался: я составлял трёхмерные таблицы выборок, фотографировал по тысяче раз шары в попытках обучить сеть, но всё же мне так и не удалось построить однозначно разделяющую кластеры сплошных и полосатых шаров гиперплоскость. Всё равно ошибки встречаются. Для этого случая я сделал небольшую коррекцию-ошибок-на-лету. Об этом — чуть ниже.
Тут в ход пошли разные высосанные из пальца ортонормированные базисы поворотов, статистики кластеров с предустановленными цветами шаров и прочая математическая основа, но всё было не то… и не то… перебрал я очень много вариантов.
В конце-концов, некий набор шаров с их достаточно точными характеристиками у нашего бота есть: обязательно есть белый и чёрный шары, и наборы сплошных/полосатых. Поверьте, проделана не малая работа.
Как определяется возможность разбития пирамиды?
Тут я было расслабился: создаём простой классификатор позиции пирамиды (каждый шар стоит в точке пирамиды) и если наш ход и наш ход — первый, то разбивам. Но не тут то было! Что-то не срабатывало! Оказывается, хитрые программисты добавили некоторый шум в начальные позиции шаров в пирамиде. Умно! А иначе можно было бы записать «идеальную партию» — безошибочную серию ударов, ведущую к победе, и, постоянно воспроизводя её, выигрывать. Но они предусмотрели такую вот защиту. Чуть подкорректировав классификатор, я достиг успеха в распознавании момента разбития пирамиды.
Когда надо разбивать пирамиду, бот выбирает один из нескольких намертво запрограммированных в него роскошных вариантов разбития и реализует его. Почти все из вышеописанных вариантов заставляют один-два шара сразу же залететь в лузы. Ну, или накрайняк очень сильно разбрасывают шары по столу, что моему алгоритму только на руку.
Как определяется количество очков на столе?
Возле моей аватарки и аватарки оппонента есть стек из забитых шаров. Он представляет из себя полосу с помещёнными туда забитыми шарами чуть меньшего радиуса, чем на столе. Однако, как быть? Одного распознавания шаров на столе мало, чтобы понять, какую серию я играю — полосатых или сплошных. Значит, надо распознать не только количество шаров в стеках, но ещё и сами шары! Пфффф… алгоритм «вычитания стола» тут не подходит, да и размеры не те.
…
невероятным усилием воли я заставил себя написать ещё один распознаватель
…
и вторым невероятным усилием — объединить оба этих распознавателя в одну универсальную функцию распознавания. Фактически, пришлось всё писать с нуля. Вот она — проблема недостаточного планирования. Но зато теперь я указываю регион и размер шаров, а на выходе получаю координаты и характеристики каждого шара! Победа разума!
Определив количество и тип забитых мною и противником шаров, ситуация на столе становится полностью детерминистичной. Теперь бот знает, что и как ему необходимо забивать.
Как определяется какие шары бить?
Тут запрограммирован строго детерминистичный алгоритм. Если мы в начале партии и разбиваем пирамиду, то можно бить в любой шар (всё равно в чёрный мы не попадём — он спрятан внутри пирамиды). Если первый ход уже был осуществлён — смотрим на количество забитых шаров. Если их нет — можно бить любой, кроме чёрного. Если есть только у противника — взять противоположный тип и бить. Если есть у меня (и не только у меня) — бить такой же тип. Наконец, если мною забиты все шары моей серии кроме чёрного — забивать чёрный. Всё! ;)
Как определяются фолы противника?
Иногда оппонент косячит. В этом случае правила игры обязывают меня к свободному удару: я должен сам поставить биток в любую точку стола и нанести удар. Итак, есть две проблемы: распознавание фола противника и правильная постановка шара под удар.
Первая проблема решается относительно просто. В отдельном потоке некий отслеживатель пытается найти такую ситуацию: сейчас ход противника и появился маркер «Fault!» на столе. В этом случае он сообщает главному потоку о том, что следующий удар необходимо делать с постановкой.
Вторая проблема — проблема постановки — решается чуть сложнее. Хотя, признаюсь вам, друзья, тут я схалтурил. Я не пытаюсь поставить биток по некоторой линии забития одного из шаров своей серии. Нет. Я просто пытаюсь поставить шар универсально — максимально близко к центру стола, где нет препятствий. Сначала я распознаю ситуацию на столе, потом вычисляю ближайшую незакрытую к центру стола точку и ставлю туда шар. Пока происходит постановка, я уже почти наверняка вычислю идеальный удар.
Как вычисляется угол и сила удара?
Итак, передо мной возникла задача за заданное время при заданной конфигурации шаров на столе и заданном правиле нанесения ударов рассчитать все возможные результативные удары и выбрать среди них лучший. Возможные значения заданного времени: {20 секунд}. Возможные конфигурации шаров: их?.. Возможные правила нанесения ударов: {любые кроме чёрного, только сплошные, только полосатые, только чёрный}.
Забивание шара
Прежде чем влезать в дебри бильярда, необходимо вначале понять физику происходящего. Что нужно, чтобы забить шар?
Для этого необходимо провести воображаемый отрезок от центра лузы до центра шара и чуть-чуть продлить его дальше до пересечения с границей шара. Точка пересечения и есть точка удара. Если ударить шар по ней, он полетит в лузу.
Чтобы биток ударил в эту точку, его надо направить отнюдь не в неё, а в точку, отстоящую от точки удара на радиус битка далее по той самой воображаемой линии.
Ну а далее, я думаю, вы уже уловили. Чтобы сам биток прилетел куда надо, нужно также построить линию от целевой точки через центр битка и пересечь её с дальним краем окружности битка.
Итак, отсюда рождается общее правило: чтобы направить любой шар в заданную точку А, необходимо соединить воображаемой линией точку А и центр этого шара и продлить её до пересечения с дальней границей окружности шара. Сюда и надо ударить шар. Я решил сделать стратегию игры бота такой же, как и у людей: бот выбирает один шар под удар и забивает его. Всё. Чем проще система, тем она надёжнее и проще её отлаживать.
Лузы
Лузы разные. И попадание в них подчинено разным законам. Например, в угловую лузу можно попасть разными способами:
Но для каждой лузы мне удалось найти универсальную точку, качение шара к которой из любого места влечёт попадание в лузу:
Я запрограммировал бот как раз целиться в эти точки. Единственное ограничение, которое налагают на себя лузы длинных бортов: залетание в них шаров возможно только в створке 70 градусов. Это также заложено в код.
Моделируемое пространство
Я решил отказаться от рикошетов. Нет нет, не пугайтесь, не в том смысле, конечно же ;) Построить такое моделируемое пространство, чтобы вообще забыть о рикошетах. Они в игре есть и остаются, а вот в пространстве их не будет. Над решением этой задачи я работал лишь вечер. Я понял: соударение шара радиуса R с бортом толщиной 0 — это то же, что и соударение материальной точки радиуса 0 с бортом толщиной R:
Значит, можно существенно упростить рассчёт физики: в плане траекторий будем работать не с шарами, а с материальными точками. Далее: по законам жанра, угол падения шара на борт равен углу отражения. Как и в случае световых лучей и зеркальной поверхности. Вы спросите: причём тут это? Отвечу. Соударение материальной точки с бортом (рикошет о борт) — это то же самое, что и продолжение движения материальной точки сквозь борт в пространство, зеркально отражённое от этого борта. То есть если бы шар мог «видеть» вперёд по направлению своего движения, а борта были бы зеркалами, то получилось бы вот что:
В таком «зеркальнобортовом» пространстве мне уже не надо задумываться о рикошетах. Они вытекают сами собой. Плюс подключаем правило движения материальной точки, и получается вообще роскошно.
В моделируемом пространстве все удары — прямые линии, рикошетов нет. А вот на столе они уже есть.
Максимальные сила удара и путь битка
Отлично, масса работы проделана! Но есть ещё чрезвычайно важный вопрос, которого мы вообще не коснулись: какой максимальный путь может пройти биток? Какая в нём энергия? Я не хочу каждый раз лупасить шары со всей силы; это будет подвергать биток риску случайного скатывания в лузу. Я хочу очень аккуратно и точно рассчитывать силу удара. Для этого мне нужно знать при какой оттяжке кия от битка в пикселях происходит минимальный удар и какой он длины, и при какой оттяжке кия от битка в пикселях происходит максимальный удар и какой он длины. Также мне надо знать какая энергия отбирается у шара при ударе о борт. Теперь осталось всё это выяснить. С минимальными ударами всё прозаично: это меряется в любой момент. С максимальными гораздо, гораздо сложнее. Диагонали стола не хватит даже для среднего удара, поэтому я явно померять длину его пути не могу. Я придумал разложить это на два случая: горизонтальный и вертикальный. Произведя потом соответствующие замеры и приравняв уравнения вместе я бы получил полную длину максимальной траектории шара и коэффициент гашения энергии о борт. Так я и сделал. Я выждал моменты, когда противник получил фол, чтобы аккуратно поставить биток прямо к краешкам бортов, да так, чтобы горизонтальному и вертикальному движению битка ничего не мешало. И дважды ударил со всей силы: один раз горизонтально, другой — вертикально. Снял показатели: при вертикальном ударе биток отскочил от длинных бортов 8 раз и, докатившись на остатке энергии ещё какой-то путь, остановился. При горизонтальном ударе число отскоков составило 5 с хвостиком. Отсюда, зная размеры стола, нетрудно получить уравнения, численно решив которые мы получим и полную длину максимального пути, и коэффициент гашения.
Пусть x — максимальная длина пути качения шара без ударов о борты в пикселях, а p < 1 — коэффициент потери энергии при ударе о борт под прямым углом. Известны ширина w и высота h стола в пикселях. Рассмотрим горизонтальный случай:
- x —— в начальный момент времени самого сильного удара шар обладает полной энергией качения на максимальную длину пути x;
- x – w —— такой энергией и, соответственно, запасом пути обладает шар, прокатившийся по горизонтали от борта до борта на ширину стола w;
- p · (x – w) —— ударившись о борт, шар потерял энергию и, следовательно, запас пути согласно коэффициенту p;
- p · (x – w) – w —— прокатившись снова от борта до борта шар ещё раз потерял запас пути, равный ширине стола;
- p · (p · (x – w) – w) —— шар снова ударился о борт и потерял энергию согласно p;
- p · (p · (x – w) – w) – w —— опять качение от борта до борта, уже третье;
- p · (p · (p · (x – w) – w) – w) —— очередной удар о борт и потеря энергии;
- p · (p · (p · (x – w) – w) – w) – w —— четвёртая потеря энергии и запаса пути при качении от борта до борта;
- p · (p · (p · (p · (x – w) – w) – w) – w) —— удар о борт;
- p · (p · (p · (p · (x – w) – w) – w) – w) – 388 —— пятое, последнее качение от борта: шар полностью потерял всю энергию и запас пути и останавился на расстоянии 388 пикселей от края борта.
Приравниваем последнее уравнение к нулю. Аналонично получаем уравнение для вертикального случая. Решая эту нелинейную систему из двух уравнений с двумя неизвестными численно, я получил искомые x и p.
Цепные правила
Разумеется, глубина удара может быть любой, лишь бы энергии хватило. Но из-за накопления погрешностей я решил остановиться на числе 4, то есть максимальное количество задействованых объектов (включая лузы) равно 4. Мой биток может ударить шар А, который ударит шар Б, который упадёт в лузу. И то (!) точность теряется настолько сильно, что я ввёл целый ряд ограничений на подобные удары. Они должны быть без рикошетов о борты, расстояния между шарами и лузой должны быть примерно равны и углы атаки близки к упругим ударам. А вот такая фантастика мне пока не светит:
Откат битка
Все страдания и рассчёты будут напрасны, если даже после феерически шедеврального удара наш биток откатится и упадёт в лузу. Даже через рикошет. Поэтому я сразу выбрасываю из рассмотрения такие удары, после которых боту может светить провал. Для рассчёта отката битка вычисляются сила и направления отката после удара битка о целевой шар. Я думал всё будет просто: вычисляем остаток энергии после упругого/неупругого удара, на какое расстояние и в каком направлении откатится биток, направление — с помощью косинуса относительного угла атаки, и смотрим, не проходит ли траектория через лузы. Но нет, подводный камень ждал меня и тут. После проведения серии тестов я заметил, что фактический откат существенно отличается от моделируемого.
И система навигации игры (жётлая) и здравый смысл с рассчётами показывают, что биток откатится по зелёной линии. Однако, после удара он катится по красной:
Вот это западлянка. Оказывается, в игре учитывается ищё и инерция кручения шара и его направление. Пришлось почти четыре вечера писать и тестировать нелинейную функцию рассчёта траектории отката. Такие мелочи бесят, но в конце оказывается, что это вовсе и не мелочи. Более менее точную функцию мне определить удалось только методом проб и ошибок. Но я сделал это! Теперь я могу смело выбрасывать удары, проводящие биток через лузы в результате отката.
Функция поиска лучшего удара
В результате анализа конфигурации стола я получал коллекцию большого количества возможных ударов. Но как выбрать лучший из них? Надо включить и оценить каждый параметр удара. Подумаем логически, чего бы нам хотелось? Число рикошетов пути от битка до целевого шара желательно бы свести к минимуму: каждый рикошет вносит маленькую, но погрешность. Расстояние от битка до целевого шара должно быть как можно меньше, но не совсем маленьким, чтобы была возможность качественно прицелиться. Как ни странно, это два разных условия. Подумайте над этим. Далее. Расстояние от целевого шара до лузы, в которую он должен упасть, должно быть как можно меньше. Безусловно. И этот путь должен содержать минимум рикошетов, желательно — ноль. Удар желателен средней силы, не слишком сильный (погрешности кручения и физического движка игры) и не слишком слабый (погрешности уже моего бота). Удар битка о целевой шар должен быть максимально «прямым» и упругим: касательные — зло! Отсюда автоматически вытекает минимальная длина отката. Из моего продолжительного подводного плавания и анализа подводных камней вытекли ещё дополнительные условия (не столь важные, но всё же значимые): надо, чтобы целевой шар в угловые лузы летел под углом, максимально близким к 45 градусам, а в лузы длинных бортов — под углом не более 35 градусов. Есть ещё некоторые дополнительные условия, но о них умолчу.
Но по самой сути все эти вещи далеко не идеально сравнимы и друг с другом, и между собой. Например, если угол атаки (упругость удара) ещё как-то сравним с другим углом атаки (скажем, 0 градусов лучше, чем 50), то такая характеристика, как сила удара…? Для разных длин траекторий нужны разные силы, ведь там и расстояние разное, и резка. Если же перевести силу удара в некоторый относительный показатель, то что делать с резкой? Ведь для разных ударов она — своя! А как сравнивать несравнимые категории, такие, например, как число рикошетов (число от 0 до, скажем, 10) и угол влёта шара в лузу длинного борта? Что важнее?
Пффф… Передо мной возникла ещё одна существенная проблема. Необходимо было привести все эти характеристики к некоторой консистентности. Скажем, к числовому диапазону от 0 до 1, где 0 — чудовищно плохо или невозможно, а 1 — абсолютно идеально хорошо. В этом и заключался следующий огромный шаг работы; поиск и выбор таких функций, которые бы отражали (и адекватно отражали) все представленные характеристики в коридор [0, 1]. А это огромная работа. Взять число рикошетов. Да, оно может быть от 0 до 10, но в среднем нормой считается 1 или 2 рикошета. 8 — это уже исключительная ситуация, встречающаяся в игре крайне редко. Посему линейно переводить диапазон [0, 10] в отрезок [0, 1] глупо и неоправдано. Пришлось искать «обратные» функции распределения для всех характеристик, подгонять, выкапывать их, высасывать из пальца. В результате всё получилось довольно сносно, но с меня сошло 77 потов.
Ну а следующий шаг — поиск весов для этих характеристик. Вес — это важность характеристики. И тут опять дилема. Что важнее чего? Я сначала попробовал поставить всем характеристикам одинаковый вес, но бот играл отвратительно. Потом начался ещё один этап работы — долгий и нудный. Подгонка и поиск нужных коэффициентов. Этот этап также занял у меня пару недель, но мне повезло. Я уже настолько прочувствовал все ситуации, что адаптивным методом вышел на очень хорошую подборку. До сих пор не нашёл ничего лучше ;)
Итак, главная определяющся функция была готова! Она, напомню, состоит из суммы произведений весовых коэффициентов на функции подгонки. В результате для каждого удара я получаю число «хорошести» удара от 0 до 1 (нормируя). Ну а дальше — дело техники: выбираем лучший удар и бьём.
Коррекция резки шаров
За месяцы тестирования я выявил интересный глюк. То ли из-за неточностей движка, то ли из-за каких-то моих косяков ударные шары, стоящие возле борта, не всегда поддаются общим законам нанесения ударов. А должны. Происходит вот что: в ситуации, когда я идеально направляю ударный шар, стоящий возле длинного борта, в лузу, вместо того, чтобы лететь строго параллельно борту и упасть в лузу он почему-то ударяется о борт и отскакивает, летя уже не в том направлении. Такое ощущение, что я недорезаю. Я ввёл специальную корректирующую функцию доведения резки до идеала. Она опять же взята с потолка и является чистой воды подгонкой. Но работает.
Адаптивный поиск за 20 секунд
На всё про всё у нас есть всего 20 секунд, и бот может не успеть найти удар. Поэтому высокоприоритетным потоком я ищу так называемые аварийные удары. Это удары, имеющие целью не забитие шара, а хотя бы прикосновение к своему шару. Если в течение 15 секунд поиска бот так и не нашёл ни одного удара на забивание, он немедленно реализует аварийный удар на прикосновение для избежания фола. А сам поиск удара я сделал адаптивным. Сначала в качестве моделируемого (того самого зеркального) пространства берётся сам стол как он есть. Если ни одного удара найдено не было, то моделируемое пространство увеличивается в три раза по горизонтали и вертикали: к столу слева и справа «приставляется» его вертикальное отражение вместе с шарами и лузами, а сверху и снизу — горизонтальное отражение. Если удар не найден и тут — происходит ещё одно достраивание моделируемого пространства. И так до тех пор, пока либо не пройдёт 15 секунд, либо число «блоков» стола не превысит максимально допустимого числа рикошетов; дальше прокатиться у шара попросту не хватит энергии.
Надо забить зелёный шар:
Прицеливание и удар
Казалось бы, достиг всего: есть и прицельная точка, и сила удара. Осталось только его осуществить. Но и тут я наткнулся на трудности, а, точнее, либо на неточность программирования, либо на скрытую защиту от товарищей программистов игры Pool Billiard. Но обо всём по порядку. Между прицельной точкой и битком находится угол удара. Допустим, он равен 27 градусов:
Бот должен найти такой пиксель на столе, чтобы, поставив туда мышку, линия удара в точности составляла 27 градусов. Так как пиксели дискретны, а не непрерывны, то в специальной зоне поиска происходит поиск пикселя, наилучшим образом удовлетворяющего данному углу.
Ну вот, казалось бы, и всё! Ставим мышку в нужный пиксель, делаем оттяжку на заданное количество пикселей к битку и отпускаем. Но нет. Не туда шар летит! Что за проклятье!? В части случаев шар бьёт идеально, в части как-то сомнительно, а иногда совсем не туда! Я потратил 4 дня, чтоб найти это плавающую ошибку. Перелопатил весь код. Оказалось, что дело совсем не на моей стороне: мышка физическая (экранная) не совпадала с мышкой игровой. На флеше ведь сделано. То ли это баг, то ли фича, но их координаты отличаются на 4 пикселя горизонтально и на 1 вертикально. Каким-то чудом я это случайно заметил; введя соответствующие поправки, получил отличный результат.
Коррекция ошибочного распознавания шаров
Да, распознавание шаров у меня не идеальное. Иногда бот ошибочно классифицирует полосатый шар как сплошной, и наоборот. Проще всего скорректировать такую ситуацию, когда неверно распознанный шар — на столе. Сложнее всего — когда в стеке забитых шаров.
Предположим, бот неверно распознал шар на столе. Пусть для определённости бот думает, что шар полосатый, когда на самом деле он сплошной. Бот забивает полосатые. Волей случая именно этот шар был выбран под удар. Что же происходит дальше? Если бот нанесёт удар не по своему шару, он получит Fault и пропуск хода. А это нехорошо. Я сделал так: если в момент прицеливания по шару (если нет рикошетов) в интерфейсе игры возле шара загорается зелёная стрелочка, то можно бить.
Если же красная, то бот немедленно переклассифицирует его на противоположный тип (теперь для бота он сплошной), отбрасывает все найденные по нему удары и берёт следующий самый лучший удар, не касающийся именно этого шара. Бот пытается ударить по другому шару. Если же тот тоже неправильно классифицирован — история повторяется. И так до тех пор, пока у бота либо не выйдет тайм-аут, либо...
… логика куда хитрей. Ведь возможна и такая ситуация: начало партии; бот забивает первый и единственный шар. На самом деле он сплошной, тогда как бот думает, что забит полосатый. Это как раз вторая ситуация из описанных в начале раздела. Что же будет происходить дальше? Бот будет абсолютно уверен, что ему необходимо забивать полосатые, когда на самом деле — сплошные. Бот будет целиться в первый полосатый шар — красная стрелка, во второй полосатый шар — опять красная стрелка, в третий — то же самое. На самом деле этот процесс не будет длиться до тайм-аута. Я запрограммировал так: если более половины шаров на столе дают красную стрелку, значит попросту неправильно распознан тип шара в стеке забитых шаров. Тогда бот немедленно переклассифицирует тип забиваемых шаров с неправильных полосатых на правильные сплошные и ищёт уже удары по сплошным, выводя себя из крутого пике. И это всё — если останется время.
Как происходит чат?
На войне любые средства хороши. А, значит, можно и нужно искать такие средства. Например, средства воздействия на противника. Игра по сути полностью закрывает оппонентов друг от друга. Они взаимодействуют только посредством игрового стола. Игрового стола и… чата! Да, в игре есть чат. И это максимальный из доступных канал вербальной коммуникации. А, значит, воздействия. Что можно сделать через чат с противником? Призвать его сдаться, конечно же, не получится, но можно здорово поотвлекать его внимание и даже потрепать нервы! Ай да метода!
Я решил не заморачиваться со связностью транслируемого текста. Ведь чат — вторичная задача. Пусть это будут просто некие короткие сообщения.
Отдельным случаем я запрограммировал несколько вариантов приветствий. Они говорятся ботом в начале партии, чтобы а) привлечь оппонента к функции чата и б) сразу настроить его на то, что я буду с ним говорить. И воспитанность вынуждает ответить, скажу я вам. Ответить — значит подключить к дополнительно отвлекающий от игры функционал болтавни и реакции на сообщения. Отмечу, что на приветствие подавляющее большинство игроков отвечает приветствием. Отлично! Пусть думают, что с ними играет человек (им даже в голову прийти не может, что тут может быть робот)!
Ну а дальше — колбасный цех! Тут в ход идут и шуточки-прибауточки, и подколы, и дразнилки, и бессвязный бред, и демотивирующие фразы… Из десяти человек примерно два всерьёз общаются с ботом. Многие отвечают матом. Бесятся. Бот их вынуждает. Это великолепно!
Ну а сам функционал чата реализуется после осуществления ботом удара и ожидания срабатывания физики; отличное место для «поговорить». Я просто помещаю выбранную фразу в буфер обмена и, посредством экранного baloon отсылаю сообщение оппоненту. Хитростей тут ноль.
Вот и всё :)
На этом моя долгая и кропотливая работа над ботом была закончена. Осталось лишь наслаждаться плодами труда.
Немного видео
Размещаю для вас презентационное видео очень старой версии бота:
И видео новой версии многочасовой игры в автоматическом режиме:
Послесловие
Дорогие друзья! Если вам понравилась эта статья, смею предположить, что вам понравятся и другие. С уважением, Андрей Миронов.
Автор: andreymironov
