Нетранзитивность — кладезь для изобретателей

Александр Поддьяков
Александр Поддьяков, профессор Департамента психологии Высшей школы экономики

В статье Натальи Резник «Камень, ножницы, бумага» [1] описаны многочисленные забавные — с человеческой точки зрения — взаимодействия самцов в борьбе за самок. У самых разных видов (ящериц, жуков и других) наблюдается сходный сценарий: есть самцы-агрессоры, вторгающиеся на чужие территории и отбивающие самок у тамошних обороняющихся самцов, и есть «тихушники», мимикрирующие под самок, — они не распознаются агрессорами и успешно делают свое черное дело. Зато «тихушников» успешно вычисляют обороняющиеся самцы. Этими очень понятными примерами дело не ограничивается — вопрос ставится значительно шире. Принцип взаимодействий «камень, ножницы, бумага» рассматривается в биологии как один из универсальных, поддерживающий биоразнообразие на самых разных уровнях. В журналах Science, Nature публикуются статьи со словами «камень, ножницы, бумага» в заголовках или списке ключевых слов. В этих текстах представлены живые примеры типа приведенных выше и предлагаются всё более продвинутые математические модели для описания, например, пространственно-временных распределений разных представителей животного и растительного мира (обзор дан в [2]).

Этот спектр явлений получил название нетранзитивной конкуренции — название происходит от логико-математического понятия «нетранзитивность» («непереходность»). Здесь превосходство А над В и затем В над С не распространяется на пару А — С: в ней С может доминировать (побеждать, превосходить А).

Интересна динамика развития разных наук. Изначально независимо, а сейчас всё более пересекаясь при обсуждении общего предмета интереса, на тему нетранзитивности превосходства вышли представители образцового по строгости типа мышления. Это математики — специалисты по теории вероятности, теоретики теории игр и изобретатели логико-математических головоломок. После статей Мартина Гарднера 1970-х годов о нетранзитивных игральных костях (числа на которых подобраны так, что кубик А чаще показывает большее число, чем кубик В, кубик В чаще показывает большее число, чем С, а С чаще показывает большее число, чем А), о нетранзитивных рулетках, наборах игральных карт и так далее пошла широкая волна популяризации темы и ее активного научного исследования [3]. Математическая премия The Carl B. Allendoerfer Award этого года присуждена за статью «Нетранзитивные игральные кости», в которой выявлен еще один важный аспект парадоксальности этих объектов [4, 5]. Что касается популяризации, то в Интернете на слова “nontransitive dice” выпадают десятки видео, где разные люди — от профессоров математики и до школьников — рассказывают о нетранзитивных игральных костях и последствиях нетранзитивности для ошибок научного вывода и реальной жизни. Самая яркая история — о том, как догадливый Билл Гейтс не попал в ловушку с нетранзитивными игральными костями, предложенными ему Уорреном Баффеттом, — фигурирует в самых разных источниках, включая сайт Microsoft [6].

Особый интерес представляет придумывание, изобретение объектов, нетранзитивных по превосходству, то есть таких, что при сравнении по заданному признаку в паре А — В надо выбрать А (как превосходящее В по этому признаку), в паре В — С — выбрать В, а в паре А — С — выбрать С.

Вот некоторые результаты, часть которых получена уже достаточно давно. Разработаны наборы игральных кубиков, в которых при удвоении набора (игроки берут не по одному кубику, а по два одинаковых) меняется направление «битья»: для одиночных кубиков A > B > C > A, а для «спаренных» AA < BB < CC < AA [7]. Также сконструированы наборы кубиков для игры втроем — такие, что, после того как двое игроков выбрали себе по кубику, третий игрок всегда может выбрать выигрышный по отношению к этим двум [7], и набор для игры вчетвером, что намного сложнее [8]. Задача разработки наборов для игры впятером, вшестером и c большим количеством игроков пока, видимо, не решена. Мое предположение: возможно, и здесь (как в ряде некоторых других задач) мы выходим на ключевой вопрос о равенстве классов сложности P—NP. В популярном изложении Лэнса Фортноу, одного из самых известных исследователей в этой области, «P — это класс задач, которые на компьютере решаются относительно быстро. NP — задачи, для которых мы хотим найти оптимальное решение. Равенство P и NP означает, что любую поставленную задачу можно быстро решить. <…> Неравенство P и NP, в свою очередь, означает, что для некоторых задач быстрое решение не найдется никогда» (из книги «Золотой билет. P, NP и границы возможного»). Но обсуждение этого аспекта применительно к нетранзитивных костям мне не встречалось — ни применительно к задаче построения набора костей для N игроков, ни применительно к задаче поиска нетранзитивных цепочек (хотя бы одной или множества цепочек с заданными свойствами) в наборе M костей (например, со случайно сгенерированными числами на гранях). А вот алгоритм генерации таких чисел на кубиках, чтобы те образовывали «простую» нетранзитивную цепочку произвольной длины для игры двух игроков, построен.

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

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

Рис. 1. «Нетранзитивные» шестерни: при попарных соединениях синяя шестерня вращается быстрее зеленой, зеленая — быстрее красной, красная — быстрее синей
Рис. 1. «Нетранзитивные» шестерни: при попарных соединениях синяя шестерня вращается быстрее зеленой, зеленая — быстрее красной, красная — быстрее синей

Если же мы будем втыкать оси этих шестерен в расположенные рядом отверстия на вертикальной стенке и закрепим на каждой оси стандартный грузик, то получим кажущийся парадоксальным результат уже в терминах нетранзитивного силового взаимодействия. А именно: при попарных соединениях груз на шестерне А поднимается («пересиливается») грузом на шестерне В, груз на шестерне В — грузом на шестерне С, но груз на шестерне С — грузом на шестерне А (рис. 2). Эта модель может пригодиться для развития представлений учеников в области механики. Аналогично, можно построить нетранзитивные двойные рычаги, где правило рычага и принцип взаимодействия «камень, ножницы, бумага» иллюстрируют друг друга.

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

Видимо, один из наиболее сложных примеров детерминированной нетранзитивности — нетранзитивные по выигрышности позиции в логических играх на размеченном игровом поле. Это, например, нетранзитивные шахматные позиции: при попарном наложении на одну доску позиция A белых предпочтительнее позиции B черных (при возможности выбора за белых или за черных надо выбрать A), позиция B черных предпочтительнее позиции C белых, позиция C белых предпочтительнее позиции D черных, но позиция D черных предпочтительнее позиции A белых (белые начинают во всех вариантах) (рис. 3). Этот пример сконструирован в демонстрационных целях. Как материал для задачи он лишен шахматного изящества и нарочито прост, даже примитивен, — например, мат может ставиться одним ходом белых. Цель — только показ самой возможности нетранзитивных отношений между шахматными позициями как ранее неизвестного свойства самой шахматной среды (нетранзитивная сила игроков-шахматистов и шахматных программ известна давно).

Рис. 3. Нетранзитивные шахматные позиции (белые начинают во всех вариантах)
Рис. 3. Нетранзитивные шахматные позиции (белые начинают во всех вариантах)

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

На основе приведенного на рисунке примера специалист по теории игр А. Ю. Филатов показал, что число нетранзитивных цепочек в шахматах огромно, а сами цепочки могут быть астрономической длины. Также он построил минимальную — и при этом симметричную — цепочку из четырех позиций, где с каждой стороны участвуют только по две фигуры: белые и черные король и пешка [10].

Рис. 4. Нетранзитивные «гуляй-башни» (пластмассовые параллелепипеды с вырезанными передними фигурными профилями и вставленными в отверстия цветными маркерами). Гуляй-башня с красным маркером ставит метку на гуляй-башне с зеленым маркером, оставаясь для той неуязвимой; гуляй-башня с зеленым маркером ставит метку на гуляй-башне с синим маркером (но не наоборот), а гуляй-башня с синим маркером — на гуляй-башне с красным маркером (но не наоборот)
Рис. 4. Нетранзитивные «гуляй-башни» (пластмассовые параллелепипеды с вырезанными передними фигурными профилями и вставленными в отверстия цветными маркерами). Гуляй-башня с красным маркером ставит метку на гуляй-башне с зеленым маркером, оставаясь для той неуязвимой; гуляй-башня с зеленым маркером ставит метку на гуляй-башне с синим маркером (но не наоборот), а гуляй-башня с синим маркером — на гуляй-башне с красным маркером (но не наоборот)

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

Это очевидно? Рассмотрим модельный пример. К опытному шахматисту приходит талантливый в шахматах и математике ребенок и говорит: «Я разработал формулу, которая позволяет оценивать по отдельности позицию белых и позицию черных и приписывать им однозначную, фиксированную количественную оценку, а затем сравнивать эти позиции — уже просто как числа, какое больше: у белых или у черных». Вместо ответа типа: «Вот сыграешь много партий и на опыте поймешь, что это не так; такая формула, я уверен, невозможна» теперь есть возможность ответа другого типа: «Есть такая штука, как нетранзивные шахматные позиции, и они означают, что позиция белых и позиция черных не могут иметь фиксированной количественной оценки без учета друг друга. В круге побед и поражений, где каждая позиция бьет соседку с одной стороны и бьется соседкой с другой, какие могут быть фиксированные численные оценки? Дать тебе готовый пример таких позиций или хочешь придумать свой пример сам?»

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

Что касается заинтересовавшегося взрослого (или ребенка тоже?), то здесь еще много задач: например, поискать ответ на вопрос, на какой минимальной доске (3×3? 4×4?) нетранзитивность позиций уже возможна; построить нетранзитивные позиции в других играх (шашках, го) и так далее. Изобретение объектов, нетранзитивных по превосходству, и придумывание задач с их участием — интересная, а для некоторых даже захватывающая деятельность, объединяющая самые разные области.

1. Н. РезникКамень, ножницы, бумага // ТрВ-Наука, № 162 от 9 сентября 2014 года.

2. elibrary.ru/item.asp?id=21630164

3. www.nkj.ru/archive/articles/31726/

4. arxiv.org/pdf/1311.6511.pdf

5. bit.ly/2gLbM3R

6. www.microsoft.com/en-us/research/project/non-transitive-dice

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

Связанные статьи

avatar
15 Цепочка комментария
9 Ответы по цепочке
4 Подписки
 
Популярнейший комментарий
Цепочка актуального комментария
4 Авторы комментариев
Станислав ЖураховскийАлексей В. ЛебедевАлександр ПоддьяковИван Авторы недавних комментариев
  Подписаться  
Уведомление о
Иван
Иван

Интересная статья.
Навела на полезные размышления.
Спасибо.

Александр Поддьяков
Александр Поддьяков

Спасибо за отклик!

Алексей В. Лебедев
Алексей В. Лебедев

Надо же, я 20 лет работаю в вероятности, а про нетранзитивные кубики не слышал. Потрясающая тема. Интересно, известны ли обобщения с дискретных (кубики) на непрерывные случайные величины?

Александр Поддьяков
Александр Поддьяков

Специально про непрерывные случайные величины раньше не искал.
Нарыл сейчас такое — не знаю, насколько релевантно (искал на intransitivity continual continuous bivariate distribution, можно модифицировать). Bivariate distribution считается одним из условий нетранзитивности.

Ulrich W. et al, (2015). Matrix models for quantifying competitive intransitivity.https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4407980/

Gowers’s Weblog https://gowers.wordpress.com/2017/05/19/intransitive-dice-iii/

Gehrlein W. (2006). Condorcet’s Paradox.
http://bit.ly/2Bq0Ca3
http://bit.ly/2i6z9Wi
(О книге — http://www.springer.com/us/book/9783540337980)

Klimenko A.Y/ (2015). Intransitivity in Theory and in the Real World
http://www.mdpi.com/1099-4300/17/6/4364/html

Александр Поддьяков
Александр Поддьяков

Есть такое подозрение, что возможности нетранзитивности непрерывных (continuous) величин обсуждаются на английском здесь, особенно в комментариях: https://gowers.wordpress.com/2017/05/30/intransitive-dice-v-we-want-a-local-central-limit-theorem/

Алексей В. Лебедев
Алексей В. Лебедев

Спасибо, будем разбираться.

Станислав Жураховский
Станислав Жураховский

В шашках построить нетранзитивныий цикл намного легче, чем в шахматах. Причина в том, что в шахматах лишний темп — это обычно преимущество, а в шашках бывает по разному (важно соотношение темпов). Поэтому в шашках довольно часто бывает цугцванг и даже обоюдный (когда начинающий проигрывает). Из простейших таких позиций на занятие оппозиции и стороится нетранзитивный цикл (всюду ход белых): A: б.e3, ч.d6 — 1:0; A: б.d4, ч.d6 — 0:1; A: б.d4, ч.e7 — 1:0; A: б.e3, ч.e7 — 0:1. Кстати, эта четверка позиций является нетранзитивным циклом и в поддавки.

Александр Поддьяков
Александр Поддьяков

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

Александр Поддьяков
Александр Поддьяков

Не могу не написать — как расставил, всё не убираю: красиво. Спасибо еще раз!

Александр Поддьяков
Александр Поддьяков

Станислав, еще раз спасибо, я сослался на созданные Вами нетранзитивные позиции в шашках — см. презентацию устного доклада на Ежегодной конференции общества математической психологии
https://www.hse.ru/data/2019/07/23/1481387139/Poddiakov%202019%20Making%20decisions%20in%20intransitivity-presentation.pdf , слайд 42.
Book of abstracts здесь http://mathpsych.org/conferences/2019/wp-content/uploads/2019/07/booklet2019.pdf, там без расшифровки.

Александр Поддьяков
Александр Поддьяков

Алексей В. Лебедев: «Интересно, известны ли обобщения с дискретных (кубики) на непрерывные случайные величины?»

Увидел, что эта проблема ставилась для будущих исследований: «One would expect that replacing discrete random variables with continuous ones requires a different methodology» https://www.researchgate.net/publication/287263681_Nontransitive_dice_sets_realizing_the_Paley_tournaments_for_solving_Schutte%27s_tournament_problem
Решена ли с тех пор, непонятно.

Алексей В. Лебедев
Алексей В. Лебедев

Большое спасибо, посмотрю.

Алексей В. Лебедев
Алексей В. Лебедев

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

Я с моим учеником пробовал брать многочлены на отрезке [0,1], в качестве функций распределения, для трех величин. При степени 2 доказывается, что нетранзитивности не бывает. При степени 3 похоже, что не бывает, но пока не доказано. При степени 4 нетранзитивность обнаружена, и вероятность пока удалось довести до 0.53, что сопоставимо со случаем трех кубиков, где 5/9, но сильно меньше максимально возможной 0.618.

Александр Поддьяков
Александр Поддьяков

Мне кажется, уже прорыв, что удалось доказать саму возможность нетранзитивности для непрерывных величин (не предположить ее, а доказать — с конкретными значениями). Я таких работ не видел.

Может, этот автор здесь что-то развивает http://mtasztaki.academia.edu/S%C3%A1ndorBoz%C3%B3ki – сюда я еще не забирался, но в ссылках никакой конкретный результат мне пока не выпадал.

Алексей В. Лебедев
Алексей В. Лебедев

Он дальше этим не занимался.

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

Естественнее рассматривать более традиционные непрерывные распределения. Например, мой ученик доказал, что для равномерного, показательного и нормального распределений нетранзитивности не бывает.

Александр Поддьяков
Александр Поддьяков

С точки зрения поиска нетранзитивости непрерывных величин в реальности (в природе), лучше идти от известных непрерывных распределений – да, правда.

Если же отталкиваться от кубиков, то можно, наверное, не добавлять случайно распределенные величины к числам на них, но попробовать другую вещь – построить функцию, проходящую через соответствующие значения (которые на кубиках).
То есть, скажем, это (если отталкиваться от трех известных кубиков)
— функция, проходящая через 2, 4, 9 (вогнутая)
— функция, проходящая через 1, 6, 8 (выпуклая)
— функция, проходящая через 3, 5, 7 (прямая).

Или примерно это и было опробовано, когда вы писали о проверке степеней функции?
Или это бред?

Алексей В. Лебедев
Алексей В. Лебедев

Эти кубики требуют 9 разных значений, у каждого по 3 разных, на самом деле достаточно 5 разных значений, у каждого не более 2 разных (см. таблицу 1 статьи С.Бозоки), и сами значения не важны, а только их соотношения между собой, и можно все уместить, например, на отрезок [0,1]. Для функции распределения желательно, чтобы при этих значениях аргумента она росла быстро (имела максимумы плотности), а при остальных медленнее. Наличие двух максимумов, разделенных минимумом, требует хотя бы степени 3 от плотности, и тогда степени 4 от функции распределения. Но это нестрогие рассуждения.

Алексей В. Лебедев
Алексей В. Лебедев

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

Александр Поддьяков
Александр Поддьяков

Я согласен, что постановка проблемы нетранзитивности произвольных случайных величинах (включая непрерывные) фундаментальнее, и интересен поиск соответствий в реальности (типа нетранзитивности прочности). М.Гарднер в своей колонке 1970 г. писал, что нетранзитивные кости — разработка Эфрона (вроде на тот момент прошло несколько лет с изобретения – то есть 60-е гг), на Трибулу у Гарднера ссылок не видно. Текстов самого Эфрона про кости найти не могу – может, не опознаю; глянул здесь https://en.wikipedia.org/wiki/Bradley_Efron http://statweb.stanford.edu/~ckirby/brad/ http://statweb.stanford.edu/~ckirby/brad/EfronCV.pdf Знал ли Эфрон о Трибуле на момент изобретения, пока непонятно. А Трибула, судя по ссылкам в современных статьях про нетранзитивные кости, писал по этой теме с конца 50-х.… Подробнее »

Александр Поддьяков
Александр Поддьяков

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

Алексей В. Лебедев
Алексей В. Лебедев

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

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

Александр Поддьяков
Александр Поддьяков

Да, спасибо за ссылку на эту статью Трибулы (не знал, а нетранзивность прочности интересовала давно) и за комментарий.

Александр Поддьяков
Александр Поддьяков

Вот еще исследование разных нетранзитивностей, в том числе при промышленном контроле качества; интересная статья
West, L.J, Hankin, R. (2008). Exact tests for two-way contingency tables with structural zeros. Journal of Statistical Software. Vol. 28.
https://www.researchgate.net/publication/46515707_Exact_Tests_for_Two-Way_Contingency_Tables_with_Structural_Zeros

Александр Поддьяков
Александр Поддьяков

Развитие идеи нетранзитивных шестерен (с первой картинки)

Голландский изобретатель головоломок Oskar van Deventer (с несколькими рекордами Гиннеса) на основе этих нетранзитивных шестерен сделал головоломку Non-Transitive-Gears

К исходной конструкции добавлены храповые механизмы (и, возможно, что-то еще). При вращении любой из трех рукояток одна из соседних с нею шестерен вращается в 2 раза быстрее, а другая — в 3 (в три, не в два!) раза медленнее. Если играть, как с черным ящиком, не зная устройства — впечатление парадоксальное.

Оценить: 
Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (4 оценок, среднее: 4,00 из 5)
Загрузка...
 
 

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

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