К сожалению, планам противника не суждено сбыться: робот легко может избежать ловушек, ответив сначала ходом на клетку 9, а затем на клетку 5. Может оказаться, что на практике при такой довольно безрассудной игре машина будет одерживать победу чаще, чем при спокойной тактике, почти заведомо приводящей к ничьей.
Истинный мастер игры в крестики и нолики, будь то человек или робот, должен не только знать наиболее вероятные ответные ходы неопытного игрока (их нетрудно установить, собрав статистические данные об уже сыгранных партиях), но и уметь анализировать стиль игры своего партнера, чтобы определить, какие ошибки тот склонен совершать особенно часто. Следует учесть и то обстоятельство, что новичок от партии к партии совершенствует свое мастерство, но здесь «простая» игра в крестики и нолики заставляет нас погрузиться в дебри весьма нетривиальных проблем теории вероятностей и психологии.
Английское название игры в крестики и нолики — тик-так-тоу — пишется и произносится по-разному. Согласно «Оксфордскому слословарю стихов Матушки-гусыни»[11] название тик-так-тоу происходит от старинной английской детской считалочки:
Я знаю многих любителей крестиков и ноликов, которые ошибочно полагают, что самое главное — это научиться неизменно выигрывать, и считают, что они уже постигли все тайны этой игры.
Истинный же мастер игры в крестики и нолики должен уметь использовать малейшее преимущество, возникающее даже в тяжелых для него ситуациях. Следующие три примера помогут читателю уяснить сказанное. Первый ход во всех трех партиях делается на одну из клеток 2, 6, 8, и 4.
Если вы начинаете с хода X8, а противник отвечает вам ходом О2, то вторым ходом вам лучше всего пойти на четвертую клетку (Х4). Этот ход приводит к выигрышу в четырех из шести возможных ответных ходов противника. Помешать вам выиграть противник может лишь ходом О7 или О9. Если противник сначала пошел Х8, а вы ответным ходом заняли одну из нижних угловых клеток, например О9, то вы еще можете надеяться на победу: противнику достаточно совершить любой из ходов Х2, Х4 или Х7.
Если противник делает первый ход Х8, то ответный ход О5 может привести к интересному развитию партии: если противник вторым ходом занимает клетку 2 (Х2), то вы можете даже позволить ему выбрать за вас ту клетку, которую вы займете при следующем ходе. При любом вашем ходе выигрыш вам обеспечен!
Рассказывая о разновидности игры в крестики и нолики, любимой древними римлянами, в которой фишки разрешалось передвигать с клетки на клетку, мы упоминали о том, что игрок, заняв центр доски, всегда выиграет. Для тех читателей, кого это интересует, приводим примерный ход двух партий в древнеримские крестики и нолики.
Обе партии гарантируют первому игроку выигрыш независимо от того, разрешается ли передвигать фишки по двум главным диагоналям или нет. Если фишки можно передвигать и по малым, побочным, диагоналям, следует придерживаться только второй партии.
Глава 5. ПАРАДОКСЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ
Теория вероятностей представляет собой область математики, необычайно богатую парадоксами — истинами, настолько противоречащими здравому смыслу, что поверить в них трудно даже после того, как правильность их подтверждена доказательством. Прекрасный пример этому — парадокс с днями рождения. Выберем наугад 24 человека. Какова, по вашему мнению, вероятность того, что двое или большее число из них родились в один и тот же день одного и того же месяца (но, быть может, в разные годы)? Интуитивно чувствуется, что вероятность такого события должна быть очень мала. На самом же деле она оказывается равной 27/50, то есть чуть выше 50 %!
Вероятность того, что дни рождения любых двух людей не совпадают, очевидно, равна 364/365 (поскольку лишь в одном случае из 365 возможных дни рождения совпадают). Вероятность несовпадения дня рождения третьего человека с днем рождения любых двух других членов отобранной группы составляет 363/365. Для четвертого человека вероятность того, что его день рождения отличается от дней рождения любых трех людей, равна 362/365 и т. д. Дойдя до двадцать четвертого участника эксперимента, мы увидим, что вероятность несовпадения его дня рождения с днями рождения остальных двадцати трех участников равна 342/365/ Таким образом, мы получаем набор из 23 дробей. Перемножив их, мы найдем вероятность того, что все 24 дня рождения различны. Сократив числитель и знаменатель произведения двадцати четырех дробей, мы получим дробь 23/50, Иначе говоря, заключая пари на то, что среди 24 по крайней мере двое родились в один и тот же день, вы будете выигрывать в 27 и проигрывать в 23 случаях из 50. (Проведенный нами подсчет вероятности не совсем точен, он не учитывает того, что год может быть високосным — то есть в феврале может быть 29 дней — и что дни рождения чаще приходятся на одни месяцы и реже на другие.
Первое обстоятельство уменьшает вероятность интересующего нас события, второе — увеличивает.)
Приведенные цифры настолько неожиданны, что экспериментальная проверка их в классе или среди сослуживцев может явиться отличным развлечением. Если присутствует более 23 человек, попросите каждого написать на листке бумаги его день рождения.
Соберите и сложите листки. Скорее всего по крайней мере две даты совпадут, что обычно вызывает невероятное удивление даже у людей, знакомых друг с другом в течение многих лет. Результат не изменится, если кто-нибудь схитрит, написав неправильную дату.
Вероятность совпадения остается и в этом случае.
Еще проще проверить парадокс, выбирая случайным образом даты рождения 24-х людей из книги «Кто есть кто» или какого-нибудь другого биографического справочника. Естественно, что чем большее число имен превышает 24, тем больше вероятность совпадения. На рис. 21 изображена кривая, показывающая рост вероятности с увеличением числа людей.
Рис. 21
График обрывается, когда число людей достигает 60, потому что дальше вероятность уже слишком близка к достоверности (то есть к значению 1) и кривую практически невозможно отличить от прямой. В действительности даже для 23-х людей вероятность совпадения по крайней мере одного дня рождения превышает 1/2 и равна 0,507… Обратите внимание, как круто поднимается кривая примерно до числа 40 и как она выходит на плато по мере приближения к достоверности. Взяв 100 человек, вы сможете заключить пари, выигрывая в 3 299 000 случаях из 3 300 000. Конечно, абсолютная достоверность достигается лишь тогда, когда взято 366 человек.
Прекрасной иллюстрацией парадокса могут служить даты рождения и смерти 33 президентов Соединенных Штатов. В каждом случае вероятность совпадения (33 даты рождения, 30 дат смерти) близка к 75 %. И действительно, Полк и Хардинг родились 2 ноября, а три президента — Джефферсон, Адаме и Монро — умерли 4 июля.
Может быть, еще более удивителен парадокс со вторым тузом.
Представьте себе, что вы играете в бридж. Сдав колоду и посмотрев на свои карты, вы говорите: «У меня туз». Можно точно вычислить вероятность того, что у вас на руках окажется и второй туз. Можно доказать, что она равна 5359/14498, то есть меньше 1/2. Допустим теперь, что мы выбрали, например, туза пик. Будем продолжать игру до тех пор, пока, взяв карты, вы не сможете сказать: «Туз пик у меня». Вероятность того, что у вас найдется еще один туз, составляет теперь 11686/20825, то есть немногим больше 1/2! Почему изменяется вероятность, если вы заранее называете масть выбранного туза?
11
Oxford Dictionary of Mother Goose Rhymes. — 1951, p. 406.
Сборники «Стихи Матушки-гусыни» соответствуют издаваемым у нас сборникам прибауток. Некоторые из «Стихов Матушки-гусыни» были переведены на русский язык С. Я. Маршаком и вышли в сборнике «Английские народные песенки».
12