Реализации алгоритмов/Парадокс Монти Холла
Здесь приведены программы на разных языках программирования, моделирующие события игры, описанной в статье Парадокс Монти Холла.
using System;
using System.Threading.Tasks;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Plus
{
public class Shool
{
static void Main(string[] args)
{
Game game = new Game(10000);
game.StartGames();
double percentСhangesСhoice =
( Convert.ToDouble(game.statistics.CountVinsChangesСhoice)
/ game.statistics.totalGame) * 100;
Console.WriteLine($"Процент победы по стратегии изменения выбора {percentСhangesСhoice}");
double percentNotСhangesСhoice =
(Convert.ToDouble(game.statistics.CountVinsNotChangesСhoice)
/ game.statistics.totalGame) * 100;
Console.WriteLine($"Процент победы по стратегии комбинаторики {percentNotСhangesСhoice }");
}
}
public class Player
{
public int selectedElement;
public int discontItem;
}
public class Game
{
Player changesСhoice ;
Player NotchangesСhoice ;
List<Street> firstPlayerList;
List<Street> secondPlayerList;
int countGame;
static Random random = new Random();
public Statistics statistics = new Statistics();
public Game(int count)
{
countGame = count;
statistics.totalGame = count;
firstPlayerList = InitStreet(count);
secondPlayerList = InitStreet(count);
}
public List<Street> InitStreet(int count)
{
List<Street> streets = new List<Street>();
for (int i = 0; i < count; i++)
{
streets.Add(new Street());
}
return streets;
}
public void StartGames()
{
for (int i = 0; i < countGame; i++)
{
changesСhoice = new Player();
NotchangesСhoice = new Player();
changesСhoice.selectedElement = random.Next(0, 3);
NotchangesСhoice.selectedElement = random.Next(0, 3);
changesСhoice.discontItem = GetNothingInStreet(firstPlayerList[i], changesСhoice.selectedElement);
NotchangesСhoice.discontItem = GetNothingInStreet(secondPlayerList[i], NotchangesСhoice.selectedElement);
changesСhoice.selectedElement = AnotherСhoice(changesСhoice, firstPlayerList[i]);
if (IsWinner(changesСhoice, firstPlayerList[i]))
{
statistics.CountVinsChangesСhoice++;
}
if (IsWinner(NotchangesСhoice, secondPlayerList[i]))
{
statistics.CountVinsNotChangesСhoice++;
}
}
}
public bool IsWinner(Player player, Street street)
{
int vinIndex = street.doors.FindIndex(x => x == Items.Car);
return player.selectedElement == vinIndex;
}
public int AnotherСhoice(Player player, Street street)
{
return new int[] { 0,1,2 }
.Where(x => x != player.discontItem && x != player.selectedElement)
.First();
}
public int GetNothingInStreet(Street street, int discont)
{
Street Localstreet = street;
List<int?> allNothingIndex = new List<int?>();
allNothingIndex.Add(Localstreet.doors
.FindAll(x => x == Items.nothing)
.Select(x => Localstreet.doors.FindIndex(y => y == x))
.FirstOrDefault());
allNothingIndex.Add(Localstreet.doors
.FindAll(x => x == Items.nothing)
.Select(x => Localstreet.doors.FindLastIndex(y => y == x))
.Where(x=>x != allNothingIndex[0])
.FirstOrDefault());
allNothingIndex = allNothingIndex.Where(x => x != null && x != discont).ToList();
int count = allNothingIndex.Count;
return allNothingIndex[random.Next(0, count )].GetValueOrDefault();
}
}
public class Street
{
public List<Items> doors;
static Random random = new Random();
public Street()
{
int car = random.Next(0, 3);
doors = new List<Items>() { Items.nothing , Items.nothing , Items.nothing };
doors[car] = Items.Car;
}
}
public class Statistics
{
public int totalGame;
public int CountVinsChangesСhoice = 0;
public int CountVinsNotChangesСhoice = 0;
}
public enum Items
{
Car = 1,
nothing = 2
}
}
Вывод программы — это число раз (из 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 range(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 range(choice):
reveal = possible_doors.pop()
if auto == primary_choice:
return 1
else:
return 0
a=0
for i in range(10000):
a+=roll_not_changing()
print(a)
a=0
for i in range(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%)
Можно просто вставить в файл monty-hall.html и открыть в браузере
<html>
<head>
<script type="text/javascript">
function getCarDoors()
{
var doors = [0, 0, 0];
var carIn = Math.floor(Math.random() * 3);
doors[carIn] = 1;
return doors;
}
function game(tries)
{
var res =
{
changedAndWon: 0,
changedAndLost: 0,
keepAndWon: 0,
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;
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])
{
if (changeChoice)
res.changedAndWon++;
else
res.keepAndWon++;
}
else
{
if (changeChoice)
res.changedAndLost++;
else
res.keepAndLost++;
}
}
return res;
}
function presentGame(count, divId)
{
var res = game(count);
var changeOkProb = res.changedAndWon / ((res.changedAndLost + res.changedAndWon) > 0 ? (res.changedAndLost + res.changedAndWon) : 1);
var keepOkProb = res.keepAndWon / ((res.keepAndWon + res.keepAndLost) > 0 ? (res.keepAndWon + res.keepAndLost) : 1);
var text = "<tr><td>Количество попыток: " + "</td><td><b>" + count + "</b></td></tr>";
text += "<tr><td>Не изменил решение и выиграл: " + "</td><td>" + res.keepAndWon + "</td></tr>";
text += "<tr><td>Не изменил решение и проиграл: " + "</td><td>" + res.keepAndLost + "</td></tr>";
text += "<tr><td>Изменил решение и выиграл: " + "</td><td>" + res.changedAndWon + "</td></tr>";
text += "<tr><td>Изменил решение и проиграл: " + "</td><td>" + res.changedAndLost + "</td></tr>";
text += "<tr><td>Вероятность выиграть, при изменении решения: " + "</td><td>" + "<b>" + (Math.round(changeOkProb * 10000) / 100) + "%</b>" + "</td></tr>";
text += "<tr><td>Вероятность выиграть, без изменения решения: " + "</td><td>" + "<b>" + (Math.round(keepOkProb * 10000) / 100) + "%</b>" + "</td></tr>";
document.getElementById(divId).innerHTML = "<table>" + text + "</table>";
}
</script>
</head>
<body>
<h1>Парадокс Монти Холла</h1>
Количество попыток:
<input type="text" value="100" id="tries" />
<input type="button" value="Запустить" onClick="presentGame(document.getElementById('tries').value, 'data');" />
<br />
<div id="data"></div>
</body>
</html>
Программа подсчитывает вероятность выигрыша в случае смены двери. Производится n попыток. Результат работы — 66 %.
function montey : boolean;
var
f, c, o : byte;
d : array [0..2] of boolean;
begin
f := random(3);
for c := 0 to 2 do
d[c] := f = c;
c := random(3);
repeat
o := random(3);
until ((not d[o]) and (o <> c));
montey := d[3 - c - o];
end;
const
n = 10000000;
var
i, k : longint;
begin
randomize;
for i := 1 to n do
if montey then
inc(k);
write(k * 100 / n : 5 : 2);
readln;
end.