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

Предисловие

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

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

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

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

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

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

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

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

Последние две главы представляют собой введение в теорию игр — раздел математики, созданный Джоном фон Нейманом в середине 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 («Моя жизнь»). В отличие от многих современников, Кардано добился определенной известности, особенно как врач. Будучи настоящим представителем эпохи Возрождения, он интересовался многими науками, пытаясь охватить все знания, известные в то время. Однако весьма часто ему не удавалось избавиться от наивного, иррационального взгляда на вещи, а порой и предрассудков, что сделало его крайне противоречивой фигурой. ...