Викторина - это игра, в которой вам нужно ответить на 15 вопросов, чтобы выиграть соревнование. Это бразильское приложение, основанное на его американском брате HQ Trivia, которое стоит более 100 миллионов долларов.
В течение 15 минут десятки тысяч игроков встречаются в трансляции, чтобы побороться за призы, которые уже были получены в размере около 13500 долларов. Днем есть два тура: один утром, а другой - ночью. Также есть дополнительные туры по понедельникам, средам и пятницам.
На каждый вопрос дается всего 10 секунд, что делает невозможным использование некоторых поисковых систем вручную. Приз делится между всеми игроками, которые правильно ответят на все 15 вопросов.
Вдохновение
Встречаю Quize на работе, до этого я уже знал и играл в HQ Trivia. В тот же день, приехав домой, я уже начал писать первые строчки проекта, который впоследствии получил название Тита.
Примечание
Ни разу Тита не использовалась вживую, передачи записывались с помощью Vysor и после того, как использовалась Тита.
Первая версия
Моя первая версия Титы была создана за короткое время и сделала очевидное:
Был сделан отпечаток экрана, текст был извлечен с помощью PyTesseract, был выполнен запрос с вопросом, а затем я подсчитал появление ответов. Тот вариант, который получил наибольшую ценность, должен быть выбран для проверки.
Но ... я не хотел останавливаться на достигнутом, я хотел ускорить работу и повысить производительность.
Первый вызов
В качестве первой задачи я решил улучшить скорость и в то же время точность PyTesseract, после некоторого времени, прочитав документацию, я решил выполнить процесс определения пороговых значений в изображениях:
С пороговым значением я смог читать тексты быстрее и почти без ошибок (каждое чтение занимает около 400 мс).
После решения этой проблемы я приступил к созданию поисковой системы. Как я уже сказал, сначала я провел простой поиск, но она была недостаточно хороша.
Спустя некоторое время, создав хорошую поисковую систему, я построил 10 типов поиска, которые в основном сводятся к поиску ответов в Google, Википедии и на первой странице Google. Наряду с этим я также выполняю определенные преобразования в строках, чтобы улучшить поиск, например, применяя методы NLP (обработка естественного языка) для удаления стоп-слов, нахожу ключевое слово вопроса, удаляя символы и акценты и применяя технику выделения слов.
Благодаря этому я смог выполнить несколько поисков таким образом, чтобы извлечь сниппеты и точные ответы из Google.
Используя библиотеку BeatifulSoup, я смог искать супы по определенным идентификаторам каждого объекта:
· Прямой ответ - Z0LcW
При прямом ответе я получаю наилучший возможный ответ, из-за этого ваша оценка очень высока.
· Фрагмент - LGOjhe
С помощью фрагмента я получаю краткое изложение вопроса, во многих случаях я получаю удовлетворительный результат с моей системой подсчета очков.
Параллелизм
Из-за повышенной сложности проекта и отсутствия параллелизма задача определения времени отклика (‹10сек) была невозможна. Из-за этого пришлось написать функции параллельного поиска с использованием библиотеки Python Multiprocessing.
Благодаря этому я смог сократить время применения методов поиска до 1 ~ 1,5 секунды. Имея результат на руках, я решил распространить многопроцессорность на другие части потока Титы, я решил, что процесс захвата экрана будет разделен (раньше я просто делал снимок экрана и вырезал интересные части изображения) на 3 отпечатка в интересующие области (плюс выигрыш во времени ~ 300 мс для части захвата). Параллелизм также применялся во время лечения.
Окончательное время поиска составило около 4 секунд, от захвата, извлечения текста, преобразования текста, поиска, вычислений и возврата.
НЛП
Некоторые преобразования заслуживают особого внимания, например:
· Удаление общих слов между двумя ответами;
· Удаление спецсимволов и акцентов;
· Стемминг;
· Удаление стоп-слов.
Система оценок
Чтобы лучше организовать различные результаты из 10 поисковых запросов, я построил систему оценок, в зависимости от их важности, я создал константу, которая умножает количество ответов в результатах исследования.
Я решил, что оценка для прямого ответа будет максимально возможной, точнее 10 000 000, для каждого нормального события на странице, которое я умножу на 300 и т. Д. Важная деталь для расчета K_Search, алгоритма, который я построил для увеличения эффективность поиска рассчитывается следующим образом:
(Встречаемость * (количество слов)) ^ (количество слов + 1)
Например:
Предложение «Снова нормальный» появляется 13 раз в данном тексте, а слово «Нормальный» встречается 18 раз в том же тексте.
Оценка за первое предложение: (13 * 2) ³ = 17576.
Оценка второго предложения: (18 * 1) ² = 324.
Таким образом, я смог создать большую силу для правильных комбинаций слов и избежать вычисления бессмысленных слов для желаемых.
K_Search
K_Search - это домашний алгоритм Титы, сначала я создаю все возможные комбинации каждого ответа, например, для предложения «Felype Castro Bastos» будут созданы такие комбинации:
Для каждой сгенерированной комбинации я выполняю поиск в BeatifulSoup и делаю пунктуацию, как описано в предыдущем разделе, придавая большее значение общей комбинации. Если в тексте есть комбинация клавиш «Felype Castro Bastos», уровень оценки будет максимальным!
Этот алгоритм работает в различных точках поиска, будь то страница Google, Википедия или даже первая страница, найденная в Google.
Телеграмма
Наряду со всем этим я также решил создать бота в Telegram, который будет отвечать за передачу мне выбранных ответов, поскольку я решил не использовать Tita в каких-либо живых играх, созданных исключительно в дидактических целях.
Поток
Финальный поток проекта выглядит так:
1. Существует автоматический захват проблемы путем определения изменения среднего цвета пикселей в изображении (есть постоянный захват изображения).
2. После захвата изображения становятся пороговыми и поэтому преобразуются в текст.
3. Сохраняется исходная форма вопросов и ответов.
4. Применяются основные преобразования, удаление специальных символов и перевод слов в нижний регистр, а также удаление общих слов между двумя ответами.
5. Все супы нужны для поиска, примерно 6 супов, предоставляемых Google, Википедией, первой страницей и т. Д.
6. После этого в каждом методе поиска выполняются определенные преобразования и выполняются поиски.
7. Я возвращаю список списков, содержащих оценку каждой техники.
8. Я складываю баллы, присвоенные каждому ответу, и после этого нормализую, оставляя окончательный результат: Ответ 1 = 98%, Ответ 2 = 2%.
9. Фрагмент (если есть), правильный ответ (если есть), вектор оценки и наиболее подходящий ответ на заданный вопрос отправляются в Telegram.
10. Цикл начинается, и ожидается следующий вопрос.
Заключение
Я сгенерировал фреймворк ровно со 100 вопросами и поехал на Титу по всем из них.
Было всего 5 ошибок, в основном вопросы, требующие большей интерпретации, чем ручной поиск (сцены из следующих глав).
Вопросы она пропустила:
1. Бастилия была парижской крепостью, которая использовалась как государственная тюрьма во Франции?
2. Кого из этих персонажей знали сотрудники: «Прав я или нет?»
3. Используется ли термин «постепенно» для описания вещей, которые делаются медленно, медленно?
4. Какой главный музыкальный приз в мире?
5. Сколько Гран-при Формулы-1 выиграл гонщик Айртон Сенна?
Очевидно, что нельзя с уверенностью сказать, что точность составляет 95%, однако во всех играх, в которых она тестировалась, в среднем было 2–3 ошибки за игру, что на практике составляет около 84%, хотя в некоторых случаях это было не так. можно проверить невооруженным глазом ответ с помощью фрагментов.
Еще один полезный механизм - это прыжки, которые можно использовать в периоды воздержания или небезопасности.
Будущее
Так как я из области машинного обучения и увлечен искусственным интеллектом (в настоящее время изучаю в университете генетические алгоритмы и практикую в этой области), я намерен сделать Титу более «гуманной», особенно ее способность интерпретировать вопросы и находить ответы более точными. Меня очень сильно вдохновляет суперкомпьютер IBM Watson, который использовался, чтобы превзойти людей в игре Jeopardy в 2011 году.
