Бильярдный бот: история создания

    Привет, хабрахабр! Эта статья посвящена подробному описанию процесса создания бильярдного бота, который без участия человека играет в игру 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 отсылаю сообщение оппоненту. Хитростей тут ноль.

    Вот и всё


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

    Немного видео


    Размещаю для вас презентационное видео очень старой версии бота:



    И видео новой версии многочасовой игры в автоматическом режиме:



    Спасибо за внимание!

    Only registered users can participate in poll. Log in, please.

    Полезна ли статья?

    • 2.9%Не интересна и не полезна: больше не надо писать на Хабр11
    • 9.0%Интересна, но не полезна: тематика «единична» и «пуста»34
    • 2.1%Не интересна, но полезна: на всякий случай сохраню, вдруг потом пригодится8
    • 86.0%И интересна, и полезна: с удовольствием буду следить за творчеством автора327
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 43

      –6
      Вашу бы энергию, да в мирное русло… На что нибудь полезное.
        +14
        … да в такое русло, чтоб деньги приносило. Предлагайте!
          –11
          Сами придумывайте. Просто видно, что у Вас есть знания, упорство и свободное время, а тратите Вы это на всякую хрень. Напишите свой биллиард, или гольф там, ну или боулинг или кёрлинг.
            +15
            А зачем нужен очередной биллиард, гольф, боулинг или кёрлинг? Ничем не лучше, чем «хрень», описанная в данной статье.
            А статья очень классная.
            –1
            торговый робот — как самое очевидное :)
              0
              Да да да. Или покерный бот. Слышал от своих друзей это уже много раз. Осталось решить — покер или биржа =) И там и там — одни боты! Правда, на биржах профессиональные, а в покере...? Чуть «менее» профессиональные? И то и то — игра с неполными условиями.
                0
                Пожалуй, посредственная игра с полными условиями, на которой можно заработать — это массовое распознавание капчи. Ну, или майнинг криптовалют. Что ещё?… надо подумать.
              +6
              Вы не программист
              +7
              Решение с ударами от борта очень красивое, да и вообще проделана огромная работа. В таблице представлена реальная вероятность выигрыша для вашего бота или это просто пример?
                +1
                Спасибо. Чуточку округлённая в лучшую сторону для чистоты восприятия.
                +5
                Проделанная работа и результат достойны уважения (если оставить в стороне моральную подоплеку использования бота в игре). Азарт и упорство способны свернуть горы )). В целом статья очень понравилась.
                +1
                А какие данные ходят между клиентом и сервером? Не проще ли было бы построить модель на них?
                  +1
                  Не интересовался, но, исходя из здравого смысла гейм-дизайна, между клиентом и сервером целесообразно было бы пустить только тайм-ауты, чат и инфо о нанесении удара (пара угол/сила). Всё остальное (так как игра строго детерминирована) можно считать на клиенте(тах). Так что врядли в трафике гуляют позиции шаров. Можете подтвердить или опровергнуть мои доводы с WireShark. Тут меня преследовал азарт больше образо-распознавательский, чем трафико-копательский.
                    +1
                    Ваш оппонент как-то должен получать расстановку шаров после вашего удара. Скорее всего, сервер обменивается с клиентами всей необходимой информацией.
                      0
                      Если использовать детерминированные вычисления — то оппоненту достаточно узнать действие игрока. Позиция шаров после этого вычисляется однозначно.

                      Другое дело, что шаров в бильярде все же не настолько много, чтобы имело смысл экономить на их позициях.
                  +4
                  Глядя на «моделируемое пространство», подумалось, что можно сделать именно такую «странную» игру — играть на поверхности тора (по сути бесконечной), в которой лузы это просто дырки в поверхности стола… :)
                    0
                    Каков же будет процент играющих в такой бильярд? Целевая аудитория? 80% играющих — это школоло. Им не такие игры нужны. Процент айтишников и математиков, которые смогут потенциально заинтересоваться — капля в море. Это моё личное мнение, которое может не совпадать с действительностью. Надо делать что-нибудь массовое… современное…
                  +3
                  Генератор абстракций интереснее… и мы все еще ждем сорцы! :)
                    +2
                    Не хватает какой-нибудь таблички со статистикой результатов или чего-то такого. Я не готов прям щас смотреть трёхчасовое видео.
                    А так, очень здорово, круто!
                      0
                      Действительно, совершенно нетривиальная задача. Есть что-то от реверс-инжиниринга. :)
                      Насколько я понял, элемент самообучаемости напрямую исходит из собранной статистики?
                        0
                        Да. Самообучаемость идёт только в плане выбора комнаты для игры.
                        +2
                        Все-таки задумка с чатом неудачно реализована. Есть несколько неудачных фраз, из-за которых очевидно, что играет бот. Ну не может человек повторять как дятел настолько длинные фразы, да еще и не в тему…
                          0
                          Согласен, чат провален и нелеп. Но, во-первых, как минимум, за те короткие 5 минут, которые длится раунд, за то небольшое количество фраз (7 — 10), которые успевает сказать бот, вряд-ли один игрок сможет о чём-то догадаться, и, во-вторых, как максимум, не стояло глобальной цели не выдать бота. Пусть догадаются! Да, будет чуточку забавнее. Это всё for fun!
                          0
                          Играю (нет не ботом, а сам) в 8 Ball Pool на андроиде.
                          Немного смутили другие пропорции и рикошеты без учета силы удара и направления крута… неестественно всё смотрится, наверно это сильно упрощает программирование?
                          0
                          ожидал в конце таблицу, где первые 100 мест занимают ваши боты!
                          авторы игры работу не предложили? :)
                            +1
                            Бот есть только у меня. Пожалуй, авторы игры вообще не догадываются о моём существовании.
                            +2
                            удивлён не стопроцентным показателем побед над человеческим мозгом, не очень сильным в геометрии (в сравнении с машиной).
                              +1
                              Вот когда бот будет думать хотя бы на шаг вперед — плюс учитывать кручение — тогда и будет близкий к 100% результат.

                              А сейчас бот периодически попросту мажет, как видно на видео.
                                +1
                                Да. И неточно классифицирует шары.
                              0
                              Имеет смысл записывать игры (позиции до/после удара) чтобы тестировать модели физики. Судя по всему вращение и проскальзывание как-то странно реализованы.

                              Для предотвращения игры чужими шарами достаточно чтобы функция определения типа выдавала еще «уверенность определения». Потом достаточно прицелиться в хорошо определенный шар (или пару) и посмотреть на зеленый/красный ободок.
                                0
                                Я думал об этом. Даже вводил весовые функции на множестве {выбор_лучшего_удара, выбор_достоверного_шара}. Глючило.
                                +1
                                В бильярде есть пара очень важных вещей, которые должны быть обязательно запрограммированы:
                                1. Кручение (качение вращающегося шара, столкновение вращающихся шаров, закручивание от столкновения с бортом и т.д.) Я пробовал писать бота, но понял что именно здесь начинается такая математика, что придется потратить на неё много времени. (играл на мейл.ру)
                                2. В результате удара шары должны встать так, чтобы следующий удар можно было сделать очень легко, а потом опять и опять — надо думать всю игру наперед, наподобие как в шахматах, тогда результат будет убойный. Все живые игроки, которых показывают по телевизору пытаются так думать насколько у них это получается.

                                Информация о расстановке шаров должна обязательно раздаваться всем клиентам. Т.к. клиенты аппаратно и программно разные, в том числе в математике может присутствовать рандом.
                                  0
                                  Спасибо за чёткие рекомендации. Я, как играющий в снукер, знаю о них не по наслышке. Пока что так, а вот во второй версии надеюсь улучшиться. Есть куда расти.
                                  +1
                                  Браво! Хабр торт, автор великолепен — куча удивительно красивых решений.

                                  А почему не стали использовать embedded browser (тот же IE, либо CEF)? С «палевом» проблем не будет, зато автоматизация многих действий должна стать значительно проще (честно, меня очень смутила реализация получения текстовых данных путем выделения мышью и копированием) + это будет одно окно, что визуально приятнее + есть возможность стрипнуть лишнее со страницы в принципе, во имя эстетики, конечно же :)

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

                                  И да, лучше не публикуйте исходники / продукт, игра будет обречена, либо придется переквалифицировать ее в соревнование ботов.
                                    +2
                                    Посмотрел видео — стоит шевелить кием, имитируя прицеливание, в момент калькуляции варианта удара (да и в целом перед ударом, это резко отличает вас от обычного игрока). Иногда расчеты занимают продолжительное время, а кий фиксирован, противник видит это. Решение не найдено, срабатывает ваш failback на последних секундах, кий резко переключается на запасной вариант и делает удар. Наличие 3-4 повторений этого сценария за игру уже ставит под сомнение «человечность» оппонента.
                                      0
                                      Классная идея. Спасибо!
                                      0
                                      Спасибо, обязательно буду стремиться к embedded browser.
                                      0
                                      У меня есть подозрение, что перебор позиций можно сильно ускорить (срезать дубли / учесть зеркальность) — это где рикошеты
                                        0
                                        По поводу ваших функций подгонки. Посмотрите в сторону логистической регрессии и как на её основе строят скоринговые модели.

                                        Only users with full accounts can post comments. Log in, please.