Пара шахматных скриптов

Safoyeth 4 Мар 2017

Сегодня я хочу оставить ещё парочку шпаргалок (в первую очередь для себя!). Речь пойдёт о шахматах, хотя всё это применимо и для любых других игр, в которых есть система соревнований и подсчёт рейтинга. Шпаргалки будут о том, как подсчитать рейтинг Эло и как провести турнир (или чемпионат) по круговой системе без каких-либо таблиц очерёдности.

Эло

Жил был такой умный американский (венгерского происхождения) профессор физики Арпад Эло, который создал (хорошую ли, плохую — о вкусах спорят) систему подсчёта рейтинга шахматистов. Много копий сломано на тему её объективности, праведности, корректности и много чего ещё, но сказать с уверенность сейчас можно одно — система используется в мире шахмат, го, сёги. Относительная простота системы позволяет адаптировать её под что угодно, главное, чтобы в игре участвовало два игрока (команды). Прочитать подробнее про рейтинг Эло можно хотя бы на википедии, мы же сразу перейдём к вычислениям.

Алгоритм расчёта рейтинга Эло такой:

Считаем математическое ожидание количества очков игрока А в партии с игроком В по такой формуле

E_A = \frac{1}{1 + 10^\frac{R_B - R_A}{400}} ,

где E_A — собственно математическое ожидание, R_A и R_B — рейтинги игроков А и В соответственно. Далее считаем само изменение рейтинга:

R'_A = R_A + K \cdot (S_A - E_A) ,

где R'_A — новый рейтинг игрока А, R_A — текущий его рейтинг, K — коэффициент, который эмпирическим (я так думаю) путём устанавливается равным 10, если шахматист имеет рейтинг выше 2400, 20, если его рейтинг меньше 2400 и 40, если он проводит первые 30 партий с момента получения рейтинга или он моложе 18 лет и имеет рейтинг ниже 2300 (да-да, прикольненько получается 😛 ). S_A — результат партии ( 1 - победа, \frac{1}{2} - ничья, 0 - поражение) и E_A - математическое ожидание, полученное выше.

То есть можно психануть и переписать всё в такую формулу:

R'_A = R_A + K \cdot (S_A - \frac{1}{1 + 10^\frac{R_B - R_A}{400}})

Соответственно, для игрока В алгоритм будет такой же.

Теперь давайте постараемся перевести непонятную математическую формулу в понятную функцию, написанную на питоне (а то, что-то я давно на нём не писал!). Собственно, сразу код:

Первым делом мы считаем ожидания для игроков (ea и eb) всё по той же формуле, затем пересчитываем рейтинги. Поскольку игроки могут иметь огромную разницу в рейтингах (2700 и 2300 к примеру), то мы должны позаботиться о разных коэффициентах (ka и kb).

Теперь можно прямо в интерпретаторе что-нибудь потестировать. Например, как-то так:

и мы получим

То есть, если слабый шахматист (в данном случае с неслабым рейтингом 2344) выигрывает у значительно превосходящего его по силам (в данном случае 2777), то он получает сразу 18 пунктов рейтинга, в случае ничейного исхода, слабый шахматист добавит себе 8 пунктов, а если он проиграет, то потеряет всего-лишь 2 пункта.

Совсем другая история у более сильного шахматиста. В данном случае человек с космическим рейтингом 2777 в случае победы над мастером (именно мастеру примерно соответствует такой рейтинг) получит лишь 1 пункт прибавки, в то время как при ничейном исходе он уже начнёт терять очки (в данном случае 4), поражение же и вовсе срезает 9 пунктов.

В этом и состоит идея Эло. Хорошо это или плохо — вопрос философский. Имеем то, что имеем. Скрипт для расчёта рейтинга Эло элементарен, но если кому-то лень его писать, лень вникать, то прошу! Решение готово к копипасту. Берите и допиливайте под свои нужды!

Создание расписания проведения турнира по круговой системе

Другая задача, которая может неожиданно возникнуть — турнир по круговой системе.

Круговая система — штука хорошая, вот только нужно как-то сделать так, кто, когда, с кем и каким цветом играет в случае шахмат/шашек и подобных игр. Или же, если это, скажем, футбол или хоккей, то кто играет дома, а кто в гостях. В принципе, в этом нет ничего особо сложного и при наличии листка бумаги и пишущего средства довольно быстро составляется таблица, которая заполняется особым хитрым образом (только адепты древних монашеских орденов, именуемые судьями, знают как именно 🙂 ). Вот тут показана эта магия (способ №3).

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

Оно не сказать, что изящно, зато работает. Мы просто генерируем список списков списков 🙂 а затем заполняем его по первому способу (тут). Если же у нас нечётное количество игроков, то мы просто добавляем ещё одного (с именемNone). Возвращаем мы кортеж просто для того, чтобы повысить читабельность. В итоге мы получаем кортеж, который содержит список туров. Каждый список туров содержит список партий. Проще показать на примере:

На выходе мы получим вот такое (немножко подправлено для красоты):

Ясно, что в первом туре нашего гипотетического турнира Крамник бы прохлаждался, зато в последнем его ждал бы Ананд. Последний тур получился бы примечательным ещё и из-за противостояния недавних соперников по матчу на первенство мира 🙂 .

Если бы у нас было 8 участников, а не 7 как сейчас, то просто вместо None была бы чья-то фамилия. Если хочется перемешать участников случайным образом, то random.shuffle вам в помощь.

У меня не было цели писать GUI, но, возможно, я это сделаю в будущем. Также мне хочется поэкспериментировать с cgi, поэтому в скором времени и расчёт Эло и построитель расписания (возможно даже с построением таблицы) появятся у меня на сайте. А пока всё!

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.




Добавить комментарий

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: