Дилемма заключенного и доминантные стратегии. Теория игр [Хорди Деулофеу] (fb2) читать онлайн

Хорди Деулофеу Дилемма заключенного и доминантные стратегии. Теория игр

Предисловие

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

Н. И. Лобачевский

Если люди отказываются верить в простоту математики, то это только потому, что они не понимают всю сложность жизни.

Джон фон Нейман

Какова взаимосвязь между играми и математикой? Математические игры — это всего лишь развлечение, или же их можно использовать для моделирования реальных событий? Что нужно для анализа игры с точки зрения математики и что может дать подобный анализ? Можно ли использовать математику при анализе поведения человека и при принятии решений?

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

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

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

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

Важная часть теории игр заключается в формулировке и анализе определенных дилемм, например, как в игре «Ястребы и голуби» (в какой степени оправдан риск?) или в дилемме заключенного (что выгоднее — молчать или доносить?). В подобных ситуациях, которые повсеместно встречаются в нашей жизни, трудный выбор между сотрудничеством и соперничеством осложняет принятие оптимальных решений. Математика не дает окончательных ответов на подобные вопросы, но с помощью оценки разных вариантов помогает определить риски безрассудного соперничества и понять выгоду сотрудничества.

Глава 1. История взаимоотношений игр и математики

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

Платон

Математика — это серьезная или развлекательная наука? Теоретическая или прикладная? Разумеется, на оба эти вопроса можно дать один и тот же ответ: «И то и другое». Но может показаться, что так мы уйдем от реального ответа, поэтому попытаемся раскрыть мысль.

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

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

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

Математика занимательная и серьезная, чистая и прикладная

Джон фон Нейман, один из главных героев этой книги, в своей лекции «Роль математики в науке и обществе» (The Role of Mathematics in Science and Society) подтвердил, что множество важнейших математических идей появились без каких-либо мыслей об их предполагаемой полезности, но по прошествии времени математические теории, модели и методы стали использоваться при решении задач в самых разных областях человеческих знаний. В то же время многие математические идеи зародились в реальном мире, в котором мы живем, потому что математика, пусть и далекая от реальности, тем не менее в разных формах присутствует в ней.

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

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

Головоломка, игра и математическая задача весьма схожи: они представляют собой вызов интеллекту. Принимая этот вызов, игрок (или тот, кто решает задачу) должен приложить определенные умственные усилия, чтобы справиться с задачей или обыграть соперника. Подобные усилия кому-то могут показаться обременительными и скучными, но они приносят подлинное удовольствие тем, кому по душе математика, загадки для ума или игры, в которых нужно подумать. Ведь, как говорил Мигель де Гусман, математика — это всегда игра, а также многое-многое другое.

Многие традиционные игры можно проанализировать с точки зрения теории игр.

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

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

Игры и математика до XVII века

С древнейших времен история математики полна упоминаний об играх и занимательных задачах. В действительности с момента появления игр (параллельно этому началось развитие математики) и до XVII века серьезную и занимательную математику нельзя отделить друг от друга, так как во многом они тесно переплетались. В 1612 году во Франции была издана первая книга, посвященная исключительно занимательной математике, — Problemes plaisants et delectables qui se font par les nombres («Приятные и восхитительные проблемы, которые создают числа») Клода Гаспара Баше де Мезириака. С этого момента два течения в математике постепенно начали расходиться, хотя в дальнейшем им не раз доводилось пересекаться. К примеру, это произошло, когда Ферма и Паскаль разработали основы теории вероятностей. Великие Ньютон, Эйлер и Гаусс проявляли живой интерес к занимательным задачам; игры также фигурируют в работах Эдуарда Люка о числах. И лишь в середине XX века эти направления окончательно объединила теория игр.

Игры и математика в Античности

Уже в двух великих цивилизациях древности, вавилонской и египетской, где математика носила исключительно практический характер, встречаются настольные игры и занимательные задачи. Первые упоминания о настольных играх, дошедшие до наших дней, относятся к египетской игре сенет и к настольной игре урских царей Вавилонии. С другой стороны, в одной из древнейших рукописей о математике — папирусе Ахмеса, который датируется примерно 1650 годом до н. э., наряду с практическими задачами о делении или вычислении среднего встречаются математические задачи без контекста, которые можно назвать занимательными. Этот древнеегипетский задачник, найденный в гробнице Рамзеса II примерно в 1850 году и приобретенный Александром Генри Риндом в 1856 году в Луксоре, в настоящее время хранится в Британском музее в Лондоне.

Супруга Рамзеса II царица Нефертари за игрой в сенет. Этот рисунок находится на стене передней залы ее гробницы.

Например, задача 24 папируса Ахмеса гласит: «Целое и седьмая его часть дают 19», что на современном языке выглядит так: «Найдите такое число, которое при сложении с одной седьмой его частью дает 19». Эта задача решается элементарно с помощью уравнения первой степени, но подобный прием, очевидно, был неизвестен древним египтянам. В папирусе Ахмеса приводится интересный способ ее решения, называемый методом ложного положения, который использовался древними во многих арифметических задачах. В этой задаче он применяется следующим образом. Ахмес предполагает, что решением является 7, и выполняет следующие действия: 7+ 7·1/7 = 8. Результат не равен 19, следовательно, нужно найти число, которое при умножении на 8 дает 19. Иными словами, нужно поделить 19 на 8. Эту операцию древние египтяне выполняли так:

(8 ×) 2 = 16,

(8 ×) 1/4 = 2,

(8 ×) 1/8 = 1.

Откуда следует: 19 : 8 = 2 + 1/4 + 1/8.

Следовательно, 7 нужно умножить на (2 + 1/4 + 1/8). Имеем: 14 + (1 + 1/2 + 1/4) + (1/2 + 1/4 + 1/8) = 16 + 1/2 + 1/8, что в современной записи выглядит как 16 + 5/8, или 16,625.

ТЫСЯЧЕЛЕТНЯЯ ИГРА СЕНЕГ

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

Доска для игры в сенет. Изображено начальное положение игры. Слева — четыре палочки, которые использовались вместо игральных костей.

Читатель отметит своеобразный способ выполнения операций, а также использование дробей.

Для деления Ахмес находит три степени числа 2, которые в сумме дают 19. Это 16, 2 и 1. Затем он находит восьмую часть для каждого из этих чисел (получив 2, 1/4, 1/8) и выполняет сложение.

НАСТОЛЬНАЯ ИГРАУРСКИХ ЦАРЕЙ. ИСТОРИЯ ДЛИНОЙ В 4 000 ЛЕТ

Наряду с египетской игрой сенет, это одна из древнейших известных нам игр. Украшенная драгоценностями доска для этой игры, найденная в шумерском городе Ур британским археологом сэром Чарльзом Леонардом Вулли примерно в 1920 году, имеет возраст свыше 4 000 лет. В настоящее время эта доска хранится в Британском музее в Лондоне. Предполагается, что эта игра была привилегией лишь королей и знати. Тот факт, что ее находили в гробницах, позволяет предположить, что ее помещали туда, чтобы усопший мог насладиться игрой в загробной жизни. Правила игры урских царей, как и древнеегипетской игры сенет, точно неизвестны.

Однако по дошедшим до нас предметам (помимо доски было найдено 7 белых и 7 черных фишек из перламутра и сланца и 6 игральных костей в форме правильной треугольной пирамиды) можно заключить, что целью игры было провести все фишки по доске быстрее соперника. Интересная форма доски из 20 клеток — два прямоугольника 3 × 2 и 3 × 4 соединены прямоугольником 1 × 2 — позволяет предположить, каким путем нужно было провести фишки по доске.

Доска для игры урских царей. На рисунке обозначены первые ходы каждого игрока.

Для вычислений с дробями используются только так называемые египетские дроби, числитель которых равен единице, а знаменатель — натуральному числу. Этот любопытный способ вычислений, придуманный египтянами, в разное время изучали выдающиеся математики. Среди них Леонардо Пизанский, именуемый Фибоначчи (1175—1250), один из величайших математиков Средневековья. Именно он первым доказал осуществимость этого метода. Англичанин Джеймс Джозеф Сильвестр (1814—1897) открыл новые способы выражения дроби в виде суммы единичных дробей. Венгерский математик Пол Эрдёш (1913—1996), автор наибольшего числа статей среди математиков современности, проявлял особый интерес к теории чисел и сформулировал несколько открытых задач о египетских дробях, предложив собственные решения некоторых из них.

Игры и математика в Средневековье

Изложив лишь некоторые наиболее интересные факты из древней истории взаимоотношений игр и математики, перенесемся в XIII век. Именно тогда жил Леонардо Пизанский, известный как Фибоначчи (1175—1250), автор «Книги абака» (1202), где впервые в истории западного мира была представлена десятичная позиционная система счисления. В этой книге описана известная задача о размножении кроликов, в которой фигурирует интересная последовательность чисел 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., получивших название чисел Фибоначчи. Закономерность для чисел Фибоначчи крайне проста (первые два члена ряда равны 1, а каждый последующий равен сумме двух предыдущих), но этот ряд обладает удивительными свойствами. Так, он связан с числом Ф, описывающим золотое сечение. Ф = (1+у√5)/2 является пределом последовательности a_n/a_n-1 при _n, стремящемся к бесконечности, где a_n — член последовательности Фибоначчи.

В одном из своих основных трудов Liber quadratorum («Книга квадратов»), опубликованном в 1225 году, Фибоначчи описывает математический турнир, прошедший при дворе короля Сицилии Федериго II, на котором он нанес поражение Иоанну Палермскому. На этих интеллектуальных турнирах, проводимых в подлинно средневековом стиле, каждый участник должен был предложить сопернику определенное число задач. Победителем объявлялся тот, кто решил больше задач за меньшее время. При этом должно было выполняться еще одно условие: участник, предложивший задачу, должен был знать ее решение. Одна из задач, упомянутых Фибоначчи, формулируется так: нужно найти такое число, что если прибавить или вычесть из его квадрата 5, то в обоих случаях результатами также будут квадраты. Любопытно, что число 1225, совпадающее с годом публикации «Книги квадратов», является квадратом. Это единственный год жизни Фибоначчи, обладающий подобным свойством: предыдущим квадратом является 1156, а следующим — 1296.

Примерно в то же время арабский писатель и ученый Ибн-Халликан первым изложил знаменитую легенду об изобретателе шахмат, «Историю Сисса бен Дахира и индийского короля Ширхама» (1256). По легенде, Ширхам так полюбил игру в шахматы, придуманную Сиссой бен Дахиром, что разрешил ему выбрать себе любой подарок, какой тот пожелает. Сисса попросил короля положить пшеничное зернышко на первую клетку доски, 2 — на вторую, 4 — на третью, 8 — на четвертую и так далее до клетки 64, каждый раз удваивая число зерен. Правитель посчитал эту просьбу слишком скромной, но затем увидел, что ему никогда не удастся выполнить ее. Действительно, 2⁰ + 2¹ + ...+ 2⁶² + 2⁶³ = 2⁶⁴ - 1 = 18446744073709551615, что в разы превышает весь годовой урожай пшеницы во всем мире.

Страница из«Книги абака» Фибоначчи.

Также в XIII веке, точнее в 1283 году, согласно повелению короля Альфонсо X Мудрого была написана «Книга игр» (Libro de los juegos). Хотя в ней больше внимания уделяется играм, чем математике, она содержит интересный анализ типов игр (как азартных, так и стратегических), популярных в то время, а также все знания, накопленные на тот момент относительно выигрышных стратегий для этих игр. Помимо шахмат и различных азартных игр, в этой книге описывается алькерк — «стратегическая» игра, то есть та, в ход которой не вмешивается случай. Это старейшая из известных нам игр такого типа.

«КНИГА ИГР» АЛЬФОНСО X МУДРОГО

В 1283 году король Альфонсо X Мудрый повелел написать «Книгу игр», известную также под названием «Книга шахмат, игр в кости и доски». Книга содержит 98 страниц со 150 цветными иллюстрациями. В ней рассказывается о наиболее известных настольных играх той эпохи: шахматах, алькерке, играх в кости и других настольных играх, среди которых отметим нарды.

Единственное издание этой книги хранится в библиотеке монастыря Сан-Лоренцо дель Эскориал близ Мадрида. Это первая из книг в истории западной цивилизации, посвященная настольным играм. Содержащаяся в книге информация и великолепные цветные иллюстрации обладают огромной ценностью. Благодаря «Книге игр» до нас дошли сведения об играх, популярных на Пиренейском полуострове 800 лет назад.

Иллюстрация из«Книги игр»Альфонсо X Мудрого, на которой изображена игра в алькерк.

АЛЬКЕРК- ДРЕВНЯЯ ИНТЕЛЛЕКТУАЛЬНАЯ ИГРА

Алькерк — игра для двух игроков, описанная в «Книге игр» Альфонсо X Мудрого. Доска имеет размеры 5x5 клеток, у каждого игрока 12 фишек. Они располагаются на доске так, что центральная клетка остается незанятой. Цель игры — убрать с доски все фишки соперника. В этом алькерк очень похож на современные шашки. Первое письменное упоминание об этой игре встречается в арабской рукописи X века «Китаб аль-Агхани», где алькерк фигурирует под названием киркат. Это позволяет предположить, что на Пиренейский полуостров игру занесли арабы. Однако многие источники дают основания полагать, что игра намного древнее: археологами были найдены старинные доски для алькерка и рисунки, которые также могли использоваться для игры.

С другой стороны, множество версий этой игры на той же доске существовало в Индии и Марокко, на досках другой формы — в Индии и на Шри-Ланке. Существует множество похожих игр, начиная от традиционных шашек и заканчивая фанороной с острова Мадагаскар или игрой авитлаканнаи североамериканских индейцев зуни.

Сверху вниз: стартовые позиции при игре в алькерк, фанорону и авитлаканнаи.

Игры и математика в эпоху Возрождения

Математику эпохи Возрождения представляют главным образом итальянские алгебраисты, среди которых Тарталья, Кардано, Бомбелли, Феррари и дель Ферро, которые занимались в основном алгеброй и решением уравнений. Говоря о математике и играх, прежде всего следует упомянуть Тарталью и особенно Кардано. Самоучка, ставший преподавателем математики, Никколо Фонтана (1499—1557), известный под именем Тарталья («заика»), знаменит благодаря найденному им алгоритму решения кубических уравнений. Также он первым перевел на итальянский язык работы Евклида и Архимеда. Соперничая со Сципионом дель Ферро в духе средневековых турниров, Тарталья одержал победу, решив все предложенные соперником задачи, большинство из которых заключались в решении кубических уравнений. По-видимому, именно это привлекло внимание Кардано, который попросил показать ему формулу для решения подобных уравнений. Тарталья согласился, и Кардано не замедлил опубликовать его результаты под своим именем, чем сильно обидел Тарталью.

Титульный лист Quesiti et inventioni diverse (1546) Никколо Тартальи.

ДЖЕРОЛАМО КАРДАНО (1501-1576)

Врач, математик, астроном, астролог и к тому же игрок, Кардано был одним из тех, кто вместе с Никколо Тартальей, Сципионом дель Ферро, Лодовиком Феррари и Рафаэлем Бомбелли внес вклад в развитие алгебры в Италии XVI века. О его жизни нам известно очень многое, так как он оставил после себя подробную автобиографию под названием De vita propria («Моя жизнь»). В отличие от многих современников, Кардано добился определенной известности, особенно как врач. Будучи настоящим представителем эпохи Возрождения, он интересовался многими науками, пытаясь охватить все знания, известные в то время. Однако весьма часто ему не удавалось избавиться от наивного, иррационального взгляда на вещи, а порой и предрассудков, что сделало его крайне противоречивой фигурой.

Среди его работ по математике выделим трактат «Великое искусство» (Ars magna), опубликованный в 1545 году. Это один из основных трудов эпохи Возрождения по алгебре. До этого, в 1539 году, он написал другую книгу под названием «Практическая арифметика» (Practica Arithmetica). Он также является автором одной из первых книг об играх и математике — «Книги об азартных играх» (Liber de ludo aleae), где впервые описываются вопросы, связанные с вероятностями, применительно к играм в кости. Приведенные им решения остроумны, но порой ошибочны. Эту книгу Кардано написал около 1564 года, но ее опубликовали лишь столетие спустя, включив в его первое полное собрание сочинений. Эта книга, которую можно считать первой работой о вероятностях, не вызвала такого отклика, как работы Паскаля и Ферма. Считается, что в переписке этих двух математиков азартные игры впервые анализируются с точки зрения теории вероятностей.

Фронтиспис книги Джероламо Кардано «Великое искусство»(Ars magna).

Хотя Тарталья не занимался анализом азартных игр целенаправленно в том смысле, как это делал Кардано, в своей книге Quesiti et inventioni diverse («Проблемы и различные изобретения», 1546) он предлагает читателю задачи и загадки, многие из которых популярны и в наши дни, например:

У некоего человека 17 лошадей. Он оставляет их в наследство сыновьям, завещав разделить коней между ними в пропорции 1/2, 1/3 и 1/9. Как сыновьям поделить наследство?

У некоего человека три фазана. Он хочет разделить их между двумя отцами и двумя сыновьями так, чтобы каждому из них достался фазан. Как это сделать?

Несомненно, одним из первых математиков, пытавшихся формально проанализировать азартные игры, был именно Кардано — возможно, наиболее одаренный и разносторонний математик того времени. Однако его работа об играх увидела свет лишь спустя столетие после его смерти, поэтому не привлекла заслуженного внимания. По-видимому, Кардано первым сформулировал задачу о разделении ставок, приведя также ее ошибочное решение, в котором уделено внимание подсчету очков каждого игрока, а не вероятностям выигрыша. Эту задачу также обсуждали в переписке Паскаль и Ферма. Мы поговорим о ней в главе 3.

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

Даны два сосуда. Один вмещает 3 пинты, второй — 5. Как отмерить ровно 4 пинты с помощью переливаний? Ни на одном из сосудов нет никаких отметок, и все, что мы можем определить, — это заполнен сосуд полностью или нет.

Наконец, нужно упомянуть о Роберте Рекорде (1510—1558), математике из Уэльса, который, подобно Кардано, прожил очень интересную жизнь. Как и многие ученые мужи Возрождения, он занимался разными науками, в частности астрономией и медициной. Рекорд известен тем, что в своем труде The Whetstone of Witte («Точильный камень остроумия», 1557) впервые использовал знак «=» для обозначения равенства, указав, что нет ничего более равного между собой, чем две параллельные прямые. Хотя представить современную алгебру без этого знака непросто, он далеко не сразу стал использоваться повсеместно. Даже в XVIII веке наряду с ныне привычным обозначением встречались и другие, например ае (начальные буквы слова aequo — «равно»). В этой книге описываются занимательные задачи, которые по большей части решаются алгебраическими методами.

Игры и математика с XVII века до наших дней

Серьезная и занимательная математика существовали бок о бок с древнейших времен. Однако в начале XVII века появляется особое ответвление, посвященное анализу игр. Как уже говорилось в начале предыдущего раздела, в 1612 году была опубликована первая книга, посвященная исключительно занимательной математике, — Problemes plaisants et delectables qui se font par les nombres Клода Гаспара Баше де Мезириака (1581—1638). Этот математик, поэт и переводчик, который был одним из первых членов Французской академии наук, известен не только как автор этой книги, но и как автор комментария к переводу «Арифметики» Диофанта с греческого на латинский язык (1621). На полях одного из экземпляров именно этой книги Ферма записал свою знаменитую теорему (подробнее о нем мы поговорим в главе 3).

Обложка книги«Арифметика»Диофанта на латинском языке с комментариями Баше де Мезириака.

Золотой век математических игр: XVII и XVIII века

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

Начиная с этого момента, уже в XVII веке появляется множество книг похожего стиля. В 1624 году Анри ван Эттен (это псевдоним французского иезуита Жана Лёрешона) опубликовал книгу Recreations mathematiques («Развлекательная математика»), которая стала более успешной, чем книга Баше, и послужила образцом для последующих изданий, среди которых работа Клода Мидоржа, изданная во Франции в 1630 году и переведенная на английский уже в 1633 году, или работа Даниэля Швентера, опубликованная в 1636 году в Германии. Но самой известной в XVIII и XIX веках стала книга Жака Озанама Recreations mathematiques et physiques («Математические и физические развлечения»), которую в 1725 году отредактировал и дополнил математик и историк науки Жан Этьен Монтукля.

Среди трудов XVIII века упоминания заслуживает книга Rational Recreations Уильяма Хупера («Рациональные развлечения», 1774), где впервые упоминается одна из задач об исчезновении клетки — великолепный пример того, как для решения простой с виду задачи используются интересные математические свойства.

Портрет математика и лингвиста Даниэля Швентера.

Хотя мы перечислили некоторых авторов книг об играх и занимательной математике, не будем забывать, что многие великие математики XVII—XIX веков сформулировали и впоследствии решили задачи, ставшие классикой жанра. Наиболее выдающиеся среди них — Исаак Ньютон (1642—1727), Леонард Эйлер (1707— 1783) и Карл Фридрих Гаусс (1777—1855).

Ньютон в своей книге Arithmetica Universalis («Универсальная арифметика»), написанной на латыни в 1707 году, наряду с важными для математики проблемами упоминает и о простейших занимательных задачах. Хотя наиболее известна так называемая задача о коровах, ниже мы приведем другую задачу, где показывается связь вероятностей и азартных игр. Одновременно бросается некоторое число обычных игральных костей. Вероятность какого из следующих событий наибольшая?

1) При броске 6 кубиков выпадет хотя бы одна шестерка.

2) При броске 12 кубиков выпадут хотя бы две шестерки.

3) При броске 18 кубиков выпадут хотя бы три шестерки.

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

Эйлер, перу которого, возможно, принадлежит наибольшее число работ среди всех математиков, также написал множество занимательных книг, например по комбинаторике, посвященных греко-латинским квадратам. Речь идет о разновидности магических квадратов, в которых необходимо расположить n символов в квадрате n × n клеток так, чтобы в каждой строке и в каждом столбце находились все возможные символы. Можно сказать, что эти квадраты стали прообразом современных судоку. Но, вне всяких сомнений, самая известная из его задач — задача о кёнигсбергских мостах, которую Эйлер опубликовал на латыни в 1759 году в бюллетене Прусской академии наук. Эта задача дала начало теории графов. Граф — это графическое представление отношений между элементами множества, состоящее из вершин (элементов множества) и ребер, соединяющих вершины (связанные между собой элементы). Теория графов используется преимущественно для формулировки и решения задач оптимизации.

Задача о кёнигсбергских мостах звучит так: можно ли обойти все четыре части города, пройдя при этом по каждому из мостов ровно один раз? Эйлер показал, что такого пути не существует, и определил, при каких условиях подобные задачи имеют решение.

Наконец, Гаусс, внесший огромный вклад в математику, также уделял время занимательным задачам, среди которых задача о восьми ферзях: нужно расположить на шахматной доске восемь ферзей так, чтобы ни один из них не находился под боем другого. Также нужно найти количество разных решений и обобщить задачу для n ферзей и доски n × n. Используя интуитивный метод, а затем систематизировав его и переформулировав задачу в терминах перестановок, Гаусс показал, что задача имеет 92 различных решения.

На этой доске размером 8x8 показано одно из решений задачи о восьми ферзях.

ПАРАДОКС ХУПЕРА

В этой головоломке дан квадрат со стороной 8 клеток, разделенный на два треугольника и две трапеции. Из этих же фигур составляется прямоугольник размерами 5x13 клеток. Получается, что площадь квадрата (64 клетки) равна площади прямоугольника (65 клеток), и это «доказывает», что 64 равно 65. Читатель обнаружит, что составить подобный прямоугольник невозможно, и увидит, где же скрывается «дырка» площадью в 1 клетку.

Даже если считать парадокс решенным, он не перестает представлять интерес с точки зрения математики. Если проанализировать задачу подробнее, становится ясно, что она далеко не так проста. Если расположить длины сторон фигур в порядке возрастания, получим 3,5,8,13 — числа Фибоначчи. Эта последовательность имеет такое свойство: квадрат произвольного члена последовательности равен произведению предыдущего члена на последующий плюс (или минус) 1. Иными словами, a_n² =а_n-1 · а_n+1+(-1)ⁿ⁺¹. Таким образом, взяв квадрат со стороной, равной одному из чисел Фибоначчи, и прямоугольник, стороны которого равны предыдущему и последующему числам Фибоначчи, мы снова получим такой же парадокс. Этот парадокс разрешим, и подобное построение можно выполнить корректно для числа Ф, описывающего золотое сечение, которое тесно связано с числами Фибоначчи: взяв квадрат со стороной Ф и разделив его на четыре части, получим прямоугольник со сторонами 1 и Ф + 1. Площадь квадрата (Ф²) будет точно равна площади прямоугольника 1 · (Ф + 1).

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

Игры и занимательная математика в XIX и XX веках

Игры и занимательная математика непрерывно развивались в течение XIX и начала XX веков, и спектр задач неуклонно расширялся. Среди авторов XIX века следует упомянуть Джеймса Джозефа Сильвестра (1814—1897), Льюиса Кэрролла (1832—1898), Эдуарда Люка (1842—1891) и Уильяма Роуза Болла (1850—1925). Рассказать обо всех подробно просто невозможно, и далее мы остановимся на книгах Кэрролла и Люка.

Преподобный Чарльз Латуидж Доджсон, известный как Льюис Кэрролл, автор сказок об Алисе, был математиком и профессором Оксфорда. Он обожал занимательную математику и планировал издать серию книг под названием Curiosa Mathematica («Математические курьезы»). Завершить этот труд ему не удалось. Во второй книге этой серии под названием «Полуночные задачи, придуманные в часы бессонницы» он демонстрирует выдающиеся способности, приводя решения как простейших и шутливых («Есть двое часов. Одни стоят, другие опаздывают на одну минуту. Какие часы показывают время точнее?»), так и довольно сложных задач («Даны три произвольные точки на бесконечной плоскости. Какова вероятность того, что они образуют тупоугольный треугольник?»).

Знаменитый автор «Алисы в стране чудес»Льюис Кэрролл также придумал бесчисленное множество математических игр.

Кэрролл был не только гениальным автором математических и логических игр, но и великим знатоком английского языка, что можно увидеть в его книгах об Алисе и в многочисленных придуманных им играх со словами. Одна из них, «Лестница слов», заключается в том, что нужно построить цепочку из слов с одинаковым количеством букв, каждый раз меняя по одной букве в слове. Например, можно превратить козу в волка: КОЗА — ПОЗА — ПОЛА — ПОЛК — ВОЛК.

Наиболее значимая роль в развитии математических игр принадлежит французскому математику Эдуарду Люка, специалисту по теории чисел и в особенности по числам Фибоначчи. Он является автором великолепного сборника Recreations mathematiques («Математические развлечения»). Эта книга содержит 35 разделов, посвященных математическому анализу игр и занимательным задачам. Среди игр, придуманных Люка, выделяются «Ханойские башни». Сам Люка, чтобы создать завесу тайны, на презентации игры в 1883 году приписал ее авторство китайскому профессору Клаусу (Claus) из колледжа Ли-Су-Стьян (Li Sou Stain). Обратите внимание, что имя несуществующего профессора — анаграмма фамилии самого Люка (Lucas), а название колледжа — анаграмма колледжа Сен-Луи (Saint Louis), где Люка преподавал математику.

Одна из последних книг XIX века по занимательной математике — Mathematical Recreations and Essays («Математические эссе и развлечения», 1892) Уолтера Роуза Болла, которая в XX веке стала одной из популярнейших книг по этой теме, выдержав более 12 изданий. Редактором одного из изданий в 1938 году выступил геометр Гарольд Коксетер.

Начальное положение колец в игре «Ханойские башни».

«ВОЕННЫЕ ИГРЫ»

Одна из игр, о которых пишет Эдуард Люка в третьем томе своей книги о занимательной математике, принадлежит к типу игр, в которых нужно окружить своими фишками фишки другого игрока. К таким играм относятся «Охота на зайца» из книги Альфонсо X Мудрого и «Лиса и гуси» — очень популярная в викторианской Англии игра, известная еще с XV века.

В «военных играх» отсутствует элемент случайности. Эта игра рассчитана на двух игроков и была очень популярной среди французских военных в XIX веке. У одного игрока три белых фишки, у другого (ему принадлежит первый ход) — одна черная фишка. Фишки располагаются на доске из 11 клеток (начальное положение фишек показано на рисунке ниже). Задача белых фишек — окружить черную, которая пытается сбежать. Фишки могут перемещаться по пустым клеткам вдоль линий игрового поля, но белые фишки не могут отступать, в то время как черная может двигаться в любом направлении.

Игра кажется простой, и при первом знакомстве может показаться, что черной фишке легко скрыться от белых. Но тщательный анализ, проведенный Эдуардом Люка, показывает, что существует выигрышная стратегия для белых фишек — у них всегда есть в запасе минимум один ход, который мешает черной фишке сбежать. После изучения вариантов развития игры становится ясно, что максимальное число ходов равно 12, и количество существенно различных игр сокращается до 16. Кажется невероятным, что эта небольшая игра требует такой выверенности ходов от играющего белыми фишками. Он всегда будет выигрывать, если ему известна выигрышная стратегия.

Начальное положение фишек в «военных играх»

Рубеж XIX и XX веков ознаменован появлением трудов, принадлежащих наиболее плодовитым авторам в области занимательной математики: англичанину Генри Эрнесту Дьюдени (1857—1930) и американцу Сэму Лойду (1841—1911). Множество задач и головоломок, которые до сих пор приковывают внимание игроков, описаны в книгах именно этих двух великих авторов.

Генри Эрнест Дьюдени, помимо прочего, является автором «Кентерберийских головоломок» (1907) и «Математических головоломок и развлечений» (1917). Последняя содержит одну из лучших и обширнейших коллекций математических игр всех времен.

«Задача галантерейщика» Гэнри Дьюдени, в которой необходимо разрезать равносторонний треугольник на четыре части и составить из них квадрат.

Среди огромной коллекции головоломок Дьюдени выделяются криптарифмы — ребусы с числами, в которых цифры обозначаются буквами так, что одинаковым буквам соответствуют одинаковые цифры, а разным буквам — разные цифры. Один из известных примеров: РЕШИ + ЕСЛИ = СИЛЕН, причем наибольшая цифра в числе СИЛЕН не превышает 5. Нужно заменить буквы цифрами так, чтобы получилось верное равенство. (Ответ к этому криптарифму следующий: 9382 + + 3152 = 12534.)

Сэм Лойд опубликовал большинство своих задач в газетах и журналах. В одну книгу под названием «Энциклопедия головоломок» их собрал его сын Сэм Лойд-младший в 1914 году, уже после смерти отца. Среди головоломок Лойда — знаменитая задача о соединении 9 точек, расположенных в форме квадрата 3 × 3, четырьмя прямыми линиями, не отрывая карандаша от бумаги (либо то же для 16 точек, квадрата 4 × 4 и шести линий), а также множество задач о расположении чисел определенным образом. Например, нужно расположить числа от 1 до 8 в вершинах куба так, чтобы сумма чисел на каждых четырех вершинах одной грани была одинаковой.

Страница «Энциклопедии головоломок» Сэма Лойда.

Традиции Дьюдени и Лойда продолжились и в XX веке. Среди ведущих авторов первой половины XX века выделяется Морис Крайчик (1882—1957), составитель нескольких книг о математических играх и редактор бельгийского журнала «Сфинкс». После Второй мировой войны на этой арене господствовал Мартин Гарднер (1914—2010), автор множества книг и статей, публиковавшихся на протяжении более 25 лет в научно-популярном журнале Scientific American (русская версия носит название «В мире науки»). Почти до самой смерти Гарднер продолжал публиковать новые издания своих работ. Всего из-под его пера вышло свыше 70 книг, среди которых Origami, Eleusis and The Soma Cube («Оригами, элузис и кубики сома»), вышедшая в 2008 году. Помимо собственных работ, он познакомил читателей с многими интересными играми, среди которых «Жизнь» Джона Конвея и «Элузис» Роберта Эббота (1956).

ЭЛУЗИС — ИГРА РОБЕРТА ЭББОТА

В каждой игре существует некая цель и определенные правила, и в этом элузис не похож ни на одну из них, ведь цель этой игры — угадать правила, придуманные одним из игроков, причем каждая партия играется по новым правилам. Игра рассчитана на 4-8 игроков, и для нее достаточно трех колод карт и нескольких фишек. Партия состоит из числа раундов по числу игроков. В каждом раунде один из игроков раздает остальным по 14 карт, после чего превращается в «бога игры», создателя правил, и выкладывает последнюю карту на стол. Раздающий должен записать на листе бумаги секретное правило, по которому формируется последовательность карт. Правила могут быть очень простыми (красное — черное или чет — нечет), но их можно придумать бесчисленное множество: четные после красных и нечетные после черных, четыре четных разной масти и четыре нечетных одной масти. В интересах того, кто придумывает правила, — сделать их неочевидными, но и не слишком сложными, так как если никто не поймет правил, игра получится неинтересной. Остальные игроки пытаются понять правило, не говоря при этом ни слова. Они поочереди выкладывают по одной карте, пытаясь сформировать ряд из «правильных» карт. «Бог игры» сообщает, является карта «правильной» (в этом случае она кладется в конец ряда) или «неправильной» — в этом случае она кладется под последнюю правильную карту, а игрок, сделавший неверный ход, получает в качестве штрафа две новые карты из колоды. Начиная с 40-й карты, ошибочный ход наказывается выходом из игры.

Игра заканчивается, когда одному из игроков удалось избавиться от всех своих карт или когда все игроки покинули игру.

В книге «Десять игр, которые ни на что не похожи» Роберта Эббота подробно описана эта великолепная игра.

Среди других авторов XX века — Яков Перельман, один из основоположников русской школы занимательной науки, француз Пьер Берлокен и англичане Иэн Стюарт, Брайан Болт и Дэвид Уэллс. Каждый из них является автором множества книг и статей в различных периодических изданиях. Заслуживают внимания и испанские авторы, которые в своих книгах о математических играх и головоломках также попытались сделать математику ближе к широкой публике.Наиболее известные среди них — Мариано Матаиш, Мигель де Гусман и Фернандо Корбалан. Их труды вкупе с книгами уже упомянутых авторов — неистощимый источник задач, игр и математических развлечений.

Задача о костяшках домино от Якова Перельмана: четыре костяшки домино расположены в виде квадрата так, что суммы чисел на его сторонах равны. Задача — составить семь таких квадратов из полного набора домино.

Появление теории игр

Важная часть этой книги, а именно главы 4 и 5, посвящена теории игр. В ней показывается, что рано или поздно все математические понятия и модели находят применение в реальном мире, даже если изначально они никак не были связаны. Это справедливо и для анализа игр.

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

Теория игр появилась в работах Джона фон Неймана, в частности в книге «Теория игр и экономическое поведение», опубликованной им совместно с экономистом Оскаром Моргенштерном в 1944 году. Изначально в теории игр шла речь об абстрактных играх для двух и более игроков, где определены выигрыш и проигрыш для каждого игрока в зависимости от совершенного хода. Как правило, игроки ходят одновременно и не знают стратегию соперников. Эти игры, используемые как математические модели, изначально применялись при анализе экономических ситуаций. Фон Нейман и Моргенштерн показали способ определения оптимальной стратегии для каждого игрока в играх этого типа. Фон Нейман предложил для решения этих задач так называемый принцип минимакса, а также расширил его для игр, в которых присутствуют случайные события (так называемые смешанные стратегии). Его методы оказались столь успешными, что математики и экономисты начали применять их при решении более сложных задач.

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

Джон фон Нейман на одной из лекций в Американском философском обществе, членом которого он являлся.

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

Глава 2. Стратегические игры и решение задач

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

Мартин Гарднер

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

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

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

Понятие выигрышной стратегии

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

Как следует изучив игру, мы задаемся вопросом: какие ходы нужно совершать, чтобы одержать победу в определенной партии? В азартных играх (например, в классической игре «Змеи и лестницы») этот вопрос не имеет смысла, поскольку игроки лишь двигают фишки согласно выпавшим очкам на игральных костях и следуют инструкциям на игровых клетках. Иными словами, здесь нет места для принятия решений, поэтому нет «хороших» или «плохих» игроков. Результат игр подобного типа полностью зависит от случая, поэтому определить какую-либо выигрышную стратегию невозможно. В этом смысле можно сказать, что интересность игры с точки зрения математики равна нулю.

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

Картина времен династии Юань (XIII-XIV века), изображающая трех игроков в го.

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

БИБЛИЯ ВЫИГРЫШНЫХ СТРАТЕГИЙ

Возможно, наиболее обширный труд о стратегических играх носит название «Выигрышные стратегии ваших математических игр» в четырех томах (издан в 1982 году). Его авторами являются трое выдающихся математиков XX века: Элвин Берлекэмп (род. в 1940 году), профессор компьютерных наук в Калифорнийском университете в Беркли с 1971 года; Джон Конвей (род. в 1937 году), автор важных работ по теории конечных групп, профессор Кембриджского и Принстонского университетов, создатель игры «Жизнь», моделирующей жизнь клеток; Ричард Гай (род. в 1916 году), почетный профессор университета Калгари. Книга посвящена играм со следующими свойствами:

1. Это игры для двух игроков, делающих ходы поочередно.

2. Это игры, в которых определено одно начальное положение и существует конечное число ходов.

3. Это игры с полной информацией: в любой момент игрокам известны все возможные ходы.

4. Ни в начале игры, ни в процессе выполнения ходов нет места неопределенности.

5. Ход партии не допускает повторения ходов. Тот игрок, который не может совершить ход, проигрывает.

Обложка первого тома книги Берлекэмпа, Конвея и Гая Winning ways for your mathematical plays

Допустим, что некая игра для двух игроков имеет следующие свойства:

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

2. Игроки совершают ходы поочередно.

3. В игре полностью отсутствует элемент неопределенности.

4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.

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

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

Использование преимуществ и определение стратегий. Игра Ним и ей подобные

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

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

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

Суть малой стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку либо, наоборот, заставить противника взять последнюю фишку. Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет: первый анализ выигрышной стратегии для игр подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.

Эта игра приобрела популярность в Европе в 70-е годы XX века благодаря фильму французского режиссера Алена Рене «В прошлом году в Мариенбаде» (1961). Герои фильма несколько раз играют в один из вариантов этой игры. Поэтому версия игры из фильма (она рассматривается далее в этой книге в параграфе «Игра 5») иногда называется Мариенбад — по имени маленького курортного города в Чехии, где происходит действие картины.

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

«Мариенбад» — одна из версий игры Ним.

Об определении стратегии

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

Игра 1: выигрывает первый

На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если читатель незнаком с этой игрой, перед прочтением следующих страниц ему будет интересно попробовать сыграть в нее самому и постараться ответить на заданные выше вопросы.

Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.

Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2011), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.

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

Игра 2: выигрывает второй

Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?

Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, ..., 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 - n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.

Игра 3: общий случай

Допустим, что на столе m фишек и каждым ходом можно брать от 1 до n фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?

Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:

1. Остаток от деления равен 0. В этом случае существует выигрышная стратегия для второго игрока, который должен оставлять на столе число фишек, кратное n+1. Для этого на каждом ходу, если первый игрок берет p фишек (0<p<n+1), второй должен брать n+1—p фишек. Это число всегда положительно, так как находится на интервале от 0 до n.

2. Остаток от деления равен r(0<r<n+1).В этом случае существует выигрышная стратегия для первого игрока. На первом ходу он должен взять r фишек, оставив на столе число фишек, кратное n+1. Теперь он может действовать подобно второму игроку из первого случая. Иными словами, если второй игрок берет p фишек (0<p<n+1), первый должен взять n+1—р.

Это общее решение применимо к бесконечному множеству игр. Читатель может применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно m - 1, а не m.

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

Сложная стратегия: игра Ним

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

Игра 4: первая версия игры Ним

В начале игры на столе три кучки, состоящие из 1, 3 и 5 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?

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

1. Оставлять на столе две кучки с одинаковым числом фишек.

2. Забирать все фишки из одной кучки.

Если игрок А выполняет ход 1, игрок Б забирает все фишки из третьей кучки и выигрывает, симметрично повторяя ходы соперника. Если игрок А забирает из одной кучки гг фишек, игрок Б забирает столько же фишек из другой, и, когда А заберет все фишки из одной кучки, игрок Б заберет все фишки из другой и выиграет. Аналогично если игрок А совершит ход 2, то Б заберет нужное число фишек из той кучки, в которой их осталось больше. На столе останутся две одинаковые кучки, и игрок Б снова одержит победу, действуя как в предыдущем случае. Поэтому победу одерживает тот, кто заставит противника совершить один из двух «запрещенных» ходов. В рассматриваемом случае, если первый игрок берет 3 фишки из кучки, в которой 5 фишек, на столе останутся три кучки с 1, 2 и 3 фишками. Первый игрок выигрывает, так как его соперник будет вынужден или взять все фишки из одной кучки, или уравнять число фишек в двух кучках (оставив в них по 1 или по 2 фишки).

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

Чтобы лучше понять суть этой стратегии, рассмотрим несколько примеров. Сначала мы рассмотрим три кучки с 1, 3 и 5 фишками (это игра 4, которую мы решили ранее). Затем мы перейдем к более привычной версии игры Ним под названием Мариенбад. В ней четыре кучки с 1, 3, 5 и 7 фишками.

В первом случае число фишек в кучках равно 1, 3 и 5.

1 в двоичной системе: 1

3 в двоичной системе: 11

5 в двоичной системе: 101

Сложим единицы в каждом столбце и увидим, что сумма цифр каждого столбца нечетная (справа налево: 3, 1 и 1). В этом случае существует выигрышная стратегия для первого игрока. Для этого ему нужно ходить так, чтобы суммы цифр во всех столбцах оставались четными. Единственный способ сделать это — забрать фишки из кучки, где их 5 (101), оставив 2 (10), то есть забрать 3 фишки из кучки с 5 фишками. Получим:

1 в двоичной системе: 1

3 в двоичной системе: 11

2 в двоичной системе: 10

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

Игра 5: Мариенбад

На столе четыре кучки фишек. В кучках лежат 1, 3, 5 и 7 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?

Аналогично предыдущему случаю получим:

1 в двоичной системе: 1

3 в двоичной системе: 11

5 в двоичной системе: 101

7 в двоичной системе: 111

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

1 в двоичной системе: 1

2 в двоичной системе: 10

5 в двоичной системе: 101

7 в двоичной системе: 111

NIMROD

В начале 50-х годов XX века инженеры английской компании Ferranti создали первый компьютер, предназначенный только для игр. Он назывался NIMROD. Первые три буквы NIM означали игру, для которой он и был спроектирован. На панели компьютера находились светящиеся лампочки, которые представляли положение фишек в игре. Прототип компьютера был представлен на выставке «Фестиваль Британии» в 1951 году. Считается, что это послужило началом эпохи электронных игр.

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

Хотя найти стратегию игры Ним было намного сложнее, чем для предыдущих игр, о которых мы рассказали, для всех этих игр справедлива одна общая идея. Нужно найти равновесную ситуацию, которая совпадает с конечным положением, и определить, какой из игроков всегда сможет сохранять подобную ситуацию, а какой — никогда. Так, в первой игре этой главы («Игра 1: выигрывает первый») равновесная ситуация такова: нужно оставить на столе число фишек, кратное 3. Во второй игре («Игра 2: выигрывает второй») нужно записать число, кратное 11, а в последней игре Ним нужно оставить в каждой кучке такое число фишек, чтобы при записи количества фишек в двоичной системе сумма цифр в столбцах всегда была четной.

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

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

ДВОИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ

Это позиционная система счисления, в которой любое число можно представить с помощью всего двух цифр: 0 и 1. Чтобы преобразовать двоичное число в десятичное, нужно заменить все единицы степенями двойки. Показатели этих степеней будут зависеть от позиции цифры: правый разряд соответствует 2⁰, следующий — 2¹ и так далее. Например, двоичное число 110101 в десятичной системе выглядит так: 1 • 2⁰ + 0 • 2¹ + 1 • 2² + 0 • 2³ + 1 • 2⁴ + 1 • 2⁵ = 1 + 4 + 16 + 32 = 53.

Аналогично для записи десятичного числа в двоичном виде нужно разделить его на 2, полученный результат снова разделить на 2 и так далее до тех пор, пока результатом деления не будет 1. Последний результат деления будет первой цифрой справа. Все прочие остатки отделения, от последнего к первому, составят следующие разряды (остаток от деления на 2 может равняться только 0 или 1). Например, 39 в двоичной системе записывается как 100111, так как 39:2 дает 19 (и остаток 1), 19:2 дает 9 (остаток 1), 9:2 дает 4 (остаток 1), 4:2 дает 2 (остаток 0), 2:2 дает 1 (остаток 0). Мы выразили число в виде суммы степеней двойки.

Итак, 39 =1 + 2 + 4 + 32 = 1•2⁰ +1•2¹+1•2²+0•2³+0•2⁴+1•2⁵ = 100111 по основанию 2. Хотя двоичная нотация появилась сравнительно недавно, свойство, на котором она основана («всякое число можно представить в виде суммы различных степеней двойки»), было известно и применялось еще в древности. Например, древние египтяне использовали для умножения такую систему. Один из сомножителей удваивался, второй делился на 2. Если число было нечетным, то на 2 делилось предыдущее число. Этот метод дает верный результат именно благодаря указанному свойству.

Страница бюллетеня Французской академии наук, посвященная двоичной системе счисления, разработанной Лейбницем в 1703 году.

НЕСКОЛЬКО ИНТЕРЕСНЫХ ИГР

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

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

Разрезаем прямоугольник. Это стратегическая игра для двух игроков. На листе бумаги в клетку нужно нарисовать прямоугольник размерами 17 × 15 клеток. Затем нужно пометить квадратик в нижнем правом углу. Каждый из игроков своим ходом делит прямоугольник на две части вертикальной или горизонтальной линией и удаляет ту часть прямоугольника, которая не содержит маленький отмеченный квадрат. Тот, кто не сможет разделить прямоугольник (то есть от прямоугольника останется только один отмеченный квадратик), проигрывает.

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

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

Какой из игроков имеет преимущество? Что изменится, если изменить начальное число точек?

Цели и правила игры: эквивалентные и отличающиеся игры

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

Игра 6: продвижение по шестиугольным клеткам

Игровое поле изображено на рисунке 1. Каждый игрок берет единственную фишку, которая изначально расположена в ячейке S, и передвигает ее на соседнюю клетку. При этом он всегда должен двигаться вправо — по горизонтали или по диагонали. Игрок, который поставит фишку в крайнюю клетку М, выигрывает.

Рисунок 1.

Если читатель попытается решить игру сам, то легко увидит, в какие клетки нужно ставить фишку, чтобы победить. Если рассуждать в обратном направлении, то станет понятно, что первый игрок будет всегда выигрывать, если будет ставить фишку в помеченные крестиком клетки. Совсем не очевидно, что эта игра аналогична игре 1 («выигрывает первый»), если не заметить, что допустимые ходы можно интерпретировать как переход на два шага вперед (если мы передвигаем фишку в горизонтальном ряду) или на один шаг вперед (если мы двигаем фишку по диагонали и переставляем ее в другой ряд). Если пронумеровать клетки таким способом, то станет четко видна аналогия между этими играми (рисунок 2).

Рисунок 2.

Игра 7: поставь последнюю фишку

На игровой доске всего один ряд из шести клеток. На нем расставлены три фишки. На каждом ходу игрок выбирает фишку и передвигает ее вправо на любое количество клеток (минимум на одну и максимум на пять, в крайнюю правую клетку). Цель игры — поставить все фишки в крайнюю правую клетку. Тот, кто ставит в эту клетку последнюю фишку, выигрывает. В одной клетке могут одновременно находиться несколько фишек. Заметим, что эта игра эквивалентна первой рассмотренной нами версии игры Ним (игра 4): каждая фишка соответствует кучке, перенос фишки вправо соответствует взятию фишек из кучки в игре Ним. Когда фишка попадает в крайнюю правую клетку, это равносильно тому, что из кучки в игре Ним взяты все фишки. Рассмотрим еще две игры и проанализируем их эквивалентность.

Игра 8: цзяньшицзы

На стол выкладываются две кучки фишек, например 7 и 5 фишек. Каждый игрок может брать из выбранной кучки любое число фишек (минимум одну). Он также может брать фишки из двух кучек сразу, но в этом случае нужно брать одинаковое число фишек из каждой кучки.

Игра 9: спасти ферзя

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

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

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

Игра 10: маргаритка

Нарисуем маргаритку с 11 лепестками и поставим по одной фишке на каждом лепестке. На каждом ходу игрок может брать одну или две фишки, причем две фишки можно брать только с соседних лепестков.

Начальная позиция в игре«Маргаритка».

Эта игра очень похожа на первую игру из этой главы, но фишек не 20, а 11. Кажется, что выигрышная стратегия для первого игрока — взять две фишки на первом ходу, затем всегда оставлять число фишек, кратное трем. Однако наложенное ограничение (можно брать не любые две фишки, а только соседние) полностью нейтрализует эту стратегию. Теперь главную роль играет не количество фишек, а их расположение. Фактически исходное число фишек неважно, так как если фишек больше трех, то выигрышная стратегия звучит одинаково для любого числа фишек.

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

«ВАВИЛОН», ИГРА БРУНО ФАЙДУТТИ

Современные абстрактные стратегические игры,несмотря на очевидную простоту, очень сложно анализировать. Хотя для них можно определить существование выигрышной стратегии, найти такую стратегию почти невозможно. Игра «Вавилон» французского автора Бруно Файдутти — наглядный пример подобных игр. На стол кладутся 12 фишек четырех разных цветов, по 3 фишки каждого цвета. Каждый из двух игроков берет одну стопку (изначально все стопки имеют высоту в 1 фишку) и кладет ее поверх другой, соблюдая следующие условия: одну стопку можно поставить на другую, если они имеют одинаковую высоту или же если верхние фишки обеих стопок одинакового цвета. Тот игрок, который не может поставить стопку поверх другой, проигрывает.

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

«Вавилон»— игра, созданная Бруно Файдутти.

Игры и псевдоигры

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

Игра 11: только нечетные

На столе лежит 20 фишек. Каждый из двух игроков своим ходом может взять 1, 3 или 5 фишек. Тот, кто забирает последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым или вторым? Что произойдет, если изменится число фишек? Эта игра является стратегической, как предыдущие, или же отличается от них?

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

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

Игра 12: круги и квадраты

Нарисуем несколько кругов и квадратов, расположив их в ряд. Каждый игрок может убирать две одинаковые фигуры (два круга или два квадрата) и заменять их одним кругом, либо же забирать две разные фигуры и заменять их одним квадратом. Количество фигур будет постоянно уменьшаться, и в конце игры останется только одна. Если останется квадрат, выигрывает первый игрок, если останется круг — второй игрок. Существует ли стратегия, которая позволяет всегда выигрывать? Что произойдет, если изменить начальное число кругов и квадратов? Является ли эта игра стратегической? Рассмотрим начальную позицию, изображенную на рисунке ниже.

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

ЕЩЕ НЕСКОЛЬКО ИНТЕРЕСНЫХ ИГР

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

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать? Что изменится, если изменить начальное число точек? Можно играть по обратным правилам: тот, кто нарисует треугольник одного цвета, проигрывает. Что произойдет в этом случае?

Плитка шоколада (1). Плитка шоколада состоит из 28 окошек, расположенных в 4 ряда по 7 квадратиков. Первый игрок делит плитку на две части, не ломая ни одно из окошек. Второй игрок берет одну из полученных частей (другая откладывается в сторону) и снова делит ее. На каждом ходу игрок берет одну из двух только что полученных частей и делит ее на две части вдоль линий, разделяющих окошки. Тот, кто не сможет разделить плитку подобным образом, проигрывает.

Как нужно играть, чтобы выигрывать? Что изменится, если плитка будет состоять из 27 окошек, расположенных в 3 ряда по 9?

Плитка шоколада (2). На этот раз плитка состоит из 50 квадратных окошек, расположенных в 5 рядах по 10. Каждый игрок делит плитку (или ее часть) вдоль вертикальной или горизонтальной линии, не ломая ни одно из окошек. На этот раз ни одна из частей не откладывается в сторону, все они продолжают участвовать в игре. Первый игрок, который своим ходом получит одно отдельное окошко, проигрывает.

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

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

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

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

Глава 3. Игры и азарт

Где заканчивается игра и начинается серьезная математика? <...> Для многих математика смертельно скучна и не имеет ничего общего с играми. Напротив, для большинства математиков это всегда игра, а также многое, многое другое.

Мигель де Гусман

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

Шевалье, который не хотел проигрывать. Азартные игры и появление вероятностей

В реальном мире сложные теории, касающиеся вероятностей, применяются в самых разных областях, так как в нашей жизни неопределенность встречается очень часто. Однако теория вероятностей берет свое начало именно в азартных играх. Можно утверждать, что теория случайных событий, основанная на понятии вероятности, начала формироваться во Франции в середине XVII века, в частности в 1654 году, в переписке Блеза Паскаля и Пьера Ферма, которые обсуждали вопросы, поставленные шевалье де Мере. Этот дворянин, знаток азартных игр, попросил Паскаля объяснить результаты некоторых азартных игр с игральными костями.

Антуан Гомбо, известный как шевалье де Мере (род. в Пуату, 1607—1685), посвятил большую часть жизни азартным играм и их анализу. Его интуитивные догадки много раз оказывались верными. По-видимому, он заработал приличную сумму различными азартными играми, где вероятность выигрыша и проигрыша одинакова. Например, такой считалась игра, где нужно было выбросить минимум одну шестерку броском четырех игральных костей. Однако Мере знал, что в этой игре один из игроков имеет преимущество. Он предложил новую игру, в которой требовалось минимум один раз выбросить две шестерки за 24 броска двух костей. Де Мере полагал, что преимущество одного из игроков здесь будет таким же, что и в исходной игре. Некоторое время спустя он убедился, что в действительности все происходит с точностью до наоборот. Поэтому примерно в 1654 году он обратился к Паскалю, чтобы тот нашел ошибку в его рассуждениях и объяснил, почему в новой игре у него не было преимущества.

Иллюстрация из «Книги игр» Альфонсо X Мудрого, на которой изображена игра в кости.

БЛЕЗ ПАСКАЛЬ (1623-1662)

Несмотря на смерть в раннем возрасте, этот французский ученый, математик и философ внес большой вклад в различные сферы науки и человеческой мысли. Он был вундеркиндом и уже в И лет участвовал в научных встречах, которые организовывал Марен Мерсенн. В 1640 году Паскаль публикует работу «Опыт о конических сечениях», в 1649 году подтверждает результаты работ Торричелли об атмосферном давлении. В 1642 году он сконструировал счетную машину, чтобы помочь отцу, сборщику налогов в Нормандии. Эта машина, получившая название паскалина, — одна из первых рабочих счетных машин. Некоторые экземпляры сохранились до наших дней и демонстрируются в музеях науки и техники. Счетная машина, предназначенная для расчетов в торговле, заинтересовала многих — от королевы Швеции Кристины до философа Готфрида Вильгельма Лейбница, который усовершенствовал машину Паскаля.

С вопросов шевалье де Мере об азартных играх началась переписка Паскаля и Пьера Ферма, в которой впервые формулируется теория вычисления вероятностей (Паскаль называл ее геометрией случайности). В пяти письмах, датированных 1654 годом, анализируются азартные игры, изучением которых до этого уже занимался Джероламо Кардано.

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

ПЬЕР ФЕРМА (1601-1665)

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

Ферма изучал юриспруденцию и большую часть жизни провел в Тулузе, где приобрел известность как королевский советник парламента (т.е. член высшего суда) этого города. Это позволило ему в свободное время отдаваться подлинному увлечению — математике. Область математики, которая интересовала его сильнее всего и в которую он внес наибольший вклад, — теория чисел. Одна из его теорем (для любого натурального числа n>2 уравнение xⁿ + yⁿ = zⁿ не имеет натуральных решений) была доказана лишь в конце XX века. Он также внес заметный вклад в геометрию и определение экстремумов функций для решения задач оптимизации еще до того, как было создано дифференциальное исчисление. В его переписке 1654 года с Блезом Паскалем впервые предприняты попытки определить понятие вероятности.

Укрощение случайности. Математическое изучение вероятностей

Чтобы познакомиться с понятием вероятности и его основными свойствами, попробуем решить две задачи, предложенные шевалье де Мере. Точная формулировка первой задачи такова: какова вероятность выбросить 6 очков минимум один раз, бросив игральные кости четыре раза? Для решения этой задачи используется собственное свойство вероятности. Оно гласит: вероятность того, что произойдет некоторое событие либо обратное ему, равна 1. Поэтому сначала мы вычислим вероятность того, что ни в одном из бросков игральных костей не выпадет 6. Очевидно, что при броске одного кубика p(не 6) = 5/6. Так как при броске четырех костей каждый бросок не зависит от остальных, можно определить требуемую вероятность перемножением отдельных вероятностей каждого события. Искомая вероятность равна:

(5/6) • (5/6) • (5/6) • (5/6) = (5/6)⁴ = 625/1296 = 0,482 < 1/2.

Отсюда следует, что вероятность выпадения минимум одной шестерки равна

1 — (625/1296) = 671/1296 = 0,518 > 1/2.

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

Аналогичным способом можно решить и вторую задачу: какова вероятность выпадения двух шестерок при броске пары кубиков 24 раза? Сперва мы снова рассчитаем вероятность того, что после 24 бросков две шестерки не выпадут ни разу. При броске двух игральных костей p(не две 6) = 35/36. Следовательно, для 24 бросков получим:

p(не две 6) = (35/36)²⁴ = 0,5086.

Следовательно, вероятность выпадения двух шестерок минимум один раз равна

1 - 0,5086 = 0,4914 < 1/2.

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

Ахиллес и Аякс играют в кости. Одна из самых известных афинских чернофигурных амфор (VI век до н.э.) — еще одно доказательство древности этой азартной игры.

ПЬЕР СИМОН ЛАПЛАС (1749-1827)

Лаплас — один из величайших математиков XVIII века. Он изучал богословие и математику, был профессором Военной академии в Париже и читал лекции в Нормальной школе. Лаплас был членом Французской академии наук и Лондонского королевского общества. Во время Великой французской революции принял руководящее участие в работах комиссии по введению метрической системы. По указу Наполеона он был назначен членом сената и канцлером, а в 1805 году был награжден орденом Почетного легиона. После реставрации Бурбонов Лаплас поддерживал Людовика XVIII, который в 1817 году присвоил ему титул маркиза.

Его основной труд по физике и математике и, возможно, наиболее значительный вклад в науку вообще — книга «Небесная механика» в пяти томах, опубликованных с 1799 по 1825 год. В этом труде Лаплас дополнил более ранние работы Ньютона, Галлея и Эйлера о гравитации и устойчивости Солнечной системы, то есть о неизменности средних расстояний планет от Солнца.

С 1780 года он занимался теорией вероятностей и в 1812 году опубликовал свою главную работу по этой теме — «Аналитическую теорию вероятностей», которая считается первой книгой по теории вероятностей. Успех этого труда побудил его в 1814 году написать «Опыт философии теории вероятностей» — популярное изложение «Аналитической теории вероятностей». В этой книге содержится полная и непротиворечивая аргументация в пользу детерминизма Вселенной. Лаплас писал: «В основе теории вероятностей — только здравый смысл, сведенный до исчисления. Нет никакой другой науки, которая точнее бы отражала наши размышления и результаты которой были бы более полезны».

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

ЗАДАЧА О РАЗДЕЛЕНИИ СТАВОК

Рассмотрим одну из первых задач в теории вероятностей. Роман и Павел играют в азартную игру, выигрывает тот, кто первым наберет 10 очков. В каждом раунде оба имеют равные шансы на победу. Победитель раунда получает 1 очко. После 17-й партии Павел выигрывает со счетом 9:8, после чего игру решено прекратить. Так как никому не удалось набрать 10 очков, игроки решают разделить сделанные ставки. Как справедливо разделить деньги между игроками? «Правильное» решение задачи может зависеть от многих факторов, в том числе не относящихся к математике, поэтому может существовать несколько «допустимых» решений. Однако если мы проанализируем вероятность выигрыша обоих игроков, то сможем справедливо разделить ставки.

До окончания игры нужно сыграть еще максимум две партии. Существует четыре возможных (и равновероятных) результата этих двух партий: (П, П), (П, Р), (Р, П), (Р, Р), где П означает победу Павла, Р — победу Романа. В трех возможных исходах победа останется за Павлом, которому до победы остается всего одно очко, и лишь единственный (последний) исход принесет победу Роману. Поэтому ставки нужно поделить в соотношении 3:1, то есть отдать 3/4 денег Павлу и 1/4 — Роману.

Еще одна задача, о которой идет речь в переписке Паскаля и Ферма, касается азартной игры: нужно решить, как разделить ставки между игроками, если игра прерывается в определенный момент. Эту задачу пытался решить еще Кардано. В его решении разделение ставок зависело от того, сколько очков у каждого игрока, а не от вероятности выигрыша в случае продолжения игры до конца.

Вопросы вычисления. Важен ли порядок?

Вспомним, что вероятность события рассчитывается по следующему правилу: p(события) = число благоприятных исходов/общее число исходов, то есть нужно определить число наблюдений, при которых наступает нужное событие, и разделить его на общее число наблюдений. Иногда подсчитать это отношение очень просто. Например, какова вероятность, что при броске кубика выпадет четное число очков? Из шести возможных исходов лишь три благоприятных (когда выпадает 2, 4 или 6). Следовательно, p(четное) = 3/6 = 0,5. Так как общее число исходов невелико, подсчет можно произвести простым перечислением всех возможных случаев. В других случаях подобные расчеты могут оказаться намного сложнее, поэтому нужно как следует разобраться в ситуации и иметь соответствующие методы для выполнения расчетов. Так, важная часть анализа сложных азартных игр и случайных событий в целом заключается в правильном перечислении всех возможных исходов.

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

Задача 1: победители забега

В забеге участвуют 12 бегунов. Сколькими способами можно сформировать тройку призеров?

Первое место может занять любой из 12 участников. Для каждого из этих 12 исходов есть И атлетов, которые могут занять второе место. Для каждой пары первого и второго призеров остаются 10 возможных вариантов третьего места. Следовательно, количество различных троек призеров равно 12 * 11 • 10 = 1320.

Мы определили количество групп из трех бегунов, которых можно выбрать из 12 участников забега, при этом порядок выбора имеет значение. Следовательно, тройки 1, 2, 3 и 2, 3, 1 отличаются: они образованы одними и теми же бегунами, но в первой тройке первым пришел бегун номер 1, вторым — номер 2, третьим — номер 3, а во второй тройке первым пришел бегун номер 2, вторым — номер 3, третьим — номер 1.

На языке математики это называется размещением из 12 элементов по 3 и обозначается V_12,3 Как мы уже заметили, оно рассчитывается как 12 • 11 • 10. В общем виде размещение из m элементов по n (очевидно, что n < m) рассчитывается так:

V_m,n = m • (m - 1) • (m - 2) • ... • (m - n + 1).

Задача 2: играем в бридж

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

Если у игрока 13 карт, то первую по порядку он может выбрать тринадцатью возможными способами, вторую — двенадцатью, третью — одиннадцатью и так далее до последней карты, которую можно будет выбрать единственным способом (она останется последней неупорядоченной). Следовательно, общее число возможных вариантов упорядочения карт равно:

13 • 12 • 11 • … • 3 • 2 • 1 = 13! = 6 227 020 800.

Эта операция называется перестановкой 13 элементов, и результат можно также записать в виде факториала. Факториал обозначается восклицательным знаком после числа. В нашем случае результат равен 13!. По определению n! равен произведению всех натуральных чисел от n до 1. В таблице ниже приведены значения факториала для первых 12 чисел, чтобы дать представление о том, насколько быстро он возрастает.

Подсчет лежит в основе множества карточных игр. Картина Лукаса ван Лейдена «Игроки в карты», 1520 год.

Задача 3: раздача карт

В игре бридж каждому игроку раздается по 13 карт из колоды в 52 карты. Сколькими различными способами можно выдать игроку 13 карт?

В этом случае нужно подсчитать число различных групп по 13 карт, которые можно выбрать из 52 карт, при этом порядок расположения выбранных 13 карт неважен. Если бы порядок карт имел значение, то общее число раздач вычислялось бы так:

52 • 51 • 50 • ... (13 множителей)... * 42 - 41 - 40 = 3,95424 • 10²¹.

Но так как порядок карт в раздаче неважен, а каждую группу из 13 карт мы посчитали 13! раз (это число перестановок 13 элементов), число способов раздачи карт в бридже равно

(52 • 51 • ... • 41 • 40)/13! = 52!/(39! • 13!) = 635 013 559 600.

Обратите внимание, что результат выражается огромным числом. В первом случае полученное число имеет 22 цифры в своей записи, во втором (когда порядок неважен) мы получили число из 12 цифр. Это сопоставимо с возрастом Вселенной в 1,5 • 10¹⁰ лет или примерно 4,7 • 10¹⁷ секунд. Таким образом, первое число (3,9 • 10²¹) более чем в 8000 раз превышает число секунд, прошедших с момента Большого взрыва, а второе число (6,3 • 10¹¹) в 42 раза больше возраста Вселенной в годах.

На языке математики результат этой задачи именуется числом сочетаний из 52 элементов по 13, которое обозначается С_12,13. Как мы уже видели, это сочетание рассчитывается по формуле: 52!/(39! • 13!). Общая формула для вычисления количества сочетаний из m по n (очевидно, что n < m):

С_m,n = m! / (m— n)! • n!

Задача 4: серия пенальти

Если финал футбольного чемпионата завершается ничьей, пробивается серия пенальти. Как правило, серия пенальти состоит из 5 ударов; все они должны выполняться разными игроками. Сколько списков из 5 пенальтистов можно составить из И игроков, которые находились на поле на момент окончания матча?

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

1. Нужно составить группы из 5 игроков так, чтобы любые две группы отличались между собой как минимум одним игроком. В этом случае нужно вычислить число сочетаний из 11 по 5: 11! / (5! • 6!) = 462.

2. Все интересующиеся футболом знают, что в реальности каждая команда подает арбитру пронумерованный список из 5 пенальтистов. Поэтому два списка, где указаны одни и те же игроки, но в разном порядке, будут отличаться. В этом случае нужно вычислить количество размещений из 11 по 5, равное 11!/6! = 55440.

Номера лотерейных билетов и другие ошибочные предположения о случайности

Представим себе такой диалог:

— Здравствуйте, можно лотерейный билет?

— Возьмите, номер 00010.

— Нет, дайте другой, этот номер очень маленький и никогда не выпадает.

— Если хотите, я дам вам второй, 00001, два по цене одного.

— Нет, они все равно почти никогда не выпадают.

— Хорошо, держите 74283.

— Другое дело, этот подойдет. Спасибо.

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

Капризы вероятностей

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

Игра в кегли

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

Кажется, что ответ — 2/3, так как единственный шар, брошенный Николаем, может быть ближе всего к кегле, а также на втором или на третьем месте. В двух последних случаях ближе всего к кегле подкатится один из шаров, брошенных Иваном. Однако можно рассуждать иначе и представить четыре возможных случая:

1. Оба шара, брошенных Иваном, находятся ближе к кегле, чем шар Николая.

2. Оба шара, брошенных Иваном, находятся дальше от кегли, чем шар Николая.

3. Первый шар Ивана окажется ближе, второй — дальше, чем шар Николая.

4. Первый шар Ивана окажется дальше, второй — ближе, чем шар Николая.

В этом случае Николай выигрывает всего один раз из четырех, поэтому вероятность победы Ивана равна 3/4. Какое из двух рассуждений неверно? Почему?

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

Обычный кубик

Борис и Роман играют в кости с обычным игральным кубиком, на грани которого нанесены очки от 1 до 6. Первым кубик бросает Борис, затем Роман. Какова вероятность, что результат Бориса будет больше, чем результат Романа?

Очевидно, что вероятность того, что игроки выбросят одинаковое число очков, равна 1/6 (она совпадает с вероятностью того, что результат Романа будет тем же, что и у Бориса). Следовательно, вероятность выбросить разное число очков равна 5/6. Вероятность того, что результат Бориса будет выше, в два раза меньше и равна 5/12.

Какова вероятность выигрыша?

У нас есть три кубика разных цветов: на гранях красного кубика нанесены числа 2, 4, 9 по два раза каждое, на гранях синего кубика — 3, 5 и 7 по два раза каждое, на гранях белого — 1, 6 и 8 также по два раза каждое. В этой игре каждый из двух игроков выбирает один кубик и бросает его. Тот, кто выбрасывает больше очков, выигрывает. Оказывается, если дать сопернику выбрать кубик первому, вы всегда сможете выбрать кубик, с которым ваши шансы на победу будут выше, чем у противника. Как такое возможно? Какой кубик нужно выбрать?

Несмотря на то что сумма цифр на гранях всех кубиков одинакова, синий кубик предпочтительнее красного, белый предпочтительнее синего, а красный предпочтительнее белого. Из девяти бросков в каждой паре кубиков обладатель первого кубика выигрывает в пяти случаях, обладатель второго — в четырех. Иными словами, вероятность выигрыша для одного из кубиков равна 5/9, для другого — 4/9. Эти вероятности легко подсчитать, проанализировав все возможные исходы для каждой пары кубиков. Поэтому если вы выбираете кубик после противника, то при верном выборе можете получить преимущество.

Фреска в Помпее, на которой изображены игроки в кости (I век).

Спорная жеребьевка

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

Преподаватель предоставляет всем ученикам равные шансы, каждый имеет вероятность выигрыша в 1/30. Очевидно, что вероятность выигрыша для первого ученика равна 1/30, так как он может выбрать любое из 30 чисел. Вероятность выигрыша второго ученика равна 29/30 * 1/29 = 1/30 — это вероятность того, что первый ученик ошибется (29/30), а второй — нет (1/29). Для третьего ученика эта вероятность равна 29/30 • 28/29 • 1/28 = 1/30 и так далее. С другой стороны, заметим, что вероятность выигрыша для первого ученика однозначно равняется 1/30, и если бы для каждого последующего она уменьшалась, то сумма вероятностей оказалась бы меньше 1. Это абсолютно невозможно, так как 30 учеников назовут все 30 возможных чисел и один из них обязательно угадает.

Не слишком интересное пари

Некий игрок в рулетку всегда ставит на четное или нечетное. Если он угадывает, то выигрывает столько же, сколько поставил; если ошибается, то теряет свою ставку. Он решает каждый раз ставить 1/10 от суммы, которая есть у него на руках. Если он начнет игру со 100 евро, сделает 10 ставок подряд, выиграв 5 раз и проиграв 3 раз, сколько денег у него останется — больше, меньше или столько же, сколько было вначале? Эту задачу можно обобщить для произвольной стартовой суммы, например, m евро и ставки в 1/n от суммы, которая находится на руках у игрока перед очередной ставкой.

Может показаться, что после 5 выигрышей и 5 проигрышей у игрока будет столько же денег, что и вначале. Однако это не так, и в действительности у него останется меньше денег. Выигрыш увеличивает сумму денег на 1/10, что равносильно умножению на 1,1. Проигрыш уменьшает сумму на 1/10, что равносильно умножению на 0,9. Поэтому после 5 выигрышей и 5 проигрышей (независимо от того, в каком порядке они происходили) имеем 100 * 1,1⁵ • 0,9⁵ = 100 • 1,61051 * 0,59049 = 100 • 0,95099 ≈ 95,099 евро. Игрок потеряет около 5 евро. Подобные рассуждения можно обобщить для произвольного случая. Тот факт, что итоговая сумма всегда будет меньше начальной, объясняется тем, что (1 + 1/n)(1 - 1/n) = 1 - 1/n², что всегда меньше 1. При умножении начальной суммы на число, меньшее 1, мы всегда получим меньшее число.

Карикатура XVIII века на игроков в «четное — нечетное». Эта игра — предшественник современной рулетки.

Парадокс дней рождения

Одна из элементарных задач теории вероятностей с очень удивительным результатом формулируется так. Какова вероятность того, что среди 25 человек найдутся двое, у которых день рождения приходится на один и тот же день? Учитывая, что в году 365 дней (не будем учитывать високосные), а в группе всего 25 человек, интуиция подсказывает, что итоговая вероятность будет невелика и в любом случае меньше 1/2. Однако расчеты с применением теории вероятностей показывают, что эта вероятность будет больше 1/2.

Так как в нашей группе может быть двое и более людей, дни рождения которых приходятся на один день, можно вычислить вероятность того, что все члены группы родились в разные дни. Для этого упорядочим членов группы: день рождения первого человека может приходиться на любой из 365 дней, второго — на любой из 364 оставшихся, третьего — на любой из 363 оставшихся и так далее. Следовательно, вероятность того, что все 25 человек родились в разные дни, равна

p(несовпадения дней рождений) = 365/365 • 364/365 • 363/365 • 341/365 = 365! / (340! • 365²⁵) = 0,4313.

Отсюда получим вероятность того, что дни рождения как минимум у двух человек совпадают: 1 - 0,4313 = 0,5687 > 1/2. В действительности эта вероятность будет превышать 1/2 уже для группы из 23 человек.

Случайность не имеет памяти

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

Бросаем монету

Преподаватель математики предложил студентам бросить монету много раз, например 150, и записать результаты, обозначив орел за 1 и решку за 0. Двое его учеников получили такие результаты:

Роман:

01011001100101011011010001110001101101010110010001

01010011100110101100101100101100100101110110011011

01010010110010101100010011010110011101110101100011.

Борис:

10011101111010011100100111001000111011111101010101

11100001010001010010000010001100010100000000011001

00001001111100001101010010010011111101001100011010.

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

Равномерное распределение нулей и единиц в результатах Романа заставило преподавателя подозревать, что сжульничал именно он. Так, если сравнить распределение нулей и единиц в результатах Романа и Бориса, то мы увидим, что результаты похожи и «правдоподобны» (78 против 72 у первого из учеников, 70 против 80 у второго). Однако в результатах Бориса присутствуют последовательности из четырех, пяти и даже девяти одинаковых чисел подряд, а в результатах Романа последовательности из единиц или нулей очень коротки (максимум три единицы или нуля подряд). Именно это и наводит на подозрения.

Проанализируем этот факт с точки зрения условной вероятности. Учитывая, что каждый бросок монеты никак не зависит от предыдущих, после каждого результата единицы и нули должны появляться примерно с одинаковой частотой. Видим, что в результатах Романа после одной единицы снова единица встречается 47 раз, ноль — 30 раз. После двух единиц подряд единица встречается всего 5 раз, в то время как ноль — 18. После каждой из 5 последовательностей из трех единиц всегда находится ноль. Подобную картину мы наблюдаем только в результатах Романа. В результатах Бориса все иначе: например, после двух единиц подряд снова единица встречается 18 раз, ноль — 14 раз; после трех единиц подряд 9 раз встречается единица и 9 раз — ноль. Следовательно, представление Романа о том, что в распределении нулей и единиц не должно быть «длинных» участков, состоящих только из нулей или только из единиц, и позволило преподавателю определить жульничество.

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

Телеконкурс

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

ОЧЕНЬ СКРОМНЫЙ ЛАУРЕАТ ДВУХ НОБЕЛЕВСКИХ ПРЕМИЙ

Химик Лайнус Полинг (1901-1994) получил первую Нобелевскую премию в 1954 году за работы в области квантовой химии. После вручения ему второй премии — Нобелевской премии мира — в 1962 году за кампанию против испытаний ядерного оружия лауреат шутливо заметил, что получить первую премию было очень сложно: вероятность этого составляла один на шесть миллиардов (это население Земли). Вторая, по его мнению, была не столь почетна: вероятность этого равнялась одному на несколько сотен (число живущих на тот момент лауреатов Нобелевской премии). Где же кроется ошибка в этих забавных, но неверных рассуждениях?

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

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

Лайнус Полинг (справа) получает Нобелевскую премию мира.

Это знаменитая противоречивая задача теории вероятностей, в которой нужно определить, как изменяется вероятность того, что за закрытой дверью находится приз. Когда конкурсант выбирает одну из дверей, вероятность выигрыша равна 1/3. Эта вероятность не изменяется, когда ведущий выбирает одну из оставшихся дверей (за которой нет приза) и открывает ее, поскольку уже известно, что за одной из двух других дверей нет приза. Однако изменяется вероятность того, что приз находится за другой закрытой дверью: она равнялась 1/3 и стала равна 2/3 (вероятности для закрытых дверей складываются). Поэтому конкурсант должен согласиться изменить свой выбор, потому что в этом случае вероятность выигрыша составит 2/3. Противоречивость задачи в том, что вероятность выигрыша для изначально выбранной двери не изменяется. Если бы ведущий не выбирал одну из дверей, за которой нет приза, а вместо этого конкурсант указывал на одну из двух оставшихся дверей и спрашивал, находится ли за ней приз, а ведущий ответил бы «нет», то в этом случае вероятность выигрыша для изначально выбранной двери изменилась бы с 1/3 на 1/2.

Эта игра допускает одно интересное обобщение. Пусть имеется n дверей, и за одной из них находится приз. Конкурсант выбирает одну дверь (не открывая ее), ведущий открывает одну из других дверей, за которой нет приза, а затем разрешает изменить первоначальный выбор. Затем ведущий открывает другую дверь (одну из всех закрытых, за исключением той, что конкурсант выбрал последней), за которой также нет приза, и снова разрешает конкурсанту изменить выбор. Игра продолжается до тех пор, пока не останется две двери и конкурсант должен будет сделать окончательный выбор. Как нужно действовать конкурсанту на протяжении игры, чтобы вероятность выигрыша была наибольшей? Какой в этом случае будет вероятность выигрыша?

Будем отталкиваться от того факта, что при открытии двери ведущим изменяются вероятности для всех закрытых дверей, кроме той, которую выбрал конкурсант. Следовательно, вероятность выигрыша будет наибольшей тогда, когда игрок не будет менять свой выбор, пока не останутся лишь две закрытые двери. В этом случае игрок изменит свой выбор ивероятность победы будет равна (n - 1)/n. Таким образом, при первом выборе вероятность выигрыша составляет 1 /n (так как число дверей равно n). Если игрок не меняет свой выбор до момента, когда останутся лишь две закрытые двери, для изначально выбранной двери вероятность выигрыша будет равна 1/n, для другой — (n - 1)/n, которая и будет наибольшей. Если же, напротив, на каком-то из промежуточных шагов игрок изменит свой выбор, в этом случае определить вероятности будет несколько сложнее. Результат будет зависеть от того, сколько раз игрок изменит свой выбор и когда. В любом случае вероятность в этом случае будет выше 1/n, так как все вероятности увеличатся по отношению к исходной минимум один раз. Когда останутся только две двери, ни для одной из них вероятность выигрыша не будет равной (n - 1)/n. Если вам интересно подробнее ознакомиться с этой игрой, попробуйте вычислить вероятности для разных стратегий. Получить верный результат будет непросто, но очень интересно.

Математика и ожидание

Одно из наиболее важных понятий, которое следует учитывать, принимая решения в азартных играх, — математическое ожидание. Перед тем как дать этому термину точное определение, рассмотрим несколько примеров. Допустим, нам предлагают сыграть в такую игру: бросают две монеты, если выпадает две решки, выигрыш равен 4 евро, если выпадает два орла — 1 евро, если выпадает орел и решка — мы проигрываем 3 евро. Стоит ли играть по таким правилам? Сколько мы надеемся выиграть (или проиграть)?

При броске двух монет имеется четыре возможных результата: две решки (р = 1/4), два орла (р = 1/4), орел и решка (р = 1/4), решка и орел (р = 1/4). Каждые четыре броска в среднем один раз выпадут две решки, один раз — два орла и два раза — орел и решка. Следовательно, в среднем наш выигрыш составит 1 • 4 + 1 • 1 + 2 • (—3) = -1 евро. Это означает, что играть невыгодно и в среднем каждые четыре броска мы будем проигрывать 1 евро, то есть 25 центов за игру. Аналогичный результат можно получить, умножив вероятности для каждого исхода на соответствующий выигрыш (или проигрыш, который будет выражаться отрицательным числом) и сложив полученные результаты. В таком случае получим

1/4.4 + 1/4.1 + 1/2 • (-3) = -1/4 евро.

Рассмотрим второй пример. В игре с обычным кубиком банк платит 6 фишек, если выпадает шестерка, 4 фишки, если выпадает нечетное число, в остальных случаях мы не получаем ничего. Сколько нужно ставить в каждом розыгрыше, чтобы игра была сбалансированной?

Учитывая, что р(6) = 1/6 и р(нечетное число) = 1/2, в каждом розыгрыше мы ожидаем выиграть 1/6•6 + 1/2•4 + 1/3•0 = 3 фишки. Следовательно, игра будет равновесной (ни банк, ни игрок не будут иметь преимущества), если каждая ставка будет равняться 3 фишкам.

Эти примеры позволяют нам ввести понятия математического ожидания и равновесных игр, а также привести их определения в общем виде. Пусть имеются события S₁ S₂, S₃ ..., S_n, являющиеся попарно несовместными (ни одно из событий не может произойти одновременно с другим), которые могут произойти в азартной игре. Вероятности событий равны р₁ р₂, р₃ ..., р_n (выполняется условие p₁ + p₂ + p₃ + … + р_n = 1), суммы ставок соответственно равны r₁, r₂, r₃ ..., r_n. Ожидаемый выигрыш или математическое ожидание М [X] игры или случайного события, где результатом является одно из событий S₁, S₂, S₃, ..., S_n, определяется следующим образом:

М [X] = р₁ • r₁ + р₂ • r₂ + р₃ • r₃ + ... + p_n • r_n.

На основании этого определения говорят, что игра является справедливой (или равновесной), если математическое ожидание (средний выигрыш на каждом ходу) совпадает с суммой сделанной ставки. Также говорят, что общее математическое ожидание игры (ожидаемая сумма выигрыша минус сумма сделанных ставок) равна 0.

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

Игра с тремя кубиками

Игра заключается в следующем: игрок ставит 1 евро на число от 1 до 6, например на 3. Затем бросают три обычных кубика. Если 3 выпадает один раз, выигрыш составляет 1 евро, если 3 выпадает два раза, выигрыш равен 2 евро, если выпадает три раза — 3 евро. Кроме этого, при каждом выигрыше игроку возвращается сумма сделанной ставки в 1 евро. Если ни на одном из кубиков не выпадает 3, игрок проигрывает свою ставку в 1 евро. Является ли игра равновесной, либо же одна из сторон имеет преимущество?

Хотя на первый взгляд может показаться, что преимущество имеет игрок, на самом деле все по-другому. Можно рассуждать так: поскольку бросают три кубика и вероятность того, что выпадет заданное число, равна 1/6 для каждого кубика, вероятность выигрыша составляет как минимум 1/2. Но, кроме этого, есть вероятность того, что выбранное число выпадет два или даже три раза, поэтому шансы игрока на победу выше.

Однако подобное рассуждение неверно. Существует 216 возможных исходов (6*6* 6). Лишь в одном случае (р = 1/216) загаданное число выпадет три раза, в 15 случаях — дважды (р = 15/216), и в 75 случаях игрок получит сумму, равную ставке (р = 75/216). Следовательно, в 125 случаях (216 - 1 - 15 - 75) игрок теряет свою ставку.

Заметим, что исходов, когда игрок проигрывает (125), больше, чем тех, когда он выигрывает (91). Если вычислить математическое ожидание для ставки в 1 евро, получим:

3 • 1/216 + 2 • 15/216 + 1 • 75/216 - 1 • 125/216 = 108/216 - 125/216 = -17/216 = -0,0787...

Следовательно, преимущество имеет банк, который в среднем выигрывает почти 8 центов с каждого поставленного евро.

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

Ожидаемый платеж

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

Если заплатить вступительный взнос до 1 марта, то он составит 150 евро. Если вы не сможете поехать, платеж возвращен не будет. При оплате после 1 марта (и даже непосредственно по прибытии на конференцию) сумма составит 200 евро.

28 февраля вы оцениваете вероятность того, что сможете поехать на конференцию. Пусть эта вероятность равна p. Что нужно сделать в зависимости от значения p — заплатить заранее или непосредственно по приезде?

Если вы уплатите взнос заранее, математическое ожидание равно -150 (вне зависимости от того, поедете вы или нет, так как взнос не возвращается).

Если вы платите непосредственно по прибытии, то математическое ожидание равно -200 • р + (1 — р) • 0 = -200 • p(вы платите только в том случае, если смогли приехать).

Математические ожидания равны при р = 150/200 = 0,75.

Следовательно, если р > 0,75, то лучше заплатить заранее, если же р < 0,75, то лучше заплатить по прибытии на конференцию. При р = 0,75 результат будет одинаков.

Можно ли обыграть банк? Вероятность повторяющихся событий

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

Начнем с анализа игры в рулетку с 37 секторами (числа от 1 до 36 и 0). Какова вероятность того, что в 10 играх три раза выпадет зеро?

Вероятность выпадения трех зеро подряд в определенный момент игры равна (1/37)³ • (36/37)⁷ = 0,00016. Общая вероятность равна этому результату, умноженному на число позиций, которое может занимать последовательность из трех нулей: Сю з = 120. Иными словами,

p(3 нуля в 10 играх) = 120 • 0,00016 = 0,0192,

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

p(r из n испытаний завершатся успешно) = С_n,r • p^r • q^(n-r), где q = 1-p, r≤n.

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

Используем биномиальное распределение, чтобы найти вероятность того, что при n бросках монеты r раз выпадет решка, r = 1, 2, ...,n при n = 8. В этом случае p(выпадения решки) = 1/2, следовательно, q = 1/2, откуда получим p^r * q^8-r = (1/2)^r • (1/2)^8-r = (1/2)⁸ = 1/256. Умножив это значение на значения сочетаний (C_8,r) для разных значений r, получим:

Симметричное распределение, которое можно увидеть из таблицы, — следствие того, что вероятность выпадания решки при одиночном броске равна 1/2. Читатель наверняка уже заметил, что последовательность чисел (1, 8, 28, 56, 50, 56, 28, 8, 1) из таблицы выше, сумма которых равна 256 (2⁸), совпадает с одним из рядов треугольника Паскаля. Следовательно, биномиальное распределение связано с биномиальными коэффициентами, которые в данном конкретном случае равны коэффициентам в биноме (а + b)⁸.

Глава 4. Математическая теория игр

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

Жан Дьёдонне

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

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

Начала теории игр

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

РОДОНАЧАЛЬНИКИ ТЕОРИИ ИГР

Уже в XVII веке такие ученые, как Христиан Гюйгенс (1629-1695) и Готфрид Вильгельм Лейбниц (1646-1716), предложили создать дисциплину, в которой бы использовались научные методы для изучения человеческих конфликтов и взаимодействий. Однако получить какие-либо значимые результаты по этой теме им не удалось. На протяжении всего XVIII века не было написано практически ни одной работы по анализу игр, которая бы имела подобную цель. Заслуживает упоминания письмо Джеймса Уолдгрейва от 1713 года, в котором приводится решение карточной игры для двух игроков под названием Le Her. Автор использовал способ, похожий на смешанную стратегию, и привел минимаксное решение. Несмотря на это, не было разработано ни теоретической базы, ни обобщений, чтобы подобный метод можно было применить в других случаях. В XIX веке многие экономисты создавали простые математические модели для анализа простейших конкурентных ситуаций. Среди них выделяется работа Антуана Огюста Курно «Исследование математических принципов теории богатства» (1838), в которой рассматривается случай дуополии и приводится решение, которое можно считать частным случаем равновесия Нэша. Тем не менее, теория игр как фундаментальная математическая теория появилась лишь в первой половине XX века.

Портрет Гэтфрида Вильгельма Лейбница, немецкого философа, который также занимался математикой.

Начнем рассказ об основах теории игр со следующего случая. Он очень прост и не представляет никакого интереса в качестве игры. Два игрока А и Б одновременно записывают число (1 или 2). Игрок Б должен заплатить игроку А сумму в евро, равную результату сложения двух записанных чисел. Очевидно, игра неравновесная (А всегда выигрывает), но тем не менее мы можем задаться вопросом: как должен действовать каждый игрок в соответствии со своими интересами? Для этого рассмотрим матрицу игры, так называемую платежную матрицу, в которой приведены возможные результаты:

Элементы матрицы обозначают сумму в евро, которую должен заплатить игрок Б игроку А при выборе соответствующей стратегии. Каждый игрок имеет два варианта действий, поэтому всего в матрице четыре элемента. Игра очень простая, и очевидно, что, действуя согласно своим интересам, А напишет 2, Б напишет 1, выигрыш игрока А составит 3 евро.

Проанализируем ходы игроков более подробно, чтобы увидеть, каковы варианты действий для каждого игрока. А не знает, какое число записал Б, но предполагает, что Б хочет платить как можно меньше. Поэтому если А напишет 1, то выиграет минимум 2 евро, если напишет 2 — выиграет минимум 3 евро. Говорят, что 3 (число в нижней левой ячейке матрицы) — это максиминное значение (максимальное среди минимальных). Аналогично Б предполагает, что А хочет получить наибольший выигрыш. Поэтому если Б запишет 1, то потеряет максимум 3 евро, если запишет 2 — потеряет максимум 4 евро. Говорят, что в этом случае 3 является минимаксным значением (минимальным среди максимальных). Если минимаксное и максиминное значения в игре находятся в одной и той же ячейке матрицы, как в нашем случае, то говорят, что игра имеет седловую точку. (Представьте себе седло, изображенное в форме двух пересекающихся кривых, в точке пересечения которой минимальное значение одной совпадает с максимальным значением другой. Эта точка пересечения и называется седловой.)

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

Теперь представим себе другую игру с теми же правилами, но с другой платежной матрицей: если оба игрока записывают одинаковое число, А выигрывает 1 евро, если же числа отличаются, Б выигрывает 1 евро.

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

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

Рассмотрим третью игру. Она похожа на две предыдущие, но определить оптимальные стратегии для каждого игрока будет сложнее. Как и в прошлых примерах, каждый игрок может записать одно из двух чисел: А может записать 1 или 8, Б может записать 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Платежная матрица этой игры выглядит так:

Заметим, что элементы матрицы обозначают выигрыши игрока А. Поэтому в случае победы игрока Б элемент матрицы является отрицательным и отражает проигрыш игрока А. Может показаться, что игра равновесная (А может выиграть 1 или 8 евро, Б — 2 или 7 евро), но седловой точки не существует: максиминное значение равно -2 (-2 > -7), минимаксное равно 1 (1 < 8). На самом деле если в платежной матрице 2x2 числа вдоль одной диагонали больше, чем вдоль другой, седловой точки не существует, поэтому для такой игры нет оптимального решения. Однако имеется важное отличие этой игры от предыдущей. В предыдущей игре наилучшим вариантом было использование случайных стратегий обоими игроками, в этом случае выигрыши уравнивались. Здесь же игрок Б имеет шансы на победу. Оптимальная стратегия для каждого игрока по-прежнему предусматривает случайные действия, но не является полностью случайной, так как каждый должен принимать решения, соблюдая определенные соотношения. Решением игры в этом случае является использование смешанных стратегий обоими игроками. О том, как определить результаты этой игры, то есть об оптимальной стратегии для каждого игрока и о средней цене игры, мы поговорим несколько позже.

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

РОЖДЕНИЕ ТЕОРИИ ИГР

В начале XX века начала складываться теоретическая основа современной теории игр, окончательно оформившейся в середине столетия. Авторство первой теоремы принадлежит логику Эрнсту Цермело (1871-1956). Он сформулировал и доказал ее в 1912 году. Эта теорема подтверждает, что любая конечная игра с полной информацией (например, шашки или шахматы) имеет оптимальное решение в чистых стратегиях, то есть в отсутствие элемента неопределенности. Эта теорема не описывает, как можно найти подобные стратегии.

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

Французский математик Эмиль Борель, автор множества исследований по теории вероятностей.

Когда достигается равновесие?

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

ДЖОН ФОН НЕЙМАН (1903-1957)

Джон фон Нейман, известный по работам во множестве областей, является одним из наиболее выдающихся математиков XX века. Он начал научную деятельность в родном Будапеште, где изучал математику. Затем он переехал в Берлин, чтобы заниматься физикой, а позже в Цюрих, где изучал химию. С 1930 года он жил и работал в США. В Гёттингене под руководством Гильберта фон Нейман занимался теоретическими вопросами чистой математики, а также совместно с Гейзенбергом работал над началами квантовой теории. Он внес существенный вклад во многие сферы науки, в частности в теорию множеств, функциональный анализ, логику, теорию вероятностей, прикладную математику в экономике, квантовую физику и метеорологию.

Его интересы выходили за рамки чистой и прикладной математики и охватывали также столь различные области, как атомная физика, проектирование компьютеров, когнитивная психология и экономика. Одно из важнейших его достижений, относящееся к прикладной математике в экономике, — создание теории игр, которую он сформулировал в книге «Теория игр и экономическое поведение»», опубликованной совместно с экономистом Оскаром Моргенштерном в Принстоне в 1944 году. Этот труд считается фундаментальным в теории игр. Он ознаменовал создание теории игр, которая уже через несколько лет, начиная с 1950-х годов, стала находить применение в анализе множества реальных ситуаций.

Джон фон Нейман (справа) и Роберт Оппенгеймер, руководитель программы по созданию первой атомной бомбы, на этой фотографии 1952 года изображены рядом с самым быстрым и точным компьютером того времени.

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

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

Представим следующую игру для двух игроков: игрок А выбирает строку (F1, F2, F3), его соперник — столбец (Cl, С2, СЗ) из следующей платежной матрицы, при этом ни один из игроков не знает о выборе оппонента. Выбор игроков определит элемент матрицы (он находится на пересечении выбранных строки и столбца), который укажет, сколько евро должен заплатить второй игрок первому. Как должен действовать каждый игрок, чтобы увеличить свой выигрыш или уменьшить проигрыш?

Игрок А анализирует минимальные выигрыши в зависимости от совершенных ходов. Если он выберет F1, минимальный выигрыш равен -2, 2 для строки F2 и - 1 для строки F3. Наибольший из минимальных выигрышей (максиминное значение) равен 2. Если игра является определенной, нужно выбирать строку F2. Аналогично игрок Б анализирует наибольшие проигрыши в зависимости от совершенных ходов. Если он выберет С1, максимальный проигрыш равен 6, 7 — для столбца С2 и 2 — для столбца СЗ. Наименьший из максимальных проигрышей (минимаксное значение) равен 2. Если игра является определенной, нужно выбирать столбец СЗ.

Так как в этой игре максиминное и минимаксное значения совпадают и равны 2 евро, говорят, что игра является определенной, имеет цену 2 и имеет решение в чистых стратегиях: игрок А выберет F2, игрок Б — СЗ. Также говорят, что 2 является седловой точкой, или точкой равновесия (максимальное из минимальных значений совпадает с минимальным из максимальных).

Этот пример можно обобщить для этого же числа игроков, но дав им возможность выбора не из трех, а из n ходов. Таким образом, платежная матрица будет иметь размеры n × n. Если для игры существует седловая точка, то говорят, что игра имеет точку равновесия, которой соответствует пара чистых стратегий (оптимальных для каждого игрока). Игра имеет стабильный результат, так как одностороннее изменение стратегии одним из игроков приведет к тому, что его результат станет хуже, соответственно, возрастет выигрыш оппонента.

ЯВЛЯЮТСЯ ЛИ ЭТИ ИГРЫ СТАБИЛЬНЫМИ?

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

Выборы и рестораны: применение игр с чистыми стратегиями

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

Предвыборные программы

Представим следующую ситуацию: в некой стране во время предвыборных дебатов внимание общественности привлекла постройка объездной магистрали вокруг столицы. Имеются два варианта: трасса может пройти севернее (С) или южнее (Ю) города. Две основные партии страны, А и Б, должны определить предвыборную программу и решить, за какой из вариантов они выступают. Также они могут избежать обсуждения и никак не касаться этого вопроса в предвыборной программе. Руководство обеих партий знает, что их сторонники поддержат любое решение, но остальное население будет склоняться к тому или иному варианту, и если обе партии сделают одинаковый выбор, избиратели воздержатся от голосования. По итогам предвыборных опросов, которые известны обеим партиям, были получены следующие результаты:

Так, если партия А предложит проложить магистраль севернее, а партия Б — южнее, партия А получит 45% голосов. Если же обе партии не будут затрагивать эту тему, партия А получит 35% голосов. Какие решения примут обе партии при заданных условиях?

Если руководствоваться приведенной матрицей, то выбор прост: партия А показывает наилучшие результаты, если будет поддерживать постройку трассы на юге. Именно этого варианта она и будет придерживаться. Аналогично партия Б заметит, что результаты партии А будут наихудшими (что устраивает партию Б), если Б будет избегать этой темы. Такой будет стратегия партии Б. Следовательно, игра имеет седловую точку (партия А голосует за постройку трассы на юге, Б избегает темы), цена игры — 45% голосов в пользу партии А.

Теперь предположим, что матрица имеет следующий вид:

Стратегия партии А по-прежнему ясна: оптимальным вариантом в любом случае является постройка магистрали на севере. Но теперь партия Б не сможет принять оптимальное решение, не зная о выборе партии А. Выбор в пользу постройки на юге (Ю) очень привлекателен, так как в этом случае партия А может остаться лишь с 20% голосов. Однако такой выбор не имеет смысла: если партия А сделает правильный выбор, то в этом случае она получит 55% голосов, а не 20%. Поэтому для партии Б предпочтительнее не касаться этой темы, в результате партия А получит 45% голосов.

Наконец, предположим, что матрица имеет следующий вид:

Теперь ни одна из партий не может сразу сделать выбор, так как оптимальное решение будет зависеть от того, что предпочтет оппонент. Поэтому сторонам нужно определить, какой вариант будет оптимален вне зависимости от выбора соперника. Иными словами, какой вариант — наилучший из худших. Так, если партия А выберет вариант С, то получит минимум 10%, минимум 45% — если выберет Ю, и минимум 10%, если не будет касаться этой темы. Следовательно, оптимальным вариантом является постройка трассы на юге. Аналогично если партия Б выберет вариант С, то партия А получит максимум 45%. Если партия Б выступит за постройку трассы на юге, то партии А может достаться до 55% голосов, а если партия Б уклонится от обсуждения, то партия А получит до 65%. Следовательно, партия Б должна выбрать вариант С.

В этом случае оптимальный выбор для каждой партии приводит к одинаковому результату в 45% голосов в пользу А. Эта точка является седловой, или точкой равновесия.

Задача о ресторане

Двое друзей, Мария и Георгий, хотят открыть ресторан у перекрестка больших дорог за городом, который окружают горы. У них не возникло никаких разногласий, кроме одного: Мария хочет открыть ресторан в низине, а Георгий — высоко в горах, и в этом вопросе их мнения полностью противоположны. Чтобы принять решение, они придумали провести игру: друзья выбрали три параллельных автомагистрали Al, А2 и АЗ, которые идут с запада на восток, и три параллельных дороги С1, С2 и СЗ, которые идут с севера на юг. Эти дороги образуют девять перекрестков. Высота каждого перекрестка приведена в следующей матрице:

Чтобы определить место будущего ресторана, компаньоны решили действовать так: Мария выбирает одну автомагистраль (Al, А2 или АЗ), Георгий — другую (Cl, С2 или СЗ). На пересечении выбранных дорог и будет построен ресторан. Как должен действовать каждый игрок, чтобы ресторан в итоге был построен в соответствии с его интересами?

Георгий — пессимист и из трех минимальных значений (470, 540, 280) выбирает максимум. Он решает выбрать дорогу С2, что гарантирует высоту в 540 метров. Аналогично Мария оценивает максимальную высоту каждой дороги (540, 1050, 930) и выбирает трассу А1, что обеспечивает наименьшую высоту, 540 метров. Итак, оба игрока сделали свой выбор и результат в 540 метров является оптимальным для каждого из них. Иными словами, если один из компаньонов изменит свой выбор, то результат будет меньше соответствовать его интересам.

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

Когда равновесия не существует: смешанные стратегии

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

Определение оптимальной смешанной стратегии

Вспомним третью (последнюю) игру, о которой говорилось в первом разделе этой главы. Каждый из двух игроков может записать одно из двух чисел: игрок А может записать 1 или 8, игрок Б — 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Матрица игры выглядит так:

Игра выглядит справедливой (игрок А может выиграть 1 или 8 евро, игрок Б — 2 или 7), седловой точки не существует: максиминное значение равно -2, минимаксное — 1. Поэтому ни для одного из игроков не существует чистой стратегии. Посмотрим, как в этом случае можно сформировать смешанную стратегию, которая будет оптимальной и позволит определить цену игры.

Смешанная стратегия — это некий «случайный» выбор одной чистой стратегии из набора. Чтобы сформировать смешанную стратегию, каждой чистой стратегии присваивается вероятность, означающая, с какой частотой игрок будет использовать эту чистую стратегию. Например, в нашем случае для игрока А есть две чистые стратегии (записать 1 или записать 8), для Б — две другие. Попробуем найти вероятности p(записать 1), p(записать 8) для игрока А и p(записать 7), p(записать 2) для игрока Б так, чтобы максимально повысить шансы каждого игрока на победу. Если мы определим вероятности и платежи для каждого случая, то сможем определить ожидаемый выигрыш.

Сначала нужно определить вероятности для чистых стратегий игрока А. Обозначим за р вероятность того, что этот игрок запишет 8. Тогда вероятность написания 1 будет равна 1 — р. Следовательно, если игрок Б запишет 7, ожидаемый выигрыш игрока А составит

V = 1 (1 - р) + (-7) р. Получим линейное уравнение V = 1 - 8р.

Если же, напротив, Б запишет 2, то ожидаемый выигрыш для игрока А составит

V = (-2)(1 - р) + 8р, что равносильно V = 10р — 2.

Игрок А хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок Б. Решив систему из двух линейных уравнений, получим значения р и V для игрока А. В данной задаче р = 1/6, V = -1/3.

Аналогично можно найти смешанную стратегию для игрока Б. Обозначим за р вероятность того, что он запишет 2. Тогда вероятность того, что он напишет 7, будет равна (1 — р). Если А запишет 1, то ожидаемый выигрыш Б составит

V = 2р + ( -1) (1 - р), что равносильно V = Зр — 1.

Аналогично если А выберет другую стратегию и запишет 8, то ожидаемый выигрыш игрока Б составит

V = ( -8)р + 7 (1 - р), то есть V = 7 - 15р.

Игрок Б хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок А. Решив систему из двух линейных уравнений, получим значения р и V для игрока Б. Результаты будут следующими: р = 4/9, V* = 1/3.

Метод, который мы только что применили, можно обобщить для матриц 2 × 2 и использовать для решения игр, которые не имеют седловой точки, в смешанных стратегиях. Проанализируем полученные результаты более подробно. Во-первых, заметим, что ожидаемые выигрыши совпадают (V = 1/3) и отличаются только знаком. Для А найденный выигрыш отрицательный, для Б — положительный. Это означает, что Б ожидает выиграть столько, сколько проиграет А. Цена игры (средний выигрыш игрока А) определяется с помощью уравнения (ad - bc)/(а + d - b - с), где a,b,c,d — элементы платежной матрицы (слева направо и сверху вниз). Так, в нашем случае цена игры равна (8 - 14)/18 = -6/18 = -1/3, что означает, что игрок А в среднем будет проигрывать 1 евро за каждые три партии, если оба игрока будут придерживаться оптимальных стратегий.

Теперь мы можем напрямую найти смешанные стратегии как для игрока А, так и для игрока Б. Соотношение, с которым игрок А должен применять смешанные стратегии, можно определить, если найти выигрыш и проигрыш для каждой строки матрицы. Так, его выигрыши равны 1 - (-2) = 3 (для первого ряда) и - 7 - 8 = -15 (для второго ряда). Следовательно, в рамках оптимальной стратегии игрок А должен действовать случайным образом, но соблюдать соотношение 15 к 3, или 5 к 1. Он должен записывать 1 в пять раз чаще (например, перед каждым ходом бросать обычный кубик, на пять граней которого нанесена цифра 1, а на одну грань — цифра 8). Заметим, что этот результат совпадает с тем, который мы получили, решив систему уравнений. Вероятность того, что игрок А запишет 8, должна равняться 1/6, следовательно, вероятность того, что он запишет 1, должна равняться 5/6.

Проведем аналогичные вычисления для игрока Б (по столбцам). Для первого столбца 1 — (—7) = 8, для второго столбца -2 -8 = -10. Следовательно, игрок Б должен придерживаться соотношения 10 к 8, либо, что аналогично, 5 к 4, в пользу числа 7. Это совпадает с решением системы уравнений, приведенной выше: мы вычислили, что вероятность написания 2 должна составлять 4/9, следовательно, вероятность написания 7 должна составлять 5/9.

Теперь мы можем сформулировать оптимальную смешанную стратегию для каждого игрока. А делает ходы произвольным образом, но должен записывать 1 с вероятностью 5/6 и записывать 8 с вероятностью 1/6. Аналогично игрок Б должен произвольным образом выбирать между 7 (с вероятностью 5/9) и 2 (с вероятностью 4/9).

ТЕОРЕМА О МИНИМАКСЕ

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

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

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

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

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

Наконец, несмотря на то что седловой точки не существует, можно показать, что если каждый игрок будет придерживаться оптимальной смешанной стратегии, то игрок Б в среднем будет выигрывать 1/3 евро за партию. Если Б выберет любую другую стратегию, а игрок А будет придерживаться прежней, то выигрыш Б уменьшится. Напротив, если игрок Б будет придерживаться оптимальной стратегии, а игрок А выберет другую, проигрыш А возрастет.

Применение смешанных стратегий

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

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

Рост компании

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

Руководство компании считает, что экономическая обстановка определяется некоей смешанной стратегией. Какова оптимальная смешанная стратегия компании и ожидаемая прибыль?

Элементы матрицы позволяют увидеть, что не существует оптимальной чистой стратегии, так как седловая точка отсутствует (максиминное значение равно 300, минимаксное равно 500). Следовательно, нужно определить оптимальную смешанную стратегию.

Обозначим за р вероятность выпуска крупной серии, (1 — р) — малой серии, V — ожидаемый доход. При плохой экономической обстановке доход будет равняться

V = 500 (1 — р) + ЮОр, что равносильно V = 500 - 400р.

При хорошей экономической обстановке доход будет равняться

V = 300 (1 — р) + 900р, то есть V = 300 + 600р.

Решением этой системы уравнений является р = l/5, V = 420. Это означает, что если бы ситуация моглаповториться несколько раз, то оптимальным вариантом было бы выпускать продукт крупной серией 1 раз из 5 случайным образом и 4 раза из 5 — малой серией, при этом средний ожидаемый доход составит 420 тысяч евро.

Средний доход можно было вычислить напрямую с помощью формулы V = (ad - bc) / (а + d - b - с), где a, b, с, d — элементы платежной матрицы (слева направо и сверху вниз). Для данной задачи получим (500 • 900 - 300 • 100)/(500 + 900 - 300 - 100) = 420000/1000 = 420, что очевидно совпадает с результатом, полученным выше из системы линейных уравнений.

С другой стороны, мы действовали так, как если бы экономическая обстановка определялась некоей смешанной стратегией. Аналогичные расчеты показывают, что вероятность хорошей экономической обстановки равна 2/5, следовательно, вероятность плохой экономической обстановки равна 3/5.

Серия пенальти

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

Элементы матрицы означают вероятность гола (то есть выигрыш бьющего) в зависимости от стратегии, выбранной обоими игроками. Например, если пенальтист бьет вправо, а вратарь прыгает в правый от себя угол, вероятность гола равна 0,9. Если же удар придется по центру и вратарь останется стоять в центре, то вероятность гола будет равной всего 0,1. Какой стратегии должны придерживаться бьющий и вратарь?

КОРПОРАЦИЯ RAND

Корпорация RAND (от англ. Research and Development — «Исследования и разработка») — американский исследовательский центр, созданный после Второй мировой войны с целью проведения стратегических исследований для военно-воздушных сил США. Многие проекты корпорации были засекречены и не доведены до логического завершения, но нет никаких сомнений, что в RAND работали одни из лучших ученых в области теории игр. В 1948 году Центр получил статус частной организации, работающей исключительно на военно-воздушные силы, которые полностью его финансировали. Именно в этой корпорации были проведены фундаментальные исследования, которые способствовали развитию теории игр.

Внутренняя организация Центра больше напоминала научно-исследовательский институт, чем военное учреждение. В 50-е и 60-е годы прошлого века помимо прикладных исследований, связанных с ядерным оружием и началом холодной войны, в корпорации также проводились фундаментальные исследования силами выдающихся математиков и экономистов. Среди них все тот же Джон фон Нейман, Джон Нэш, Меррил Флад, Кеннет Эрроу и многие другие ученые, расцвет деятельности которых пришелся на этот короткий промежуток времени, совпавший с началом бурного роста теории игр.

Новая штаб-квартира корпорации RAND в Санта-Монике, Калифорния.

Первоначальный анализ показывает, что не существует доминантной чистой стратегии и что задача не имеет решения в чистых стратегиях, так как максиминное значение равно 0,6, а минимаксное — 0,8. Иными словами, пенальтист ожидает забить 6 из 10 пенальти, а вратарь ожидает, что пропустит гол в 8 из 10 случаев. Оба хотят (и могут) улучшить свой результат (т. е. выигрыш): пенальтист хочет, чтобы вероятность забить была выше 0,6, а вратарь хочет, чтобы вероятность пропустить была ниже 0,8.

Рассчитаем оптимальную смешанную стратегию для бьющего и для вратаря, а также среднюю цену игры, которая будет означать среднюю вероятность того, что с пенальти будет забит гол. В этом случае средняя цена игры будет лежать в интервале от 0,6 до 0,8.

Чтобы определить оптимальную смешанную стратегию для бьющего, нужно рассчитать вероятности выбора каждой из трех чистых стратегий. Обозначим их p(правый угол), p(левый угол), p(центр). Так как p(правый угол) + p(левый угол) + p(центр) = 1, число переменных можно сократить до двух: p(правый угол), p(центр), 1 - p(правый угол) - p(центр). Ожидаемую цену игры обозначим за V.

Если вратарь прыгнет в правый от себя угол, то ожидаемый выигрыш пенальтиста составит

V = 0,9 p(правый угол) + 0,8 p(центр) + 0,5 (1 - p(правый угол) - p(центр)).

Если вратарь останется в центре, то

V = 0,9 p(правый угол) + 0,1 p(центр) + 0,8 (1 - p(правый угол) - p(центр)).

Если же вратарь прыгнет в левый от себя угол, то

V = 0,6 p(правый угол) + 0,7 p(центр) + 0,8 (1 - p(правый угол) - p(центр)).

Мы получили систему из трех линейных уравнений. Ее решением будет являться p(правый угол) = 0,37; p(центр) = 0,19; p(левый угол) = 1 - p(правый угол) - p(центр) = 0,44. Цена игры для бьющего равна V = 0,71.

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

Преимущества и ограничения метода минимакса

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

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

Мортон Дэвис во введении в теорию игр рассказывает о различных исследованиях, которые проводились в 1950—1970-е годы. Целью исследований было наблюдение за поведением реальных игроков в матричных играх. Так, в 1964 году Ричард Брейер придумал игру, разрешимую в чистых стратегиях, то есть в этой игре было легко найти точку равновесия. Игрокам говорили, что против них в одних случаях будет играть опытный игрок, в других — игрок, который будет действовать случайным образом. В действительности игроки всегда играли против экспериментатора, который менял стратегию: иногда он следовал оптимальной стратегии Б, иногда действовал случайным образом. Платежная матрица этой игры выглядела так:

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

Опыты показали, что игроки применяли стратегию б, когда видели, что экспериментатор всегда придерживается стратегии Б. Напротив, когда экспериментатор действовал случайным образом, они меняли стратегию и обычно применяли вариант а, чтобы получить максимальный выигрыш, осознавая при этом возможность проигрыша. Последующие опросы показали, что более половины игроков считали, что систематическое следование стратегии Б со стороны экспериментатора «глупо», так как он соглашался с проигрышем в 1. Если бы он применял другие стратегии, то, «возможно», мог бы улучшить свой результат. Игроки не обратили внимания, что если бы они следовали стратегии б, то экспериментатору был бы гарантирован проигрыш минимум в 1.

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

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

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

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

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

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

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

Глава 5. Что наша жизнь? — Игра! Применения теории в реальном мире

Конкуренция лежит в основе науки... и всей жизни. <...> Соперничество и сотрудничество делают нас такими, какие мы есть.

Эрвин Неер, лауреат Нобелевской премии по медицине

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

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

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

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

Можно сказать, что все множество ситуаций, изучаемых в теории игр, можно разделить на две полярные группы: игры с нулевой суммой, основанные на чистом соперничестве, и игры, основанные на чистом сотрудничестве. И те и другие легко решить, по крайней мере в теории. Игры, основанные на чистом соперничестве, рассматривались в прошлой главе. Аналогично можно анализировать ситуации, основанные на чистом сотрудничестве: действия пилота раллийного автомобиля и его штурмана, действия партнеров в танце, действия пилота самолета и диспетчера — это всё примеры ситуаций, где оба игрока имеют одну цель, и решение состоит в том, чтобы объединить усилия (эффективно координировать ходы).

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

РАЗВИТИЕ ТЕОРИИ ИГР

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

В 50-е годы XX века в теории игр произошел заметный прорыв. Появились первые исследования дилеммы заключенного, Джон Нэш определил понятие оптимальной стратегии для игр со множеством игроков, когда оптимальную стратегию нельзя определить заранее (подобная ситуация известна как равновесие Нэша). Этот алгоритм применим для некооперативных игр, но может быть расширен и для кооперативных. В это же время теория игр впервые начала применяться в других областях помимо экономики, например, в философии и политологии. Позднее, уже в 1970-е годы, теория игр начала применяться в биологии в основном благодаря работам Джона Мейнарда Смита, который ввел понятие эволюционно стабильной стратегии.

Фотография Оскара Моргенштерна, который вместе с Джоном фон Нейманом является создателем теории игр.

Математика сотрудничества: игры с ненулевой суммой

Чтобы показать разницу между играми с нулевой и с ненулевой суммой, рассмотрим ситуацию, связанную с распространением рекламы. Две компании, А и Б, хотят прорекламировать свою продукцию. В обе компании поступает предложение от телеканала: рекламу можно показать днем (когда ее увидят 40% телезрителей) или вечером (тогда ее увидят 60% зрителей), причем можно выбрать только один из предложенных вариантов. Известно, что дневная и вечерняя аудитории не пересекаются. Если обе компании закажут рекламу на одно и то же время, то их продукцию купят 30% зрителей, включивших телевизор в это время, и никто из тех, кто смотрел телевизор в другое время. Если же компании закажут рекламу на разное время, то охватят 50% аудитории, которая в тот момент находилась у экранов. Какое решение оптимально для каждой компании? Будет лучше проконсультироваться с другой компанией или скрыть свои намерения?

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

Если А и Б запустят рекламу днем, то каждой компании достанется 12% аудитории (30% от 40%). Если рекламные ролики выйдут в разное время, то результаты будут симметричны: если А запустит рекламу днем, а Б — вечером, то А получит 20% (половину от 40%), компания Б — 30% (половину от 60%). Если обе компании в этом случае сменят стратегии на прямо противоположные, противоположными окажутся и результаты.

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

МАТРИЦА ДЛЯ ИГРОКА А

МАТРИЦА ДЛЯ ИГРОКА Б

С учетом того, что матрицы симметричны и что стратегии А указаны в строках, а стратегии Б — в столбцах, анализ обеих матриц проводится аналогичным образом. Можно выполнить те же действия, что и для игр с нулевой суммой: седловая точка отсутствует (максиминное значение равно 18, минимаксное — 12), поэтому нужно найти смешанную стратегию, чтобы определить цену игры для игрока А. Эта стратегия такова: нужно использовать стратегию 1 (выпускать рекламу днем) с вероятностью 3/5 и стратегию 2 (выпускать рекламу ночью) с вероятностью 2/5. Таким образом мы получим цену 19,2 (средний выигрыш за партию). Аналогично для игрока Б (с учетом симметрии): в каждых пяти партиях он должен произвольным образом два раза выбрать стратегию 1 и три раза — стратегию 2, при этом его средний выигрыш будет тем же. Пока что нет никаких отличий от прошлых примеров, и читатель может посчитать, что мы определили оптимальную стратегию для каждого игрока и что игра решена.

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

Это происходит потому, что оптимальные стратегии в играх с нулевой суммой основаны на ограничении или уменьшении выигрыша соперника. Если игра имеет нулевую сумму, то уменьшение выигрыша одного игрока равносильно увеличению выигрыша другого, но в нашем случае это не так. Допустим, что компания Б не будет использовать смешанную стратегию и всегда будет применять стратегию 2 (выпуск рекламы вечером), в то время как компания Б будет придерживаться смешанной стратегии. В этом случае компания А в среднем получит 30 • 2/5 + 18 • 3/5 = 22,8, а компания Б — по-прежнему 19,2. Заметим, что выигрыш Б не изменился, а выигрыш А возрос. В играх с нулевой суммой это невозможно. Очевидно, компания Б может действовать подобным образом и всегда использовать чистую стратегию 2, ожидая, что А будет придерживаться смешанной стратегии. В этом случае результат Б возрастет, результат А останется на прежнем уровне.

Но что произойдет, если обе компании используют чистую стратегию 2? Обе получат лишь по 18% аудитории, выигрыш обоих игроков уменьшится одинаково. Кажется, что мы зашли в тупик: каждая компания может выиграть больше, не повредив конкуренту, но если оба игрока захотят получить больше, то, напротив, выиграют меньше среднего ожидаемого значения.

Однако возможен и другой вариант. Допустим, что оба игрока заключили соглашение, чтобы не попасть одновременно в клетки с наименьшим выигрышем, то есть не размещать рекламу в одно и то же время. В этом случае каждая компания получит больше, при этом выигрыши компаний могут стать равными: если компания А будет чередовать стратегии 1 и 2, а компания Б — чередовать стратегии 2 и 1, то средний выигрыш для обеих компаний будет равен 25% за партию. Компания А будет попеременно получать 20 и 30 процентов, компания Б — 30 и 20. Это решение кажется оптимальным и, более того, является равновесным.

Разумная мысль: равновесие Нэша

Фон Нейман и Моргенштерн, изучив игры с нулевой суммой для двух лиц, перешли к анализу игр с большим числом игроков, учитывая возможные альянсы (группы из двух игроков и более, которые действуют согласованно), то есть отошли от чисто конкурентных игр. В 50-е годы XX века именно Джон Нэш расширил теорию игр, включив в нее некооперативные игры для n игроков, где альянсы были запрещены. Нэш уделял особое внимание играм с ненулевой суммой для двух и более игроков и пришел к мысли о равновесии, которое теперь известно как равновесие Нэша.

Алгоритм Нэша (или по меньшей мере его суть) кажется простым. Допустим, что разные игроки проанализировали игру и каждый выбрал определенную стратегию. Зная результат игры, зададим каждому игроку вопрос: считает ли он результат удовлетворительным? Иначе говоря, предпочел бы он действовать иначе? Если ответ положителен, то есть все участники считают, что грамотно выбрали стратегию, то, согласно Нэшу, в игре достигнуто равновесие.

Рассмотрим применение этой идеи в конкретном случае. В следующей матрице приведены результаты игры с ненулевой суммой:

Оба игрока выбрали стратегию 2. Узнав результат, они остались довольны выбором и сочли, что сделали все возможное. Первый игрок (его стратегии указаны в строках) считает, что его выигрыш, 5, был максимально возможным. Второй игрок, узнав, что первый выбрал стратегию 2, также посчитал свой выбор оптимальным: он выиграл 2, а мог не выиграть ничего.

Эту ситуацию можно оспорить, сказав, что первый игрок сделал «правильный» выбор, потому что выбранная им стратегия (2) является доминантной, а второй игрок может решить, что стоило выбирать первую стратегию, так как в этом случае он мог выиграть 100. Однако в конкурентной игре, где каждый игрок хочет увеличить свой выигрыш, подобная ситуация невозможна, если игрок 1 будет действовать рационально.

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

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

Однако так происходит не всегда, и порой точка равновесия выглядит непривычно и имеет необычные свойства.

ДЖОН ФОРБС НЭШ (РОД. 1928)

Возможно, труды Нэша, особенно его первые работы, являются важнейшими после работ фон Неймана за всю короткую историю теории игр. Уже в детстве Нэш продемонстрировал выдающийся интеллект и в то же время обнаружил трудности в общении с другими людьми. Он начал изучать химию, но вскоре переключился на математику, где отличался особым талантом. В 1948 году он получил стипендию Принстонского университета, где в то время работали Эйнштейн и фон Нейман, для написания докторской диссертации по теории игр под руководством Альберта Такера. В 1950 году он представил свою диссертацию — краткую и оригинальную работу о некооперативных играх. Его труд быстро нашел широкое признание среди специалистов по теории игр. Нэш придумал настольную игру на поле с шестиугольными клетками, позднее получившую название «Геке». По-видимому, Нэш не знал, что несколькими годами ранее такую же игру придумал Пит Хейн. Нэш доказал, что в этой игре должна существовать выигрышная стратегия для первого игрока.

Начиная с 1950-х годов он работал в Массачусетском технологическом институте (MIT) и в корпорации RAND — знаменитой организации ВВС США, занимавшейся стратегическими исследованиями. Спустя некоторое время после свадьбы, в 1959 году, ему пришлось пройти курс лечения от шизофрении. Впоследствии болезнь усилилась и преследовала ученого в разные годы жизни. Несмотря на болезнь, он продолжал работать и в 1994 году получил Нобелевскую премию по экономике.

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

Дилемма заключенного и другие классические задачи теории игр

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

Меррил Флад, в свое время работавший в RAND, проанализировал различные ситуации из повседневной жизни, особенно те, в которых игрокам требовалось распределить между собой дополнительный выигрыш. Одна из таких ситуаций — продажа подержанного автомобиля. Допустим, покупатель готов купить машину у друга, который, в свою очередь, готов ее продать. Чтобы узнать стоимость машины, друзья отправляются в автомагазин, который согласен приобрести автомобиль за 1000 долларов и продать за 1300 долларов, получив минимум 300 долларов за свои услуги. Если продажа будет совершена без участия магазина, очевидно, что друзья сэкономят 300 долларов и смогут разделить эту сумму между собой. В этом случае наиболее рационально разделить эту сумму пополам, то есть продать машину за 1150 долларов. Таким образом, каждый из друзей получит по 150 долларов.

Это решение рационально, но не единственно. Один из игроков, например покупатель, может решить, что не готов платить больше 1100 долларов, то есть продавец получит 100 долларов в дополнение к установленной цене. И наоборот, продавец может установить минимальную цену в 1250 долларов, аргументируя это тем, что покупатель все равно сэкономит 50 долларов. Заметим, что если покупатель не примет предложение продавца, рационально рассудив, что выгода разделена «несправедливо», то повредит сам себе, потому что установленная цена все равно будет ниже цены магазина.

Однако мысль о «справедливом» распределении выгоды не всегда столь очевидна. Иногда может существовать несколько решений, которые будут казаться полностью обоснованными. Допустим, Михаил хочет отправиться из Барселоны в Мадрид (600 км) на машине, чтобы посетить важное совещание и вернуться на следующий день. Он узнает, что Петр, его друг, который живет в Сарагосе, тоже должен поехать в Мадрид в этот же день. Друзья решают вместе поехать на машине и туда, и обратно. Как нужно распределить расходы на поездку, учитывая, что Сарагоса расположена на полпути между Барселоной и Мадридом?

Вариант 1. Так как Михаил проедет в два раза больше, чем Петр, расходы нужно разделить на 3, Петр заплатит одну треть, Михаил — две трети.

Вариант 2. Так как Михаил проедет в одиночку половину пути, а другую половину друзья проедут вместе, то Михаил оплатит расходы за половину дороги плюс еще одну четверть, а оставшаяся четверть расходов (половина половины) придется на долю Петра. Получается, что расходы нужно разделить на 4, Петр оплатит одну четверть, Михаил — три четверти.

Чтобы подсчитать расходы на поездку, предположим, что поездка из Барселоны в Мадрид обойдется Михаилу в 600 евро (если он поедет один), а поездка из Сарагосы в Мадрид обойдется Петру в 300 евро. Если они поедут вместе, то сэкономят 300 евро. В первом варианте Михаил платит 400 евро (экономит 200), Петр платит 200 евро (экономит 100). Во втором варианте Михаил платит 450 евро (экономит 150), Петр платит 150 евро (также экономит 150). Получается, что во втором варианте выгода распределяется одинаково, а в первом распределение происходит пропорционально понесенным расходам. Таким образом, в конкретной ситуации может существовать несколько разумных и обоснованных решений.

Дилемма заключенного

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

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

Две противоборствующие стороны Р1 и Р2 должны определить политику в области вооружений. Каждая из сторон может независимо от другой выбрать одну из двух стратегий:

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

Б: сотрудничать, то есть разоружаться или наложить ограничение на некоторые виды оружия.

АЛЬБЕРТ УИЛЬЯМ ТАКЕР (1905-1995)

Такер внес важный вклад в топологию, нелинейное программирование и теорию игр. Он окончил Торонтский университет с дипломом по математике, затем защитил докторскую в Принстонском университете в 1932 году. Некоторое время он работал в Гарварде, Кембридже и Чикаго, затем вернулся в Принстон, где преподавал до 1970 года, свыше 20 лет возглавляя кафедру математики. В 1950 году он дал название самому известному и интересному парадоксу в теории игр — дилемме заключенного, а также впервые привел интерпретацию зтой задачи. Тем самым он внес фундаментальный вклад в модель соперничества и сотрудничества, над которой позднее работали Меррил Флад и Мелвин Дрешер в Принстонском университете.

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

Существует четыре возможных решения: (А, А), (А, Б), (Б, А) и (Б, Б). Первая координата в каждой паре — стратегия Р1, вторая — стратегия Р2. Возможные исходы можно представить таблицей:

Пересечениям возможных стратегий можно присвоить значения (в терминах теории игр — платежи), учитывая, что для каждого игрока они будут отличаться и в каждой ячейке будет два числа: одно означает выгоду Р1, второе — выгоду Р2. Получим следующую платежную матрицу:

Если понимать эти числа как выигрыши, то дилемма очевидна. Что нужно делать Р1? Для любого из вариантов, доступных Р2, для Р1 будет выгоднее вооружаться. Если Р2 выберет вариант А, Р1 выиграет 2 в случае вооружения и 0 в противном случае. Если Р2 выберет вариант Б, Р1 выиграет 5, если будет вооружаться, и 4 в противном случае. Так как матрица симметричная, для Р2 можно привести аналогичные рассуждения. Для любой из двух стратегий Р1 наибольший выигрыш Р2 принесет выбор в пользу вооружения. Говорят, что решение (А, А), означающее, что обе стороны вооружаются и получают выгоду в 2, является равновесным некооперативным решением, к которому стремятся обе стороны.

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

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

Хотя дилемма заключенного является частью теории игр, проблема, лежащая в основе этой задачи, рассматривалась задолго до появления этой теории. Английский философ Томас Гоббс (1588—1679), автор «Левиафана», рассуждая об абсолютизме, анализирует развитие общества и рассматривает проблему, схожую с дилеммой заключенного. Гоббс писал, что изначально общество пребывает в анархии, где есть место только конкуренции. Чтобы сотрудничество стало возможным, нужно наложить ограничения и обеспечить их выполнение. Гоббс рассматривал общественный договор как результат сотрудничества и полагал, что общество должно подчиниться правительству, так как независимые решения, предполагающие сотрудничество или соперничество, не должны приниматься отдельными людьми.

Ситуации, напоминающие дилемму заключенного, также можно встретить в деловом мире. На конкурентном рынке часто случается, что конкуренты отвергают практический подход, будучи убежденными, что со временем подобное поведение окажется выгодным для всех, в том числе и для них самих. Так, соглашение книжных магазинов не предоставлять скидок выше определенного процента (например, 10%) или решение профсоюза закрывать магазины в определенный час (например, в 20:00) направлены на рост продаж. Все участники знают, что, если хотя бы один из них не выполнит соглашение, его нарушат и остальные и никто не получит выгоды; напротив, расходы лишь возрастут.

РОБЕРТ АКСЕЛЬРОД И ПОВТОРЕНИЕ ДИЛЕММЫ ЗАКЛЮЧЕННОГО

Роберт Аксельрод, преподаватель политологии в университете Мичигана, математик и доктор политических наук, является экспертом в кооперативных задачах и специалистом по играм, подобным дилемме заключенного. Среди его трудов выделяется «Эволюция сотрудничества» (The Evolution of Cooperation), где изучается развитие сотрудничества как явления. Основная мысль книги такова: стратегии, используемые людьми, эволюционируют в сторону более эффективных, где обязательным элементом является сотрудничество. Говоря о дилемме заключенного, Аксельрод замечает, что если игра проводится один раз, то нельзя узнать поведение соперника, наградить его за сотрудничество или наказать за соперничество, поэтому нужно думать о краткосрочных результатах. Напротив, если игра повторяется несколько раз, то стратегии могут основываться на предыдущих взаимодействиях и их основным принципом будет взаимность: если противник часто сотрудничал с нами, будет лучше, если мы тоже продолжим сотрудничество, но если попыток сотрудничества не было, то нам не стоит и пытаться этого делать. Так как никому не удавалось определить оптимальную стратегию, Аксельрод организовал турнир между экспертами по теории игр, чтобы изучить, как они будут действовать и как будут пытаться скрыть действенные стратегии. В результате оказалось, что лучшей из всех стратегий оказалась простейшая, так называемая «око за око». Нужно начинать с сотрудничества (и никогда не отказываться от него первым), а затем повторять стратегию, выбранную соперником на прошлом ходу. Если противник сотрудничал с нами, стоит продолжать сотрудничество, но если он отказался это сделать, то нужно сразу выразить несогласие с этим.

Игра «Струсил — проиграл»

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

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

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

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

3. Один из игроков решает свернуть, другой — нет. Первый «теряет престиж» и получает всего 1 очко, второй считается победителем и ему присуждается 5 очков.

Представим эти стратегии и платежи в виде матрицы:

ИГРА «СТРУСИЛ — ПРОИГРАЛ»

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

Эта игра чаще встречается в кино, например в фильме Николаса Рэя «Бунтовщик без причины» (Rebel without A Cause, 1955), где подростки мчатся на машинах к обрыву и тот, кто затормозит первым, — проиграл, «цыпленок».

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

Анализ ситуации показывает, что если оба участника хотят достичь максимального выигрыша в 5 очков, то есть не сворачивать, то оба получат наихудший результат. Кажется, что будет лучше свернуть в сторону. В этом случае оба получат хороший результат, но никто не хочет сворачивать первым, так как получит всего 1 очко, а соперник — 5.

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

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

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

Сотрудничать или умереть. Игра «Ястребы и голуби»

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

Ранее считалось, что принятие решений — прерогатива толькоразумно мыслящих существ и, следовательно, о теории игр можно говорить только в связи с человеческой деятельностью. Однако Джон Мейнард Смит в 1978 году показал, что теория игр также применима к некоторым видам животных, которые выбирают коллективные стратегии поведения, чтобы поддерживать и улучшать развитие. Это пример не индивидуального, а коллективного поведения, которое может повлиять на биологический вид в целом. Борьбу вида за выживание можно рассматривать как соперничество, в рамках которого определенные действия отдельных особей могут привести к вымиранию остальных. Аналогично «альтруизм» отдельных особей может оказаться для них смертельным, но принесет выгоду для вида в целом.

Джон Мейнард Смит сформулировал дилемму ястребов и голубей, которую можно считать вариантом игры «Струсил — проиграл». Когда два животных сражаются за добычу, как правило, оба действуют агрессивно и пытаются нанести увечья противнику. Когда схватка вот-вот начнется, возможны два варианта: отступить, потеряв добычу, но сохранив жизнь (так поступают голуби), либо драться до победы и, возможно, потерять жизнь (так действуют ястребы).

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

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

Платежи были определены по следующему принципу: достижение цели (добычи или самки) оценивается в 10 очков, увечья приносят -20 очков. В схватке между ястребами выигрыши и проигрыши чередуются, в среднем каждый из участников получает -5 очков. В схватке ястреба с голубем победителем всегда выходит ястреб (10 очков), голубь отступает (0 очков). В схватке двух голубей пострадавших нет, но голуби тратят время и подвержены ненужному риску, поэтому Смит оценил эту ситуацию в -3 очка. В схватке между голубями победитель получает 10 - 3 = 7 очков, проигравший получает -3 очка, поэтому в среднем каждый получает 2 очка.

ДЖОН МЕЙНАРД СМИТ (1920-2004)

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

Он учился в знаменитом Итонском колледже, затем изучал инженерное дело в Тринити-колледже Кембриджского университета. С юных лет он был членом коммунистической партии, но покинул ее в 1956 году после советского вторжения в Венгрию. Он достаточно быстро сменил сферу научной деятельности и занялся генетикой в Университетском колледже Лондона. Там же он преподавал зоологию и в 1958 году опубликовал научно-популярную книгу «Теория эволюции», ставшую чрезвычайно известной. С 1962 года работал в университете Суссекса, одним из основателей которого он являлся. В 1973 году внес свой основной вклад в теорию игр, сформировав концепцию эволюционно стабильной стратегии. Кульминацией его исследований в этой области стала книга «Эволюция и теория игр», вышедшая в 1982 году, в которой он описывает известную игру «Ястребы и голуби». В 1977 году был избран членом Лондонского королевского общества. В 1986 году получил медаль Дарвина. Европейское общество эволюционной биологии учредило премию для молодых исследователей, носящую его имя.

На основе этой игры Смит ввел понятие эволюционно стабильной стратегии, подавляющей любую возникающую мутацию. Смит показал, что популяция, состоящая только из голубей, равно как и только из ястребов, не является эволюционно стабильной. Смит отметил, что в соответствии с платежной матрицей игры в эволюционно стабильной популяции доля ястребов составит 8/13, доля голубей — 5/13. Иными словами, при таком соотношении популяция будет защищена от резкого роста численности ястребов или голубей. Правильность этого утверждения можно подтвердить, но применить его на практике несколько сложнее. Можно считать, что 8/13 популяции несут в себе ген ястреба, который определяет соответствующее поведение.

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

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

Об играх для более чем двух игроков

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

Игры для n игроков

Чтобы объяснить основные понятия, введенные фон Нейманом и Моргенштерном для подобных игр, и уяснить предложенное ими решение, рассмотрим упрощенный пример из экономики. Три компании А, Б и В имеют равную стоимость в 1 евро. Любая компания может образовать альянс с другой. При образовании альянса его стоимость увеличивается на 9 евро. Стоимость альянса двух компаний — 11 евро, трех компаний — 12 евро. Допустим, что все три компании равноценны во всех смыслах. Какой альянс будет выгоднее и как нужно будет распределить полученную выгоду?

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

Проанализируем задачу. Без образования альянсов каждая компания остается в начальных условиях и стоимость каждой по-прежнему равна 1 евро. Если три компании образуют альянс (общая стоимость 12 евро), то, учитывая симметричность ситуации, равномерным распределением выгоды, которое устроит всех участников, будет передача каждой компании 4 евро. Это обозначается тройкой (4, 4, 4). Возможно распределить выгоду и по-другому, но сумма платежей всегда будет равна 12 евро. Если альянс образуют две компании, например Б и В, третья (А) получает всего 1 евро, другие две — в сумме 11 евро. Одно из возможных распределений выгоды — (1; 5,5; 5,5).Так как в этом случае выгода двух компаний выше, чем в предыдущем, этот вариант кажется более вероятным.

Однако решение (1; 5,5; 5,5), которое кажется наиболее вероятным, нестабильно, так как компания А, не вступившая в альянс, может сделать предложение, например, компании Б, и обе получат выгоду, например (5, 6, 1). Теперь может вмешаться компания Б, которая предложит компании А уменьшить ее платеж в рамках альянса. С новым предложением также может выступить компания В. Это может происходить бесконечно. Сложно найти какое-то справедливое распределение, которое можно было бы считать решением игры.

Анализ игры для n игроков, проведенный фон Нейманом и Моргенштерном, показывает, что единственного оптимального решения не существует. Однако из анализа видно, что не всякое распределение может являться частью решения, поэтому нужно определить множество распределений, которые составят решение игры.

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

Определив нужные понятия, мы можем сформулировать требования к множеству распределений, составляющих решение. Таких условий два.

1. Ни над каким распределением платежей, являющимся частью решения, не может доминировать другое распределение, которое также является частью этого решения.

2. Над любым распределением, которое не является частью решения, должно доминировать распределение, являющееся частью решения.

Фон Нейман и Моргенштерн считают, что при этих условиях предложенное решение, во-первых, не содержит внутренних противоречий, во-вторых, соответствует социально приемлемому поведению. Описанный метод можно применять с некоторыми ограничениями: так, игроки в любой момент времени должны одновременно и свободно обмениваться информацией.

Кооперативные игры, альянсы и распределения

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

Пример 1

Три предпринимателя, Анна (А), Борис (Б) и Василий (В), заключили удачную сделку, и им нужно распределить полученную прибыль — 200000 евро. Они решают разделить деньги простым большинством: каждая персона имеет один голос, никаких других ограничений не накладывается. Существует четыре возможных коалиции, которые могут получить большинство: АБВ, АБ, АВ и БВ. Однако внутри каждой коалиции прибыль может быть распределена множеством способов.

Анна предлагает разделить деньги так: А = 68 000 евро, Б = 66 000 евро, В = 66 000 евро. Борис предлагает по-другому: А = 60 000 евро, Б = 70 000 евро, В = 70 000 евро. Этот вариант больше устраивает и Бориса, и Василия, который предлагает третий вариант: А = 70 000 евро, Б = 0 и В = 130000 евро. Этот вариант выгоднее не только для Василия, но и для Анны. Как и в примере из прошлого раздела, игроки могут выдвигать новые предложения снова и снова, и непохоже, чтобы существовала коалиция, выгодная для всех троих. Точки равновесия не существует, поскольку для любого предложения может последовать новое, которое будет более выгодным для каждого игрока в новой коалиции.

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

Пример 2

Допустим, что в прошлом примере предприниматели решили разделить прибыль согласно сделанным вложениям. Таким образом, Анна имеет 5 голосов, Борис — 3, Василий — 1 голос. Теперь большинство могут получить следующие коалиции: АБВ, АБ, АВ, А.

Анна имеет большинство, поэтому она может присвоить все деньги себе: А = 200000 евро, Б = 0 и В = 0. Распределение будет несправедливым, но стабильным. Анна согласна с таким решением, а образовать альянс без нее невозможно. Следовательно, приведенное решение удовлетворяет всем необходимым условиям, которые мы определили выше.

В подобных играх ценой игры называется платеж, который гарантирован каждому игроку, если тот будет действовать рационально, и не зависит от решений остальных участников. В примере 1 никому из них не гарантирована какая-либо сумма. Следовательно, ценой игры будет А = 0, Б = 0 и В = 0. Напротив, во втором примере ценой игры будет А = 200 000, Б = 0 и В = 0.

Пример 3

Усложним ситуацию еще больше, чтобы сделать ее более реальной. По результатам выборов 81 кресло в парламенте было распределено между пятью партиями следующим образом: А = 33, Б = 24, В = 15, Г = 6, Д = 3. Ни одна из партий не имеет абсолютного большинства (41 кресло), и для формирования правительства необходимо образовать коалицию. Эта коалиция займется распределением бюджетов и установит нужные обязанности. Партии имеют схожую идеологию, и предполагается, что мера ответственности определяется подконтрольным бюджетом. Кроме того, предполагается, что никто не будет нарушать процедуру голосования.

Из всех возможных альянсов (1 из пяти партий, 5 из четырех, 10 из трех, 10 из двух и 5 из одной) нам важны лишь 16 (они будут иметь минимум 41 кресло в парламенте). Так как ни одна партия не имеет большинства, цена игры для каждой партии равна 0, так как ни одна из партий не должна обязательно входить в состав коалиции, которая сформирует новое правительство.

ЛЛОЙД СТАУЭЛЛ ШЕПЛИ (РОД. 1923)

Этот американский математик и экономист внес фундаментальный вклад в теорию игр. Он изучал математику в Гарвардском университете, откуда выпустился в 1948 году после службы в армии и участия во Второй мировой войне в звании сержанта. Затем он в течение года работал в корпорации RAND и в 1953 году получил степень доктора в Принстонском университете, где в то время работали создатели теории игр. Затем он вернулся в RAND, где проработал до 1981 года, после чего занял должность профессора в Калифорнийском университете (UCLA). Уже в своей докторской диссертации он ввел некоторые значимые понятия теории игр, например вектор Шепли. На протяжении всей своей долгой научной деятельности он публиковал и продолжает публиковать исследования по этой тематике. Является членом Национальной академии наук США с 1979 года. Лауреат множества премий, среди которых премия фон Неймана (1981).

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

В нашем примере в альянсе, образованном всеми пятью партиями, ни одна из них не играет определяющую роль. Например, в коалиции БВГД партии Б и В играют определяющую роль: без их участия коалиция не наберет большинство (без партии Б коалиция будет иметь лишь 24 места, без партии В — 33). Напротив, Г и Д не играют определяющей роли: если одна из этих партий покинет коалицию, та сохранит большинство (без партии Г коалиции будет принадлежать 42 кресла, без партии Д — 45). Число коалиций, в которых определяющую роль играют те или иные партии, представлено в таблице ниже

Теперь мы можем распределить бюджет согласно модели Шепли. Допустим, что коалиция образована всеми партиями, и в их распоряжении находится бюджет в размере 2,6 млрд евро. Распределение по модели Шепли (в миллионах евро) выглядит так:

А = 1000,

Б = 600,

В = 600,

Г = 200,

Д = 200.

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

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

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

Библиография

Comas, О., El mundo en juegos, Barcelona, RBA, 2005.

Corbalan, F., Juegos matematicos para secundaria у bachillerato, Segunda edition, Madrid, Sfntesis, 1998.

Davis, M.D., Introduction a la teoria de juegos, Col. Ensayo, Madrid, Alianza, 1998. DEULOFEU, J., Una recreation matematica: historias, juegos у problemas, Barcelona, Planeta, 2001.

—: Gimnasia mental 2, Madrid, Martinez Roca, 2003.

Gardner, M., Matematicas para divertirset Barcelona, RBA, 2007.

Lucas, E., Recreaciones matematicas, 4 vols, Madrid, Nivola, 2007-2008.

Mlllan, A., GlORGIO, I., El mundo сото un juego matematico. John von Neumann un tientifico del siglo XX, Madrid, Nivola, 2001.

Packel, E., Las matematicas de los juegos de apuestas, Col. La Tortuga de Aquiles 5, Madrid, DLS-EULER, 1995.

Poundstone, W., El dilema del prisionero. John von Neumann, la teoria de juegos у la bomba, Coleccion Ciencia у Tecnica, Madrid, Alianza, 2005.

Steen, L.A. у otros, Las matematicas en la vida cotidiana, Madrid, Addison-Wesley/ Universidad Autonoma de Madrid, 2006.

Оглавление

Предисловие

Глава 1. История взаимоотношений игр и математики

  Математика занимательная и серьезная, чистая и прикладная

  Игры и математика до XVII века

    Игры и математика в Античности

    Игры и математика в Средневековье

    Игры и математика в эпоху Возрождения

  Игры и математика с XVII века до наших дней

    Золотой век математических игр: XVII и XVIII века

    Игры и занимательная математика в XIX и XX веках

  Появление теории игр

Глава 2. Стратегические игры и решение задач

  Понятие выигрышной стратегии

  Использование преимуществ и определение стратегий. Игра Ним и ей подобные

    Об определении стратегии

      Игра 1: выигрывает первый

      Игра 2: выигрывает второй

      Игра 3: общий случай

    Сложная стратегия: игра Ним

      Игра 4: первая версия игры Ним

      Игра 5: Мариенбад

    Цели и правила игры: эквивалентные и отличающиеся игры

      Игра 6: продвижение по шестиугольным клеткам

      Игра 7: поставь последнюю фишку

      Игра 8: цзяньшицзы

      Игра 9: спасти ферзя

      Игра 10: маргаритка

    Игры и псевдоигры

      Игра 11: только нечетные

      Игра 12: круги и квадраты

Глава 3. Игры и азарт

  Шевалье, который не хотел проигрывать. Азартные игры и появление вероятностей

  Укрощение случайности. Математическое изучение вероятностей

  Вопросы вычисления. Важен ли порядок?

    Задача 1: победители забега

    Задача 2: играем в бридж

    Задача 3: раздача карт

    Задача 4: серия пенальти

  Номера лотерейных билетов и другие ошибочные предположения о случайности

    Капризы вероятностей

      Игра в кегли

      Обычный кубик

      Какова вероятность выигрыша?

      Спорная жеребьевка

      Не слишком интересное пари

      Парадокс дней рождения

    Случайность не имеет памяти

      Бросаем монету

      Телеконкурс

  Математика и ожидание

    Игра с тремя кубиками

    Ожидаемый платеж

  Можно ли обыграть банк? Вероятность повторяющихся событий

Глава 4. Математическая теория игр

  Начала теории игр

  Когда достигается равновесие?

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

    Выборы и рестораны: применение игр с чистыми стратегиями

      Предвыборные программы

      Задача о ресторане

  Когда равновесия не существует: смешанные стратегии

    Определение оптимальной смешанной стратегии

    Применение смешанных стратегий

      Рост компании

      Серия пенальти

  Преимущества и ограничения метода минимакса

Глава 5. Что наша жизнь? — Игра! Применения теории в реальном мире

  Математика сотрудничества: игры с ненулевой суммой

  Разумная мысль: равновесие Нэша

  Дилемма заключенного и другие классические задачи теории игр

    Дилемма заключенного

    Игра «Струсил — проиграл»

    Сотрудничать или умереть. Игра «Ястребы и голуби»

  Об играх для более чем двух игроков

    Игры для n игроков

    Кооперативные игры, альянсы и распределения

      Пример 1

      Пример 2

      Пример 3

Библиография