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

Какие задачи все же удастся решить?.

Так вот, оказывается, что можно делать довольно интересные вещи. Удивительно, что некоторые задачи, которые вначале выглядят совсем простыми, требуют больше размышлений и вычислений, чем кажется на первый взгляд. Далее в этой главе рассказывается о Роско Леруа и одной.

такой задаче.

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

Роско описывает ситуацию.

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

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

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

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

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

Моделирование отбивающего.

- Для всякого моделирования такого рода нужен какой-то генератор случайных чисел, - продолжал Роско.

- Так, - сказал я, - и какие же у вас оказались для этого приспособления?.

- Не так много, - отвечал Роско. - У нас было три одинаковых обычных игральных кости, от одной до шести точек на каждой грани. И я решил, что с их помощью легко будет смоделировать вероятности, потому что именно они нам были нужны. Мы решили, что проще всего бросать все три кости одновременно, складывать очки и по сумме определять успех или поражение.

- Вероятности? Я не совсем понимаю, - сказал я.

- Разумеется, вероятности! В этом и есть идея воображаемого бейсбола. Допустим, что у базы стоит отбивающий, средний результат которого равен 0,250. На первом уровне приближения (забудем на минуту о прогулках) мы случайным образом определяем, удалось ли ему отбить мяч, для чего нам надо получить случайное событие с вероятностью 250 из 1000. Никогда не замечал у Роско такого интереса к теории вероятностей и статистике, но меня еще многое ждало впереди.

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

- Хорошо, допустим, вы сделали все эти упрощения. Как вы моделируете действия отбивающего в доме? - спросил я.

- Мы должны позаботиться только о двух вещах, - отвечал Роско. - Выступлениях в доме (plate appearances - PA) и официальных выходах на биту (at-bat - AB). Если игрок получает «базу на болах», или «прогулку», это засчитывается ему как PA, но не как официальный AB. Поэтому в принципе нужны два числа: процент от выступлений в доме, за которые игрок получает AB, и его показатель отбивания (batting average). Допустим, например, что игрок получает базу на болах один раз из каждых 10 выступлений в доме.

Тогда надо сначала определить, получает ли игрок прогулку, путем случайного испытания с вероятностью успеха 0.1. Если есть три кости, необходимо выяснить, какое количество очков выпадает с такой вероятностью. Так что бросаешь кости, получаешь эту сумму - и вперед! Отбивающий идет на первую базу и все в порядке. С другой стороны, если выпадет другая сумма, игрок не получает «прогулку». Вместо этого у него официальный выход на биту. Допустим, что средний показатель отбивания у него .250 и есть событие на костях, у которого такая вероятность. Если оно выпало, то он успешно отбил мяч, если нет, значит, он попал в аут. Можно, конечно, по статистике выходов на биту моделировать тип удара - одиночный, двойной, тройной или хоумран. И так далее. Я взял в качестве примера средний показатель отбивания, но можно детализировать модель по своему вкусу в зависимости от того, сколько «сложных ситуаций» ты хочешь учесть.

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

- Достаточно понятно. Суть ясна. Так в чем проблема? - поинтересовался я.

- Проблема в следующем, - ответил Роско. - Можно ли моделировать вероятности с помощью такого простого приспособления, как три игральные кости, и при этом обеспечить необходимое разрешение? Например, если мы сможем моделировать только вероятности .250, .500 и .750, то этого будет недостаточно для хорошей модели.

- Начать с того, что если ты станешь бросать три кости одновременно, то получишь суммы от 3 до 18, т. е. 16 разных исходов, - отвечал я.

- Верно, - сказал Роско, - именно так мы и приступили к делу.

Первые шаги.

- Понедельник разобрался с комбинаторикой. Для трех костей с шестью гранями возможны 6x6x6 исходов, или 216 возможностей, но всего 16 разных сумм. Итак, у него получилась табл. 20.1.

Таблица 20.1. Количество вариантов для получения различных сумм

- Это мне нравится, - отвечал я. - Симметрия видна невооруженным глазом. Например, 3 и 18 появляются по одному разу, как и должно быть. Для 4 и 17 значения одинаковы, и т. д. Чаще всего получаются 10 и 11, потому что эти суммы дают многие комбинации. И в сумме получается 216, так что все, возможно, правильно. Но, по всей видимости, получится всего восемь разных значений для вероятностей.

- Видимость бывает обманчива, - отвечал Роско. - Но для большей надежности сложим-ка те вероятности, которые у нас уже есть. - И он показал табл. 20.2.

Таблица 20.2. Вероятности, соответствующие каждой сумме

- Надо же! - воскликнул я. - Роско умеет делить на 216!.

- Спокойно, сынок, - сказал Роско. - Все только начинается.

Следующие шаги.

- Должно быть очевидно, что если ты хочешь смоделировать вероятность 0,00463, то для успеха банкомет должен выбросить 3 очка. Конечно, можно ждать и 18 - симметричного результата, но нам нужны отдельные вероятности, поэтому мы выбираем что-нибудь одно. Выберем 3. - Роско подождал секунду и выдал свой первый сюрприз.

- Но что будет, если определить «успех» как выпадение 3 или 4 очков? Вероятность выбросить 3 составляет 0,00463, а вероятность выбросить 4 составляет 0,01389, поэтому вероятность выбросить 3 или 4 составляет просто 0,00463 + 0,01389, или 0,01852. Теперь ты видишь, что можно создать некоторые другие отличные значения вероятности, рассматривая как «успешные» несколько сумм.

- Так, правильно ли я понял? - отвечал я. - Чтобы моделировать.

0,00463, мне надо, чтобы выпала тройка. Чтобы моделировать 0,01389, мне надо, чтобы выпало число 4. А чтобы моделировать 0,01852, мне нужно, чтобы выпало 3 или 4. Только и всего?.

- Да, ты понял правильно. Но как ты определишь, какие еще есть возможности? - Улыбка на лице Роско граничила с ухмылкой. Я всерьез задумался.

Получение дополнительных вероятностей.

- Так, - сказал я, - добавляем в твою таблицу еще колонку. Какие-то новые вероятности можно получать, рассматривая другие «совокупные» исходы. - Я поправил таблицу Роско, и получилась табл. 20.3.

Таблица 20.3. Дополненная таблица вероятностей

- Что ж, ты на правильном пути, - реагировал Роско. - В твоей четвертой колонке явно появились новые вероятности. Например, вероятность выпадения 3 или 4 равна 0,00463 + 0,01389, или, как ты вычислил, 0,01852. Вместо «3 или 4» можно сказать «4 или меньше». Говоря «5 или меньше», ты имеешь в виду, что успешный исход составляет выпадение суммы 3, 4 или 5. На самом деле мы с Понедельником тоже действовали именно в этом направлении. Только это далеко не все.

- Прежде чем ты двинешься дальше, - сказал я, - давай посмотрим, сколько вероятностей у нас уже есть. Я отмечу в таблице все различные вероятности. - И я добавил затенение, получив табл. 20.4.

Таблица 20.4. Дополненная таблица вероятностей с затенением

- Я насчитал 8 в одной колонке и 14 в другой, т. е. всего 22. Это правильно? - спросил я.

- Не совсем, - отвечал Роско.- У нас наблюдается, так сказать, случайное вырождение. Вероятность выпадения 6 совпадает с вероятностью выпадения «5 или менее». Это потому, что 10 способов дают 6, и (1 + 3 + 6 = 10) дают 3, или 4, или 5, т. е. 5 или меньше. Так что я думаю, у нас пока 21 различная вероятность. Но, как я сказал, это далеко не все. Есть множество других комбинаций.

Про бейсбол мы, конечно, уже забыли.

Задача несколько осложнялась. - И что же вы предприняли дальше? спросил я у Роско.

- Ну, кое-что стало понятно, - отвечал Роско. - Понедельник усадил меня и стал рассказывать умные вещи. Для начала он сообщил, что если мы хотим генерировать вероятности для бейсбола, то выбрали не лучший путь. Он предложил систему, в которой можно было бы бросать одну кость несколько раз и генерировать все то, что нам надо для бейсбола. Я вынужден был с ним согласиться.

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

Действительность уродлива.

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

Роско закурил сигару, и я решил, что сейчас последует завершение истории. - Надо сказать, Понедельник предложил решение задачи уже на следующий день, - продолжал Роско.

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

/216, или 0,00463.

- Как генерировать первую вероятность, мы уже знаем! - сказал я.

Роско усмехнулся.

- А почему ты считаешь, что важно определить максимально возможное количество вероятностей?- спросил я.

- Потому что, - сказал Роско, - если этого не сделать, возникнет проблема. Допустим, что ты покопаешься и найдешь 87 различных вероятностей, а не 21, как мы пока смогли.

Как узнать, что ты нашел их все и ничего не пропустил? Зная максимальное число, ты можешь остановиться, когда достигнешь его. Если нет, то придется выяснять, почему не получается найти остальные. На самом деле надо выяснить, сможем ли мы реализовать 108 возможностей до вероятности 0,5. Остальные 108 получатся как дополняющие решения.

Это было разумно. В данной области стандартно применяется такой прием. Если ты знаешь, что 3 выпадает с вероятностью 0,00463, то выпадение чего угодно, кроме 3, имеет вероятность (1 - 0,00463), или 0,99537. Поэтому получить вероятности до 0,5 всегда бывает достаточно.

Решение Понедельника.

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

- Сначала он решил выяснить, - продолжал Роско, - все ли начальные девять «путей» могут быть построены. У него получилась табл. 20.5.

Таблица 20.5. Как получить первые 9 способов

- Кажется, понимаю, - сказал я. - Понедельник пытается выяснить, сможет ли он построить полный набор «способов» вплоть до 108 из элементов колонки «количество способов» - 1, 3, 6, 10, 15, 21, 25 и 27. Очень толково.

- Да, - ответил Роско,- мысль именно такая. Но помни, что каждым элементом он может воспользоваться только дважды. Симметрия помогает, но обрати внимание, что «способы» расходуются, поэтому необходима внимательность. Например, предположим, что мы уже использовали 3 и 18 и нам нужен еще один «путь». У нас ничего не выйдет. Поэтому придется соблюдать известные ограничения.

- А-а, - сказал я, - так ответ все еще под сомнением.

- Понедельник оказался на высоте, - сказал Роско.- Вот как он рассуждал дальше. Получается, что есть 10 способов выпадения 6. Если взять 6 и дополнительное к нему 15, получатся две десятки, стало быть, мы можем теперь конструировать количество способов от 1 до 29. Теперь мы можем везде добавлять от 1 до 29, если при этом нам не понадобятся дополнительно суммы 3, 4, 5, 6, 15, 16, 17 и 18. Мы израсходовали все элементы количества способов 1, 3, 6 и 10.

- Ну, от 29 до 108 все еще далековато, - сказал я.

Роско изложил решение Понедельника до конца. - Если теперь использовать одну из сумм с 21 путями, например 8, то диапазон расширится с 29 до 50. А у тебя еще остаются по две суммы для 15, 25 и 27 путей. Взяв вторую сумму с 21 способом, расширим диапазон с 50 до 71. Пара по 27 способов дает нам 125 вариантов, а это больше нужных нам 108. Так что задача решаема.

- Стало быть, ты утверждаешь, - отвечал я, - что реализуемы все варианты, т. е. мы покроем весь интервал с шагом в

/216. Это поразительно. Ты построил фактическую таблицу?

Таблица 20.6 (продолжение)

- Обрати внимание,- сказал Роско, - что некоторые решения не единственны. Но этого и не требуется. Нам достаточно найти лишь один набор сумм, который дает требуемое количество способов «попасть в него».

Полученные уроки.

Когда Роско закончил рассказ, он не выглядел совершенно удовлетворенным. «Что тебя беспокоит, Роско?» - спросил я.

- Ну, во-первых, я опять обманулся, - отвечал он.- Я думал, что это задачка для детей, а оказалось, что она гораздо сложнее. Это всегда раздражает.

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

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

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

/216

Замечательно то, что можно решить эту задачу на необитаемом острове и без всяких компьютеров, Microsoft Excel и сводных таблиц, потратив только время, энергию и проявив интеллектуальное любопытство. Это также означает, что Блез Паскаль мог решить эту задачу в XVII веке: у него были все необходимые для этого инструменты. В недостатке интеллекта и любознательности его тоже не упрекнешь. Любопытно, что, как отмечает Хемминг, примерно в 1642 г. Галилей решал вопрос о том, какая сумма более вероятна при бросании трех костей- 9 или 10. Он добрался как минимум до нашей табл. 20.1, правильно рассудив, что 10 немного более вероятно, чем 9. Так что люди размышляли о подобных вещах задолго до появления бейсбола.

Роско и Понедельник в конечном итоге смогли моделировать равномерное распределение с точностью около половины процента,

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

Резюме.

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

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

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

Перехожу к последней части книги, которую я назвал «Более сложные вопросы».