Текст книги "Код креативности. Как искусственный интеллект учится писать, рисовать и думать"

Гу Ли, соотечественник Ке Цзе и победитель большинства международных турниров по го, добавляет: «Работая вместе, люди и искусственный интеллект вскоре познают глубочайшие тайны го». Хассабис сравнивает свой алгоритм с телескопом «Хаббл». Это сравнение отражает взгляд многих на новый искусственный интеллект такого рода. Это инструмент, позволяющий исследовать глубже, дальше, шире, чем когда-либо раньше. Он должен не заменить человеческое творчество, но стимулировать его.

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

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

Учитывая, что игра го всегда казалась мне защитой от проникновения компьютеров в занятия математикой, может ли область моей собственной работы стать следующей мишенью DeepMind? Чтобы по-настоящему оценить потенциал этого нового искусственного интеллекта, нам нужно будет более пристально рассмотреть принципы его работы и покопаться в его внутреннем устройстве. Но поразительнее всего то, что для создания программ, которые, возможно, оставят меня без работы, DeepMind использует те самые инструменты, которые веками создавали именно математики. Так может ли это математическое чудовище Франкенштейна обратиться против своего же создателя?

4
Алгоритмы – секрет современной жизни

Аналитическая машина ткет алгебраические

узоры точно так же, как жаккардовый

станок ткет цветы и листья.

Ада Лавлейс

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

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

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

Предположим, что у нас есть два числа, M и N (предположим также, что N меньше M). Прежде всего разделим M на N и обозначим остаток от деления N₁. Если число N₁ равно нулю, то N – наибольшее число, на которое делятся оба исходных числа. Если же число N₁ не равно нулю, то разделим N на N₁ и обозначим остаток от деления N₂. Если число N₂ равно нулю, то N₁ – наибольшее число, на которое делятся и M, и N. Если же число N₂ не равно нулю, то повторим ту же операцию. Разделим N₁ на N₂ и обозначим остаток от деления N₃. Остатки от деления будут становиться все меньше и меньше, оставаясь при этом целыми числами, так что рано или поздно мы должны дойти до нуля. Алгоритм гарантирует, что, когда это произойдет, остаток от предыдущего деления будет наибольшим числом, на которое делятся и M, и N. Это число называется их наибольшим общим делителем.

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

Если M = 36, а N = 15, то при делении M на N получится остаток N₁ = 6. При делении N на N₁ получится остаток N₂ = 3. Но при делении N₁ на N₂ никакого остатка не получится, и таким образом мы выясняем, что наибольшее число, на которое делятся и 36, и 15, равно 3.

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

1. Он должен состоять из точно сформулированных и однозначных инструкций.

2. Процедура всегда должна заканчиваться (а не уходить в бесконечный цикл!), какие бы числа в нее ни ввели.

3. Она должна выдавать ответ для любых значений, введенных в алгоритм.

4. В оптимальном варианте алгоритм должен быть быстрым.

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

Если самые старые алгоритмы появились более 2000 лет назад, почему же само это название происходит от имени персидского математика IX века? Мухаммад Аль-Хорезми был одним из первых руководителей великого «Дома мудрости» в Багдаде и отвечал за перевод многочисленных древнегреческих текстов по математике на арабский язык.

Слово «алгоритм» происходит от латинской транскрипции его имени. Хотя все инструкции к алгоритму Евклида приведены в его «Началах», язык Евклида чрезвычайно невразумителен. Мышление древних греков было очень геометрическим; вместо чисел они говорили о длинах отрезков, а их доказательства состояли из изображений – приблизительно как в нашем примере с мощением пола. Но изображений недостаточно для строгих математических утверждений. Для них требуется язык алгебры, в котором буква может обозначать любое число. Именно в этом и состояло изобретение Аль-Хорезми.

Чтобы суметь ясно изложить, как работает алгоритм, нужен язык, позволяющий говорить о любом числе, не указывая, какое именно это число. Мы уже видели, как работает этот принцип, в объяснении действия алгоритма Евклида. Мы присвоили числам, которые пытались анализировать, имена – N и M. Эти переменные могут представлять любые числа. Могущество этого нового лингвистического подхода к математике состояло в том, что он позволял математикам понять грамматику, лежащую в основе операций с числами. Можно было не говорить о конкретных примерах работы того или иного метода. Новый язык алгебры дал возможность объяснять закономерности, определяющие поведение чисел. Подобно коду компьютерной программы он показывает, почему метод работает независимо от того, какие числа мы выберем, – в соответствии с третьим критерием нашего определения хорошего алгоритма.

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

Алгоритм длянеобитаемого острова

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

На заре интернета (я говорю о начале 1990-х) существовал каталог, в котором были перечислены все имеющиеся веб-сайты. В 1994 году их было всего 3000. Интернет был настолько мал, что было достаточно легко пролистать этот перечень и найти в нем то, что нужно. С тех пор ситуация сильно изменилась. Когда я начинал писать этот абзац, в интернете был 1 267 084 131 активный вебсайт. Спустя несколько предложений это число возросло до 1 267 085 440 (текущее состояние можно проверить по адресу http://www.internetlivestats.com).

Как же Google решает, какой именно из миллиардов сайтов рекомендовать? Мэри Эшвуд, 86-летняя бабушка из города Уигана[22]22
  Пригород Манчестера.


[Закрыть], всегда тщательно вставляла в свои поисковые запросы вежливые «пожалуйста» и «спасибо», возможно представляя себе, что обращается к группе энергичных практикантов, которые просеивают бесконечные запросы вручную. Когда ее внук Бен открыл ее лэптоп и увидел запрос «пожалуйста переведите римское число mcmxcviii спасибо», он не смог устоять перед искушением рассказать всему миру о заблуждениях своей бабушки через твиттер. Каково же было его удивление, когда кто-то из сотрудников Google ответил на его сообщение:

Дорогая бабушка Бена,

как вы поживаете?

Вы порадовали нас в мире миллиардов поисковых запросов.

Кстати, ответ – 1998.

Спасибо ВАМ

В этом случае бабушка Бена достучалась до человеческой части Google, но компания, разумеется, никак не может лично отвечать на все те запросы, которые поступают в систему Google – по миллиону каждые 15 секунд. Но, если в Google нет волшебных эльфов, прочесывающих интернет, как же поисковой системе удается столь поразительно эффективно находить ответы, нужные пользователю?

Причина всего этого – в мощности и красоте алгоритма, который Ларри Пейдж и Сергей Брин сочинили в стэнфордском студенческом общежитии в 1996 году. Сначала они собирались назвать свой алгоритм Backrub[23]23
  Буквально «массаж спины», «спиночёс» (англ.).


[Закрыть], но в конце концов остановились на имени Google, от принятого в математике названия числа, равного единице со ста нулями, – «гугол» (англ. googol). Их целью было ранжировать страницы интернета, что должно было помочь в ориентировании в этой постоянно растущей базе данных, так что название огромного числа казалось вполне уместным.

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

Такой метод вполне работоспособен, но его очень легко обмануть: любой хозяин цветочного магазина может тысячу раз вписать в метаданные своего сайта выражение «Цветы к Дню матери» и моментально окажется на первом месте в результатах поиска всех любящих сыновей и дочерей. Нужна поисковая система, которой хитрым веб-дизайнерам было бы не так просто помыкать. Как же можно получить неискаженную меру важности веб-сайта? И как выяснить, на какие сайты можно не обращать внимания?

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

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

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

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

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

Для его применения прежде всего нужно построить матрицу, отражающую перераспределение шаров между веб-сайтами. В первом столбце матрицы записывается доля шаров, передаваемых от веб-сайта А другим сайтам. В данном случае 0,5 общего числа шаров переходит сайту В, а еще 0,5 – вебсайту С. Тогда матрица перераспределения выглядит следующим образом:

Задача состоит в нахождении собственного вектора этой матрицы с собственным значением, равным 1. Это вектор-столбец, который не изменяется при умножении на саму матрицу[24]24
  Матрицы перемножаются по следующему правилу (примеч. авт.):


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

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

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

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

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

Информация об основном устройстве поисковой системы общедоступна, но внутри алгоритма есть параметры, которые держатся в тайне и изменяются со временем, что несколько затрудняет взлом алгоритма. Но замечательнее всего устойчивость алгоритма Google и его неуязвимость к попыткам его обмануть. Веб-сайту очень трудно сделать у себя что-либо, что повысило бы его рейтинг. Его положение могут усилить только другие сайты. Если вы посмотрите на веб-сайты, которым алгоритм ранжирования страниц Google присваивает высокий рейтинг, вы увидите среди них сайты многих крупных новостных агентств и университетов, например Оксфорда и Гарварда. Это связано с тем, что многие сторонние сайты размещают ссылки на данные и мнения, опубликованные на сайтах университетов, потому что многие люди по всему миру высоко оценивают исследования, которыми мы занимаемся.

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

Однако алгоритм не вполне неуязвим для хитроумных атак, организаторы которых понимают, как работает математика. В течение короткого периода летом 2018 года в результатах поиска в Google по слову idiot[25]25
  Идиот (англ.).


[Закрыть] на первом месте среди изображений оказывалось изображение Дональда Трампа. Активисты придумали, как использовать авторитетное положение в интернете сайта Reddit. Они предложили читателям этого сайта голосовать за сообщение, содержащее слово idiot и изображение Трампа, и связь между этими двумя элементами взлетела на самый верх рейтинга Google. Со временем этот пик сгладился, но не из-за вмешательства человека, а благодаря работе алгоритма. Google не любит играть в бога, но верит – в долгосрочной перспективе – в силу своей математики.

Разумеется, интернет – «существо» динамическое. Каждую наносекунду в нем появляются новые сайты и новые ссылки, а сайты, уже существующие, закрываются или обновляются. Это означает, что и рейтинг страниц должен изменяться динамически. Чтобы не отставать от непрерывной эволюции интернета, Google должен регулярно прочесывать Сеть и обновлять подсчет ссылок, соединяющих сайты. Это делается при помощи программ, носящих очаровательное имя «Google-пауков».

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

Два лондонских математика, Хавьер Лопес Пенья и Хьюго Тушетт (оба – страстные футбольные болельщики), решили проверить, не поможет ли алгоритм Google проанализировать команды, готовящиеся к чемпионату мира. Если представить каждого игрока веб-сайтом, а каждый пас от одного игрока к другому – ссылкой с сайта на сайт, то весь комплекс пасов, выполненных во время матча, можно считать сетью. Пас партнеру по команде говорит о доверии к этому игроку, – как правило, футболисты стараются не пасовать слабым игрокам, которые легко могут потерять мяч. Кроме того, чтобы получить пас, игрок должен оказаться открытым для передачи. Неподвижный футболист редко получает пас.

Они решили определить, у каких футболистов оказывается самый высокий рейтинг по количеству передач по данным, опубликованным ФИФА во время чемпионата мира 2010 года. Результаты получились в высшей степени увлекательными. При анализе игры сборной Англии показатели двух игроков, Стивена Джеррарда и Фрэнка Лэмпарда, оказались заметно выше, чем у всех остальных. Это отражает тот факт, что мяч очень часто передавался через этих двух полузащитников: без них игра сборной Англии просто развалилась бы. В том году выступление Англии на чемпионате мира было не особенно успешным: еще на раннем этапе турнира команда выбыла из соревнования, проиграв своему старому заклятому врагу – сборной Германии.

Совсем иначе обстояло дело в команде, ставшей победителем чемпионата, – сборной Испании. Алгоритм равномерно распределил ранги всех ее футболистов, то есть в команде не было явно выраженного центрального игрока, ключевого для всей игры. Это отражает чрезвычайно успешный стиль «тотального футбола», или «тики-така», которого придерживалась испанская команда: в нем игроки постоянно пасуют мяч друг другу, и эта стратегия способствовала победе Испании.

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

Сетевой анализ применяется даже к литературе. Эндрю Беверидж и Цзе Шань занялись эпической сагой «Песнь льда и пламени» Джорджа Р.Р. Мартина, широко известной по телесериалу «Игра престолов». Всякий, кто знаком с этим повествованием, хорошо знает, как трудно бывает предсказать, кто из его героев доживет до следующего тома – и даже до следующей главы, – так как Мартин безжалостно убивает даже лучших из созданных им персонажей.

Беверидж и Шань решили создать сеть между персонажами этих книг. Они выделили 107 основных героев, которые стали узлами сети. Затем персонажей соединили ребрами, взвешенными в соответствии с прочностью взаимоотношений между ними. Но как алгоритм может оценить значение такой связи? Алгоритму предложили просто подсчитать число появлений имен двух персонажей в тексте на расстоянии не более 15 слов друг от друга. Полученное значение не является мерой их дружбы – оно просто указывает на определенный уровень взаимодействия или взаимосвязи между ними.

Проанализировать решили третий том эпопеи, «Бурю мечей», так как к этому моменту повествование полностью развилось; исследование начали с анализа рейтингов узлов сети, соответствующих персонажам. Очень быстро были выделены три героя, важные для развития сюжета: Тирион Ланнистер, Джон Сноу и Санса Старк. Это открытие вряд ли удивит кого-либо, читавшего книги или смотревшего сериал. Удивительным было то, что компьютерный алгоритм, не понимавший, что он читает, пришел к такому же выводу. Он сделал это не простым подсчетом появлений имени каждого персонажа – в этом случае на вершине списка оказались бы другие имена. Более тонкий анализ сети позволил выявить главных героев.

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

Математика – секрет счастливого брака

Пусть Сергей Брин и Ларри Пейдж и создали код, направляющий вас на сайты, которые вы искали, даже сами того не зная, но может ли алгоритм работать в такой интимной сфере, как поиск родственных душ? Зайдите на сайт знакомств OKCupid, и там вас встретит лозунг, гордо заявляющий: «Мы найдем вам пару при помощи математики».

«Алгоритм подбора партнеров» таких сайтов знакомств перебирает профили пользователей и составляет из них пары на основе их симпатий, антипатий и черт характера. Судя по всему, эти сайты совсем не плохо справляются со своей работой. Более того, кажется, что алгоритмам подбор партнеров удается лучше, чем нам самим: в исследовании, результаты которого были недавно опубликованы в журнале Proceedings of the National Academy of Sciences, были рассмотрены 19 000 человек, сочетавшихся браком между 2005 и 2012 годами. Выяснилось, что у пар, встретившихся в интернете, браки получились более счастливыми и устойчивыми.

Первый алгоритм, принесший своим создателям Нобелевскую премию, был изначально сформулирован двумя математиками, Дэвидом Гейлом и Ллойдом Шепли, в 1962 году. Они использовали алгоритм подбора партнеров для решения так называемой «Задачи о марьяже». Гейл умер в 2008-м, так и не успев получить своей награды, но Шепли разделил премию 2012 года с экономистом Элвином Ротом, который разглядел важность этого алгоритма не только в вопросе личных связей, но и в применении к социальным проблемам, в том числе к справедливому предоставлению услуг здравоохранения или мест для обучения в вузах.

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

Задача о марьяже, которую решили Шепли и Гейл, больше похожа на салонную игру, чем на элемент передовой экономической теории. Чтобы понять, в чем именно состоит эта задача, представим себе четырех гетеросексуальных мужчин и четырех гетеросексуальных женщин. Всем им предложили расположить четырех представителей противоположного пола в порядке личных предпочтений. Алгоритм должен распределить их по парам так, чтобы получить устойчивые браки. Это означает, что в результате ни один мужчина и ни одна женщина не должны стремиться друг к другу больше, чем к назначенным им партнерам. В противном случае вполне вероятно, что в какой-то момент они оставят своих супругов и сбегут друг с другом. На первый взгляд не вполне ясно, можно ли вообще решить эту задачу – даже при наличии всего четырех пар.

Возьмем один конкретный пример и рассмотрим, как Гейлу и Шепли удалось гарантировать стабильность этих союзов, причем систематическим и алгоритмическим образом. Роли четырех мужчин у нас будут играть четыре короля из карточной колоды: король пик, король червей, король бубен и король треф. Женщинами будут соответствующие дамы. Все короли и дамы выразили свои предпочтения:

Для королей:

Для дам:

Предположим теперь, что вначале мы предлагаем сочетать каждого из королей с дамой той же масти. Почему эта комбинация даст неустойчивые браки? Дама треф назвала короля треф наименее предпочтительным партнером, так что, честно говоря, она будет счастливее с любым другим королем. А теперь посмотрим на список короля червей: дама червей стоит у него на последнем месте. Он явно предпочел бы даму треф тому варианту, который ему предложили. В этом сценарии можно предположить, что дама треф и король червей сбегут от своих супругов друг с другом. Таким образом, подбор дам и королей по масти приводит к неустойчивым бракам.

Как же подобрать пары так, чтобы никакие две карты в конце концов не сбежали друг с другом? Вот какой механизм разработали Гейл и Шепли. Он состоит из нескольких раундов предложений от дам королям, которые повторяются до тех пор, пока не получится распределения по устойчивым парам. В первом раунде работы этого алгоритма все дамы делают предложение королям, которых они предпочитают больше всего. Первое место в списке дамы пик занимает король червей. У дамы червей первым стоит король треф. Дама бубен выбирает короля пик, а дама треф делает предложение королю червей. Похоже, что король червей – главный сердцеед в этой компании: он получил сразу два предложения. Он выбирает из двух дам ту, которую предпочитает больше, то есть даму треф, и отказывает даме пик. Итак, у нас есть три предварительные помолвки и один отказ.

Первый раунд

Дама, получившая отказ, вычеркивает из своего списка первого кандидата и в следующем раунде делает предложение второму – королю пик. Но теперь король пик получает два предложения. В первом раунде ему сделала предложение дама бубен, а теперь – еще и дама пик. Судя по его рейтингу, он предпочитает даму пик. Поэтому он довольно жестокосердно отвергает даму бубен (с которой у него была заключена предварительная помолвка в первом раунде работы алгоритма).

Второй раунд

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

Третий раунд

Наконец все участники разбиты по парам, и все браки устойчивы. Хотя мы изложили этот алгоритм в терминологии милой салонной игры с карточными дамами и королями, он применяется сейчас во всем мире: в Дании – для распределения детей по детским садам, в Венгрии – для записи учеников в школы, в Нью-Йорке – для назначения раввинов в синагоги, а в Китае, Германии и Испании – для подбора университетов для студентов. Национальная служба здравоохранения Великобритании использует его при подборе пациентов для получения донорских органов, что помогло спасти множество жизней.

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