Fórum PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Probabilidade - Vampiros

2 participantes

Ir para baixo

Probabilidade - Vampiros Empty Probabilidade - Vampiros

Mensagem por LucasIME Ter 02 Out 2012, 17:02

Um problema muito legal que eu vi quando estava estudando para Olímpiada de Programação:

Felipinho está empolgado com seu novo jogo de RPG sobre guerras entre clãs de vampiros. Nesse jogo ele representa um personagem de um vampiro e constantemente entra em conflito contra vampiros de outros clãs. Tais batalhas são realizadas com base nas características de cada personagem envolvido e com a ajuda de um dado comum de seis faces.

Por simplicidade, vamos considerar apenas as lutas entre dois vampiros, vampiro 1 e vampiro 2. Cada um possui uma energia vital (chamaremos de EV1 e EV2 respectivamente) e, além disso, são determinadas uma força de ataque AT e uma capacidade de dano D.

O combate é realizado em turnos da maneira descrita a seguir. A cada turno um dado é rolado, se o valor obtido for menor do que ou igual a AT , o vampiro 1 venceu o turno, caso contrário o vampiro 2 é quem venceu. O vencedor suga energia vital do adversário igual ao valor D, ou seja, D pontos de EV são diminuídos do perdedor e acrescentados ao vencedor. O combate segue até que um dos vampiros fique com EV igual a ou menor do que zero.

Por exemplo, suponhamos que EV1 = 7, EV2 = 5, AT = 2, D = 4. Rola-se o dado e o valor obtido foi 3. Nesse caso, o vampiro 2 venceu o turno e, portanto, 4 pontos de EV são diminuídos do vampiro 1 e acrescentados ao vampiro 2. Sendo assim, os novos valores seriam EV1 = 3 e EV2 = 9. Observe que se no próximo turno o vampiro 2 ganhar novamente, o combate irá terminar.

Os valores de AT e D são constantes durante todo o combate, apenas EV1 e EV2 variam.

Apesar de gostar muito do jogo, Felipinho acha que os combates estão muito demorados e e gostaria de conhecer de antemão a probabilidade de vencer, para saber se vale a pena lutar. Assim, ele pediu que você , dados os valores iniciais de EV1 , EV2 , além de AT e D, calculasse a probabilidade de o vampiro 1 vencer o combate.
LucasIME
LucasIME
Fera
Fera

Mensagens : 262
Data de inscrição : 22/03/2011
Idade : 27
Localização : Rio de Janeiro

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por aprentice Ter 02 Out 2012, 20:02

A probabilidade do vampiro 1 atacar é:
P[v1] = AT/6
Então, segue que a probabilidade do vampiro 2 atacar é:
P[v2] = 1 - AT/6
O número de ataques que seria fatal para ambos os vampiros é:
x = ⌈EV2/D⌉
y = ⌈EV1/D⌉
Para o vampiro 1 ganhar:
v1 ataca x vezes
v2 ataca y-1 vezes ou y-2 vezes ou ... ou 0 vezes

A probabilidade de um ramo onde y deixa de atacar k vezes é dada por:
P[k] = ((P[v1])^x)*(P[v2])^(y-k)
A quantidade de ramos desse tipo é dada por:
Q[k] = (x + y - k)!/x!(y - k)!

Então a probabilidade do vampiro 1 ganhar é dada por:
P = Q[1]P[1] + Q[2]P[2] + Q[3]P[3] + ... + Q[y]P[y]

Sou péssimo em probabilidade.Está ligeiramente certo?
É possivel simplificar a partir desse ponto e chegar na resposta final?
aprentice
aprentice
Jedi
Jedi

Mensagens : 355
Data de inscrição : 28/09/2012
Idade : 27
Localização : Goiânia - Goiás - BR

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por LucasIME Ter 02 Out 2012, 20:27

Seu raciocínio está parcialmente correto, so que você esqueceu de uma coisa:

Quando um vampiro da dano D no outro, a vida ele próprio aumenta em D. Isso vai mudar drasticamente (para mais difícil =P) o problema. Assim não vamos ter mais um número total K de rodadas máximo para a partida terminar. E agora? =0

PS: Ja respondi sua MP.
LucasIME
LucasIME
Fera
Fera

Mensagens : 262
Data de inscrição : 22/03/2011
Idade : 27
Localização : Rio de Janeiro

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por aprentice Qua 03 Out 2012, 00:14

Amanhã vou tentar de novo.
Tá com cara de Bayes e algum raciocinio envolvendo ataques seguidos... ' - '

Edit: arreguei. : |
aprentice
aprentice
Jedi
Jedi

Mensagens : 355
Data de inscrição : 28/09/2012
Idade : 27
Localização : Goiânia - Goiás - BR

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por LucasIME Sab 06 Out 2012, 16:55

Solução:

Spoiler:


Bem, antes de mais nada, repare que os casos em que D > 1 podem ser
reduzidos para um caso D = 1 (não é difícil verificar isso). Então
vamos supor que o caso já foi reduzido para D = 1.

Seja N = EV1+EV2 (iniciais). Seja o estado i a quantidade de EV do
vampiro 1. Então quando ele chega em i = N ele venceu, mas se chegar
em i = 0 ele perdeu.

Seja P[i] a probabilidade de o vampiro 1 chegar ao estado N estando no
estado i. Nesse caso temos, obviamente, que P[0] = 0 e P[N] = 1.

Seja p a probabilidade de o vampiro 1 vencer uma rodada. Como ele
precisa tirar AT ou menos para isso, então p = AT/6. A probabilidade
de ele perder, logicamente, é 1-p.

Sendo assim, P[i] = (1-p)P[i-1] + pP[i+1]

Repare que p + (1-p) = 1, logo

(p + (1-p))P[i] = (1-p)P[i-1] + pP[i+1]
pP[i] + (1-p)P[i] = (1-p)P[i-1] + pP[i+1]

Rearrumando:

pP[i+1] - pP[i] = (1-p)P[i] - (1-p)P[i-1]
p(P[i+1] - P[i]) = (1-p)(P[i] - P[i-1])
P[i+1] - P[i] = ((1-p)/p)(P[i] - P[i-1])

Ora, sabemos que P[0] = 0, então

P[2]-P[1] = ((1-p)/p)(P[1]-P[0])
P[2]-P[1] = ((1-p)/p)P[1]

Continuando:

P[3]-P[2] = ((1-p)/p)(P[2]-P[1])
P[3]-P[2] = ((1-p)/p)((1-p)/p)P[1]
P[3]-P[2] = [((1-p)/p)^2]P[1]


Fazendo isso para os demais termos, percebemos que:

P[i]-P[i-1] = P[1]((1-p)/p)^(i-1)


Ora, se adicionarmos os i-1 primeiros termos, teremos:

(P[2]-P[1])+(P[3]-P[2])+...+(P[i]-P[i-1]) = P[i]-P[1] = P[i] *
somatório(j de 1 a i-1)((1-p)/p)^j

Ou seja:

P[i]-P[1] = P1[((1-p)/p) + ((1-p)/p)^2 + ... + ((1-p)/p)^(i-1)]
P[i] = P1[((1-p)/p) + ((1-p)/p)^2 + ... + ((1-p)/p)^(i-1) + 1]

Se p = 1/2, então temos ((1-p)/p) = 1 e, portanto:

P[i] = iP1

Caso p != 1/2, essa série converge para:

P[i] = P[1] * [(1 - ((1-p)/p)^i) / (1 - (1-p)/p)]


Sabemos que P[N] = 1, então temos que
P[N] = NP[1] => P[1] = 1/N para p = 1/2
P[1] = (1 - (1-p)/p) / (1 - ((1-p)/p)^N) para p != 1/2


Substituindo P[1] na fórmula, chegamos a

P[i] = i/N para p = 1/2
P[i] = (1 - ((1-p)/p)^i) / (1 - ((1-p)/p)^N) para p != 1/2

Solução de: Pedro Demasi

LucasIME
LucasIME
Fera
Fera

Mensagens : 262
Data de inscrição : 22/03/2011
Idade : 27
Localização : Rio de Janeiro

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por aprentice Dom 07 Out 2012, 01:24

Muito bom!
Tinha esboçado esse raciocinio, mas jurava que não era bem por ai.
aprentice
aprentice
Jedi
Jedi

Mensagens : 355
Data de inscrição : 28/09/2012
Idade : 27
Localização : Goiânia - Goiás - BR

Ir para o topo Ir para baixo

Probabilidade - Vampiros Empty Re: Probabilidade - Vampiros

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo


 
Permissão neste fórum:
Você não pode responder aos tópicos