Pesquisar este blog

terça-feira, 17 de maio de 2011

O Jogo da Estratégia

Em 1972, quando o jogo War foi lançado no Brasil, o panorama internacional ainda era dividido entre comunistas e capitalistas. Hoje, depois de quase três décadas de mudanças geopolíticas que levaram à criação de novos países, um dos mais clássicos jogos de tabuleiro continua entretendo várias gerações e já conta até com uma versão online. Há uma longa discussão sobre até que ponto a sorte e a estratégia contribuem para definir o vencedor em uma partida de War.

É evidente que o fator sorte é essencial, desde o sorteio do objetivo, passando pela retirada das cartas e, sobretudo, durante os ataques. Porém, se um jogador utilizar o cálculo de probabilidades para identificar as alternativas de ataque onde as chances de ganhar são maiores, terá certa vantagem em relação aos demais adversários, o que pode até compensar um eventual azar no lançamento dos dados.

Utilizo como exemplo a situação ilustrada abaixo, onde um jogador, representado pelas peças brancas, está a dois territórios de atingir seu objetivo de conquistar a Ásia e a América do Sul. A configuração do tabuleiro no início de sua jogada é esquematizada a seguir, onde as peças dos adversários são indicadas pela cor preta.


Se o jogador tem direito de colocar 7 peças antes de realizar os ataques, qual é a melhor forma de distribuí-las nos dois territórios? Seria colocar 4 peças no Brasil e 3 na Índia, tentando conquistar a Colômbia em um confronto 5x3 e o Vietnã com um confronto 4x2? Ou é melhor passar uma peça a mais para a Índia, realizando um confronto 4x3 no Brasil e outro 5x2 no Vietnã?  Em situações como esta, deseja-se descobrir, dentre todas as alternativas possíveis, aquela que leva à maior chance de vencer os confrontos.

Para entender a análise que segue, será necessário conhecer as regras dos ataques do War, além da nomenclatura por mim adotada ao longo do texto:

- um confronto do tipo AxD corresponde à tentativa de um jogador, com A peças no território de ataque, conquistar um território inimigo ocupado com D peças. Um confronto evolui através de uma sequência de “ataques”, que persistirão até que a defesa perca todas as suas peças (e o território é conquistado) ou o atacante fique só com uma peça, dita de “ocupação” (quando fracassa a tentativa de conquista do território).

- Cada ataque de “X dados contra Y” consiste no lançamento de X dados pelo atacante e Y dados pelo defensor, onde X e Y correspondem ao número de peças restantes nos territórios de ataque e defesa, descontando-se a peça de ocupação do atacante e limitando ambos os valores a um máximo de 3. Os valores obtidos nos dados do atacante e do defensor são ordenados de forma decrescente e comparados um a um, eliminando-se os valores mais baixos que sobram quando X Y. Em cada comparação, o jogador com menor valor no dado perde uma peça do território, sendo o defensor o ganhador quando ocorrer um empate. A tabela abaixo exemplifica alguns ataques:

Ataque
(X × Y)
Dados do atacante
Dados do defensor
Resultado
3 × 3
{6,3,2}
{3,3,1}
Atacante perde 1 peça e o defensor perde 2 peças.
3 × 1
{4,4,1}
{6,4}
Atacante perde 2 peças e o defensor, nenhuma.
1 × 2
{6}
{5,5}
Defensor perde 1 peça e o atacante, nenhuma.

Há diversas formas de o defensor ser derrotado. Por exemplo, em um confronto do tipo 5x3, que se inicia com um ataque de “3 dados contra 3”, o atacante pode conquistar o território adversário das seguintes formas:

A) eliminando as três peças do defensor logo no 1º ataque;
B) eliminando duas peças do defensor e perdendo uma peça no 1º ataque, e em seguida, vencendo um confronto 4x1 (que se inicia com um ataque de 3 dados contra 1);
C) eliminando uma peça do defensor e perdendo duas peças no 1º ataque, e em seguida vencendo um confronto 3x2 (que se inicia com um ataque de 2 dados contra 2)
D) perdendo 3 exércitos no 1º ataque, e em seguida vencendo um confronto 2x3 (que se inicia com um ataque de 1 dado contra 3).

Ressalta-se que cada um dos confrontos remanescentes nas opções B a D pode ainda se desdobrar em novos ataques. Além disso, em cada ataque devem ser avaliadas todas as combinações possíveis de valores para os dados lançados. Por exemplo, no ataque de 3 dados contra 3, há 66 = 46.656 combinações possíveis de resultados para os dados.

Portanto, o cálculo das probabilidades de conquista de um território requer um esforço considerável, já que a quantidade de combinações é muito grande. Tentei inicialmente realizar os cálculos no EXCEL, mas tive que recorrer a um código estruturado, com loops que permitissem varrer todas as possíveis opções e calcular as probabilidades exatas associadas a cada uma delas1. A tabela abaixo mostra as probabilidades de conquista de território pelo atacante, para 18 possíveis confrontos entre atacante e defensor, variando de 2 até 7 peças para o atacante e de 1 até 3 peças para o defensor.1

nº peças de ataque
X
nº peças de defesa
Probab. Conquista
(%)
nº peças de ataque
X
nº peças de defesa
Probab. Conquista
(%)
nº peças de ataque
X
nº peças de defesa
Probab. Conquista
(%)
2
X
1
41,67%
2
X
2
10,61%
2
X
3
1,84%
3
X
1
75,42%
3
X
2
36,27%
3
X
3
9,99%
4
X
1
91,64%
4
X
2
65,60%
4
X
3
32,76%
5
X
1
97,15%
5
X
2
78,55%
5
X
3
43,74%
6
X
1
99,03%
6
X
2
88,98%
6
X
3
55,81%
7
X
1
99,67%
7
X
2
93,40%
7
X
3
68,36%

Esta tabela serve como um “guia” para auxiliá-lo nas estratégias de ataque ou de remanejamento de peças para defesa. Através dela descobre-se que:

- No ataque 4x1 típico de início de jogo, caso um jogador persista nos ataques até conquistar o território (ou ficar com apenas 1 peça), sua chance de conquista é de 91,64%. Estas chances se reduzem para 75,42% no confronto 3x1 e, na situação mais ousada, onde se tenta conquistar o território com apenas uma peça de ataque alem da peça de ocupação (2x1), é mais provável que o atacante não conquiste o território.

- Se, ao término de sua jogada, um jogador deixar 2 peças de defesa protegendo um território, a chance de se resistir a um ataque 5x2 do próximo adversário é de 21,45%.

- Se um jogador adicionar mais uma peça de ataque em um confronto que seria originalmente do tipo 4x1, suas chances de conquista aumentarão em cerca de 5,5%. Se ele irá realizar um confronto 5x2 em outra parte do tabuleiro, seria melhor utilizar essa peça adicional de ataque nesse outro confronto, onde essa peça teria um valor “marginal” maior, pois aumentaria suas chances de conquista em mais de 10%.

Volto ao exemplo do início do texto. Como os confrontos mencionados estão localizados em diferentes partes do tabuleiro, seus resultados são independentes. Assim, a probabilidade do jogador vencer ambos os confrontos (e tornar-se o vencedor do jogo) é feita multiplicando-se as probabilidades de conquista em cada confronto. A tabela a seguir mostra as chances de se ganhar o jogo para diversas alternativas de colocação das peças.

Colocação das peças
Ataque Brasil X Colômbia
Ataque Índia X Vietnã
Probabilidade de vencer ambos os confrontos
(1)
´ (2)
Tipo de confronto
Chance de conquista (1)
Tipo de confronto
Chance de conquista (2)
4 no Brasil e
3 na Índia
5x2
78,55%
4x3
32,76%
25,73%
3 no Brasil e
4 na Índia
4x2
65,60%
5x3
43,74%
28,69%
2 no Brasil e
5 na Índia
3x2
36,27%
6x3
55,81%
20,24%

Percebe-se que a estratégia mais intuitiva, que seria a de se colocar 3 exércitos no Brasil e 4 na Índia (para, desta forma, ter uma superioridade de 2 exércitos sobre a defesa em ambos os confrontos) é, de fato, a mais adequada. Mas veja como que nem sempre a intuição ajuda: a terceira estratégia listada na tabela, onde a maior diferença entre o número de peças do atacante e do defensor (6x3) foi utilizada para atacar o território de defesa mais fortalecido, é pior do que a primeira estratégia, onde essa diferença é utilizada para atacar o outro território, menos fortalecido (5x2). Portanto, utilizando a teoria das probabilidades pode-se chegar a estratégias de jogo que sejam mais interessantes e que normalmente não seriam seguidas na prática.


1Posso enviar aos interessados os detalhes desses cálculos. Por exemplo, para cada tipo de confronto, identifiquei a probabilidade da conquista do território ocorrer perdendo-se nenhuma, 1, 2 ou 3 peças, e assim por diante. Isto pode ser útil caso queiramos responder à seguinte pergunta: “qual a probabilidade de conquistar um território em um confronto 4x1 perdendo-se no máximo 1 peça?” Neste exemplo específico, esta probabilidade é de 88,42%.

Obs: No site da Wikipédia, são listadas probabilidades de vitória para diversos ataques do jogo de War. Os valores listados nessa página NÃO são iguais aos mostrados na tabela deste texto, pois aqui calculo a probabilidade de conquista completa do território (ou seja, considerando uma série de ataques em seqüência), enquanto lá as probabilidades correspondem apenas aos ataques individuais. As probabilidades calculadas por mim para esses ataques conferem com os valores desse site.

31 comentários:

  1. A melhor estratégia é atacar apenas um, reforçar e ganhar na próxima rodada! ;)

    ResponderExcluir
  2. Cara muito bom seu post, vc joga no warnet? se me pudesse mandar os cálculos completos me ajudaria muito.... elmergu@ig.com.br Abraços

    ResponderExcluir
  3. Obrigado pelo comentário, Edson. Não jogo no Warnet não... Dei uma olhada no site, legal. Mandei a planilha EXCEL com os cálculo desse post para o seu email. Abraços!

    ResponderExcluir
    Respostas
    1. amigo poderia me mandar a tabela me ajudaria muito em um projeto

      Excluir
    2. Olá, pode me mandar a planilha para o meu email. Seria de grande ajuda.
      lucas0zamecki@gmail.com
      Obrigado

      Excluir
  4. Parabéns pelo post! Muito interessante essa ideia de obter as probabilidades de conquista de território para cada tipo de confronto.
    No começo do ano, eu também usei simulações para calcular algumas dessas probabilidades (fiz somente as probabilidades de perder x territórios em um ataque). Foi muito bom ver que alguém obteve resultados bem próximos aos meus.
    Qual foi a quantidade de simulações você usou?
    Eu também tenho interesse nessa planilha com mais resultados dessas simulações. Meu email é lucasbcr@gmail.com.
    Abraços!

    ResponderExcluir
  5. Caro Lucas,
    Obrigado pelo comentário.
    Na verdade, eu não fiz os cálculos por simulação não.
    Eu varri todas as combinações dos dados e verifiquei o resultado do ataque para cada uma dessas combinações.
    As probabilidades calculadas são, portanto, exatas.
    Abraços,
    André

    ResponderExcluir
  6. Este comentário foi removido pelo autor.

    ResponderExcluir
  7. Este comentário foi removido pelo autor.

    ResponderExcluir
  8. Ola também tenho interesse nessa planilha com mais resultados.
    Meu email é joao_carlos_nunes@yahoo.com.br
    Abraços!

    ResponderExcluir
  9. Adolfo Luiz B. Vianna17 de outubro de 2012 05:57

    Olá, André! Muito interessante esse seu post, por uma dessas coincidências da vida (e isso me lembrou um livro que acabei de ler recentemente e recomendo, "O andar do bêbado" - mas acredito que vc já o tenha lido, rs), também sou professor de matemática (do pré-vestibular social - PVS - da Fundação CEDERJ aqui no Rio), e bacharel na disciplina pela UERJ, para onde voltei há dois anos, para fazer a Licenciatura (ou seja, cursar os créditos da Fac. de Educação, basicamente). E estou há uma semana quebrando a cabeça com uma planilha que montei no Excel justamente para calcular as probabilidades envolvidas em um ataque no jogo de WAR, inicialmente trabalhando apenas com ataques de 3 exércitos contra 3. O problema é que não quero recorrer a programas, por uma questão meio boba, de "orgulho intelectual" talvez, e isso aumenta exponencialmente o trabalho, já que estou analisando, em cada um dos confrontos das 56 configurações possíveis (duas a duas), qual é a perda do ataque. Mas já cheguei a alguns resultados interessantes, como por exemplo o fato de que o Valor Esperado do ganho forma uma P.A., quando se analisa apenas as pontuações "triplas" (ou seja, 1-1-1, 2-2-2, 3-3-3, 4-4-4, 5-5-5 e 6-6-6). Bom, confesso que estou indeciso agora, isso tem me distraído tanto (amar a matemática tem dessas coisas, rs) que temo receber a planilha com tudo pronto e isso me decepcionar... Mas vá lá que seja, quero receber sim, se for possível envie-a por favor para: adolfo.vianna@gmail.com. Parabéns pelo seu site, cara! E um grande abraço!

    ResponderExcluir
  10. Adolfo Luiz B. Vianna18 de outubro de 2012 06:57

    O que acho interessante é que o meu trabalho tem um enfoque mais centrado nos ataques individuais, e não na eventual conquista de territórios. Assim, o que estou calculando são os Valores Esperados de cada possibilidade de ataque (por exemplo, se se obtém 5 - 5 - 5 nos três dados vermelhos, é de se esperar (claro, trata-se de probabilidade, portanto de uma tendência, que não necessariamente se confirma na prática) que você vença 2 combates (perdendo então 1, é claro).

    ResponderExcluir
    Respostas
    1. Obrigado pelo Interesse, Adolfo,
      Na verdade os cálculos foram feitos de forma exata, por enumeração, mas recorri a um programa em Fortran pelo grande volume de cálculos que teriam que ser realizados.
      Enviei para o seu email a planilha, qualquer dúvida entre em contato.
      Abs,
      André

      Excluir
    2. amigao me manda esta planilha adm-edinardo@hotmail.com

      Excluir
  11. Este comentário foi removido pelo autor.

    ResponderExcluir
  12. Muito bons os cálculos. Adoro jogar war. Jogo War e War 2, os melhores jogos de estratégia da Grow em www.wargratis.com.br

    ResponderExcluir
  13. Este comentário foi removido pelo autor.

    ResponderExcluir
  14. Olá, André Luiz! Muito bom o post! Tenho interesse na planilha completa, poderia enviar? gresgala-1@yahoo.com.br. Abraços!!

    ResponderExcluir
  15. Olá, gostaria da planilha completa também, poderia me enviar?
    bernardoamaral@id.uff.br
    Muito Obrigado!!

    ResponderExcluir
  16. Olá. Como você chegou no valor 9,99% no 3x3? Em meus cálculos ficou mais próximo de 12% que 10%. Os demais valores (exceto o 6x3, que se baseia no 3x3) bateram.

    ResponderExcluir
    Respostas
    1. Fiz uma simulação, e confirmei meus cálculos. A probabilidade é de 12,20%. O ataque é feito com dois dados contra três (já que o exército de ocupação não ataca). Há duas formas de ganhar o território: ganhando um, ou ganhando dois exércitos na primeira disputa. A probabilidade de ganhar dois é de 12,59%, e resulta num novo ataque de dois dados contra um, cuja probabilidade já foi calculada em 75,42%. Multiplicando, fica 9,4954%. A outra forma é cada lado perdendo um no primeiro confronto. Essa probabilidade é de 25,48%, e em seguida o confronto é de um dado contra dois, cuja probabilidade já foi calculada em sua própria tabela, e é de 10,61%. Multiplicando fica 2,7034%, que somado à primeira parcela resulta em 12,20% após os arredondamentos. Devido a essa diferença, o valor de 6x3 acabou ficando alterado também (mas não altera o resultado final do exemplo dado em seu site).

      Coloquei uma planilha em http://goo.gl/XsJ4CN (2,74 MB) em que calculei todas as probabilidades até 60x60 (a diferença é que em minha planilha não contei o exército de ocupação, de forma que o que eu chamei de 3x3 você anotou como 4x3). As probabilidades individuais dos confrontos foram calculadas de uma maneira mais simples (e mais espaçosa!), com enumeração de todas as possibilidades na própria planilha (abas individuais para cada tipo de confronto), para evitar eventuais erros de programação (e a necessidade de macros). Já as probabilidades de conquista foram calculadas de forma recursiva usando essas probabilidades de confronto pré-calculadas.

      Algumas coisas interessantes podem ser vistas. Conforme aumenta a quantidade de exércitos, a vantagem da defesa vai ficando mais evidente, de forma que num ataque de 40 contra 30 da defesa, a chance de conquistar o território é de míseros 22,82% !

      Excluir
    2. Caro Eduardo,

      De fato o cálculo do 2x3 está errado na planilha que enviei. Muito obrigado pela sua contribuição! No entanto, não encontrei o erro nos meus cálculos para o ataque 6x3: da forma como calculei, ela não depende da probabilidade de ganhar o confronto 2x3 perdendo 1 peça, que era o valor que estava errado na minha planilha. Qual o valor que você encontrou para essa probabilidade?

      Parabéns também pela iniciativa de calcular as probabilidades para uma gama maior de possibilidades. Agora você já pode se programar também para ataques astronômicos...

      Quanto ao seu comentário em ataques grande, isso segue mais ou menos a intuição que ocorre na prática, de que, quanto maior o número de peças da defesa, maior tem que ser o excedente do ataque (em valores absolutos) para ter grandes chances de ganhar.

      Grande abraço e espero que continue interessado no tema de cálculo de probabilidades.

      Excluir
    3. Refiro-me ao 6x3 em que há seis exércitos no território de ataque, com cinco atacando efetivamente. Encontrei o valor de 56,65%, e na sua tabela está 55,81%

      Seguem os cálculos com uma descrição detalhada.

      Notação: será usado ponto decimal em vez de vírgula.

      Funções:

      Seja P(x,y) a probabilidade do ataque conquistar um território quando o ataque tem x peças (incluindo o exército de ocupação) e a defesa tem y peças. Para facilitar a notação e não ter que ficar colocando condições na mesma, é útil adotar a convenção de que P(x,y)=0 quando x<2, e P(x,y)=1 quando x>=2 e y<1.

      Seja p(n,x,y) (com n>=0) a probabilidade de o ataque eliminar n peças da defesa em um confronto específico com até três dados, quando o ataque tem x peças (incluindo ocupação) e a defesa tem y. Quando n>x-1 ou n>y, obviamente temos p(n,x,y)=0. Como são no máximo 3 dados de cada lado por confronto, temos p(n,3,3)=p(n,3+k,y+m) para quaisquer k e m não-negativos.

      Seja N(x,y)=min({x-1,y,3}) a quantidade de dados a serem confrontados quando o ataque tem x peças (incluindo ocupação) e a defesa tem y. Por exemplo: N(3,3)=2, N(7,5)=3, N(2,7)=1.

      Podemos definir a probabilidade de conquista de forma recursiva:

      P(x,y) =
      p(0,x,y)*P(x-N(x,y),y) +
      p(1,x,y)*P(x-(N(x,y)-1),y-1) +
      p(2,x,y)*P(x-(N(x,y)-2),y-2) +
      p(3,x,y)*P(x,y-3)

      Essa definição recursiva foi utilizada (com pequenas alterações, pois a função N ficou implícita na montagem das fórmulas) na planilha que postei anteriormente. Pode ser usada também para o cálculo das tabelas usando programação dinâmica. Uma versão de cálculo em javascript pode ser vista em http://dudz.com.br/WAR/prob_war.html .

      A ideia dessa definição consiste em utilizar probabilidades já conhecidas, com menos peças, para calcular a probabilidade de conquista de território com a quantidade de peças desejadas. Como existem quatro resultados possíveis por confronto (perder de zero a três peças), cada caso (com sua probabilidade associada, que pode ser calculada por enumeração simples) deve ser multiplicado pela probabilidade de conquista de território com a quantidade de peças que vai sobrar em cada um dos quatro casos.

      Para o caso particular de P(6,3), temos:

      P(6,3) =
      p(0,6,3)*P(3,3) +
      p(1,6,3)*P(4,2) +
      p(2,6,3)*P(5,1) +
      p(3,6,3)*P(6,0)
      =
      0.3830*0.1220 +
      0.2647*0.6560 +
      0.2147*0.9715 +
      0.1376*1
      =
      0.5665

      Note que o valor de P(3,3) influencia no resultado, como mencionei anteriormente.

      Conferência prática, com simulações:

      Na simulação java em http://pastebin.com/XyfnAVMm fica evidenciado esse resultado, após rodar 10 milhões de simulações, resultando em "P(6,3) = 0.5664994".

      Excluir
  17. Versão no Google Docs, que não precisa do LibreOffice instalado:
    http://goo.gl/0e9hNN

    Esta versão contém apenas os resultados finais, sem a enumeração que demonstra as probabilidades dos confrontos.

    ResponderExcluir
    Respostas
    1. Obrigado por disponibilizar esse material para os interessados.
      Abraço!

      Excluir
  18. Bom comentário para questões de prova de matemática meu camarada. Pra quem joga e é bom no jogo é muito mais que simples probabilidade de dados. War se ganha na estratégia, percepção de movimentos dos adversários, blefes, alianças, tréguas e persuasão. Tudo isso faz parte da "arte da guerra". Quem não entende isso não joga bem. O cara que se convence (ou se deixa convencer )de que 6x3 estatisticamente é bom pra ele, tá frito! Quem fica na vantagem nesse caso é quem joga em seguida.

    ResponderExcluir
  19. Bom comentário para questões de prova de matemática meu camarada. Pra quem joga e é bom no jogo é muito mais que simples probabilidade de dados. War se ganha na estratégia, percepção de movimentos dos adversários, blefes, alianças, tréguas e persuasão. Tudo isso faz parte da "arte da guerra". Quem não entende isso não joga bem. O cara que se convence (ou se deixa convencer )de que 6x3 estatisticamente é bom pra ele, tá frito! Quem fica na vantagem nesse caso é quem joga em seguida.

    ResponderExcluir
  20. Pessoal!
    Não entendo muito de estatística. Mas talvez minha questão seja interessante.
    No War, quando faço uma troca e tenho mais de um território para atacar, fico em dúvida sobre quantos exércitos devo colocar em determinado território para conseguir conquista-lo.
    Ex.: Vou invadir um território que tem 15 exército. Quantos exércitos deverei colocar no meu território para "garantir" (estatisticamente) a conquista?
    Da mesma forma posso precisar defender um território prestes a ser atacado por, por exemplo, 20 exércitos. Quantos exércitos (no mínimo) deverei reforçar para "garantir" que não perderei meu território?
    Se me derem o cálculo faço uma planilha no Excel.
    Abraços a todos!!!

    ResponderExcluir
  21. Parabéns pelo site e pelo material. Há muito tempo procurava por este conteúdo. Você ainda pode enviar a planilha pro meu email?

    ResponderExcluir
  22. Olá André Luiz, gostaria de receber também os cálculos detalhados. Estou fazendo o trabalho e gostaria de dar olhada na maneira que fez. weslleymath@hotmail.com
    Obrigado.

    ResponderExcluir
  23. Olá, tudo bem? Eu gostaria muito de entender este cálculo.
    Estou fazendo um estudo em Teoria dos Jogos, e gostaria de utilizar o War para simular algumas situações por se tratar de um jogo sequencial de informações perfeitas e que apresenta certo nível de incerteza nas escolhas.

    Agradeço!

    ResponderExcluir