Журнал `Компьютерра` №739

анализы: "Камень, ножницы, бумага" в небумажных областях

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

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

Специалисты по интеллектуальным играм сталкиваются с такой ситуацией нередко: в борьбе компьютерных программ, участвующих в соревнованиях по шахматам, нардам и т. п., программа А может регулярно выигрывать у программы В, та - у С, а программа С, вроде бы самая слабая в этой тройке, может систематически выигрывать у А [Мельников Б., Радионов А. Программирование недетерминированных игр // Гордон А. Г. Диалоги. М.:Предлог, 2005. С. 93–112.Мосеев А. В. Применение методов искусственного интеллекта в переборных алгоритмах. Дипломная работа.Ульяновск: УГУ, 1999. Финоженок Д. GridWars II: битва за процессоры // Компьютерра, 2003, #28 (503).]. Если бы речь шла о спортсменах (а в спорте подобные ситуации тоже не редкость), "парадокс" мог бы объясняться психологическими или физиологическими причинами (например, большая спортивная злость членов одной команды, большее физическое утомление и демотивированность кого-то из спортсменов и т. д.). Но похоже, что нетранзитивность (непереходность) превосходства, когда одно превосходит другое, другое - третье, а третье, в свою очередь, почему-то превосходит первое, - это отнюдь не менее важное свойство мира, чем кажущаяся более логичной его же, превосходства, транзитивность [Объясняя понятие непереходности превосходства по-житейски, можно сказать, что превосходство А над В и затем В над С не переходит, не распространяется и на пару А-С: А не превосходит С.]. Кстати, транзитивность превосходства мы тоже начинаем осваивать с детства - вспомним детские задачки вроде "Петя выше Толи, Толя выше Бори.

Кто из них выше всех?".

Несмотря на простоту такого рода примеров ("Петя, Толя, Боря", с одной стороны, и "камень, ножницы, бумага" - с другой), транзитивность и нетранзитивность превосходства вызывают дискуссии самых разных специалистов, ведущиеся на самых разных уровнях.

Причем часть из этих специалистов убеждена в том, что на самом деле, если глубоко разобраться и тонко учесть все факторы ("taking all considered"), нетранзитивность превосходства окажется иллюзией, следствием ошибочных рассуждений и неправильно интерпретированных наблюдений. Другие, напротив, считают, что как раз транзитивность превосходства - это всего лишь результат выдергивания и искусственной изоляции короткой цепочки превосходств из более общего цикла взаимодействий, в котором они реально существуют. Причем и те и другие рассуждают достаточно строго, и их не упрекнешь в очевидных логических ошибках - например, в попытках поставить и решить задачу типа "Петя выше Толи, Толя толще Бори. Кто из них директор?".

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

Брэдли Эфрон (Bradley Efron), специалист по статистике из Стэнфордского университета, предложил комплекты игральных костей, обладающих парадоксальными свойствами [Секей Г. Парадоксы в теории вероятностей и математической статистике. М.:Мир, 1990.].

(Психолог В. А. Петровский удачно назвал эти комплекты "бойцовским клубом игральных кубиков".) Все кубики любого такого набора одинаковы и "честны" в отношении своей геометрической формы, веса и т. д.

Единственная разница между ними - в числах, нанесенных на их грани. Числа подобраны так, что на верхней грани первого кубика при бросках чаще выпадает большее число, чем на втором; на втором чаще выпадает большее число, чем на третьем, и т. д., но последний кубик чаще показывает большее число, чем первый (!). Благодаря этому первый систематически выигрывает у второго, второй - у третьего и т. д., но последний кубик - казалось бы, аутсайдер! - систематически выигрывает у первого - казалось бы, безусловного фаворита.

Кто не верит в этот факт нетранзитивности превосходства "чаще показывать большее число" (сразу поверить трудно), может поэкспериментировать в Интернете на странице edp.org/dice.htm с симуляцией соревнований или самостоятельно решить приведенную ниже задачку [Roberts T. S. A ham san d - wich is better than no thing: Some thoughts about transitivity // Australian Senior Ma thematics Journal. 2004.18 (2). P. 60–64].

Есть четыре игральных кубика со следующими числами на гранях.

Кубик A: 7, 7, 7, 7, 1, 1

Кубик B: 6, 6, 5, 5, 4, 4

Кубик C: 9, 9, 3, 3, 3, 3

Кубик D: 8, 8, 8, 2, 2, 2

Каково соотношение побед и поражений в парах A-B, B-C, C-D и D-A?

(Ответ: каждый предшествующий кубик в среднем выигрывает у последующего вдвое больше партий, чем проигрывает. Но последний кубик D выигрывает вдвое больше партий у кубика А, чем проигрывает ему.)

Поэтому при возможности выбора из пары кубиков А и В надо выбрать А, оставив сопернику более "проигрышный" кубик В; при выборе между В и С надо выбирать В; при выборе между С и D надо выбирать C; но при выборе между D и А надо выбирать D.

Известный популяризатор математики Мартин Гарднер, который в течение многих лет вел математическую рубрику в журнале Scientific American, писал, что нетранзитивные кости "позволяют глубже осознать значение…

открытий, связанных с общим классом вероятностных парадоксов, в которых нарушается правило транзитивности. С помощью любого из этих наборов игральных костей вы можете держать пари в условиях, настолько противоречащих интуиции, что опытные игроки почти не в состоянии разобраться в них, даже если они полностью проанализируют ход игры"[Гарднер М. Крестикино лики. М.: Мир, 1988. С.63–66.].

Разработан и алгоритм генерации чисел для такого рода объектов (причем не только кубиков, но и многогранников, рулеток и т. п.), образующих цепочку любой длины[Deshpande M. N. Intran sitive dice // Teaching statistics. 2000. 22 (1). 4–5.].

Что все-таки хорошо - рулетки, игральные кубики и прочие геометрические фигуры взаимодействуют лишь числовым образом и непосредственно, физически, друг на друга не бросаются, уязвимых мест друг у друга не ищут и не стараются лупить по этим местам из штатного вооружения. Так бывает не всегда. Как же проявляется нетранзитивность превосходства в "бойцовских клубах" без кавычек - в ситуациях непосредственного боевого столкновения сторон с целью физического уничтожения противника или, по крайней мере, выведения его из строя? (Здесь я на время зайду на территорию Михаила Ваннаха, но с мирными целями.)

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

Схватка длится до выхода механизма из строя. Отталкиваясь от особенностей реально используемых в этой игре устройств, представим три условных танка следующих типов [Поддьяков А. Н. Непереходность (нетранзитивность) отношений превосходства и принятие решений // Психология. Журнал Высшей школы экономики. 2006. № 3.С. 88-111.].

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

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

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

Нет нужды подробно объяснять, что модель баланса "нападение - защита - уязвимые места" применима и к спорту, и к борьбе компьютерных программ, и к психологической борьбе. Кроме того, возможно, именно такого типа механизмы взаимодействий лежат в основе активно изучаемых в биологии отношений "бойцовской силы" (combative relations) разных видов живых существ. Остановимся на этом подробнее.

В журнале Nature прошла целая серия статей по биологии со словами "камень-ножницы-бумага" (rock-paperscissors games) в заголовках; статьи с несколько другими заголовками, но на ту же тему нетранзитивности публиковались и в других журналах [Boddy L. Interspecific com bative interactions between wood-decaying basidiomycetes // FEMS Microbiology Ecology. 2000. 31. 185–94. Kerr B. et al. Local dispersal promotes biodiversity in a reallife game of rock–paperscissors // Nature. 2002. 418.P. 171-174.

Kirkup B. C., Riley M. A. An ti bioticmediated antagonism leads to a bacterial game of rockpaperscissors in vivo // Nature. 2004. 428. P. 412-414. Reichenbach T. et al. Mobility promotes and jeopardizes bio diversity in rock-paperscissors games // Nature. 2007. 448. P. 1046-1049.] В этих работах показано, как, например, один вид микроорганизмов вытесняет с территории второй вид, этот второй вытесняет третий, а третий, в свою очередь, вытесняет первый. Отношения "бойцовской силы" между этими видами нетранзитивны.

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

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

Картинки не только красивы сами по себе, но и многое говорят о правде биологической жизни. На русском языке рекомендую статью А. М. Гилярова "Виды могут конкурировать по принципу “камень-ножницы-бумага”"(elementy.ru/news/430582), где это очень хорошо описано и показано на видеороликах.

Добавим: дело не ограничивается взаимодействием только самих конкурирующих видов, а имеет следствия разной степени отдаленности. Полученные в этих исследованиях данные могут объяснять некоторые особенности поведения весьма высокоорганизованных живых существ, кажущиеся на первый взгляд нерациональными. Так, в биологических экспериментах обнаружена нетранзитивность предпочтений у пчел: при возможности выбора между цветками А и В пчела выбирает цветок А (садится на него), при выборе между В и С предпочитает В, но С предпочитает А [Shafir S. Intransitivity of pre ferences in honey bees: support for comparative evalu ation of foraging op tions // Animal Behaviour. 1994. 48. 55–67.]. Возможное рациональное объяснение этой "нелогичности" выборов состоит в том, что некоторые растения угнетающе действуют на растения другого вида, и если пчела "знает" это на инстинктивном уровне или воспринимает своими рецепторами, то она может избегать цветов, ставших в ходе этой борьбы неприятными или опасными (или, наоборот, стремиться к цветам, ставшим особенно вкусными), что и приводит к нетранзитивности предпочтений.

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

Есть три преподавателя. Первый отлично знает математику и может ее преподавать; удовлетворительно знает географию, но не настолько хорошо, чтобы ее преподавать; и не знает испанского языка. Второй отлично знает географию и может ее преподавать, удовлетворительно знает испанский, не знает математики. Третий же отлично знает испанский и может его преподавать; удовлетворительно знает математику и не знает географии. Можно убедиться, что отношение "быть лидером" (в меркантильном варианте - отношение "получать больше денег при взаимодействии") будет нетранзитивным на курсах взаимного повышения квалификации, организованных в этой группе: в паре "учитель 1 - учитель 2" станет лидировать (и получать больше денег) первый учитель, в паре "учитель 2 - учитель 3" - второй, а в паре "учитель 1 - учитель 3" - третий. Аналогично строятся круги превосходства: "Врач для врача", "Ремонтник для ремонтника" и т. п. (Заинтересовавшийся читатель может продолжить построение сходных структур на том материале, который ему нравится.) Кстати, в психологической типологии Карла Густава Юнга различные типы личностей образуют именно такой, нетранзитивный круг психологических отношений и взаимодействий.

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

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

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

Когда люди играют несколько десятков таких игр подряд, то в группе участников наблюдается следующая динамика[Semmann D. et al. Vo lunteering leads to rock-paperscissors dynamics in a public goods game // Nature. 2003. 425. P. 390-393.]. Вначале "инвесторы" с направленностью на кооперацию вкладывают большую часть своих денег (или даже все деньги) в общую кассу, и прибыль, делимая на всех членов "кооператива", большая. Соответственно, растет материальная заинтересованность вступить в "кооператив" и получить часть этой прибыли, своих денег почти не тратя - растет число "халявщиков". Теперь те, кто раньше вкладывал много, понимают, что они оказались в невыгодном положении - мало того что отдают боольшую часть своей начальной суммы, уменьшая тем самым остаток, так еще и прибыль уменьшается. Поэтому в группе увеличивается число "одиночек", не желающих в создавшихся условиях образовывать какие-либо "кооперативы" и вкладывать деньги в "общие проекты". Распределяемая прибыль падает, количество "халявщиков" тоже (игра не стоит свеч). Потенциальные инвесторы, подумав, опять решают рискнуть, и т. д., и снова все идет по кругу: динамика "инвесторов - халявщиков - одиночек" развертывается по логике "камня, ножниц и бумаги"[Тут бы нам и порадоваться, с надеждой экстраполируя эти данные на окружающую действительность. Если сейчас нечестных - халявщиков - много, значит, станет меньше. Одно "но" - это исследование проведено на европейской выборке. Что касается россиян, то у них в другом исследовании выявилась печальная тенденция. Получив возможностьштрафовать халявщиков (например, заплатив одну монету, участник может снять с того, кто ему не нравится, три монеты), наши люди, в отличие от европейцев, в среднем сильнее наказывают как раз не халявщиков (тех, кто вложил меньше их), а тех, кто вложил больше их. В результате все участники расходятся со(Gachter S., Herrmann B. The limits of selfgovernance in the presence of spite: experimental evidence from urban and rural Russia // IZA Discussion Papers. 2006.No. 2236)].

Разумеется, это лишь упрощенная модель. В реальной экономической жизни сюда добавятся факторы, связанные с транзитивностью/нетранзитивностью отношений биологических видов и влияющие, например, на урожай той или иной культуры, с парадоксами нетранзитивности на политических выборах (разные версии парадокса Кондорсе [Баранов В. Грабли маркиза де Кондорсе // Компьютерра, 2000, #6 (335). offline.computerra.ru/2000/335/2939] и не только), с периодически возникающим желанием применить оружие, различные виды которого тоже находятся в нетранзитивных отношениях, и т. д. Сюда также добавятся факторы, связанные с человеческими интеллектуальными и эмоциональными ошибками - когда люди принимают объективно транзитивные отношения превосходства за нетранзитивные и наоборот.

Из вышеизложенного понятно, что отношения между транзитивностью и нетранзитивностью превосходства могут быть весьма сложными и трудно просчитываемыми. Классическая аксиома транзитивности превосходства ("если первое превосходит второе в определенном отношении, а второе превосходит третье, то первое превосходит третье в указанном отношении"), следование которой считается обязательным в традиционной теории принятия решений, а не-следование - ошибкой, перестает работать в сложных ситуациях, когда сравниваемые объекты взаимодействуют между собой - цифровым ли, физическим, социальным или иным образом (а также всеми вместе). Такие задачи трудно формализовать, но решать приходится. Ответ на вопрос, кто (или что) победит и как можно в ситуацию вмешаться, вводя новые механизмы, орудия и правила, интересен не только при прогнозе исхода футбольных соревнований или соревнования программ по интеллектуальным играм.