Hackenbush

Hackenbush

Um jogo simples partesan é o jogo de Hackenbush. Há duas cores: A é preto, B é vermelho. Dada uma figura como na Figura 1, A pode apagar qualquer vara preta; B qualquer vara vermelha. Se algo ficar desconexo do chão, é eliminado também. Hackenbush é um jogo partesan, já que preto e vermelho têm alternativas de jogo distintas.

Figura 1

Olhe a Figura 1 e analisemos as alternativas. Suponha que A comece. Se A eliminar sua vara ‘1’, B responde eliminando a sua vara ‘1´’ e, já que as demais varas ficariam sem contato com o chão, elas sumiriam também, com o resultado de vitória para B (por ser último a jogar).

Por outro lado, se A eliminar vara ‘2’, B ainda pode responder e garantir vitória, se bem de modo mais complicado: B elimina ‘2´’, A, sem escolha, elimina ‘1’ e B responde com ’1´’, ganhando de novo. Assim, se A começar, B garante vitória, seja como A jogar.

Se B começar, ele pode eliminar ‘2´’, levando junto a vara preta ‘2’. A, novamente sem opção, tira ‘1’ e B responde com ‘1´’. Logo, se B começar, B ainda garante vitória. Se associarmos um valor positivo à vitória de A e valor negativo à vitória de B, a Figura 1tem de todo modo um valor negativo – pois seja quem começa a partida, B pode garantir vitória. (para uma explicação disso, vá à página Apresentação).

Para entender melhor a questão de decisões práticas ao jogar certa partida de Hackenbush, vamos primeiro ver como calcular com maior precisão o valor de uma configuração em Hackenbush. A configuração de valor zero descreve a situação indicada na Figura 2a: quem começa, perde (por exemplo, situação vazia ou então, de duas varas simples, uma de cada cor). Diremos que a configuração é positiva e de valor x se der x jogadas de vantagem para A; idem, porém negativa, se for para B. Neste sentido, se houver k varas pretas simples e h varas vermelhas, o valor é k - h.

Na Figura 2b temos uma configuração cujo valor declaramos como igual a ½. Justificamos este valor fracionário mostrando que, se chamamos o valor de 2b de x, temos na Figura 2c uma configuração cujo valor é 2x – 1 e que simultaneamente tem valor 0. O fato de 2x – 1 = 0 justifica a avaliação de x = ½.

Figura 2a

Figura 2b

Considere a configuração 2c. Suponha que jogador A comece, eliminando ou vara 1 ou vara 2. Então vara a ou b é eliminada também, uma das quais permanece. Jogador B responde eliminando a vara que sobrou: a ou b, e volta a ser a vez de jogador A. Este não tem mais escolha, elimina a vara que lhe resta, e B responde eliminando a vara c, ganhando o jogo. Logo o valor da configuração inicial é menor ou igual a zero, já que não há nenhuma vantagem para A (positivo).

Se o jogador B começar a partida, ele começa eliminando a vara a ou b. Jogador A responde, eliminando a vara 1 ou 2 que ainda tem vara vermelha anexa – pois isso sempre será melhor de que deixar uma vara vermelhaa mais para seu adversário. O Jogador B volta a agir, eliminado a vara c. A conclui e ganha o jogo, eliminado a vara que lhe resta. Logo o valor da configuração é maior ou igual a zero.

Estas duas opções levam-nos a dizer que o valor da configuração é zero – ou seja, quem começa o jogo, perde – e isso implica que a configuração em Figura 2b vale ½. Existe um método exato de determinar o valor de uma configuração – apesar de às vezes não ser nem um pouco fácil de implementar! Vejamos este método no caso de Hackenbush.

Na Figura 2b há duas possibilidades, podendo jogar primeiro ou A ou B. Jogador A deseja que o valor da configuração após a sua jogada seja o maior possível, ou seja, de preferência positivo e quanto maior melhor. JogadorBdeseja o contrário: que tenha o menor valor possível. Escrevemos à esquerda os valores das configurações que jogadas de A podem induzir. À direita escrevemos os valores que as várias possíveis jogadas de B podem criar. Em 2b é muito simples, com somente uma opção para cada jogador. O valor da configuração é o número “mais simples” maior de que o maior valor à esquerda e menor de que o menor à direita. Assim, resulta em { 0 | 1 }, que como vimos vale ½.

Figura 3 Em Figura 3 a técnica pode ser usada também. Se A jogar o valor é zero; se B jogar primeiro assume o valor ½.Valor { 0 | ½ } => igual a ¼. Repetindo o cálculo várias vezes podemos avaliar configurações mais complicadas. Jogos partesans mais raramente têm configuraçõesde valores fuzzy. O Hackenbush acima não tem. Isso é mais comum em jogos imparciais.

Para ver um exemplo com valores fuzzy, vá à página sobre Hackenbush Infantil ou Kayles.