Замечания Сергея Полозкова

Вот текст по ссылкам из Википедии. С формулами.

Рейтинги и звания ФИДЕ

Примерное соответствие рейтингов Эло и мужских шахматных званий (женские эквиваленты званий считаются со скидкой в 100—200 пунктов в зависимости от звания), а также разрядов (здесь пол шахматиста не учитывается)[3]:

свыше 2750 — участник турнира претендентов на матч за звание чемпиона мира;
свыше 2500 — чемпион мира среди женщин;
свыше 2500 — международный гроссмейстер;
свыше 2400 — международный гроссмейстер среди женщин;
2400—2500 — международный мастер;
2200—2400 — международный мастер среди женщин;
2200—2400 — национальный мастер;
2000—2200 — национальный мастер среди женщин;
2000—2200 — кандидат в мастера;
1800—2000 — первый разряд;
1600—1800 — второй разряд;
1400—1600 — третий разряд;
1000—1400 — четвёртый разряд (средний любитель);
ниже 1000 — новичок.
В системе рейтингов Эло принято, что переход от одного класса игры к следующему происходит примерно через 200 пунктов рейтинга (начиная с игроков уровня первого разряда). Если различие между двумя игроками составляет 200 пунктов, то сильнейший игрок набирает в среднем около 0,76 очка за игру, если различие составляет 400 пунктов, то это среднее примерно равно 0,91. Различие в 600 пунктов означает, что сильнейший игрок выигрывает «почти» всегда (в среднем около 0,97 очка за игру). Если рейтинги обоих игроков равны, вероятность победы одного из них равна вероятности победы другого из них (что равносильно среднему количеству 0,5 очков за игру). Эти вероятности, конечно, не учитывают резко изменившуюся спортивную форму игрока в конкретный момент. Напротив, если сила игрока изменяется относительно медленно (в то время как игрок проводит статистически достаточно большое количество игр, учитываемых для изменения рейтинга), то рейтинг постоянно подстраивается под изменения силы игрока.

Чем стабильнее играет шахматист, тем точнее можно оценить его рейтинг. Наиболее точно рейтинг можно получить на основе турниров, в которых играют примерно равные по силам игроки.

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

Вычисляется ожидаемое количество очков рейтинга, которое получит игрок по формуле:

EA = 1 / ( 1 + 10 ^ ((RB-RA)/400) )
где:

EА — ожидаемое количество очков, которое наберёт игрок А
R_А — рейтинг игрока A;
R_В — рейтинг игрока B.

Stockfish — бесплатный шахматный движок с поддержкой UCI с открытым исходным кодом, доступный для различных настольных и мобильных платформ. Он разработан Марко Костальбой, Джоной Кийски, Гэри Линскоттом и Тордом Ромстадом, при большом вкладе сообщества разработчиков с открытым исходным кодом.

Stockfish последовательно занимает первое место или около вершины большинства рейтинговых списков шахматных движков и является сильнейшим обычным шахматным движком с открытым исходным кодом в мире.[3][4] Он выиграл неофициальный чемпионат мира по компьютерным шахматам в 6 сезоне (2014), 9 сезоне (2016), 11 сезоне (2018), 12 сезоне (2018), 13 сезоне (2018), 14 сезоне (2019) и 16 сезоне (2019). Он финишировал вторым в 5 сезоне (2013), 7 сезоне (2014) и 8 сезоне (2015).

Stockfish произошел от Glaurung, движка с открытым исходным кодом Торда Ромстада, выпущенного в 2004 году.

Рейтинг
По состоянию на 2020 год Stockfish является лидером рейтинг-листов шахматных движков.

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

Преимущество альфа-бета-отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа.

Число́ Ше́ннона — оценочное минимальное количество неповторяющихся шахматных партий, вычисленное в 1950 году американским математиком Клодом Шенноном. Составляет приблизительно 10120. Вычисление описано в работе «Программирование компьютера для игры в шахматы» (англ. «Programming a Computer for Playing Chess»), опубликованной в марте 1950 года в журнале Philosophical Magazine и ставшей одним из фундаментальных трудов в развитии компьютерных шахмат как дисциплины. В основу вычислений легло предположение о том, что каждая игра длится в среднем 40 ходов и на каждом ходе игрок делает выбор в среднем из 30 вариантов.[1] Для сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4⋅1079 до 1081, то есть в 1040 раз меньше числа Шеннона.

Кроме этого, Шеннон высчитал и количество возможных позиций, равняющееся примерно

64!/32!/(8!^2)/(2!^6)=
~10^43

Это число, однако, включает также ситуации, исключаемые правилами игры и поэтому недосягаемые в дереве возможных ходов. В настоящее время появился ряд работ, уточняющих или даже опровергающих это число.

По поводу двойной экспоненты объясните. Но компьютер просто обходит узлы дерева по обычной экспоненте.


====================================================


В шахматном ролике вы сказали, что КМС выигрывает у перворазрядника "почти всегда: в 90-95 процентов случаев". Это не так.

Разница между разрядами, в частности, между первым и КМС составляет в среднем 200 пунктов рейтинга ЭЛО. Первый разряд - это 1800-2000 пунктов, КМС - 2000-2200 пунктов. В статье Википедии "Рейтинг Эло" явно написано, что при разнице 200 пунктов сильнейший игрок набирает 0.76 очков за игру, а в разделе "вычисление рейтинга Эло" приведена формула:

EA = 1 / ( 1 + 10 ^ ((RB-RA)/400) )

EA - это ожидаемое количество очков, которое наберёт игрок А в партии с В.
RA - рейтинг А,
RB - рейтинг В.

Получаем КМС наберёт в среднем 0.76 очком с перворазрядником. (Очко за победу, 0.5 - за ничью, 0 - за поражение).

Также Вы говорили, что "компьютеры играют лучше нас за счёт того, что в них встроены нейронки". Ещё до появления сильных шахматных нейронок обычные движки, где рассматривается дерево ходов, значительно превзошли человека.

Даже сейчас нейронная сеть Leela Chess Zero играет на одном уровне с новейшей версией движка StockFish. Движки строят дерево ходов с альфа-бета отсечением и ещё используют всякие улучшения.

Так что компьютер играет лучше нас, так как он очень быстро просчитывает дерево ходов и никогда не зевает тактику.

Теперь про число неповторяющихся шахматных партий (число Шеннона). Оценка порядка 10^120 из предположения, что игра длится в среднем 40 ходов (глубина 80, так как играют оба). И на каждом ходе в среднем 30 вариантов. Так что экспонента простая, а не двойная с точки зрения обхода дерева для компьютерной программы (в статье про алгоритм альфа-бета отсечения).

Теперь ссылки на статьи в Википедии:
Рейтинг Эло

Stockfish - (сильнейший шахматный движок)

Альфа-бета-отсечение - (алгоритм поиска на дереве)

Число Шеннона

Ссылка на ролик и фразу про 90-95% и КМС