Программы, моделирующие парадокс Монти-Холла
Материал из Викиучебника
Здесь приведены программы на разных языках программирования, моделирующие события игры, описанной в статье Парадокс Монти Холла.
Содержание |
[править] Python
Вывод программы — это число раз (из 10000), когда победил участник, не сменивший решение и затем число раз когда победил участник сменивший решение.
import random def roll_changing(): all_doors = set([1,2,3]) possible_doors = all_doors.copy() auto = random.randint(1,3) a=0 primary_choice= random.randint(1,3) try: possible_doors.remove(auto) possible_doors.remove(primary_choice) except: pass #номер какой из осташихся откроет ведущий? choice = random.randint(1,len(possible_doors)) for i in xrange(choice): reveal = possible_doors.pop() all_doors.remove(reveal) all_doors.remove(primary_choice) choice = all_doors.pop() if auto == choice: return 1 else: return 0 def roll_not_changing(): all_doors = set([1,2,3]) possible_doors = all_doors.copy() auto = random.randint(1,3) a=0 primary_choice= random.randint(1,3) try: possible_doors.remove(auto) possible_doors.remove(primary_choice) except: pass #номер какой из осташихся откроет ведущий? choice = random.randint(1,len(possible_doors)) for i in xrange(choice): reveal = possible_doors.pop() if auto == primary_choice: return 1 else: return 0 a=0 for i in xrange(10000): a+=roll_not_changing() print a a=0 for i in xrange(10000): a+=roll_changing() print a
Вывод (пример)
3313 6748
Эту задачу можно свести к более простой задаче, и её моделирование будет очень простым:
1 стратегия: если мы не меняем выбор, то не зависимо от того, какую дверь открыл ведущий, мы выигрываем только тогда, когда сразу и точно угадали дверь. Другими словами, мы выиграли — если загаданный номер двери ведущего совпадает с номером двери, которую выбрали мы.
2 стратегия: если же мы меняем выбор, то всё становится наоборот: мы проигрываем, если сразу угадали дверь, но поменяли её. И выигрываем, если сразу не угадали дверь, но изменили её на дверь ведущего.
Получается, что для подсчёта выигрышей по первой стратегии достаточно считать только случаи, когда мы точно угадали, загаданный ведущим, номер двери. А выигрыши по второй стратегии — это проирыши по первой. Вот и реализация этого алгоритма:
#!/usr/bin/python -Ou # # Written by kocmuk.ru, 2008 # import random num = 10000 # количество игр, которое мы хотим сыграть win = 0 # начальное значение выирышей, которых мы добъёмся, если не будем менять выбор for i in range(1, num): # играем num игр if random.randint(1,3) == random.randint(1,3): # в случае, если мы угадали сразу, win +=1 # увеличиваем количество выигрышей на 1 print "Я не менял выбора и выиграл:", win, "игр" # выигрыши по первой стратегии print "Я менял выбор и выиграл:", num-win, "игр" # проигрыши по первой стратегии - это выигрыши по второй
[править] Си++
Вычисление условных вероятностей по теореме Байеса.
Если слева и справа отобразить мнимые двери, периодически повторяющиеся, то получим: -0,-1,[-2,0,1,2,+0],+1,+2
В этом случае можно точно утвержать, что какую бы дверь не выбрал игрок, ведущий откроет, или следующую, или предыдущую.
Если игрок выбрал дверь 0, то предыдущая будет -2 или, что эквивалентно, просто 2.
Если игрок выбрал дверь 2, то следующая будет +0 или, что эквивалентно, просто 0.
В решении задачки по Байесу эту симметрию оговаривали и считали, что игрок выбирает всегда нулевую дверь, от этого допущения смысл не меняется.
Поэтому эксперимент расскладывается на две группы не пересекающихся событий:
0)Ведущий открыл следующую, от выбранной игроком, дверь.
1)Ведущий открыл предыдущую, от выбранной игроком, дверь.
Все вероятности подсчитываются для каждого из событий 0) и 1) отдельно.
Кроме стратегий игрока "менять выбор" и "не менять выбор", добавлены стратегии ведущего "честный", "нечестный 0" и "нечестный 1".
using namespace std; // равновероятная генерация случайных чисел 0, 1 int rand2() { return (rand() % 2); } // равновероятная генерация случайных чисел 0, 1, 2 int rand3() { return (rand() % 3); } // случайно прячем приз class CSituation { public: void GenerateRandom() { m_nPriceNo = rand3(); m_bOpened[0] = m_bOpened[1] = m_bOpened[2] = false; m_nOpenedByAnchor = -1; m_nSelectedByUserFirstTime = m_nSelectedByUserSecondTime = -1; } bool m_bOpened[3]; // двери int m_nPriceNo; // где спрятан приз // выбор игрока и ведущего int m_nSelectedByUserFirstTime, m_nSelectedByUserSecondTime, m_nOpenedByAnchor; }; // стратегия честного ведущего, // игроку выгодно менять выбор, шансы удваиваются class CAnchorStrategyOpenRandom { public: static void Act(CSituation& situation) { int arVars[2] = { (situation.m_nSelectedByUserFirstTime + 1) % 3, (situation.m_nSelectedByUserFirstTime + 2) % 3 }; // Ведущий открывает случайную дверь, если игрок первым выбором угадал приз int nVariantNo = rand2(); int nVariant = arVars[nVariantNo]; if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo]; situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true; } static char* GetName(){return "Anchorman randomly opens an empty door, 50% : 50%";} }; // 0 стратегия нечестного ведущего, // для игрока не важно менять выбор или нет, шансы равны, // в ситуации если ведущим открыта дверь, следующая сразу за выбранной игроком class CAnchorStrategyOpenNotRandom0 { public: static void Act(CSituation& situation) { int arVars[2] = { (situation.m_nSelectedByUserFirstTime + 1) % 3, (situation.m_nSelectedByUserFirstTime + 2) % 3 }; // Ведущему больше нравится дверь, следующая сразу за выбранной игроком. // Если он её отркыл, значит приз равновероятно может находиться в двух оставшихся. int nVariantNo = 0; int nVariant = arVars[nVariantNo]; if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo]; situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true; } static char* GetName(){return "Anchorman tries to open only the next empty door.";} }; // 1 стратегия нечестного ведущего, // меняя выбор, игрок гарантированно выигрывает приз, // в ситуации если открыта дверь, следующая сразу за выбранной игроком class CAnchorStrategyOpenNotRandom1 { public: static void Act(CSituation& situation) { int arVars[2] = { (situation.m_nSelectedByUserFirstTime + 1) % 3, (situation.m_nSelectedByUserFirstTime + 2) % 3 }; // Ведущему больше нравится дверь, идущая перед выбранной игроком. // Если он её не отркыл, значит там точно лежит приз. int nVariantNo = 1; int nVariant = arVars[nVariantNo]; if(nVariant == situation.m_nPriceNo) nVariant = arVars[1 - nVariantNo]; situation.m_bOpened[situation.m_nOpenedByAnchor = nVariant] = true; } static char* GetName(){return "Anchorman tries to open only the previous empty door.";} }; // выбор игроком двери class CUserStrategySelectFirst { public: static void Act(CSituation& situation) { situation.m_nSelectedByUserFirstTime = rand3(); } }; // игрок не меняет выбор class CUserStrategyKeepTheChoose { public: static void Act(CSituation& situation) { situation.m_nSelectedByUserSecondTime = situation.m_nSelectedByUserFirstTime; situation.m_bOpened[situation.m_nSelectedByUserSecondTime] = true; } static char* GetName(){return "Keep the choose";} }; // игрок меняет выбор class CUserStrategyChange { public: static void Act(CSituation& situation) { situation.m_nSelectedByUserSecondTime = (situation.m_nSelectedByUserFirstTime + 1) % 3; if(situation.m_bOpened[situation.m_nSelectedByUserSecondTime]) situation.m_nSelectedByUserSecondTime = (situation.m_nSelectedByUserSecondTime + 1) % 3; situation.m_bOpened[situation.m_nSelectedByUserSecondTime] = true; } static char* GetName(){return "Change the choose";} }; // симуляция игры // TUserStrategy - стратегия игрока // TAnhorStrategy - стратегия ведущего // nCountIteration - количество испытаний template<class TUserStrategy, class TAnhorStrategy, int nCountIteration> void TestFull() { const char* pcszDesc0 = "next door was opened"; const char* pcszDesc1 = "previous door was opened"; int nWin[2] = {0}; int nLoose[2] = {0}; const char* aDesc[] = {pcszDesc0, pcszDesc1}; CSituation situation; for(int i = 0; i < nCountIteration; i++) { situation.GenerateRandom(); CUserStrategySelectFirst::Act(situation); TAnhorStrategy::Act(situation); TUserStrategy::Act(situation); int iNextDoor = (situation.m_nSelectedByUserFirstTime + 1)%3; bool bIsConditionNextDoor = (situation.m_nOpenedByAnchor == iNextDoor); int iCondition = bIsConditionNextDoor?0:1; // Посчитаем шансы на выигрыш для каждой ситуации: // 0 - известно, что ведущий открыл дверь, которая сразу следует за выбранной игроком // 1 - известно, что ведущий открыл дверь, которая предшествует выбранной игроком if( situation.m_bOpened[situation.m_nPriceNo]) { nWin[iCondition]++; } else { nLoose[iCondition]++; } } for(int i = 0; i < sizeof(nWin)/sizeof(int); i++) { int nCount = nWin[i] + nLoose[i]; cout << i << ") " << aDesc[i] << " (" << nCount*100/nCountIteration << "%)" << " - "; cout << "Wins: " << nWin[i] << " (" << nWin[i]*100/nCount << "%)" << "; "; cout << "Loose: " << nLoose[i] << " (" << nLoose[i]*100/nCount << "%)" << endl; } } // две стратегии игрока, для одной стратегии ведущего // TAnhorStrategy - стратегия ведущего // nCountIteration - количество испытаний template<class TAnhorStrategy, int nCountIteration> void Test() { cout << "========================================================" << endl; cout << "Anchorman strategy: " << TAnhorStrategy::GetName() << endl; cout << endl; cout << "User strategy: " << CUserStrategyKeepTheChoose::GetName() << endl; TestFull<CUserStrategyKeepTheChoose, TAnhorStrategy, nCountIteration>(); cout << endl; cout << "User strategy: " << CUserStrategyChange::GetName() << endl; TestFull<CUserStrategyChange, TAnhorStrategy, nCountIteration>(); cout << endl; } // главная точка входа программы int _tmain(int argc, _TCHAR* argv[]) { srand( (unsigned)time( NULL ) ); const int nCountIteration = 1500000; // количество испытаний cout << "Number of iteration: " << nCountIteration << endl; Test<CAnchorStrategyOpenRandom, nCountIteration>(); // честный ведущий Test<CAnchorStrategyOpenNotRandom0, nCountIteration>(); // нечестный 0 Test<CAnchorStrategyOpenNotRandom1, nCountIteration>(); // нечестный 1 cin.get(); return 0; }
Вывод (пример)
Number of iteration: 1500000 ======================================================== Anchorman strategy: Anchorman randomly opens an empty door, 50% : 50% User strategy: Keep the choose 0) next door was opened (50%) - Wins: 249595 (33%); Loose: 500575 (66%) 1) previous door was opened (49%) - Wins: 249423 (33%); Loose: 500407 (66%) User strategy: Change the choose 0) next door was opened (50%) - Wins: 499649 (66%); Loose: 250748 (33%) 1) previous door was opened (49%) - Wins: 499504 (66%); Loose: 250099 (33%) ======================================================== Anchorman strategy: Anchorman tries to open only the next empty door. User strategy: Keep the choose 0) next door was opened (66%) - Wins: 500077 (50%); Loose: 499641 (49%) 1) previous door was opened (33%) - Wins: 0 (0%); Loose: 500282 (100%) User strategy: Change the choose 0) next door was opened (66%) - Wins: 500856 (50%); Loose: 500137 (49%) 1) previous door was opened (33%) - Wins: 499007 (100%); Loose: 0 (0%) ======================================================== Anchorman strategy: Anchorman tries to open only the previous empty door. User strategy: Keep the choose 0) next door was opened (33%) - Wins: 0 (0%); Loose: 499974 (100%) 1) previous door was opened (66%) - Wins: 499930 (49%); Loose: 500096 (50%) User strategy: Change the choose 0) next door was opened (33%) - Wins: 500122 (100%); Loose: 0 (0%) 1) previous door was opened (66%) - Wins: 499991 (50%); Loose: 499887 (49%)
--ViPetroFF 18:00, 8 октября 2009 (UTC)
[править] Программа на Javascript, моделирующая задачу
Можно просто вставить в файл monty-hall.html и открыть в браузере
<html>
<head>
<script>
function getCarDoors(){
var doors = new Array(3);
doors[0] = 0;
doors[1] = 0;
doors[2] = 0;
var carIn = Math.floor(Math.random() * 3);
doors[carIn] = 1;
return doors;
}
function game(tries){
var changedAndWon = 0;
var changedAndLost = 0;
var keepAndWon = 0;
var keepAndLost = 0;
for (j = 0; j < tries; j ++){
var d = getCarDoors();
var myChoice = Math.floor(Math.random() * 3);
var changeChoice = Math.floor(Math.random() * 2) == 1 ? true : false;
var otherOpen;
var otherClosed;
var opened = false;
for (i = 0; i < 3; i ++){
if (i != myChoice && d[i] == 0 && !opened){
otherOpen = i;
opened = true;
} else if (i != myChoice){
otherClosed = i;
}
}
var selected = changeChoice ? otherClosed : myChoice;
if (d[selected] == 1){
if (changeChoice){
changedAndWon ++;
} else {
keepAndWon++;
}
} else {
if (changeChoice){
changedAndLost ++;
} else {
keepAndLost++;
}
}
}
var res = new Array(4);
res["changeAndWon"] = changedAndWon;
res["changedAndLost"] = changedAndLost;
res["keepAndWon"] = keepAndWon;
res["keepAndLost"] = keepAndLost;
return res;
}
function presentGame(count, divId){
var res = game(count);
var changedAndWon = res["changeAndWon"];
var changedAndLost = res["changedAndLost"];
var keepAndWon = res["keepAndWon"];
var keepAndLost = res["keepAndLost"];
var changeOkProb = changedAndWon / ((changedAndLost + changedAndWon) > 0 ? (changedAndLost + changedAndWon) : 1);
var keepOkProb = keepAndWon / ((keepAndWon + keepAndLost) > 0 ? (keepAndWon + keepAndLost) : 1);
var text = "<tr><td>Number of tries: " + "</td><td><b>" + count + "</b></td></tr>";
text += "<tr><td>kept decision and won: " + "</td><td>" +keepAndWon + "</td></tr>";
text += "<tr><td>kept decision and lost: " + "</td><td>" +keepAndLost + "</td></tr>";
text += "<tr><td>changed decision and won: " + "</td><td>" +changedAndWon + "</td></tr>";
text += "<tr><td>changed decision and lost: " + "</td><td>" +changedAndLost + "</td></tr>";
text += "<tr><td>Probability to win if change decision: " + "</td><td>" + "<b>" + (Math.round(changeOkProb * 10000) / 100) + "%</b>" + "</td></tr>";
text += "<tr><td>Probability to win if keep decision: " + "</td><td>" + "<b>" + (Math.round(keepOkProb * 10000) / 100) + "%</b>" + "</td></tr>";
document.getElementById(divId).innerHTML = "<table>" + text + "</table>";
}
</script>
</head>
<body>
<h1>Monty Hall problem</h1>
Number of tries:
<input type="text" value="100" id="tries" />
<input type="button" value="Run simulation"
onClick="presentGame(document.getElementById('tries').value, 'data'); return false;" />
<br />
<div id="data"></div>
</body>
</html>
[править] Программа на Turbo Pascal, моделирующая задачу
program paradacs;
uses crt;
label 1;
var a:array[1..3] of byte;
i,b:integer;
c: byte;
begin;
clrscr;
writeln('Program by Kisuke, paradocs Monty Holla');
randomize;
i:=random(3)+1;
{writeln(i);}
a[i]:=1;
Writeln('Viberite nomer dveri');
readln(b);
If b=1 then begin
Writeln('Hotite smenit vash vibor? Otvet (da - 1) (net - 0) ');
read(c);
if c=1 then begin
if i=2 then b:=2;
if i=3 then b:=3;
if i=1 then b:=4;
end;
if i=b then writeln('Ugadali')
else writeln('Ne ugadali');
readln; goto 1;
end;
If b=2 then begin
Writeln('Hotite smenit vash vibor? Otvet (da - 1) (net - 0) ');
read(c);
if c=1 then begin
if i=1 then b:=2;
if i=3 then b:=3;
if i=2 then b:=4;
end;
if i=b then writeln('Ugadali')
else writeln('Ne ugadali');
readln; goto 1;
end;
If b=3 then begin
Writeln('Hotite smenit vash vibor? Otvet (da - 1) (net - 0) ');
read(c);
if c=1 then begin
if i=1 then b:=1;
if i=2 then b:=2;
if i=3 then b:=4;
end;
if i=b then writeln('Ugadali')
else writeln('Ne ugadali');
readln; goto 1;
end;
1: readln;
end.
Или
program paradox;
uses crt;
label 1;
var a:array[1..3] of byte;
i,b,m,n:longint;
begin;
writeln('Program by Kisuke&SHOGUN, Monty Hall problem');
randomize;
n:=1;
m:=0;
for n:=1 to 1000000 do
begin
i:=random(3)+1;
a[i]:=1;
b:=random(3)+1;
If b=1 then begin
if i=2 then b:=2;
if i=3 then b:=3;
if i=1 then b:=4;
end else
If b=2 then begin
if i=1 then b:=2;
if i=3 then b:=3;
if i=2 then b:=4;
end else
If b=3 then begin
if i=1 then b:=1;
if i=2 then b:=2;
if i=3 then b:=4;
end;
if i=b then m:=m+1 else
end;
writeln(m);
readln;
end.
Из миллиона вариантов это программа показала верными 555830, что превышает 50 %.
[править] Программа на Delphi
Программа на Delphi, позволяющая пользователю вводить кол-во итераций и случайным образом рассчитывать на ПК кол-во выигрышей.
unit PMH;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Panel1: TPanel;
Label1: TLabel;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
I,max,cnt: longint; //счетчик итераций, максимум (вводимый пользователем), счетчик выигрышей
choose:1..3; //выбор пользователя
a: array[1..3] of integer; //собственно, сами двери, содержащие автомобиль(1) и козу (0)
begin
max:=strtoint(Form1.Edit1.Text);
cnt:=0;
for I := 1 to max do
begin
{распределяем случайным образом нули и единицы в массиве (автомобиль и коз),
при этом автомобиль должен быть в кол-ве одной штуки, козы в кол-ве двух штук}
a[1]:=random(1);
if a[1]<>1 then a[2]:=random(1) else begin a[2]:=0; a[3]:=0; end;
if a[2]<>1 then a[3]:=1 else a[3]:=0;
choose:=random(3)+1; //делаем случайный выбор
{меняем выбор, в соответствии с открытием ведущим двери с козой}
{алгоритмы просчитываются деревом ветвлений}
if choose=1 then begin
if a[2]=1 then choose:=2 else choose:=3;
end
else
if choose=2 then begin
if a[1]=1 then choose:=1 else choose:=3;
end
else
if a[1]=1 then choose:=1 else choose:=2;
if a[choose]=1 then cnt:=cnt+1; //при совпадении выбора и автомобиля инкрементируем счетчик выигрышей
end;
Panel1.Caption:=inttostr(cnt);
end;
end.
