Версия 14:47, 13 марта 2008

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() (она просто перемещает указатель массива на одну позицию вперёд).

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