Меню Рубрики

Задача кто сколько очков набрал шахматный

Задание 19. В турнире по шахматам принимают участие мальчики и девочки. За победу в шахматной партии начисляют 1 очко, за ничью — 0,5 очка, за проигрыш — 0 очков. По правилам турнира каждый участник играет с каждым другим дважды.

а) Каково наибольшее количество очков, которое в сумме могли набрать девочки, если в турнире принимают участие пять мальчиков и три девочки?

б) Какова сумма набранных всеми участниками очков, если всего участников девять?

в) Сколько девочек могло принимать участие в турнире, если известно, что их в 9 раз меньше, чем мальчиков, и что мальчики набрали в сумме ровно в четыре раза больше очков, чем девочки?

а) Первая девочка играет с 5 мальчиками и 2 девочками, то есть проводит 7 игр по 2 раза. Вторая девочка играет с 5 мальчиками и 1 девочкой (обратите внимание, что игру со второй девочкой уже учли ранее), то есть проводит 6 игр по 2 раза. Третья девочка играет с 5 мальчиками (все остальные игры с двумя девочками уже учтены), то есть проводит 5 игр по 2 партии. Таким образом, всего девочки проводят 7+6+5=18 игр и играют по 2 партии, то есть партий. За одну партию девочка максимум может получить 1 очко. Следовательно, максимальное количество очков, которое могут получить девочки, равно 36.

б) При участниках, общее число возможных пар равно

,

каждая пара играет по 2 раза, то есть играется 72 партии. В каждой партии максимум зарабатывается одно очко. Следовательно, максимальное число очков равно 72.

в) Обозначим через число девочек, тогда мальчиков будет , и всего участников . Общее число пар, которые образуют девочки, определяется формулой , и так как проводится по 2 партии на каждой встрече, то общее число партий для девочек, равно

Общее число очков, которые заработали и мальчики и девочки, равно

,

и так как мальчики заработали в 4 раза больше очков, чем девочки, то данная величина соотносится как 4:1, то есть число очков девочек составляет

,

откуда имеем два решения: и . Так как число девочек должно быть больше 0, то имеем ответ 1 девочка.

источник

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

(две нетрудные и одна потруднее)

1)
На шахматном турнире для 12 участников каждый сыграл ровно по одной партии с каждым из остальных. За выигрыш давали 1 очко, за ничью , за проигрыш 0. Вася проиграл только одну партию, но занял последнее место, набрав меньше всех очков. Петя занял первое место, набрав больше всех очков. На сколько очков Вася отстал от Пети?

2)
16 шахматистов провели между собой турнир: каждые два шахматиста сыграли ровно одну партию. За победу в партии давался 1 балл, за ничью — 0,5 балла, за поражение — 0 баллов. Оказалось, что ровно 15 шахматистов поделили первое место. Сколько очков мог набрать шестнадцатый шахматист?

3)
В шахматном турнире участвовали 8 шахматистов, причём каждый сыграл с каждым
ровно по одной партии. Известно, что любые два шахматиста, сыгравшие между собой
вничью, набрали в итоге разное число очков. Найдите наибольшее возможное число ничьих в
этом турнире. (За выигрыш партии шахматисту начисляется 1 очко, за ничью – 1/2 очка,
за поражение – 0.)

Последний раз редактировалось Yadryara 15.05.2016, 22:35, всего редактировалось 2 раз(а).

Никто не хочет решать? Ну попробую.

На очко. Нетрудно показать, что другое преимущество невозможно.

Вася мог набрать только очков, сведя все остальные партии вничью, поскольку результат главного лузера должен быть строго меньше 50% от возможного количества очков.

Всего разыгрывалось очков. И расклад только один: Петя набрал . Ещё человек набрали по .

Видимо ровно одну партию между собой ?

Тогда разыгрывалось всего очков.

Заслуженный участник

Заслуженный участник

Последний раз редактировалось Yadryara 16.05.2016, 14:13, всего редактировалось 6 раз(а).

3. 20 ничьих. Расклад будет чуть позже.

1-й проиграл 2-му
1-й проиграл 3-му
1-й проиграл 4-му
1-й выиграл у 5-го
2-й выиграл у 5-го
2-й выиграл у 6-го
3-й выиграл у 6-го
6-й выиграл у 7-го

Всего сыграно турнирных партий. боевых и ничейных.

1-й —
2-й —
3-й —
4-й —
5-й —
6-й —
7-й —
8-й —

Заслуженный участник

Сейчас этот форум просматривают: нет зарегистрированных пользователей

источник

И снова здравствуйте, дорогой друг!

Собственно ответ на вопрос: как получить разряд по шахматам , — не так уж и сложен. Самое простое: сыграть в турнире, который будет обсчитываться уполномоченной на это организацией, и показать соответствующий результат. То есть набрать определенное количество очков.

При этом важно помнить, что прежде всего важно научиться хорошо играть. В этом, как нельзя лучше, — вам помогут наши программы подготовки шахматистов.

Раньше, когда тема выполнения разряда была актуальна для автора этих строк, а это было в 70-80 годах прошлого столетия, — система была многоступенчатой.

Сегодня все проще гораздо. Ключевую роль играет рейтинг. Выполнить разряд по шахматам можно за один турнир.

Правила выполнения разрядов взяты мной не из головы, разумеется. Существуют законодательные нормы, изложенные в следующем документе, актуальном на конец 2016г.

Если есть желание ознакомиться с этим документом полностью, ссылка здесь

Я же акцентирую ваше внимание на моментах по теме нашей статье.

Квалификационная иерархия в шахматах выглядит следующим образом:

Гроссмейстер, международный мастер, мастер спорта, кандидат в мастера, 1 разряд, 2 разряд, 3 разряд , юношеские разряды: также 1, 2 и 3.

Важно, что разрядами принято считать все, что ниже мастера спорта. Гроссмейстер, Международный мастер, Мастер спорта, – это уже звания.

То есть, шахматисты от третьего разряда до КМС — это шахматисты-разрядники, мастера спорта и выше – имеют соответствующее шахматное звание.

Кстати, с недавнего времени в шахматы вернули и юношеские разряды. Их также три: третий, второй и первый.

Схема выполнения аналогична для всех разрядов. Разница только в рейтингах турниров.

Например, вы решили выполнить 1 разряд.

  • Сыграть в турнире со средним российским рейтингом не менее 1701 пункта. Это видно из таблицы.
  • Сыграть не менее:

а) 9 партий, если играете в классические шахматы по круговой или швейцарской системе. 8 партий, если турнир с выбыванием

б) 11 партий для быстрых шахмат

в) 7 партий для командных турниров

  • Набрать в турнире определенный процент очков от максимально возможного. Причем в фактически состоявшихся партиях. Неявки соперников не в счет.

В турнире со средним рейтингом в диапазоне 1701—1725 – 75% от максимально возможного количества очков.

2 разряд и 3 разряд – схема абсолютно аналогична, полагаю на рисунке все видно и достаточно понятно.

Для выполнения нормы кандидата в мастера:

О количестве участников мы уже говорили чуть выше. То есть, если для выполнения нормы вам нужно сыграть 9 партий, — в турнире должны участвовать 10 человек, включая вас.

Где получить разряд?

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

Сведения о выполнении разрядов и рейтингов передаются в российскую шахматную федерацию. Международные рейтинги присваивает ФИДЕ, сведения туда подаются по этим же инстанциям.

На практике квалификационные турниры организуются городскими шахматными клубами, которые находятся в ведении соответствующего регионального спортивного органа. Областного Спорткомитета например. Если вам нужны корочки, – порядок их выдачи уточните у организаторов турнира.

Еще несколько рекомендаций:

Полагаю, вы обратили внимание: чем выше средний рейтинг турнира, тем меньше очков вам нужно набрать для выполнения разряда .

Например, для выполнения первого разряда в турнире из 16 человек со средним рейтингом 1720 вам нужно набрать 75% очков. В пересчете это 15*0.75 = 11,25 очка. Округляется всегда в большую сторону, то есть 11,5 очков. Или, как говорят шахматисты, — «плюс 8». Расклад может быть такой: 8 партий выиграл и семь ничьих.

Для сравнения: в турнире со средним рейтингом 1880 вам достаточно 40%. При тех же 16 игроках это 6 очков. Или «минус три».

Логика подсказывает: казалось бы, чем сильнее турнир, тем лучше. Меньше очков надо набрать для получения разряда. Логика в целом верна, однако не все так однозначно. Чем выше рейтинг, тем сильнее игроки.

Представьте, что в турнире играют одни Крамники и Карякины. Сколько очков вы наберете?

Так что, в этом вопросе выбор за вами.

Еще момент: Если у участника турнира нет рейтинга, ему ставится рейтинг равный 1000. Это может существенно снизить средний рейтинг турнира.

Соответственно вам придется набирать большее количество очков, чтобы выполнить разряд. Старайтесь выбирать турниры, где таких «темных лошадок» нет.

Если не получилось выполнить с первого раза, ничего страшного. Это дело времени при хорошей игре.

Есть такой вид шахмат, как игра по переписке. Это и есть дистанционно .

В игре по переписке также существует квалификационная система, похожая на ту, которую мы разобрали выше. Например:

Подробнее можно посмотреть по ссылке, указанной в начале статьи. Под пунктом 6.

Есть и специальные турниры для «заочников».

Однако это другой вид шахмат, дисциплина «заочные шахматы». Процедура присвоения разрядов аналогична очной, — через уполномоченные организации. Сегодня мы не будем подробно обсуждать шахматы по переписке. Это тема для отдельной статьи.

Играя через интернет, онлайн , — также можно участвовать в квалификационных турнирах. Например здесь . Такие турниры считаются «заочными шахматами» и проводятся соответственно по правилам заочных шахмат.

Как видите, получить разряд по шахматам вполне реально. Как ребенку , так и взрослому . При одном условии. Важно научиться хорошо играть.

Читайте статьи на нашем блоге, играйте, работайте над ошибками и повышайте свое мастерство. А рейтинг и разряд не заставят себя ждать.

Благодарю за интерес к статье.

Если вы нашли ее полезной, сделайте следующее:

  1. Поделитесь с друзьями, нажав на кнопки социальных сетей.
  2. Напишите комментарий (внизу страницы)
  3. Подпишитесь на обновления блога (форма под кнопками соцсетей) и получайте статьи к себе на почту.

источник

Среди систем, по которым проводятся шахматные соревнования, наиболее распространены следующие: олимпийская, швейцарская, круговая, матчевая, схевенингенская54, и каждая из них имеет свои математические особенности.

В турнирах, проводимых по олимпийской, или кубковой, системе проигравшие сразу выбывают из борьбы, и поэтому элемент случайности здесь наиболее велик. Такая система хороша для тех, кто любит играть по оринципу «или все, или ничего».

В кубках как бы считается, что если шахматист А играет сильнее Б, а Б, в свою очередь, сильнее В, то и А играет сильнее В, т. е. что отношение между силой шахматистов, как говорят математики, транзитивно. Однако на орактике дело обстоит далеко не так. Например, чемпион мира Ласкер постоянно выигрывал у Чигорина, Чигорин побеждал Пильсбери, а Пильсбери имел перевес в счете с Ласкером. А вот пример аналогичного нарушения транзитивности для современных шахматистов: Фишер имеет оеревес в личных встречах с Ларсеном, Ларсен * — с Геллером, а у Геллера перевес в счете против Фишера. Из сказанного, в частности, следует, какую большую роль в кубке играет жребий…

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

В розыгрыше кубка города участвуют n шахматистов. Предварительно проводятся кубки районов, и победители уже разыгрывают главный кубок (противники играют по одной партии, и при ничьей белые выбывают). Сколько партий нужно сыграть, чтобы определить обладателя кубка города, если в нем р районов с числом шахматистов n1, n2, …, np?

Для решения задачи достаточно заметить, что поело каждой партии из борьбы-выбывает ровно один участник. Так как в конце концов из n шахматистов, разыгрывающих кубок, выбывают (n — 1) — все, кроме победителя, то всего будет сыграна (n — 1) партия. Таким образом, ответ не зависит ни от числа районов в городе, ни от распределения шахматистов в них.

Преимущество олимпийской системы заключается в большом числе шахматистов, которые могут одновременно играть в турнире (точнее, начать его). Тем же достоинством обладает и швейцарская система, которая имеет еще один плюс — проигравшие здесь не выбывают. Эта система обычно применяется в турнирах с числом участников, большим 20. При этом 10 — 13 туров, как правило, хватает, чтобы определить достойных победителей. Напомним, например, что XXXV юбилейный чемпионат страны (Харьков, 1967 г.) проходил по швейцарской системе; в нем играло 130 шахматистов (в 13 туров), и чемпионами стали М. Таль и Л. Полугаевский.

Перед началом турнира по швейцарской системе проводится жеребьевка. В первом туре встречаются номера 1 и 2, 3 и 4 и т. д., причем нечетные номера играют белыми. В последующих турах, опять же по жребию, между собой играют участники, имеющие одинаковое количество очков. Если в одной «очковой» группе число участников нечетно или их не удается разбить на пары так, чтобы партнеры каждой пары встречались впервые, то «смешивают» соседние группы. При жеребьевке стремятся к тому, чтобы участники чередовали цвет фигур.

Самая распространенная и объективная система проведения шахматных соревнований — круговая, при которой все участники турнира встречаются друг с другом. Иногда, чтобы элемент случайности свести к минимуму, турнир проводят в два или даже большее число кругов. Порядок встреч по турам и цвет фигур, которым играют шахматисты в круговом турнире, зависит только от номеров его участников (получаемых ими при жеребьевке) и указывается в специальных таблицах, составленных немецким шахматистом Й. Бергером. Несложный математический анализ этих таблйц позволяет вывести простые правила для нахождение номера тура,, в котором встречаются противники, и цвета их фигур. Укажем эти оравила для турнира с четным числом участников n.

Если номера обоих участников отличны от n, то сложим их. Номер тура получается при вычитании из этой суммы 1, если она не превосходит n, и вычитании n, если она больше n. Если сумма нечетна, то белыми играет меньший номер, а если четна, то — больший. Например, ори десяти участниках второй номер с пятым играет белыми в 6-м туре (2 + 5 = 7 — нечетное число, меньшее 40; 7 — 1 = 6), а шестой номер с восьмым играет черными в 4-м туре (6 + 8 = 14 — четное число, большее 10; 14 — 10 = 4).

Расписание встреч последнего номера отличается от остальных. Чтобы узнать, в каком туре он играет с данным участником, удвоим номер этого участника. Теперь из результата надо вычесть 1, если он не больше n, и вычесть n, если больше. При этом с первой половиной номеров последний участник играет черными, а со второй — белыми.

Если число участников n нечетно, то добавлением «фиктивного» участника с номером n + 1 мы перейдем к уже разобранному случаю. При этом встреча с «фиктивным» партнером попросту означает, что в соответствующем туре шахматист свободен от игры. При четном n участники первой половины турнирной таблицы играют на одну партию белыми больше (за счет «белой» партии с последним номером), и поэтому при жеребьевке шахматисты предпочитают вытягивать номера от 1 до n/2.

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

Всякий закончившийся круговой турнир полностью характеризуется графом, вершины которого соответствуют участникам турнира, а ребра — встречам между ними. Такой граф содержит n вершин и C 2 n ребер и называется полным. Если партия результативна, то соответствующему ребру можно приписать стрелку, направленную от победителя к побежденному. Графы такого типа (и их обобщения) называются графами турниров, их исследованию посвящено довольно много серьезных работ.

Читайте также:  Что за слово футбол девочка очки

О круговых турнирах составлено множество математических и логических задач. Конечно, в их формулировке можно использовать различные виды спорта, но предпочтение почти всегда отдается шахматам. Рассмотрим несколько таких задач.

Всего в круговом турнире было сыграно 55 партий. Два участника выбыли из него, один успел сыграть 10 партий, а другой — одну. Встречались ли эти шахматисты между собой?

Пусть n — число участников турнира, тогда (n — 2) шахматиста, закончившие турнир, сыграли между собой (n — 2)(n — 3)/2 партий. А два интересующих нас шахматиста провели 10 или 11 встреч — в зависимости от того, сыграли между собой или нет. Таким образом, надо рассмотреть два квадратных уравнения:

(n — 2)(n — 3)/2 + 10 = 55 и (n — 2)(n — 3)/2 + 11 = 55.

При этом нас интересуют лишь целые и положительные значения n. Такое решение (n = 12) имеет лишь первое уравнение, откуда и следует, что указанная партия состоялась.

Для тренировки шахматист играет не менее одной партии в день и, чтобы не переутомиться, не более 12 партий в неделю. Доказать, что можно найти несколько дней подряд, в течение которых он сыграет ровно 20 партий.

Так как шахматист играет не более 12 партий в неделю, то за 77 дней он проведет не более 132 встреч. Пусть аi — число партий, сыгранных им за i дней, начиная с первого. Поскольку каждый день играется хотя бы одна партия, то среди чисел а1, a2, …, а77 нет равных, причем а77 ≤ 132.

Осталось убедиться, что среди этих чисел найдется хотя бы одна пара таких, разность между которыми равна 20. Если это не так, то среди следующих 153 чисел: а1, а2, …, а77, а1 + 20, …, a76 + 20 также нет равных. Это означает, что а76 + 20 ≥ 153, т. е. а77 > а76 ≥ 133 — противоречие. По существу, мы здесь использовали так называемый принцип Дирихле, утверждающий, что если в каждую клетку сажать не более одного зайца, то разместить шесть зайцев в пяти клетках невозможно.

В турнире играло n шахматистов — гроссмейстеров и мастеров. После его окончания оказалось, что каждый участник половину очков набрал, играя с мастерами. Доказать, что √ n — целое число.

Пусть а — число мастеров, а b — гроссмейстеров. Мастера между собой разыграли а(а — 1)/2 очков, а так как это половина всех их очков, то столько же они набрали с гроссмейстерами. Аналогично гроссмейстеры, как между собой, так и с мастерами, набрали b(b — 1)/2 очков. Из того, что число партий между старшим и младшими по званню равно аb, получаем (а — 1)/2 + b(b — 1)/2 = ab или, после упрощений, а + b = (а — b)². Так как n = а + b, то √ n = √ a + b = |а — b| — целое число, что и требовалось доказать.

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

Воспользуемся методом математической индукции. Для двух участников утверждение очевидно. Предположим теперь, что оно верно для произвольного турнира с к участниками. Покажем, что в этом случае в требуемом порядке можно расположить и k + 1 участников. Расположим нужным образом произвольных k из них (по предположению это можно сделать) и посмотрим, как (k + 1)-й сыграл с первым. Если он выиграл или сыграл вничью, то поставим его на первое место, а если проиграл, то посмотрим, как он сыграл со вторым и т. д. Если мы в конце концов найдем среди упорядоченных k участников такого, у которого (k + 1)-й выиграл (а предыдущему проиграл), то поставим (k + 1)-го перед ним, в противном случае поставим его на последнее место. В результате все k + 1 участника будут расположены в необходимом порядке.

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

Пусть каждая команда состоит из n шахматистов. В этом случае схевенингенский турнир продрлжается ровно п туров. Для n = 6 возможное расписание турнирг представлено на рис. 73, причем оно легко обобщается для любого n. Здесь строки таблицы соответствуют участникам первой команды, а столбцы — участникам второй. Номер тура, г котором играют между собой данные противники, стоит в клетке, лежащей на пересечении соответствующей строки и столбца, а цвет фигур (участников первой команды) определяется цветом этой клетки.

Каждый столбец и каждая строка квадрата, выделенного на рис. 73, содержат все числа от 1 до 6, расположенные в том или ином порядке. В общем случае строки и столбцы квадрата содержат все числа от 1 до n. Такой квадрат в комбинаторном анализе называется латинским квадратом порядка п. (Эйлер, который исследовал эти квадраты, вместо чисел пользовался латинскими буквами, чем и объясняется название таких квадратов.) Ясно, что всякий латинский квадрат порядка n, клетки которого окрашены в черно-белый цвет, дает некоторое расписание схевенингенского турнира для двух команд, состоящих из n шахматистов.

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

Организаторы товарищеского матча СССР — Югославия, состоявшегося в 1970 г., попытались найти расписание (для мужских команд, состоящих из шести человек каждая), удовлетворяющее сразу трем следующим, довольно естественным, условиям:

1) все шахматисты играют одинаковое число партий белыми и черными;

2) в каждом туре участники обеих команд играют одинаковое число партий белыми и черными;

3) все шахматисты в каждом туре меняют цвет фигур.

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

Очевидно, следует рассматривать только четные n, так как в противном случае одновременно нарушаются первые два условия.

Если все участники команды в каждом туре играют одним цветом (как в расписании на рис. 73), то условие

3) выполняется, а условие 2) — нет. Однако условия 2) и 3) одновременно выполняться не могут. Действительно, если имеет место условие 2), то найдутся хотя бы два представителя разных команд, которые уже в первом туре играют одним цветом. Так как по условию 3) эти шахматисты в каждом туре должны менять цвет фигур, то они до конца турнира не встретятся между собой!

Будем считать условие 2) более важным и ради него откажемся от условия 3) (организаторы упомянутого матча именно так и поступили). Теперь надо выяснить, существует ли расписание схевенингенского турнира, удовлетворяющее только первым двум условиям. Перед началом матча СССР — Югославия организаторы попытались найти такое расписание, но у них ничего не вышло.

Предположим, что клетки некоторого латинского квадрата порядка n можно раскрасить в черный и белый цвета так, чтобы одновременно выполнялись следующие два условия;

а) в каждом столбце и в каждой строке квадрата содержится одинаковое число белых и черных клеток;

б) половина всех клеток квадрата, в которых записано одно и то же число (любое), окрашена в белый цвет, а половина — в черный.

Раскрашенный указанным образом латинский квадрат дает расписание «схевенингена», удовлетворяющее условиям 1) и 2) — для команд, состоящих из n шахматистов. Действительно, из а) непосредственно следует справедливость условия 1), а из б) — условия 2).

Итак, возникает следующая чисто математическая задача, эквивалентная нашей задаче о составлении расписания.

При каких n (четных) существует латинский квадрат порядка n, клетки которого можно раскрасить в черный и белый цвета так9 чтобы одновременно выполнялись условия а) и б)?

Введем еще одно понятие, связанное с латинскими квадратами. При наложении одного такого квадрата на другой (оба порядка n) получаются n² пар чисел, стоящих на одинаковых местах — первое число пары берется из первого квадрата, а второе — из второго квадрата (пары, отличающиеся порядком чисел, считаются различными). Два латинских квадрата порядка n называются ортогональными, если все n² пар чисел, возникающих при наложении, отличаются друг от друга. Например, латинские квадраты четвертого порядка на рис. 74 ортогональны, так как при наложении одного из них н а другой все n² = 16 пар чисел различны.

Покажем, что если существуют два ортогональных латинских квадрата порядка n (n четно), то каждый из них можно раскрасить так, чтобы выполнялись условия а) и б).

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

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

Итак, задача о шахматном турнире неожиданно привела нас к одному из интереснейших разделов комбинаторного анализа — теории латинских квадратов! Проблема существования ортогональных латинских квадратов в общем случае не поддавалась разгадке около 200 лет. Лишь в 1960 г. было, наконец, доказано, что ортогональные квадраты существуют для всех n, не равных 2 и 6. Из этого результата вытекает, в частности, что не имеет решения известная задача Эйлера о 36 офицерах: в клетках квадрата 6×6 разместить делегации от 6 полков, состоящие из шести офицеров разного звания, так, чтобы ни в одном горизонтальном и вертикальном ряду не повторялись ни полк, ни звание. Действительно, эта задача эквивалентна задаче нахождения пары ортогональных квадратов шестого порядка, а такой пары не существует.

Теперь мы знаем, что для любой пары команд, состоящих из четного числа шахматистов (но не из двух и не из шести!) существует расписание схевенингенского турнира, удовлетворяющее условиям 1 и 2. Однако в упомянутом матче СССР — Югославия каждую страну (на мужских досках) представляло именно шесть человек, и поэтому наша проблема снова остается открытой. В самом деле, при n = 2 или n = 6 мы не можем утверждать, что расписание имеется, хотя и нет оснований утверждать обратное (во всяком случае, из отсутствия ортогональных квадратов это не следует).

Простой перебор показывает, что для n = 2 нужное расписание составить невозможно. Что же касается интересующего нас случая n = 6, то здесь ручной перебор вариантов чрезвычайно велик. Чтобы «закрыть» проблему, математик и шахматный мастер А. Битман решил прибегнуть к помощи ЭВМ. Предварительно из всех латинских квадратов шестого порядка он отобрал лишь 22 так называемых неизоморфных (остальные получаются из них перестановкой строк и столбцов и ничего нового не дают). Машине предстояло «раскрасить» эти 22 квадрата всевозможными способами и выяснить, существуют ли раскраски, удовлетворяющие условиям а) и б).

В результате в 16 случаях из 22 ЭВМ обнаружила необходимую раскраску. Таким образом, искомое расписание схевенингенского турнира было найдено! Одно из них показано на рис. 75 (в отличие от рис. 74,г в данном случае раскраска не является шахматной). Это расписание примечательно еще и тем, что здесь никто из шахматистов не играет более двух партий подряд одним цветом. Поскольку полного чередования цвета, как мы знаем, добиться невозможно, то расписание на рис. 75 можно считать идеальным.

54. От названия голландского города Схевенинген; в шахматной литературе эту систему часто (хотя и не точно) называют шевенингенской, или, кратко, шевенинген.

55. Исчерпывающее решение ряда таких задач приведено в журнале «Квант», 1972, № 8.

источник

Помогите решить задачи по математике для 8 класса. Будет олимпиада по логика-математическим задачам и сами не можем решить. Для минусов вн

1. Полная стоимость доставки мебели больших габаритов в фирме по перевозке складывается из стоимости её доставки к дому и стоимости подъёма мебели на необходимый этаж. Стоимость подъёма мебели на каждый следующий этаж превышает стоимость её подъёма на предыдущий на одну и ту же величину. Найдите полную стоимость доставки мебели на 11-й этаж дома, если известно, что Петровым, живущим на 4-м этаже, доставка мебели обошлась в 890 руб., а Ивановым, живущим на 7-м этаже, доставка мебели из той же фирмы, — в 980 руб.
А. 950 руб. Б. 1000 руб. В. 1100 руб. Г. 1150 руб.

2. Группа из пяти мальчиков: Андрея, Бориса, Василия, Григория и Дмитрия — отправились в поход. Мальчики бросают жребий, чтобы определить двоих дежурных. Какова вероятность того, что дежурными окажутся Андрей и Борис?
А. . Б. . В. . Г. .

3. В турнире по футболу участвовало 5 команд. Каждая команда должна была сыграть с каждой ровно один матч. В связи с погодными условиями организаторы некоторые игры отменили. В итоге оказалось, что все команды набрали различное количество очков, и ни одна команда в графе набранных очков не имеет нуля. Какое наименьшее количество игр могло быть сыграно в турнире, если за победу начислялось три очка, за ничью — одно, за поражение — ноль?
А. 8. Б. 7. В. 6. Г. 5.

4. В математической олимпиаде участвовал 21 из 25 учащихся класса, а в олимпиаде по информатике — 18, а по физике — 16. Какое наименьшее количество учащихся класса могли принять участие во всех трёх этих олимпиадах?
А. 7. Б. 5. В. 4. Г. 3.

5. Сколько отрезков потребуется, чтобы изобразить фигуру с номером 20, которая получается из предыдущей так, как 2-я фигура, изображённая на рисунке, получается из 1-й, 3-я из 2-й, 4-я из 3-й?
А. 495. Б. 551. В. 610. Г. 672.

6. На соревнованиях 6 гимнасток набрали в одном упражнении вместе 45 баллов, получив в качестве оценок и 7, и 8, и 9 баллов и только эти баллы. Сколько гимнасток получило 7 баллов?
А. 4. Б. 3. В. 2. Г. 1.

7. В классе, где учится Николай, на каникулы учитель математики задал 101 задачу. За правильно решённую задачу он начислял 3 балла, за неправильно решённую снимал 1 балл, а за задачу, которую ученик не решал, снимал 15 баллов. Николай набрал 211 баллов. К решению скольких задач он не приступал, если он решил правильно более 80, но менее 90 задач?
А. 1. Б. 2. В. 3. Г. 4.

8. Средний треугольник получен соединением отрезками середин сторон большого, маленький треугольник получен соединением отрезками середин сторон среднего. Площадь закрашенного треугольника равна 1 см2. Чему равна площадь большого треугольника?
А. 4 см2. Б. 8 см2. В. 12 см2. Г. 16 см2.

9. Имеется 9 одинаковых слитков золота и 11 одинаковых слитков серебра. Их взвесили (золото — на левую чашу весов, серебро — на правую), и весы оказались в равновесии. После того, как слиток золота переложили на правую чашу, а слиток серебра — на левую, левая чаша стала легче на 468 г. Какова масса одного слитка золота?
А. 1253 г. Б. 1287 г. В. 1334 г. Г. 2106 г.

10. Количество диагоналей выпуклого многоугольника больше 2015. Какое наименьшее количество вершин может быть у этого многоугольника?
А. 63. Б. 64. В. 65. Г. 66.

11. Длины ножек циркуля 5 см и 3 см. Они соединены так, что могут вращаться друг относительно друга. Какое расстояние — наименьшее и наибольшее — может быть между его концами?

12. В теннисном турнире принимали участие 9 мальчиков и 6 девочек. Каждые два участника сыграли между собой две партии. Мальчики выиграли в два раза больше партий, чем девочки. Сколько партий выиграли девочки у ребят, если ничьих не было?

13. В классе 13 мальчиков и 13 девочек. На новый год каждый мальчик отправил СМС 6-и девочкам, а каждая девочка — 8-и мальчикам. Обязательно ли найдутся мальчик и девочка, обменявшиеся СМС?

14. Таня за 5 дней прочитала книгу, в которой 138 страниц. Каждый следующий день она читала больше, чем в предыдущий, а в последний день, в воскресенье, она прочитала в 5 раз больше, чем в первый. Какое наибольшее количество страниц могла прочитать Таня в первый день?

источник

Шахматы – страсть миллионов людей. Для кого-то они становятся любимым хобби, а для кого-то смыслом жизни и источником доходов. Существует довольно сложная иерархия рейтингов и разрядов, которая позволяет объективно оценить общий уровень мастерства шахматистов и их текущие достижения. В России рейтинги и разряды по шахматам, юношеские и взрослые, находятся в компетенции Российской шахматной федерации. Международный рейтинг составляет ФИДЕ в виде шорт-листа, в котором сведены и сопоставлены игроки всех стран.

Разряд отражает мастерство игрока на длительном этапе времени. Разряды в шахматах присваиваются на несколько лет, их нужно постоянно подтверждать. Рейтинг – переменная величина, она показывает текущие достижения шахматиста, зависит от выступлений игрока на турнирах и исчисляется в баллах, количество которых меняются после соревнований.

Любому шахматисту, начавшему выступать на официальных турнирах, независимо от его пола или возраста, присваивается начальный рейтинг – 1000 баллов. Ниже тысячи баллов рейтинг быть не может. Он растет, если игрок успешно выступает на соревнованиях, и снижается, если шахматиста преследуют неудачи.

В 1970 году ФИДЕ взяла на вооружение новый способ подсчета общего для всех шахматистов рейтинга с помощью метода профессора Арпада Эло. Данная система расчета способствовала созданию объективной и наглядной иерархии игроков из разных стран. Метод основан на математическом допущении, что сила любого шахматиста является вероятностной переменной, которая подчиняется закономерному распределению.

На основе актуального рейтинга методом Эло можно математически предсказать ожидаемое количество очков, которые наберет шахматист на предстоящем турнире против определенных соперников. Рейтинг игрока растет, если реальное количество очков будет больше ожидаемого, и падает в обратном случае.

ФИДЕ обновляет шорт-листы с рейтингами игроков шесть раз в год и публикует их на своем официальном сайте. Если шахматист в течение года не участвовал ни в одном официальном соревновании, то его рейтинг «замораживается», но не обнуляется. Шахматист на время исключается из шорт-листа. Как только он начинает участвовать в турнирах, ему возвращаются все «замороженные» рейтинговые баллы.

Значения международного рейтинга можно примерно соотнести с российскими званиями и разрядами в шахматах. Так, у перворазрядника будет от 1800 до 1999 баллов по методу Эло, у кандидата в мастера — от 2000 до 2199, у гроссмейстера — от 2500 до 2699, у супергроссмейстеров, которые реально претендуют на победу в чемпионате мира, — свыше 2700 баллов. Кроме баллов ФИДЕ присваивает игрокам три почетных пожизненных звания: мастер, международный мастер и самое высокое – международный гроссмейстер.

Среди мужчин максимального рейтинга — 2889 баллов — достигал Магнус Карлрсен в 2014 году.

У женщин пальма первенства — 2735 баллов летом 2005 года — у венгерки Юдит Полгар.

В России установлено два шахматных звания, а также четыре взрослых и три юношеских разряда. Звания – мастер спорта и шахматный гроссмейстер – могут присваиваться игрокам с 12 и 16 лет соответственно и являются пожизненными регалиями, которые не нужно подтверждать.

Юношеские разряды введены для оценки мастерства шахматистов в возрасте до 15 лет, которые учатся в школе шахмат или самостоятельно участвуют в турнирах. Ныне редко используемый четвертый взрослый разряд условно равен первому юношескому. Второй и третий юношеский разряды присваиваются более слабым игрокам.

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

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

• Для первого юношеского разряда нужно набрать 60 % от максимального количества очков на турнире с низшим коэффициентом – 5.

• Чтобы получить 3, 2 и 1 разряды в шахматах, нужно набрать не менее 75 % от максимального количества очков на соревновании с коэффициентами 4, 3, 2 соответственно.

• Чтобы стать кандидатом в мастера, нужно сначала получить два кандидатских балла, которые присуждаются за победу, или 75 % очков в соревновании с коэффициентом 1, а затем выполнить установленную областную, республиканскую или краевую норму.

В течение двух лет шахматист должен подтвердить свой разряд на соревнованиях, набирая на них не менее 75 % от требуемой разрядной нормы. Например, КМС, не выполнивший дважды эти условия, понижается до первого разряда, но с сохранением двух кандидатских баллов. Если же он не выполнит 75 % от перворазрядной нормы, то он переводится в первый разряд. Шахматисты с первым, вторым и третьим разрядом в шахматах переводятся на один разряд ниже, если они на трех турнирах подряд не смогли набрать определяемого нормой количества очков.

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

Однако для профессионального роста нужен тренер по шахматам. К выбору школы и учителя нужно подходить с особым тщанием. Сейчас в Интернете много предложений от шахматистов, которые обещают быстро и эффективно повысить мастерство ученика любого уровня. Но на поверку часто оказывается, что главная цель этих тренеров – как можно скорее получить деньги. Они не обладают знаниями в педагогике, опытом и наработанными методиками обучения, поэтому не способны дать подопечному фундаментальные знания.

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

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

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

Если же шахматист занимается самостоятельно и выступает на турнирах по собственной инициативе, то нужное свидетельство о разряде в шахматах он может получить в ближайшем по месту жительства центре физической культуры и спорта. Там требуется представить:

• выписку из протокола или копию протокола турнира с подписью главного судьи соревнования, эта бумага будет главным свидетельством выполнения игроком требуемых разрядных норм;

• подписанную главным судьей копию справки, которая подтверждает достаточную квалификацию и состав судейской коллегии;

• паспортные данные в виде ксерокопии второй и третьей страниц с адресом прописки или свидетельство рождения для ребенка моложе четырнадцати лет;

• две фотографии размером три на четыре сантиметра.

источник

Здравствуй, Хабр!

В этой статье речь пойдёт о небольшом программистском этюде на тему машинного обучения. Замысел его возник у меня при прохождении известного здесь многим курса «Machine Learning», читаемого Andrew Ng на Курсере. После знакомства с методами, о которых рассказывалось на лекциях, захотелось применить их к какой-нибудь реальной задаче. Долго искать тему не пришлось — в качестве предметной области просто напрашивалась оптимизация собственного шахматного движка.


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

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

Строго говоря, настоящая оценка может принимать только три значения: выигрыш, проигрыш или ничья — 1, 0 или ½. По теореме Цермело для любой заданной позиции она определяется однозначно. На практике же из-за комбинаторного взрыва ни один компьютер не в состоянии просчитать варианты до листьев полного дерева игры (исчерпывающий анализ в эндшпильных базах данных — это отдельный случай; 32-фигурных таблиц в обозримом будущем не появится… и в необозримом, скорее всего, тоже). Поэтому программы работают в так называемой модели Шеннона — пользуются усечённым деревом игры и приближённой оценкой, основанной на различных эвристиках.

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

Первые такие усовершенствования поиска появились ещё на заре шахматного программирования, в 60-х годах XX в. Можно упомянуть, например, технику форсированного варианта (ФВ) — продление отдельных ветвей поиска до тех пор, пока позиция не «успокоится» (закончатся шахи и взаимные взятия фигур). Продления существенно увеличивают тактическую зоркость компьютера, а также приводят к тому, что дерево поиска становится очень неоднородным — длина отдельных ветвей может в несколько раз превышать длину соседних, менее перпективных. Другие улучшения поиска, наоборот, представляют собой отсечения или сокращения поиска — и здесь критерием отбрасывания плохих вариантов может, в числе прочего, служить всё та же статическая оценка.

Параметризация и улучшение поиска методами машинного обучения — отдельная интересная тема, но сейчас мы оставим её в стороне. Займёмся пока только оценочной функцией.

Статическая оценка представляет собой линейную комбинацию различных признаков позиции, взятых с некоторыми весовыми коэффициентами. Какие это признаки? В первую очередь, количество фигур и пешек у той и другой стороны. Следующий важный признак — положение этих фигур, централизация, занятие дальнобойными фигурами открытых линий и диагоналей. Опыт показывает, что учёт только этих двух факторов — суммы материала и относительной ценности полей (зафиксированной в виде таблиц для каждого типа фигур) — при наличии качественного поиска уже может обеспечивать силу игры в диапазоне до 2000-2200 пунктов Эло. Это уровень хорошего первого разряда или кандидата в мастера.

Дальнейшее уточнение оценки может включать всё более и более тонкие признаки шахматной позиции: наличие и продвинутость проходных пешек, близость фигур к позиции неприятельского короля, его пешечное прикрытие и т. д. Легендарная «Каисса», первая чемпионка мира среди программ (1974) имела оценочную функцию из нескольких десятков признаков. Все они подробно описаны в книге «Машина играет в шахматы», библиографическая ссылка на которую приводится в конце статьи.


Одна из самых «навороченных» оценочных функций была у машины Deep Blue, прославившейся своими матчами с Каспаровым в 1996-97 гг. (подробную историю этих матчей можно прочитать в недавней серии статей на Geektimes.)

Широко распространено мнение, что сила Deep Blue основывалась исключительно на колоссальной скорости перебора вариантов. 200 миллионов позиций в секунду, полный (без отсечений) перебор на 12 полуходов — к таким параметрам шахматные программы на современном железе только-только приближаются. Однако, дело было не только в быстродействии. По объёму «шахматных знаний» в оценочной функции эта машина также намного превосходила всех. Оценка Deep Blue была реализована аппаратно и включала до 8000 различных признаков. Для настройки её коэффициентов привлекались сильные гроссмейстеры (достоверно известно о работе с Джоэлем Бенджамином, тестовые партии с разными версиями машины играл Давид Бронштейн).

Не располагая такими ресурсами, как создатели Deep Blue, ограничим задачу. Из всех признаков позиции, учитываемых для подсчёта оценки, возьмём самый значимый — соотношение материала на доске.

Если взять любую шахматную книгу для начинающих, сразу за главой с объяснением шахматных ходов обычно приводится табличка сравнительной ценности фигур, примерно такая:

Тип Стоимость
Пешка 1
Конь 3
Слон 3
Ладья 5
Ферзь 9
Король

Королю иногда приписывается конечная стоимость, заведомо бóльшая, чем сумма всего материала на доске — например, 200 единиц. В данном исследовании мы оставим Его Величество в покое, и рассматривать королей не будем вообще. Почему? Ответ простой: они всегда присутствуют на доске, поэтому их материальная оценки взаимно вычитаются, и на общий баланс сил не влияют.

Приведённые стоимости фигур должны рассматриваться только как некоторые базовые ориентиры. В реальности фигуры могут «дорожать» и «дешеветь» в зависимости от ситуации на доске, а также от стадии партии. В качестве поправки первого порядка обычно рассматривают комбинации из двух-трёх фигур — своих и противника.

Вот как оценивал различные сочетания материала в своём классическом «Учебнике шахматной игры» третий чемпион мира Хосе-Рауль Капабланка:

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

Слон в игре против пешек сильнее коня, а вместе с пешками также оказывается более сильным против ладьи, нежели конь. Слон и ладья тоже сильнее коня и ладьи, но ферзь и конь могут оказаться сильнее, чем ферзь и слон. Слон часто стоит больше трех пешек, о коне же это редко можно сказать; он даже может оказаться слабее трех пешек.

Ладья по силе равна коню и двум пешкам или же слону и двум пешкам, но, как сказано выше, слон в борьбе против ладьи сильнее коня. Две ладьи несколько сильнее ферзя. Они немного слабее двух коней и слона и еще слабее двух слонов и коня. Сила коней падает по мере размена фигур на доске, сила же ладьи, напротив, возрастает.

Наконец, как правило, три легкие фигуры сильнее ферзя.

Оказывается, большей части подобных правил можно удовлетворить, оставаясь в рамках линейной модели, и просто слегка сместив стоимости фигур от их «школьных» значений. Например, в одной из статей приводятся следующие граничные условия:

И значения, им удовлетворяющие:


Имена переменных соответствуют обозначениям фигур в английской нотации: P — пешка, N — конь, B — слон, R — ладья, Q — ферзь, K — король. Стоимости здесь и далее указаны в сотых долях пешки.

На самом деле, приведённый набор значений не является единственным решением. Более того, даже несоблюдение каких-то из «неравенств им. Капабланки» не приведёт к резкому падению силы игры программы, а только повлияет на её стилевые особенности.

В качестве эксперимента я провёл небольшой матч-турнир четырёх версий своего движка GreKo с разными весами фигур против трёх других программ — каждая из версий сыграла 3 матча по 200 партий со сверхмалым контролем времени (1 секунда + 0.1 сек. на ход). Результаты приведены в таблице:

Версия Пешка Конь Слон Ладья Ферзь vs. Fruit 2.1 vs. Crafty 23.4 vs. Delfi 5.4 Рейтинг
GreKo 12.5 100 400 400 600 1200 61.0 76.0 71.0 2567
GreKo A 100 300 300 500 900 55.0 69.0 73.0 2552
GreKo B 100 320 330 500 900 57.0 71.0 64.0 2548
GreKo C 100 325 325 550 1100 72.5 74.5 69.0 2575

Мы видим, что некоторые вариации в весах фигур приводят к колебаниям силы игры в диапазоне 20-30 пунктов Эло. Более того, одна из тестовых версий показала даже лучший результат, чем основная версия программы. Впрочем, однозначно утверждать об усилении игры на таком малом количестве партий преждевременно — доверительный интервал вычисления рейтинга составляет сравнимую величину в несколько десятков пунктов Эло.

«Классические» стоимости шахматного материала были получены интуитивно, путём осмысления шахматистами своего практического опыта. Предпринимались также попытки подвести под эти значения какую-то математическую базу — например, на основе мобильности фигур, числа полей, которые они могут держать под контролем. Мы же попробуем подойти к вопросу экспериментально — на базе анализа большого количества шахматных партий. Для вычисления стоимостей фигур нам не понадобится приближённая оценка позиций из этих партий — только их результаты, как самая объективная мера успеха в шахматах.

Для статистического анализа был взят PGN-файл, содержащий почти 3000 шахматных партий в блиц между 32 разными шахматными движками, в диапазоне от 1800 до 3000 пунктов Эло. С помощью специально написанной утилиты для каждой партии был составлен список материальных соотношений, возникших на доске. Каждое соотношение материала попадало в статистику не сразу после взятия фигуры или превращения пешки — сначала должны были произойти ответные взятия или несколько «тихих» ходов. Таким образом отфильтровывались краткосрочные «скачки материала» на 1-2 хода при разменах.

Затем по уже известной нам шкале «1-3-3-5-9» рассчитывался материальный баланс позиции, и для каждого его значения (от -24 до 24) накапливалось количество очков, набранных белыми. Полученная статистика представлена на следующем графике:

По оси x — материальный баланс позиции ΔM с точки зрения белых, в пешках. Он вычисляется как разность суммарной стоимости всех белых фигур и пешек и такой же величины для чёрных. По оси y — выборочное математическое ожидание результата партии (0 — победа чёрных, 0.5 — ничья, 1 — победа белых). Мы видим, что экспериментальные данные очень хорошо описываются логистической кривой:

Простой визуальный подбор позволяет определить параметр кривой: α=0.7, размерность его — обратные пешки.
Для сравнения на графике приведены ещё две логистические кривые с другими значениями параметра α.

Что это означает на практике? Пусть мы видим случайно выбранную позицию, в которой у белых перевес в 2 пешки (ΔM = 2). С вероятностью, близкой к 80%, мы можем утверждать: партия закончится победой белых. Аналогично, если у белых не хватает слона или коня (ΔM = -3), их шансы не проиграть всего лишь около 12%. Позиции с материальным равенством (ΔM = 0), как и можно было ожидать, чаще всего заканчиваются вничью.

Теперь мы готовы сформулировать задачу оптимизации оценочной функции в терминах логистической регрессии.
Пусть нам дан набор векторов следующего вида:

где Δi, i = P. Q — разность количества белых и чёрных фигур типа i (от пешки до ферзя, короля не считаем). Эти вектора представляют собой материальные соотношения, встретившиеся в партиях (одной партии обычно соответствует несколько векторов).

Пусть дан также вектор yj, компоненты которого принимают значения 0, 1 и 2. Эти значения соответствуют исходам партий: 0 — победа чёрных, 1 — ничья, 2 — победа белых.

Требуется найти вектор θ стоимостей фигур:

минимизирующий функцию стоимости для логистической регрессии:

,
где
— логистическая функция для векторного аргумента.

Для предотвращения «переобучения» и эффектов неустойчивости в найденном решении в функцию стоимости можно добавить параметр регуляризации, не дающий коэффициентам в векторе принимать слишком большие значения:

Величина коэффициента при параметре регуляризации выбирается небольшая, в данном случае использовалось значение λ=10 -6 .

Для решения задачи минимизации применим простейший метод градиентного спуска с постоянным шагом:

где компоненты градиента функции Jreg имеют вид:

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

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

Так как первая часть задачи — разбор PGN-файлов и выделение для каждой позиции набора признаков — уже была практически реализована в коде шахматного движка, оставшуюся часть было решено также написать на C++. Исходный код программы и тестовые наборы партий в PGN-файлах доступны на github. Программа может быть собрана и запущена под Windows (MSVC) или Linux (gcc).

Возможность использовать в дальнейшем специализированные средства вроде Octave, MATLAB, R и т.п. также предусмотрена — в процессе работы программа генерирует промежуточный текстовый файл с наборами признаков и исходами партий, который легко может быть импортирован в эти среды.

Файл содержит текстовое представление набора векторов xj — матрицы размерности m x (n + 1), в первых 5 столбцах которой содержатся компоненты материального баланса (от пешки до ферзя), а в 6-м — результат партии.

Рассмотрим простой пример. Ниже приводится PGN-запись одной из тестовых партий.

Соответствующий фрагмент промежуточного файла имеет вид:

В 6-м столбце везде 0 — это результат партии, победа чёрных. В остальных столбцах — баланс числа фигур на доске. В первой строке полное материальное равенство, все компоненты равны 0. Вторая строка — лишняя пешка у белых, это позиция после 24-го хода. Обратим внимание, что предшествующие размены никак не отражены, они происходили слишком быстро. После 27-го хода у белых уже 2 лишних пешки — это строка 3. И т.д. Перед заключительной атакой чёрных у белых пешка и конь за две ладьи:

Как и размены в дебюте, финальные ходы в партии на содержимое файла не повлияли. Они были отсеяны «фильтром тактики», потому что представляли собой серию взятий, шахов и уходов от них.

Такие же записи создаются для всех анализируемых партий, в среднем получается по 5-10 строк на игру. После разбора PGN-базы с партиями этот файл поступает на вход второй части программы, занимающейся собственно решением задачи минимизации.

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

После нормировки и округления получаем следующий набор величин:

Тип Стоимость
Пешка 100
Конь 288
Слон 345
Ладья 480
Ферзь 1077
Король

Проверим, выполняются ли «правила Капабланки»?

Соотношение Численные значения Выполняется?
B > N 345 > 288 да
B > 3P 345 > 3 * 100 да
N > 3P 288 нет
B + N = R + 1.5P 345 + 288

= 480 + 1.5 * 100

да (с погрешностью
Q + P = 2R 1077 + 100 > 2 * 480 нет

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

Можно ли полученные значения использовать для усиления игры программы? Увы, на данном этапе ответ отрицательный. Тестовые блиц-матчи показывают, что сила игры GreKo от использования найденных параметров практически не изменилась, а в ряде случаев даже снизилась. Почему так произошло? Одна из очевидных причин — уже упоминавшаяся тесная связь поиска и оценки позиции. В поиске движка заложен целый ряд эвристик для отсечения неперспективных ветвей, и критерии этих отсечений (пороговые значения) тесно завязаны на статическую оценку. Меняя стоимости фигур, мы резко сдвигаем масштаб величин — форма дерева поиска меняется, требуется новая балансировка констант для всех эвристик. Это достаточно трудоёмкая задача.

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


Ананд и Карлсен соперничают за мировую корону

В таблице ниже представлены результаты решения регрессионной задачи для партий этих шахматистов.

Ананд Карлсен Андерсен
Пешка 100 100 100
Конь 216 213 286
Слон 230 243 289
Ладья 355 352 531
Ферзь 762 786 1013
Король

Легко заметить, что «человеческие» значения стоимости фигур оказались вовсе не такими, каким учат начинающих в учебниках. В случае Карлсена и Ананда бросается в глаза меньший масштаб шкалы — ферзь стоит чуть больше 7.5 пешек, соответственно сжался весь диапазон для других фигур. Слон по-прежнему чуть дороже коня, но и тот, и другой не дотягивают до традиционных трёх пешек. Две ладьи оказываются слабее ферзя, и т.д.

Надо сказать, что похожая картина наблюдается не только у Виши и Магнуса, но и для большинства гроссмейстеров, партии которых удалось протестировать. Причём какой-то зависимости от стиля не выяснилось. Значения смещены от классических в одну и ту же сторону и у позиционных мастеров вроде Михаила Ботвинника и Анатолия Карпова, и у атакующих шахматистов — Михаила Таля, Юдит Полгар…

Одним из немногих исключений стал Адольф Андерсен — лучший европейский игрок середины XIX века, автор знаменитой «вечнозелёной партии». Вот для него значения стоимости фигур оказались очень близки к тем, которые используют компьютерные программы. Напрашиваются самые разнообразные фантастические гипотезы, вроде тайного читерства немецкого маэстро через портал во времени… (Шутка, конечно. Адольф Андерсен был крайне порядочным человеком, и никогда бы себе такого не позволил.)


Адольф Андерсен (1818-1879),
человек-компьютер

Почему наблюдается такой эффект со сжатием диапазона стоимости фигур? Конечно, не стоит забывать о крайней ограниченности нашей модели — учёт дополнительных позиционных факторов мог бы внести существенные коррективы. Но, возможно, дело в слабой технике реализации человеком материального перевеса — относительно современных шахматных программ, конечно. Проще говоря, человеку тяжело безошибочно играть ферзём, потому что у того слишком много возможностей. Вспоминается хрестоматийный анекдот о Ласкере (в других вариантах — Капабланке / Алехине / Тале), якобы игравшем с форой со случайным попутчиком в поезде. Кульминационной фразой было: «Ферзь только мешает!»

Мы рассмотрели один из аспектов оценочной функции шахматных программ — стоимость материала. Убедились, что эта часть статической оценки в модели Шеннона имеет вполне «физический» смысл — она гладким образом (через логистическую функцию) связана с вероятностью исхода партии. Затем рассмотрели несколько распространённых комбинаций весов фигур, и оценили порядок их влияния на силу игры программы.

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

Куда двигаться дальше? Для более точной оценки позиции можно добавлять в модель новые шахматные знания — то есть увеличивать размерность векторов x и θ. Даже оставаясь в области только материальных критериев (без учёта полей, занимаемых фигурами на доске), можно добавить целый ряд релевантных признаков: два слона, пара из ферзя и коня, пара из ладьи и слона, разноцвет, последняя пешка в эндшпиле… Шахматистам хорошо известно, как ценность фигур может зависеть от их сочетания или стадии партии. В шахматных программах соответствующие веса (бонусы или штрафы) могут достигать десятых долей пешки и более.

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

Однако, как уже было отмечено выше, для непосредственного усиления игры программы полученные результаты могут оказаться непригодными. Часто случается так: после обучения на сериях тестов программа начинает лучше решать тесты (в нашем случае — предсказывать результаты партий), но не лучше играть! В настоящее время в шахматном программировании мейнстримом стало интенсивное тестирование исключительно в практической игре. Новые версии топ-движков перед выпуском тестируются на десятках и сотнях тысяч партий со сверхкороткими контролями времени…

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

В ходе исследований ни одна шахматная фигура не пострадала.

Адельсон-Вельский, Г.М.; Арлазаров, В.Л.; Битман, А.Р. и др. — Машина играет в шахматы. М.: Наука, 1983
Книга авторов советской программы «Каисса», подробно описывающая как общие алгоритмические основы шахматных программ, так и конкретные детали реализации оценочной функции и поиска «Каиссы».

Корнилов Е. — Программирование шахмат и других логических игр. СПб.: БХВ-Петербург, 2005
Более современная и «практическая» книга, содержит большое количество примеров кода.

Feng-hsiung Hsu — Behind Deep Blue. Princeton University Press, 2002
Книга одного из создателей шахматной машины Deep Blue, в подробностях рассказывающая об истории её создания и внутреннем устройстве. В приложении приведены тексты всех шахматных партий, сыгранных Deep Blue в официальных соревнованиях.

Chessprogramming Wiki — обширная коллекция материалов по всем теоретическим и практическим аспектам шахматного программирования.

Machine Learning in Games — сайт, посвящённый машинному обучению в играх. Содержит большое количество научных статей по исследованиям в области шахмат, шашек, го, реверси, нардов и т.д.

Kaissa — страница, посвящённая «Каиссе». Детально представлены коэффициенты её оценочной функции.

Stockfish — сильнейшая на сегодня программа, с открытым исходным кодом.

A comparison of Rybka 1.0 beta and Fruit 2.1
Детальное сравнение внутреннего устройства двух популярных шахматных программ.

GreKo — шахматная программа автора статьи.
Была использована в качестве одного из источников тестовых компьютерных партий. Также на основе её генератора ходов и парсера PGN-нотации была изготовлена утилита для анализа экспериментальных данных.

pgnlearn — код утилиты и примеры файлов с партиями на github.

источник