Kodumaro :: Paradoxo de Monty Hall, parte Ⅰ

Publicado em 22 de Maio, 2016
As sombras da programação.
Monty Hall

O Paradoxo de Monty Hall diz que, em se descartando algumas escolhas erradas, as desconhecidas restantes combinam as probabilidades daquelas descartadas.

O exemplo clássico desse paradoxo são três portas fechadas, uma com um carrozero e as outras duas com bodes. O convidado precisa escolher uma porta, e receberá como prêmio o que estiver atrás dela.

Então o convidado escolhe uma porta. O mestre de cerimônia em vez de abrira porta escolhida, abre uma das outras duas portas, mostrando um bode atrás dela. Então ele pergunta se o convidado quer continuar com a porta escolhida ou se prefere trocar para a outra porta ainda fechada.

Segundo o Paradoxo de Monty Hall, o convidado tem 33% (uma chance em três)de ganhar o carro se mantiver a escolha inicial, mas 67% (duas em três) se trocar para a outra porta. Isso porque se a possibilidade dele ganhar era 33%, ela não se altera, portanto a possibilidade do carro estar em uma das outras duas portas – agora apenas uma – é de 67%.

Nesta sequência de artigos escreveremos um código para colocar à prova esse paradoxo. No processo aprenderemos um pouco sobre OTP, o framework de serviços de Erlang. Neste primeiro artigo, faremos funcionar o primeiro ator: o mestre de cerimônias.

Boilerplate

Vamos começar com um boilerplate OTP para o mestre de cerimônia. Será um arquivo chamado mh_mc.erl. Usaremos o gen_server:

-module(mh_mc).
-behavior(gen_server).

-export([start_link/0, stop/0]).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2, terminate/2,
         code_change/3]).


%% API

-spec start_link() -> {ok, Pid} when Pid :: pid().
-spec stop() -> ok.

start_link() -> gen_server:start_link({local, ?MODULE}, ?MODULE, null, []).

stop() -> gen_server:cast(?MODULE, stop).


%% Behavior

init(null) -> {ok, []}.

code_change(_OldVsn, State, _Extra) -> {ok, State}.

handle_call(_Request, _From, State) -> {reply, ok, State}.

handle_cast(stop, State) -> {stop, normal, State};

handle_cast(_Request, State) -> {noreply, State}.

handle_info(_Info, _State) -> ok.

terminate(_Reason, _State) -> ok.

Nosso código é dividido em duas partes: API (interface com outros atores) ecomportamento (interface com OTP).

A API por enquanto tem apenas duas funções, descritas nas declarações -spec: start_link/0, que inicia o mestre de cerimônias, e stop/0, que encerra o processo.

Já podemos testá-o, aliás:

sh$ erlc mh_mc.erl
sh$ erl
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Eshell V7.3 (abort with ^G)
1> mh_mc:start_link().
{ok, <0.35.0>
2> processes().
[<0.0.0>,<0.3.0>,<0.6.0>,<0.7.0>,<0.9.0>,<0.10.0>,<0.11.0>,
<0.12.0>,<0.14.0>,<0.15.0>,<0.16.0>,<0.17.0>,<0.18.0>,
<0.19.0>,<0.20.0>,<0.21.0>,<0.22.0>,<0.23.0>,<0.24.0>,
<0.25.0>,<0.26.0>,<0.27.0>,<0.28.0>,<0.29.0>,<0.33.0>,
<0.35.0>]
3> mh_mc:stop().
ok
4> processes().
[<0.0.0>,<0.3.0>,<0.6.0>,<0.7.0>,<0.9.0>,<0.10.0>,<0.11.0>,
<0.12.0>,<0.14.0>,<0.15.0>,<0.16.0>,<0.17.0>,<0.18.0>,
<0.19.0>,<0.20.0>,<0.21.0>,<0.22.0>,<0.23.0>,<0.24.0>,
<0.25.0>,<0.26.0>,<0.27.0>,<0.28.0>,<0.29.0>,<0.33.0>]
5>

As funções de comportamento são:

  • init/1: função chamada pelo OTP para inicializar o processo, configurando o estado inicial.
  • code_change/3: diz ao OTP o que fazer quando o módulo é atualizado. No caso, apenas continua rodando o código novo com o mesmo estado.
  • handle_call/3: diz ao OTP o que fazer quando outro processo faz uma chamada, aguardando retorno. Em nosso boilerplate, apenas responde ok.
  • handle_cast/2: diz ao OTP o que fazer quando outro processo lança uma chamada assíncrona. Se o requisição for stop, usada pela função stop/0, encerra o processo normalmente, caso contrário, não responde nada e continua com o estado atual.
  • handle_info/2: diz ao OTP o que fazer em caso de timeout.
  • terminate/2: função chamada pelo OTP quando o processo encerra.

Iniciando o sistema

A primeira coisa a se fazer é inicializar o sistema criando as portas e colocando os bodes e o carro atrás de cada uma aleatoriamente.

O método que inicializa o processo é init/1. Ele pode continuar recebendo null. O processo deve cuidar pessoalmente de configurar as portas.

Vamos representar as portas usando uma lista de possibilidades. Podemos chamar as possibilidades de prize():

-type prize() :: car | goat.

Podemos também definir que as portas são a, b e c:

-type door() :: a | b | c.
[update 2016-05-23]

Colocamos as declarações de tipo no arquivo mh.hrl, que deve ser importando usando:

-include("mh.hrl").
[/update]

A primeira coisa que precisamos fazer é resetar o sistema de aleatoriedade:

init(null) ->
  random:seed(now()),
  {ok, []}.

Vamos agora colocar bodes atrás de todas as portas:

init(null) ->
  random:seed(now()),
  Doors = [{a, goat}, {b, goat}, {c, goat}],
  {ok, Doors}.

Agora precisamos escolher uma porta para coloca o carro:

init(null) ->
  random:seed(now()),                                         % inicializa o gerador de números aleatórios
  Doors = [{a, goat}, {b, goat}, {c, goat}],                  % inicializa as três portas com bodes
  CarDoor = lists:nth(random:uniform(3), [a, b, c]),          % escolhe uma porta pra colocar o carro: a, b ou c
  {ok, lists:keyreplace(CarDoor, 1, Doors, {CarDoor, car})}.  % inicia o processo com as portas configuradas

O estado inicial do mestre de cerimônias consiste em uma lista de três portas, a, b e c, cada uma com um bode (goat) ou o carro (car) atrás. Nós não conhecemos essa formação, mas processo conhece.

Merece atenção especial a última linha:

  • ok informa ao OTP que tudo correu bem.
  • O segundo elemento da tupla é a lista de portas. lists:keyreplace/4 faz a substituição de um elemento de uma lista de tuplas baseada em uma posição das tuplas:
    • CarDoor é a porta escolhida;
    • 1 indica que a substituição é feita pelo primeiro elemento de cada tupla;
    • Doors é a list original (apenas bodes);
    • {CarDoor, car} é o novo elemento carro na porta CarDoor.

Obtendo o valor das portas

Não faz sentido termos as portas se não pudermos obter seus valores ao final.Para obter o prêmio atrás de um porta, precisamos configurar o método de comportamento handle_call/3.

No momento, a função é:

handle_call(_Request, _From, State) -> {reply, ok, State}.

Imediatamente antes, acrescente outra assinatura:

handle_call({door, Door}, _From, State) ->
    case lists:keyfind(Door, 1, State) of
        {_, Prize} -> {reply, {prize, Prize}, State};
        false -> {reply, null, State}
    end;

Agora, se o processo receber uma chamada síncrona no formato {door, Door}, retornará o conteúdo daquela porta. Precisamos apenas de uma interface. Primeiro vamos exportá-la e definir sua especificação:

-export([start_link/0, stop/0, get_prize/1]).

...

-spec get_prize(Door :: door()) -> {ok, Prize} when Prize :: prize() | {error, _}.

Podemos implementar a função get_prize/1, que apenas faz a chamada para OTP:

get_prize(Door) ->
    case gen_server:call(?MODULE, {door, Door}) of
        {prize, Prize} -> {ok, Prize};
        Other -> {error, Other}
    end.

A outra porta

A última coisa é oferecer a outra porta para abertura. Esse processo tem doisfluxos:

  1. O convidado escolheu a porta com o carro, então o mestre de cerimônias deveescolher uma das outras duas portas, aleatoriamente;
  2. O convidado escolheu uma porta com bode, então o mestre de cerimônias deveabrir a outra com bode.

Imediatamente acima da implementação de falha de handle_call/3, crieuma nova implementação tratando do pedido de outra porta para troca:

handle_call({other, Door}, _From, State) ->
    case lists:keyfind(Door, 1, State) of
        {_, goat} ->
            % convidado escolheu um bode (67%)
            {OtherDoor, _} = lists:keyfind(car, 2,
                                           lists:keydelete(Door, 1, State));
        {_, car} ->
            % convidado escolheu o carro (33%)
            {OtherDoor, _} = lists:nth(random:uniform(2),
                                       lists:keydelete(Door, 1, State));
        false -> OtherDoor = null
    end,
    {reply, OtherDoor, State};
[update 2016-05-23]

A linha que encontra a porta com o carro merece uma explicação maisprofunda.

{OtherDoor, _} = lists:keyfind(car, 2,
                               lists:keydelete(Door, 1, State));

A primeira função avaliada é:

lists:keydelete(Door, 1, State)

Ela retorna uma nova lista a partir de State, removendo a tupla cujo primeiro elemento é Door, ou seja, a porta escolhida pelo convidado. Assim, restam duas portas, uma com um bode, outra com o carro. É preciso retornar a porta com o carro.

Então entra o outro lists:keyfind/3, cujo primeiro parâmetro é car e o segundo 2. Ele retorna a tupla cujo segundo elemento é car.

Finalmente o partern matching seleciona apenas a letra da porta, armazenando-a em OtherDoor.

[/update]

Também precisamos aqui criar uma interface, da mesma forma:

-export([start_link/0, stop/0, get_prize/1, suggest_another_door/1]).

...

-spec suggest_another_door(Door :: door()) -> {ok, OtherDoor} when OtherDoor :: door() | {error, _}.

...

suggest_another_door(Door) ->
    case gen_server:call(?MODULE, {other, Door}) of
        null -> {error, null};
        OtherDoor -> {ok, OtherDoor}
    end.

Testando

Precisamos testar agora pra ver se funciona!

sh$ erlc mh_mc.erl
sh$ erl
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Eshell V7.3 (abort with ^G)
1> mh_mc:start_link().
{ok,<0.35.0>}
2> mh_mc:get_prize(a).
{ok,goat}
3> mh_mc:get_prize(b).
{ok,goat}
4> mh_mc:get_prize(c).
{ok,car}
5> mh_mc:suggest_another_door(a).
{ok,c}
6> mh_mc:suggest_another_door(b).
{ok,c}
7> mh_mc:suggest_another_door(c).
{ok,b}
8> mh_mc:suggest_another_door(a).
{ok,c}
9> mh_mc:suggest_another_door(b).
{ok,c}
10> mh_mc:suggest_another_door(c).
{ok,a}
11> mh_mc:stop()
ok
12>

Arquivos para baixar

Próximos passos

No próximo artigo criaremos o segundo ator, o convidado, que deve escolher uma das três portas e depois decidir se troca de porta ou não.

Erlang | Funcional | Lógica