(파이썬) 몬티 홀 문제(Monty Hall problem)

공부가 짧아서
이런 랜덤과 확률을 이용한 시뮬레이션도
족보 있는 알고리듬인 줄 몰랐습니다. 
이런 식으로 푸는 걸 몬테 카를로 방법이라고 하더군요.

 

몬테 카를로 방법(Monte Carlo method)
무작위 수와 확률과 모의실험(시뮬레이션)을 통해 문제를 해석하고 해결함.

 

몬티홀 문제는

사고 실험으로만 이해하기는 다소 혼란스럽지만...
간단히 코딩할 수 있고...
코딩을 하면 좀 더 이해가 쉬워지는 것 같습니다...

https://namu.wiki/w/%EB%AA%AC%ED%8B%B0%20%ED%99%80%20%EB%AC%B8%EC%A0%9C

몬티 홀 문제 - 나무위키

Suppose you’re on a game show, and you’re given the choice of three doors.
Behind one door is a car, behind the others, goats. 
You pick a door, say #1, 
and the host, who knows what’s behind the doors, 
opens another door, say #3, which has a goat. 
He says to you, "Do you want to pick door #2?" 
Is it to your advantage to switch your choice of doors? 

당신이 한 게임 쇼에 참여하여 세 문들 중 하나를 고를 기회를 가졌다고 생각해보자. 
한 문 뒤에는 자동차가 있으며, 다른 두 문 뒤에는 염소가 있다. 
당신은 1번 문을 고르고, 문 뒤에 무엇이 있는지 아는 사회자는 염소가 있는 3번 문을 연다. 
그는 당신에게 "2번 문을 고르고 싶습니까?"라고 묻는다. 
당신의 선택을 바꾸는 것은 이득이 되는가?

---------------------------------------------

 

몬티 홀 문제는 일반적으로 다음의 룰을 통해 진행된다.

• 문 3개가 있는데 한 문 뒤에는 자동차가 있고 나머지 두 문 뒤에는 염소가 있다.
• 참가자는 이 상황에서 문을 하나 선택하여 그 뒤에 있는 상품을 얻는다.
• 참가자가 어떤 문을 선택하면
• 사회자는 나머지 두 문 중에 염소가 있는 문 한 개를 열어
• 참가자에게 그 문에 염소가 있다고 확인시켜준다.
• 그 후 사회자는 참가자에게 선택한 문을 닫혀있는 다른 문으로 선택을 바꿀 기회를 준다. 

 

고전적인 몬티홀 문제는 이 게임을 수학적으로 풀기 위해 다음과 같은 전제를 사용한다.

• 사회자는 자동차가 어느 문 뒤에 있는지 알고 있다.
• 사회자는 염소가 들어 있는 문을 임의로 선택한다.

-------------------------------------------

# Monty Hall problem
# https://comdoc.tistory.com/
# 2020-09-19

from random import randint


def monty_hall():
    # (0, 1, 2) 중 차를 둘 문 선택
    car = randint(0, 2)

    # 참가자의 첫 번째 선택
    first_choice = randint(0, 2)

    # 사회자가 열어야 하는 문
    # 다음 while문을 무조건 돌리기 위해 초기값을 car로 넣었음.
    open_door = car

    # (사회자는 미리 답을 알고 있어) 차가 있는 문을 열지 않음. 참가자가 선택한 문도 열지 않음.
    # 차가 있는 문을 열거나 참가자가 선택한 문을 고르면, 다시 선택.
    # 사회자는 차가 없고, 참가자가 선택하지 않은 문을 고르게 됨.
    while open_door == car or open_door == first_choice:
        open_door = randint(0, 2)

    # 참가자의 두 번째 선택. 
    # 다음 while문을 무조건 돌리기 위해 초기값을 first_choice로 넣었음.
    second_choice = first_choice

    # 참가자가 두 번째 선택을 한다면, 첫 번째 선택과 달라야 하고, 열려진 문도 아님.
    while second_choice == first_choice or second_choice == open_door:
        second_choice = randint(0, 2)

    # 첫 번째 선택이 맞을까? 두 번째 선택이 맞을까?
    return car == first_choice, car == second_choice


hits_of_first = hits_of_second = 0
total = 10000
for _ in range(total):
    hit_of_first, hit_of_second = monty_hall()
    if hit_of_first:
        hits_of_first += 1
    elif hit_of_second:
        hits_of_second += 1
print(f"first: {hits_of_first}/{total} = {hits_of_first / total}")
print(f"second: {hits_of_second}/{total} = {hits_of_second / total}")

first: 3358/10000 = 0.3358
second: 6642/10000 = 0.6642

1만 번 반복했을 때 결과는 위와 같습니다.

처음 선택으로 결정했을 때는 당연히 1/3 
바꿨을 때는 2/3

----------------------

코딩을 하면서도 헷갈린 건데요. 

처음엔 아무것도 모르는 상황에서 문 하나를 고릅니다. 
확률은 1/3이 될 수밖에 없죠. ㅇㅇ
(저도 이 정도는 알아욧...)

두 번째 선택에선
사회자가 차가 없는 문을 하나 열어준 뒤,
나머지 2개 중에서 하나를 고르니까
확률은 1/2이 될 것 같은데요...
(저도 처음엔 이렇게 생각을...)

실제 코딩을 하면서 정리를 해보니

두번째 선택에서
사회자가 고른 문을 제외한
나머지 2개중 하나를 고르는 것이 아니라

사회자가 고른 문과 첫번째 골랐던 문,
이 둘을 제외하고
다른 하나를 고르는 것이더군요.

그래서 2/3가 나옵니다. ㅎㅎㅎ

이래서 이 문제가 재미있는 것 같습니다.

 

20세기 최고의 전설적인 수학자 중 하나로 여겨지는 폴 에르되시도 선택을 바꾸든 아니든 확률은 같다고 생각했고, 
컴퓨터로 실험해본 뒤에야 바꾸는 것이 유리한 선택임을 인정했다고 한다.

 

수학적으로는 이렇게 이해하는 게 가장 쉬운 것 같습니다. 

youtu.be/eCrSFFDTGI0

 

PS1) 공통되는 부분을 함수로 정리하면 더 깔끔해집니다.  

# Monty Hall problem
# https://comdoc.tistory.com/
# 2020-09-19

from random import randint


def except_and_random_choice(ex1, ex2):
    chosen = ex1
    while chosen in (ex1, ex2):
        chosen = randint(0, 2)
    return chosen


def monty_hall():
    car = randint(0, 2)
    first_choice = randint(0, 2)
    open_door = except_and_random_choice(car, first_choice)
    second_choice = except_and_random_choice(first_choice, open_door)
    return car == first_choice, car == second_choice


hits_of_first = hits_of_second = 0
total = 10000
for _ in range(total):
    hit_of_first, hit_of_second = monty_hall()
    if hit_of_first:
        hits_of_first += 1
    elif hit_of_second:
        hits_of_second += 1
print(f"first: {hits_of_first}/{total} = {hits_of_first / total}")
print(f"second: {hits_of_second}/{total} = {hits_of_second / total}")

 

PS2) 떠오르는 생각의 흐름을 따라 코딩한다면 다음과 비슷할 겁니다. 
배열을 만들고 배열에서 제외할 건 제외하고 고르는 과정을 반복하겠죠. 
이렇게 코딩해도 좋습니다만, 저는 깔끔한 게 좋아서.... 

# Monty Hall problem
# https://comdoc.tistory.com/
# 2020-09-19

from random import choice


def monty_hall():
    doors = [0, 1, 2]

    # (0, 1, 2) 중 차를 둘 문 선택
    car = choice(doors)

    # 참가자의 첫 번째 선택
    first_choice = choice(doors)

    # 사회자가 열어야 하는 문
    # (사회자는 미리 답을 알고 있어) 차가 있는 문을 열지 않음. 참가자가 선택한 문도 열지 않음.
    temp = doors[:]  # doors 를 카피함.
    temp.remove(car)
    if car != first_choice:  # car와 first_choice가 같으면 두번째 remove 시 ValueError 발생
        temp.remove(first_choice)
    open_door = choice(temp)

    # 참가자의 두 번째 선택.
    # 참가자가 두 번째 선택을 한다면, 첫 번째 선택과 달라야 하고, 열려진 문도 아님.
    temp = doors[:]  # doors 를 카피함.
    temp.remove(open_door)
    temp.remove(first_choice)
    second_choice = choice(temp)

    # 첫 번째 선택이 맞을까? 두 번째 선택이 맞을까?
    return car == first_choice, car == second_choice