Материал из Linuxformat.

PHP. Загадка Монти Холла

У вас возникли сложности с загадкой из последнего выпуска LXF? Пол Хадсон (Paul Hudson) покажет вам, как решать такие задачи методом грубой силы, с помощью разума и команды тренированных коз.

Все, кто когда-либо изучал высшую математику, за редким исключением, относятся к числам с большим уважением. Посмотрите, с какой нежностью мы даём названия отдельным классам чисел, выражая своё восхищение их магией! Гармонические числа, совершенные числа, полусовершенные числа, гиперсовершенные числа, дружественные числа, и даже, верите или нет, сверхъестественные числа. Мы любим их за предсказуемость, неизменность и точность. Это даёт уверенность в их логичности, позволяет стоить сложные доказательства и делать с ними почти всё что угодно, кроме оплаты счёта в ресторане.

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

Возьмём, к примеру, загадку Монти Холла. Этот относительно простой вопрос приводит многих людей в ужас до тех пор, пока они не примут магию чисел. Загадка носит имя Монти Холла (Monty Hall), ведущего старого американского игрового шоу под названием «Давайте заключим сделку» (Let’s make a Deal), в котором в том или ином виде эта ситуация повторялась каждый раз. Сама загадка звучит так: вы участвуете в игре, и ведущий предлагает вам выбрать одну из трёх дверей. За одной из них дорогая машина, главный приз! За другими двумя дверями находятся козы. После того, как вы выбрали дверь случайным образом, ведущий (который, конечно, знает, за какой дверью приз) открывает одну из оставшихся дверей, за который обнаруживается коза. Затем он предлагает вам или остаться у прежней двери, или изменить свой выбор и указать на другую, оставшуюся закрытой. Итак, вы смените дверь или останетесь на месте?

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

Ломаем голову

Перед тем, как писать какой-либо код, важно понять почему загадка Монти Холла причиняет людям такие страдания. Для начала определим несколько моментов, чтобы не ввести никого в заблуждение. Победой мы будем называть выбор двери, за которой находится машина. Поражение – выбор двери с козой. Двери будем различать по номерам: 1, 2 и 3. Ведущий – это ведущий игрового шоу, а игрок – это участник игры. Уф! Теперь можно приступить к анализу проблемы. В игре вы должны вначале выбрать дверь, и поскольку дверей три и возможность мошенничества мы не рассматриваем, вероятность угадать с первого раза равна одной трети.

Предположим, вы выбрали дверь номер 1. Существует один шанс из трёх (то есть 1/3), что за этой дверью находится приз. Ведущий точно знает, где машина, и он открывает дверь номер 2, чтобы показать козу. При этом двери номер 1 и номер 3 остаются закрытыми. И вот тут большинство людей совершает ошибку, так как они думают, что шансы найти машину за 1 и 3 дверями равные. «В конце концов, - объясняют они,-есть две двери на выбор, мошенничество мы не учитываем, значит мы можем следовать первому закону теории вероятностей, так как это та же самая задачка, какая была при трёх закрытых дверях».

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

1-3 - это двери,
A-C - это возможности

Итак, теперь когда ведущий открывает одну из оставшихся дверей (в нашем примере он открыл дверь номер 2), вероятность найти машину за одной из оставшихся дверей по прежнему равна 2/3, однако вы теперь точно знаете, за которой из этих дверей находится коза! А это значит, что теперь вероятность найти машину за дверью номер 3 равна 2/3, тогда как у 1 двери остались прежние шансы 1/3. Итак, измените вы свой выбор или будете стоять на своём? Конечно, измените!

Диаграмма в правом нижнем углу наглядно демонстрирует ситуацию. Если вы выбрали третью дверь, существует три различных варианта развития событий. В случае A дверь номер 3 содержит козу, и ведущий откроет дверь номер два. Если мы останемся с дверью номер 3, то проиграем, а изменение выбора (на дверь номер 1) сулит выигрыш. В случае B за третьей дверью снова коза, а ведущий откроет дверь номер 1. Значит, останутся закрытыми третья дверь (наш выбор) и дверь номер 2. Если мы останемся с дверью номер 3, то проиграем, а победа нам достанется при изменении решения. Итак, и в случаях A и B для победы нам нужно изменить своё решение, в случае C при изменении своего выбора мы проиграем. Таким образом, вероятность выигрыша в случае изменения решения равна 2/3, тогда как настойчивость сулит победу только в 1/3 ситуаций.

Ломаем код

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

В терминах программирования нам потребуются три функции: Функция для запуска загадки Монти Холла, нечто для анализа полученных от пользователя данных, многократного запуска функции, а затем — печати результатов и небольшой HTML-код, позволяющий указать, какой тест нужно запустить. Всего у нас получится порядка сотни строк кода, но мы будем писать его по частям и начнём с самого лёгкого — с HTML.

<form method="post">
<p>Число итераций: <select name="iterations">
<?php
  /// Сгенерируем все варианты автоматически
  for ($i = 50; $i <= 10000; $i += 50) {
    if (isset($_POST['iterations']) && ($_POST['iterations'] == $i)) {
      print "<option value=\"$i\" selected>$i</option>";
  } else {
      print "<option value=\"$i\">$i</option>";
  }
}
?>
</select></p>
<!--Тут мы выберем "Нет", если давали этот ответ раньше-->
<p>Нужно ли изменять выбранную дверь?
<select name="DoSwitch">
<option value="Yes">Да</option>
<option value="No" <?php
  if (isset($_POST['DoSwitch']) && ($_POST['DoSwitch'] == "No"))
    print "selected";
?>>Нет</option></select></p>
<p><input type="submit" value="Докажите!" /></p>
</form>

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

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

if (isset($_POST['DoSwitch'])) {
  /// запускаем этот код, только если форма была заполнена
  $wins = 0;
  $losses = 0;
  /// Многократный вызов функции
  /// Она возвращает "Win" (победа) или "Lose" (поражение)
  for ($i = 0; $i < $_POST['iterations']; ++$i) {
    $result = MontyHall($_POST['DoSwitch']);
    /// Сохраняем результат
    if ($result == "Win") {
      ++$wins;
    } else {
      ++$losses;
    }
  }
  /// Печать результатов
  print "<h1>Потрясающее устройство для экспериментального решения загадки Монти Холла</h1>";
  print "<p>Число итераций: {$_POST['iterations']}</p>";
  print "<p>Игрок изменял выбор?: {$_POST['DoSwitch']}</p>";
  print "<p>Число побед: $wins</p>";
  print "<p>Число поражений: $losses</p>";
}

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

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

function MontyHall($DoSwitch) {
  /// Создадим массив дверей и перемешаем в случайном порядке
  $doors = array(1=>"Goat", 2=>"Goat", 3=>"Car");
  shuffle($doors);
  /// выберем дверь и удалим её из массива
  $our_choice = array_rand($doors);
  $our_door = $doors[$our_choice];
  unset($doors[$our_choice]);
  /// а теперь "откроем" дверь
  /// Берём первую из оставшихся дверей и проверяем, там ли коза
  if (reset($doors) == "Goat") {
    // Первая же дверь из оставшихся содержит козу,
    // удалим её из списка доступных!
    // получаем ключ текущей позиции
    $cur_key = key($doors);
    unset($doors[$cur_key]);
  } else { // первая дверь не содержит козу, так что удалим вторую
    next($doors);
    $cur_key = key($doors);
    unset($doors[$cur_key]);
  }
  /// Должен ли игрок изменить выбор?
  if ($DoSwitch == "Yes") {
    /// Да, должен. Есть ли машина за оставшейся дверью?
    if (reset($doors) == "Car") {
      // Да - мы выиграли!
      return "Win";
    } else {
      // коза :(
      return "Lose";
    }
  } else {
    // игрок не должен изменять решение
    if ($our_door == "Car") {
      // мы с первого раза выбрали верную дверь
      return "Win";
    } else {
      // опять коза! :(
      return "Lose";
    }
  }
}

И снова я написал очень подробные комментарии и даже использовал понятные имена переменных, так что вам нет прощения, если вы этого не поймёте! Единственная вещь, которая может остаться неясной — это работа с массивом $doors. В коде используются вызовы не слишком часто используемых функций reset(), next() и keys(). Первая из них устанавливает внутренний указатель массива (определяющий, какая позиция является текущей) на первый элемент и возвращает его значение. Так что строка if (reset($doors) == «Goat») значит перейти к первому элементу массива $doors, получить его значение, и если оно равно «Goat»(коза), то условие истинно. Затем мы используем функцию key(), которая возвращает ключевое значение для текущего элемента массива (то есть для первого, так как мы вызвали reset()). После чего полученное значение мы используем для удаления этого элемента из массива. Это выглядит как странный трюк, но помните, у нас нет другого способа узнать индекс первого элемента, так как мы по сути не знаем, который элемент подлежит удалению. Если значение первого элемента не равно «Goat», то мы удалим второй, перейдя к нему с помощью функции next() (она просто перемещает указатель массива на одну позицию вперёд).

Начало и конец

Итак, у нас осталась одна дверь в переменной $our_door и одна дверь в массиве $doors. Финальный вопрос — стоит ли игроку изменить свой выбор. Конечно, мы получили ответ на него в качестве аргумента функции, так что мы просто проверяем его и действуем соответствующим образом. Если мы должны переменить дверь, то мы возвращаем «Win», когда в последнем элементе $doors содержится слово «Car» (машина), в противном случае возвращаем «Lose». Если же игрок должен стоять на своём, то «Win» или «Lose» определяется содержимым переменной $our_door («Car» или «Goat» соответственно). Просто.

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

Всё, что нам осталось — это скопировать полученный скрипт из вашего домашнего каталога в /var/www/html (этот путь может меняться в зависимости от дистрибутива) и вызвать его через web-браузер. Можете сравнить ваш скрипт с моим, хотя бы для того, чтобы убедиться, что вы соединили кусочки в правильном порядке.

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

Многие люди не согласны с решением о выгоде изменения своего выбора после того, как ведущий показал первую козу. Конечно, они ошибаются и достойны публичного осмеяния. Но если этим непросвещенным человеком является кто-то из ваших близких, то гораздо лучше было бы показать ему, где он ошибается, и привить немного любви к числам. Итак, используйте этот скрипт, чтобы показать как работает загадка Монти Холла, и подбросьте им «Флатландию» Эббота (Abbott, «Flatland»), чтобы они поняли, чего они лишены.

Домашнее задание

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

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

• Облегчить… Заставьте скрипт n раз запускать тест со сменой двери и еще n раз — сохраняя изначальный выбор, для того чтобы избавить пользователя от необходимости переключать кнопки. Результаты надо показать в разных частях экрана.
• Схитрить… Наш скрипт даже не пытается подсчитать проценты выигрышей или проигрышей на основе полученных данных. Для простых значений это просто сделать в уме. Например, если вы сделали 1000 тестовых запусков, то вы с первого взгляда распознаете ситуацию. Но если у вас было 19350 тестов, то результат уже не настолько очевиден.
  Подсчитайте число побед и поражений в процентном соотношении и выведите полученные значения.
• Расширить… Загадку Монти Холла можно обобщить. Теоретически, мы можем рассмотреть сотню дверей, с 99 козами и 1 машиной — и ведущий должен будет открыть 98 дверей после того, как мы выберем одну. В этой ситуации мы получим шанс на победу при смене двери, равный 99/100. Наш скрипт не может обработать эту ситуацию, но вы можете расширить интерфейс пользователя еще одним элементом, позволяющим задать число дверей, передавать затем это значение в функцию MontyHall() и создавать в функции массив из множества коз и одной машины в конце.
• Добить! Представьте себе, что ведущий шоу не знает, где находится машина. Что случится тогда с вашими шансами на победу и почему? Я жду ваших ответов на открытках, как обычно.