Pull to refresh

Tim Salimans o выигрыше в конкурсе предсказаний результатов шахматных партий от Kaggle

Reading time4 min
Views4.2K
Original author: Tim Salimans
Kaggle организует соревнования для людей, которые занимаются data mining. Сейчас открыты два конкурса. Один на 3 миллиона долларов, цель которого улучшить систему, по которой людей кладут в больницы. Второй — с призовым фондом 3000 долларов, чтобы улучшить измерения эллиптичности галактик, что позволит лучше измерить так называемую «темную материю» во вселенной.

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

Участникам конкурса предоставлялись результаты более 1,84 миллиона встреч более чем 54.000 шахматистов. Задача была предсказать результаты 100.000 игр между этими же шахматистами за следующие три месяца. В конкурсе приняли участие 189 команд.

Далее от первого лица.

Меня зовут Tim Salimans, я аспирант эконометрики в Erasmus University Rotterdam. Для своей работы я постоянно работаю с данными, моделями и алгоритмами, и конкурсы от Kaggle оказались интересным способом, чтобы использовать эти навыки в социальной и конкурентной среде. Конкурс от Kaggle, Delloitte и FIDE по предсказанию результатов шахматных соревнований был первым, в котором я учавствовал, и мне очень повезло, что я занял первое место. В то же самое время я использовал платформу Kaggle-in-class, для того чтобы проводить конкурс курса по эконометрике, где я был ассистентом. Оба конкурса были очень интересными. В этом посте я рассказываю не технические детали шахматного конкурса. Если вас интересуют технические детали, включая мой код, смотрите мою веб-страницу.

Рейтинг в шахматах

Перед тем как начать решать новую задачу хорошо посмотреть, что другие люди делали до вас. Так как Kaggle уже проводил конкурс по улучшению системы рейтинга, логично было посмотреть блог-посты победителей. После чтения этих постов и различной академической литературы, я понял, что система рейтингов в шахматах предполагает, что характеристики каждого игрока могут быть описаны одним числом. Предполагаемый результат матча между двумя игроками тогда — некая фунцкия разницы между их рейтингами. Yannis Sismanis, победитель первого конкурса, для этой цели использовал логистическую кривую и оценивал рейтинг, минимизируя регуляризированную версию модели (в деталях о его подходе можно прочесть в статье размещенной на arxiv). Jeremy Howard, занявший второе место, вместо этого использовал модель TrueSkill, которая использует нормальную фунцкию распределения и оценивает рейтинг через Байесовский вывод.

Я решил начать с TrueSkill, и расширить ее ограничивая рейтинг каждого игрока рейтингами его недавних соперников, похоже на то как Yannis Sismanis сделал в первом конкурсе. Кроме того я ввел веса в алгоритм, что позволило мне сделать более недавние матчи более значимыми для рейтинга. После нескольких экспериментов, используя отличный пакет Infer.NET от Microsoft, я написал весь код в Matlab.

Использование расписания матчей

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

Для того чтобы использовать такую информацию из расписания, я сгенирировал предсказания за последние 1,5 года, используя окно в 3 месяца. Затем, я сделал два шага пост-обработки используя эти предсказания и настоящие результаты матчей. Первый шаг использовал стандартную логистическую регрессию, а второй шаг использовал вариацию логистической регрессии со взвешенными локальными весами. Наиболее важными переменными в процессе пост-обработки были:
  • предсказания основной модели
  • рейтинг игроков
  • число матчей каждый игрок играл
  • рейтинг соперников каждого игрока
  • вариация качества встреченных игроков
  • среднее предсказание процента побед во всех матчах в одном месяце для каждого игрока
  • предсказания Random forrest для этих переменных

Эта пост-обработка значительно улучшила мой рейтинг в турнире и я хорошо оторвался от других участников. Позже, другие участники сделали похожие улучшения и последние недели соревнования были очень интересными. После длинных выходных я зашел на страницу рейтинга и обнаружил, что меня обошла команда PlanetThanet. Чуть подправив свой подход, у меня получилось вновь выйти на первое место. После этого я должен был ехать на конференцию в США. По прибытию я узнал, что меня вновь обошли, на этот раз Shang Tsung. Только послав последнее предсказание из номера в отеле Сент-Луиса, я окончательно смог заполучить первое место.

Заключение

Наибольший вклад в победу внесло использование расписания матчей. Хотя интересно само по себе, это не идеально для изначальной цели соревнования — улучшить систему рейтинга шахматистов. К моему облегчению, набор данных, который Jeff Sonas выложил позднее показал, что моя модель делает хорошие предсказания без использования этой информации. В заключении, я хотел бы поблагодарить и организаторов, и участников конкурса за отличное мероприятие.
Tags:
Hubs:
Total votes 4: ↑4 and ↓0+4
Comments5

Articles