Experiências, Lógica

Quando a realidade esmaga a intuição

Suponha que você esteja num programa desses tipo porta dos desesperados. O apresentador lhe convida a participar do jogo que funciona da seguinte forma:

Existem 3 portas. As 3 estão fechadas de forma que você não consegue ver o que cada uma contém. Porém, uma delas esconde um carro como premiação e as outras duas um bode cada. A decisão de onde estará a porta com o carro é feita aleatoriamente. E depois de escolhida a porta, o prêmio é fixado a ela. Imagine que você (o participante) escolhe uma das 3 portas. Logo após você anunciar  sua escolha, o apresentador faz aquele suspense e abre uma das outras 2 portas, de forma que ele sempre deixa um bode sair. Agora você tem 2 portas: uma com o carro e uma com o bode. Agora o apresentador lhe faz a pergunta chave: “Você deseja trocar de porta ou continuar na mesma?” Qual seria a melhor decisão para você ganhar o carro? “Obviamente dá no mesmo. É  50% de chance de qualquer jeito…” Pois é. Fácil, né? NÃO! Por mais que a sua intuição clame desesperadamente para ser ouvida, a verdade é que, trocar de porta, nesse caso, dobra suas chances de vencer em relação a continuar com a primeira escolha. Mais especificamente, ao trocar de porta você tem 2/3 de chance de ganhar o carro.

 

The Monty Hall Problem


Esse problema,”The Monty Hall Problem”, ficou conhecido mundialmente após Marilyn Vos Savant publicá-lo em uma coluna sua numa revista de puzzles e matemática nos E.U.A. Os leitores da revista ao se depararem com o problema ficaram chocados com a resposta. E não eram pessoas do dia-a-dia ou alunos prevestibulandos, eram de fato Ph.Ds em matemática, doutores em estatísticas, cientistas renomados e etc. Estes enviaram cartas agressivas para a senhora Vos Savant em sua própria coluna, expondo o erro crasso que ela supostamente havia cometido. Eles argumentavam coisas do tipo

“Não vou nem mesmo perder muito tempo com a explicação do problema. Queira reconhecer seu erro e admitir que a resposta é 50% como nós dois bem sabemos…”

“Quer você mude sua resposta, quer não, a resposta é 50-50 de chance. Esse país já está cheio de ignorantes em matemática. Não precisamos do maior QI do mundo propagando isso. Que vergonha!”

Após algumas semanas de cartas e mais cartas, explicações e mais explicações, os matemáticos cederam e aceitaram a resposta de Vos Savant. “Quando a verdade se choca tão violentamente com a intuição” – disse ela – “as pessoas ficam chocadas.”

Paul Erdös (pronuncia-se ‘Erdish’), grande matemático húngaro, maior publicador de trabalhos na área, foi uma das pessoas que se chocaram com a resposta. E pior ainda: por não entender porque a resposta está certa. Aconselho esse livro, contando mais sobre essa e outras histórias.

 

O que danado isso tem a ver com programação ?


Bom, desafiei algumas pessoas no trabalho com esse problema a título de brincadeira. Como era de se esperar, todos responderam que a chance era 50-50 e protestaram veementemente quando eu falei que era muito melhor idéia trocar de porta. Experimente. As pessoas realmente enlouquecem com isso. É a intuição delas que está em jogo! Após muita discussão, foi feito um simulador em Java para provar que a chance era de 50%. Catch-22. O programa respondeu que era melhor trocar de porta, com aproximadamente 2/3 de chance de vencer ao fazer isso. Muito bem. A resposta passou a ser aceita, mas não se fazia ideia do porquê disso acontecer. Uns falaram em paradoxo, ainda outros em 2 respostas corretas, enfim. O programa que simulava o problema foi escrito de forma bem algorítmica, bem orientado a estatística mesmo e nada revelava sobre o insight da solução. Daí me veio a ideia de escrever um simulador com código orientado a objetos e bem fluente, de modo que o código se comunique conosco, dizendo o porquê de nossas chances aumentarem ao trocar de porta. Igual uma equação matemática ou um gráfico “falam” com a gente. Daí que surgiu a ideia do post. O ponto aqui não é recriminar as pessoas que não aceitaram a resposta do desafio, afinal de contas, eu também não aceitei de imediato.  Mas mostrar como a solução vem a tona facilmente se nos empenharmos em fazer um código que reflita o modelo de negócio de forma mais real possível. Isso se aplica ao Monty Hall Problem, ao jogo da velha que você fez no 1° período, ao sistema de GPS que você programou, ao sistema do seu banco e por aí vai.

Primeiramente, vamos entender porque a solução é realmente trocar de porta e depois vamos analisar como bom código, escrito com fluência, refletindo os requisitos do problema especificado, ajudam a entender a solução. Se você já leu até aqui, não pare agora😉

 

Exagere sempre que puder


Sempre que você se deparar com um problema de lógica, uma boa abordagem é estressar o problema. Exagere. Tanto pra mais quanto pra menos, exagere! Claro, isso vai te ajudar a pensar não só no problema ali, mas em outras versões adaptadas do mesmo. Meio que estudando o problema olhando todos os seus lados assim como alguém estuda um cubo mágico antes de tentar completá-lo.

Vos  Savant fez isso ao dar a primeira dica da solução. Imagine que você tem, não 3 portas, mas 1.000.000 delas. Um carro e 999.999 bodes. Se o apresentador abrisse todas as portas exceto a 777.777, você trocaria bem rápido, não ? Esse primeiro argumento mata a questão. Porque se você diz que não trocaria, você está dizendo que a probabilidade de você estar certo na primeira vez que escolheu 1 entre 1 milhão de portas é a mesma que a probabilidade de você acertar agora com 1 entre 2 portas!  É danado né? Você ver o apresentador abrir 999.998 portas com bodes e ainda assim você achar que a sua porta tem um carro, e não a outra, a única que ele não abriu!

A segunda dica da solução é a mais simples, Marilyn Vos Savant desenhou todas as hipóteses possíveis e a conclusão vem rápido:

Possibilidades existentes

Se você não trocar de portas, você perde 2 em 3 vezes!

Analisando o problema com Orientação a Objetos


Como falei, o algoritmo feito inicialmente para o simulador era extremamente algorítimico: utilizando arrays, números pra representar portas, o main era o programa de auditório e por aí vai. É verdade que é bem mais rápido de se fazer se você quiser apenas provar que trocar é a melhor solução. Mas não dá pra ter insight nenhum da solução olhando pra um código não OO. Por isso, implementei um código bem simples em Java que possui uma representação mais realista. Temos assim, classe Porta, classe Participante e classe Show para retratar esse problema. Veja abaixo:

public class Show {

  private List<Porta> portas;

  private Participante participante;

  public Show(int quantidadePortas) {

    this.participante = new Participante();
 
    this.portas = new ArrayList<Porta>();

    for(int i = 0; i < quantidadePortas; i++) {
      this.portas.add(new Porta(i));
    }

    Porta premiada = sortearPorta();
    premiada.setPremiada(true);
  }

  public boolean simular(boolean trocar) {
    participante.escolherQualquerPorta(this.portas);
    abrirPortas();
    if(trocar) {
      participante.trocarPorta(this.portas);
    }
    return this.participante.getPorta().premiada();
  }

  public void setPortas(List<Porta> portas) {
    this.portas = portas;
  }

  private Porta sortearPorta() {

    int numPorta = sortearNumero(this.portas.size()-1);

    return this.portas.get(numPorta);
  }

  private void abrirPortas() {

    Porta escolhida = this.participante.getPorta();

    Porta portaRestante = null;

    this.portas.remove(escolhida);

    if(escolhida.premiada()) {
      portaRestante = sortearPorta();
    }
    else {
      for(Porta porta : this.portas) {
        if(porta.premiada()) {
          portaRestante = porta;
          break;
        }
      }
    }

    this.portas.clear();
    this.portas.add(escolhida);
    this.portas.add(portaRestante);
  }

  private int sortearNumero(int maximo) {
    return (int)Math.round(Math.random()*(maximo));
  }

  public List<Porta> getPortas() {
    return portas;
  }

  public static void main(String... args) {

    int acertos = 0;

    int rodadas = 100;

    int numPortas = 3;

    for(int i = 0; i < rodadas; i++) {

      Show show = new Show(numPortas);

      boolean resultado = show.simular(true);
      if(resultado) {
        acertos++;
      }
    }

    System.out.println("Taxa de acerto: " + 100*(((double)acertos/(double)rodadas)) + "%");
  }

}

class Participante {

  private Porta porta;

  public void escolherQualquerPorta(List<Porta> portas) {
    int numPorta = (int)Math.round(Math.random()*(portas.size()-1));
    this.porta = portas.get(numPorta);
  }

  //Troca pela primeira porta que não seja a dele
  public void trocarPorta(List<Porta> portas) {
    for(Porta temp : portas) {
      if(temp.getNumero() != this.porta.getNumero()) {
        this.porta = temp;
        break;
      }
    }
  }

  public Porta getPorta() {
    return porta;
  }

  public void setPorta(Porta porta) {
    this.porta = porta;
  }

}

class Porta {

  private int numero;

  private boolean premiada;

  public Porta(int numero) {
    this.numero = numero;
  }

  public int getNumero() {
    return numero;
  }

  public void setNumero(int numero) {
    this.numero = numero;
  }

  public boolean premiada() {
    return premiada;
  }

  public void setPremiada(boolean premiada) {
    this.premiada = premiada;
  }

}

Esse é o código pra simular o resultado do problema proposto.  Por default ele está trocando de porta. Se você quiser testar sem trocar de porta basta modificar o parâmetro do método ‘simular’ para false.  Mas o propósito disso tudo é analisar esse código. Um princípio muito importante de desenvolvimento de software é a chamada “Divisão de Responsabilidades”. Cada classe tem um propósito, e apenas um. O mesmo é válido para métodos.  As classes acima possuem essa característica.  Por exemplo,  a classe Participante reproduz as ações que o participante fará durante o jogo: escolherPortaAleatoriamente() e trocarPorta(). Participante não sorteia porta ou simula o jogo de alguma forma. Quem faz isso é a classe Show, que representa o jogo como um todo.  Dessa forma, o código fica mais fácil de entender. Logo, a chave para o problema ser do jeito que é também fica na cara. Por exemplo, no problema citado, uma parte do código que me dá um bom insight do porquê da solução é:

 


Porta escolhida = this.participante.getPorta();

Porta portaRestante = null;

if(escolhida.premiada()) {
  portaRestante = sortearPorta();
}
else {
  for(Porta porta : this.portas) {

    if(porta.premiada()) {
      portaRestante = porta;
      break;
    }
  }
}

Se você observar bem, verá que esse método revela a intenção do apresentador do programa, digamos, a mente dele ao manipular as portas. Note que existem 2 portas que são escolhidas pelo apresentador para NÃO serem abertas: ‘escolhida’ e ‘portaRestante’. Ou seja, a porta escolhida pelo participante inicialmente e mais uma porta restante. Sempre teremos 2 portas ao final: uma delas é a escolhida pelo participante e a outra… bem, aí que está a ‘mágica’. Observe como a outra porta é escolhida para permanecer fechada. O apresentador do programa não escolhe por acaso! Veja que o método ‘abrirPortas’ tem acesso a informações a coisas que supostamente não era pra ter. Mas são regras do jogo! Logo, ele sabe o que está por trás das portas. Vou repetir: A classe Show tem acesso a informações encapsuladas em todas as portas – se ela esconde um bode ou um carro. Participante só tem acesso a porta que ele escolheu. Agora observe a forma como o apresentador pensa pra decidir que portas ficarão fechadas. O if-else é como se estivesse perguntando a si mesmo: “A porta escolhida pelo participante  é a premiada? Se for, vamos escolher qualquer uma outra pra ficar fechada. Caso a porta que ele esteja agora tenha um bode, abra todas EXCETO a que tem o carro.” Então há ganho de informação na passagem da primeira escolha pra segunda! E o apresentador sabe de tudo isso pelo acesso que ele tem às portas. Na primeira escolha, o participante tem 1/3 de chance de acertar. Mas na segunda, o participante deve antecipar que o apresentador sempre vai abrir uma porta com um bode. O ganho de informação se concretiza quando o participante realiza que ele está de fato trocando a chance de apostar em uma porta pela chance de apostar em duas.  E no código isso fica explícito na forma do apresentador decidir que portas serão abertas.

Ganho de informação? É. Tipo, caso um E.T aterrise no programa logo após o momento que o apresentador abriu uma porta e saiu um bode, e ele veja que existem apenas 2 portas, onde em uma delas está o prêmio, com certeza as chances serão de 50%. Mas aí que tá: ele não teve o ganho de informação obtido no momento da abertura da porta!

Modifique o atributo ‘numPortas’ no método main para 10.000 e veja como as suas chances aumentam. Isso corresponde ao primeiro argumento de Vos Savant para trocar de portas. Repare que a cada porta existente nesse caso, o apresentador irá pensar de forma a só abrir as portas com bodes. Ganho de informação multiplicado… Se eu fosse você, trocaria fácil!

Agora é com você… pronto pra colocar o Sérgio Mallandro no bolso?

Padrão

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s