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

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

В статье Натальи Резник «Камень, ножницы, бумага» [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

Подписаться
Уведомление о
guest

27 Комментария(-ев)
Встроенные отзывы
Посмотреть все комментарии
Александр Поддьяков
5 года (лет) назад

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

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

А Трибула, судя по ссылкам в современных статьях про нетранзитивные кости, писал по этой теме с конца 50-х.
H. Steinhaus, S. Trybuła. On a paradox in applied probabilities, Bull. Acad. Polon. Sci. 7 (1959) 67–69.

О разных нетранзитивностях – объективных и (не очень точно) померенных

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

Раз в статье Трибулы 1961 г. прочность каждого бруска сравнивается относительно одного и того же внешнего стандарта (ввинчиваемого винта, шурупа), то речь, скорее, не об объективной нетранзитивности прочности – той нетранзитивности, когда при непосредственном механическом взаимодействии брусок А ломает бы (истирает, еще как-то портит) брусок В больше , чем В портил А; В портит С больше, чем С – В; а С портит А больше, чем А – С.

А кости Эфрона – это нетранзитивность, не связанная с неточностью измерения.

Я когда-то задавал вопрос о возможности нетранзитивности твердости А. Р. Оганову и Л. А. Ашкинази; оба ответили отрицательно.

Александр Поддьяков
5 года (лет) назад

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

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

Алексей В. Лебедев
Алексей В. Лебедев
5 года (лет) назад

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

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

Александр Поддьяков
5 года (лет) назад

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

Александр Поддьяков
5 года (лет) назад

Вот еще исследование разных нетранзитивностей, в том числе при промышленном контроле качества; интересная статья
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

Александр Поддьяков
5 года (лет) назад

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

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

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

Александр Поддьяков
2 года (лет) назад

В развитие идеи нетранзитивных шахматных позиций опубликована статья международного мастера по шахматной композиции Г.Л.Попова http://superproblem.ru/doc/columns/expert/2021/Non-transitivity.pdf

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

На видео https://youtu.be/rRKv90Uj3xM показаны игрушечные механические обезьянки. Они помогают друг другу нетранзитивным образом, по кругу: красная чистит зубки синей, синяя – зеленой, зеленая – красной (как в игре «камень, ножницы, бумага», только здесь не битье по кругу, а помощь).

Идея моя – прототип опубликован в «Науке и жизни»:

Принцип «камень, ножницы, бумага» в механических игрушках и его «родственные связи» // Наука и жизнь. 2022. № 4.
https://www.nkj.ru/archive/articles/43663/

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

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

Написал тогда “Мое предположение: возможно, и здесь (как в ряде некоторых других задач) мы выходим на ключевой вопрос о равенстве классов сложности P—NP”. Обнаружил сходное через 5 лет (сейчас): “For instance, in the set of k = 910 allowed nine-sided dice, the longest possible cycle is at least 891 (finding the precise length is NP-hard)”.

Julius B. Kirkegaard and Kim Sneppen. Emerging diversity in a population of evolving intransitive dice. PHYSICAL REVIEW E 106, 054409 (2022)
https://doi.org/10.1103/PhysRevE.106.054409

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