E02 Dados generalizados
Um dado generalizado \(D\) é uma $k$-upla de inteiros $(a_0, ..., a_{k-1})$. O resultado $r$ de um lance de $D$ é uma das faces $i$ de $D$, escolhido uniformemente ao acaso dentre todos as possibilidades; isto é, se $i$ é um dos valores de $0$ a $k-1$, então o resultado $r$ é igual a $i$ com probabilidade $1/k$. Supomos também que, quando lançamos $D$ várias vezes, todos os resultados são independentes. Naturalmente, quando lançamos o dado $D$, estamos interessados no valor resultante, isto é, o valor $a_r$ escrito na face resultante $r$.
Exemplos. O dado usual é $D = (1, ..., 6)$. Cada um dos valores de $1$ a $6$ ocorre como o valor resultante do lance de $D$ com probabilidade $1/6$. Um exemplo diferente é o dado $D = (1, 1, 2, 3)$. Nesse dado, o valor resultante é $1$ com probabilidade $1/2$, enquanto que os valores $2$ e $3$ tem probabilidade $1/4$ cada um.
Jogo elementar. Alice e Bob jogam o seguinte jogo elementar: Alice tem um dado generalizado $D_A$ e Bob tem um dado generalizado $D_B$. Alice e Bob lançam seus dados, obtendo valores $v_A$ e $v_B$, respectivamente. Alice ganha se $v_A > v_B$ e Bob ganha se $v_B > v_A$. Se $v_A = v_B$, o jogo é declarado empate.
Escreva um programa java, chamado CompareDice.java, que pode ser usado para estimar a probabilidade de Alice vencer esse jogo. Seu programa deve receber os dados generalizados $D_A$ e $D_B$ como entrada e deve simular o jogo entre Alice e Bob várias vezes para estimar a probabilidade de vitória $p_A$ de Alice. Seu programa deve receber, também como entrada, o número de vezes $T$ que o jogo deve ser simulado para se obter a estimativa para $p_A$.
Suponha que $D_A = (1, 2, 3)$ e $D_B = (1, 1, 3, 3)$. Para estimar $p_A$, simulando o jogo $1000000$ vezes, você executaria seu programa como segue:
$ java CompareDice 3 1 2 3 4 1 1 3 3 1000000
Seu programa deve ter a saída como nos exemplos de execução abaixo:
$ java CompareDice 3 1 2 3 4 1 1 3 3 1000000
A: 1 2 3
B: 1 1 3 3
Number of A wins: 332869
Number of B wins: 333230
Probability that A wins: 0.4997290192598998
$ java CompareDice 3 1 2 3 4 1 1 3 3 1000000
A: 1 2 3
B: 1 1 3 3
Number of A wins: 333311
Number of B wins: 332914
Probability that A wins: 0.500297947390146
$ java CompareDice 4 1 2 2 2 3 1 1 3 1000000
A: 1 2 2 2
B: 1 1 3
Number of A wins: 499721
Number of B wins: 333244
Probability that A wins: 0.5999303692231966
O jogo dos dados generalizados. O jogo dos dados generalizados é como segue. Temos um conjunto de dados generalizados $D_1$, $D_2,\dots$ à disposição de Alice e Bob. Alice e Bob examinam esse conjunto e decidem, de alguma forma, quem será o 1o. jogador e quem será o 2o. jogador. O 1o. jogador escolhe um dos dados disponíveis $D_a$ como sendo seu dado. O 2o. jogador, conhecendo o dado $D_a$ escolhido pelo 1o. jogador, escolhe um dado $D_b$ dentre os dados restantes. Aí eles jogam o jogo elementar usando seus respectivos dados.
Exemplo. Suponha que os dados disponíveis são
D_1 = (1, 2, 3),
D_2 = (1, 2, 2),
D_3 = (2, 2, 3).
Você preferiria ser o 1o. jogador ou você preferiria ser o 2o. jogador? Se você prefere ser o 1o. jogador, qual dado você escolheria? Um pequeno raciocínio mostra que é melhor ser o 1o. jogador e escolher o dado D_3.
O jogo entre Alice e Bob. Alice e Bob recebem a seguinte lista de dados generalizados:
D_1 = (2, 6, 7),
D_2 = (1, 5, 9),
D_3 = (3, 4, 8).
Suponha que Bob permite a Alice escolher se ela será o 1o. jogador ou se ela será o 2o. jogador. O que ela deve fazer? Use seu programa para decidir a estratégia de Alice.
Entrega. Você deve entregar seu programa CompareDice.java. Além disso, você deve entregar execuções de seu programa que dizem à Alice o que ela deve fazer no jogo entre ela e Bob acima. Diga explicitamente como Alice deve proceder.