Алгоритмы для жизни: Простые способы принимать верные решения - [16]

И беглый анализ экономики Голливуда подтверждает эту догадку. Прибыль крупнейших киностудий к 2011 году упала на 40 % по сравнению с 2007-м, а продажи билетов снизились в 7 раз за последние 10 лет. Как выразились в журнале The Economist, «зажатые между ростом расходов и падением доходов, крупные киностудии ответили на вызов выпуском новых фильмов, которые, по их мнению, должны стать хитами: обычно сиквелов, приквелов или чего-то с участием узнаваемых персонажей». Другими словами, они дергают за рычаги лучших игровых автоматов, пока их не вышвырнули из казино.

Закрепи победу

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

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

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

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

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

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

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

Индекс Гиттинса

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

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