Baixe o Projeto AQUI!
O jogo da Senha, originalmente conhecido por “Master Mind”, foi apresentado à indústria de jogos e entretenimentos (não eletrônicos) em 1970.
O jogo basicamente consiste de um tabuleiro com, normalmente, quatro furos grandes, onde se posicionam os pinos de código, além de, normalmente, quatro furos menores onde se posicionam os pinos de chave.
Os pinos de código são coloridos, num conjunto finito de cores. Os pinos de chave são pretos ou brancos.
O objetivo é descobrir uma senha secreta, composta de uma sequência não repetitiva de pinos de código, na base de tentativa e erro.
Para cada tentativa o jogador recebe uma resposta através dos pinos de chave. Basicamente uma de três informações diferentes lhe são passadas a respeito de cada um dos seus pinos de código.
a) O pino não faz parte da senha, e neste caso uma casa vazia é mostrada no espaço dos pinos de chave.
b) O pino faz parte da senha, mas está numa posição incorreta, e neste caso um pino de chave branco é colocado em algum furo.
c) O pino compõe a senha e está posicionado no seu local correto, e assim um pino de chave preto vai surgir como resposta.
Note que não há qualquer relação entre as posições ocupadas pelos pino de chave e de código. Tipicamente se reservam os primeiros furos para possíveis pinos pretos, e em seguida os pinos brancos e finalmente os furos que restam vazios.
O Projeto.
Basicamente temos um alfabeto, composto de uma sequência de diferentes caracteres ASCII, que representarão os pinos de código. Ao invés de cores, caracteres. Além disso, o tamanho do quebra-cabeças também é variado (no jogo de tabuleiro são sempre quatro pinos de código).
O sistema já está pronto, e pode ser baixado aqui. Ocorre que, infelizmente, ele implementa um agente resolvedor que executa testes aleatórios, embora não repetitivos, até que encontra uma solução. Não parece ser a escolha mais adequada.
O seu trabalho é implementar uma estratégia mais inteligente, que naturalmente resolva o problema com menos tentativas. Idealmente é interessante que sua solução funcione para qualquer alfabeto, e qualquer tamanho de quebra-cabeças. Mas inicialmente é satisfatório trabalhar com o alfabeto dos algarismos decimais (0 a 9) e senhas de tamanho igual a 5.
Detalhes do sistema.
O sistema, que segue com testes de unidade, pode ser baixado aqui.
Para executá-lo é necessário configurar um arquivo com os parâmetros de operação. Estes parâmetros são três: ALPHABET, que é uma String com os diferentes caracteres que representarão os pinos de código, PUZZLESIZE, que é o tamanho do quebra-cabeças, ou seja, de quantos caracteres do alfabeto será composta a senha e SOLVER_TYPE, que indica o tipo de resolvedor que será instanciado para que se resolva o problema. Junto com o sistema já está disponível o resolvedor aleatório descrito acima, e ele será instanciado caso a opção para este parâmetro seja RANDOM.
Junto com o sistema segue um arquivo de parâmetros para exemplo.
Para executar é necessário se invocar a classe de fachada. Basicamente isso pode ser feito usando o comando (execute-o a partir do diretório bin).
java facade.Facade <arquivo_de_parametros> <número de execuções>
Invocado assim, o sistema irá gerar um jogo a partir dos parâmetros definidos em <arquivo_de_parametros> e instanciará um resolvedor (também definido em <arquivo_de_parametros>) que resolverá o problema um certo número repetido de vezes (definido em <número de execuções>). Estas múltiplas execuções permitirão aproximar mais os resultados de médias comparativas a fim de aferir o desempenho de diferentes métodos de resolução do problema.
Informações críticas.
Dentro da classe MasterMind há um método instanciateSolver, que permite facilmente a criação de diferentes objetos para resolver o problema. Uma nova opção no arquivo de parâmetros, um novo teste e um novo objeto criado e... voilà!
Cada objeto que vai resolver o problema deve implementar a interface Solver (padrão de projeto Strategy), e portanto o método public int solve(), que recebe um conjunto de caracteres (os que compõem o alfabeto), o tamanho do quebra-cabeças e um objeto do tipo Answer.
Cada jogo (Instância da classe MasterMind) possui um objeto do tipo Answer que armazena a senha secreta que deve ser descoberta. Este objeto pode ser “consultado”: o método answer.analyze() recebe uma String e a compara com a solução do problema, retornando outra String com uma sequencia de letras “b” (de Black), “w” (de White) ou “o”. Esta String representa a resposta dos pinos de chave: furo com pino preto (“b”), com pino branco (“w”), ou vazio (“o”).
Um objeto do tipo Answer também responde se uma dada String é a solução correta (método correct()).
Avaliação.
Você deverá implementar seu resolvedor de acordo com as especificações acima. Idealmente seu resolvedor deverá funcionar para qualquer alfabeto e qualquer tamanho de quebra-cabeças válido. Mas inicialmente pode-se trabalhar com o alfabeto “0123456789” e desvendar senhas de tamanho igual a 5.
Cada consulta feita (answer.analyze()) a fim de encontrar a sequência correta deve ser contada, e o desempenho de um método será melhor quanto menos consultas ele fizer para resolver o problema.
Você deve preparar um experimento para mostrar que seu método é melhor do que o RandomSolver que segue implementado junto com o projeto.
Você deve redigir um pequeno artigo descrevendo seu método, o experimento que foi realizado, e os resultados obtidos.
Faça avaliações estatísticas (pode considerar um erro com intervalo de confiança de 95%) para provar que seu método é melhor que o RANDOM, e quanto.
Note que sua análise precisa ficar robusta, para que a qualidade de seu solver possa ser comparado aos demais!
Faça considerações a respeito de uma comparação entre seu método e o RandomSolver. Faça considerações a respeito dos resultados: porque melhorou? Porque não melhorou mais (se for o caso)? Que alternativas poderiam (se for o caso) ser tentadas para melhorar ainda mais seus resultados? Porque?
Boa Sorte!