Geekly articles weekly

Dagaz: Fora do nevoeiro

imagem Tudo isso é a rainha da rainha Mab.
Ela tece nos estábulos de uma crina
E o cabelo derruba um emaranhado ...

William Shakespeare

Foi um lançamento longo, mas muito foi feito. Um gerente de sessão apareceu , permitindo reverter movimentos feitos por engano. Em alguns lugares, o design de som foi adicionado. E, no entanto, criei uma maneira legal de oferecer várias opções alternativas para a colocação inicial em um jogo. E o mais importante - finalmente cheguei aos jogos com informações incompletas.

Vou explicar o que está em jogo. Nos jogos de tabuleiro habituais, como xadrez ou damas , os jogadores, a qualquer momento do jogo, têm informações completas sobre a localização das peças (próprias e do oponente), as regras para movê-las, os objetivos do jogo etc. Esses jogos são muito bem estudados e se enquadram na categoria de " jogos com informações completas ". Agora, imagine que algumas dessas informações possam estar ocultas do player.


The Fog of War é uma ótima ilustração do tema. De acordo com as regras do “ Blind Chess ”, os jogadores não podem ver todas as peças do inimigo, mas apenas as que são colocadas nos campos, que podem ser alcançadas com um movimento de qualquer uma das suas peças. Fiz duas adições a esta regra:

  1. Obviamente, o jogador sempre vê suas peças, mas pela maneira como são exibidas - na forma normal ou translúcida, ele pode julgar se o oponente as vê.
  2. Apenas para fins decorativos, coloquei “nuvens” em áreas atualmente invisíveis.

Tendo dominado o princípio geral, fiquei um pouco empolgado e fiz um grande número de jogos com o "nevoeiro da guerra". Além do próprio Xadrez , tenho opções "sombrias" para Xiang , Changi , Shatrange , Sittuyin e muitos outros jogos. Existe até um " Blind Guns "! Todos esses jogos têm uma coisa em comum:

O computador está trapaceando!
Nem tentei fazer alterações nos algoritmos dos bots para esses jogos, porque apostei que condições desiguais compensariam pelo menos parcialmente o jogo extremamente fraco em comparação aos humanos. Como escrevi anteriormente, o desenvolvimento de IA de alta qualidade para jogos de tabuleiro é uma tarefa muito difícil. Obviamente, as regras têm exceções. Mesmo com um jogo muito fraco do bot, será difícil para uma pessoa jogar um jogo desconhecido, literalmente cheio de armadilhas. O que podemos dizer sobre sua versão "sombria"

No entanto, em geral, essa não é uma abordagem muito correta. Eu quero ver um bot que possa fazer exatamente com os dados que seu adversário possui - homem. Por que isso é importante? Tudo é muito simples - pela maneira como o bot toca, às vezes é muito fácil adivinhar se ele tem acesso a informações ocultas (espreitadelas) ou não. E, claro, é muito mais interessante para uma pessoa brincar com esse bot que não espia (brincar com outra pessoa é ainda mais interessante, mas essa é uma história diferente).

E aqui vale a pena escolher um jogo um pouco diferente do xadrez (já que não estou pronto para desenvolver um bot "honesto" jogando xadrez "às cegas"). Existem muitos desses jogos e não se pode dizer que eles são mais simples que xadrez ou damas. Eles são apenas diferentes e requerem uma abordagem individual.

Por exemplo
Há um jogo infantil com o qual ainda não consegui desenvolver um bot. É chamado de "Selva" ou Dou Shou Qi . O objetivo do jogo é penetrar no território inimigo. Cada um dos jogadores tem um "den" - um campo central na primeira linha. Se alguma das figuras do inimigo entrar no covil, ele venceu (você não pode ocupar o covil com suas próprias figuras).


Os números são ordenados por antiguidade. O elefante vence todas as figuras, seguido por: Leão, Tigre, Leopardo, Cachorro, Lobo, Gato e Rato. Um rato pode vencer apenas um elefante e outro rato; além disso, esta é a única figura que pode se mover na água (no meio do tabuleiro existem dois reservatórios). Um tigre e um leão podem pular sobre a água, mas apenas se o rato não bloquear a água. Com exceção dos saltos, todas as figuras se movem da mesma maneira - para um campo adjacente vertical ou horizontalmente. O covil é cercado por armadilhas. A figura na armadilha é vulnerável a qualquer figura inimiga.

Como você pode ver, as regras são bem simples. O que impede o desenvolvimento de um bot para este jogo? Primeiro de tudo, os números de baixa velocidade. Se houver ameaças, eu aprecio os benefícios das trocas, mas, na maior parte do jogo, as peças simplesmente rodam uma após a outra por longas distâncias. Não posso ver o jogo para um grande número de jogadas adiante (devido a restrições na duração do cálculo da jogada), como resultado das quais as alterações ficam fora do horizonte de visualização e todas as jogadas se tornam equivalentes para mim.

Para começar, decidi me concentrar no BanQi - Chinese Blind Chess. Este é um jogo muito original, com informações ocultas, semelhante ao "Jungle". É importante para mim que os desenvolvimentos, em conexão com a criação de um bot para este jogo, possam ser usados ​​em outros jogos, como Dou Shou Qi , Luzhan Qi , Stratego ou mesmo (possivelmente) Tafl .


Vou falar sobre as regras. O jogo corre na metade do tabuleiro para "Xadrez Chinês" ( Xiang Qi ), enquanto o layout original do tabuleiro não desempenha nenhum papel. As peças são colocadas dentro das células (como nas tradicionais), e não nas interseções de linhas (como no xadrez chinês). No início do jogo, todas as peças são completamente misturadas e colocadas no tabuleiro com a face para baixo (uma vez que as peças tradicionais de Syants são algum tipo de barril, e seu número coincide com o número de campos na metade do tabuleiro, isso não é difícil).

Em seguida, os jogadores alternam seus movimentos. Executando um movimento, o jogador pode inverter qualquer uma das peças fechadas ou mover uma peça da sua cor aberta anteriormente. As cores dos jogadores são determinadas pelo primeiro movimento. Se a primeira peça preta for aberta, o jogador que a abriu jogará em preto. Todas as figuras do jogo seguem o mesmo caminho (com exceção do "Cannon" na versão de Taiwan, que discutirei mais adiante) - em uma célula adjacente vertical ou horizontalmente. A possibilidade de tomada é determinada pela ordem de antiguidade das figuras:

Geral> Conselheiro> Elefante> Carroça> Cavalo> Canhão> Soldado

Figuras mais antigas são mais jovens ou iguais a elas, com uma exceção: um soldado atinge o general (uma espécie de " Pedra-Papel-Tesoura "). Resta dizer algumas palavras sobre o BanQi de Taiwan:

  1. Ao contrário da versão chinesa, no Taiwan BanQi, um general não pode vencer um soldado.
  2. O canhão se move de acordo com as regras do XiangQi , ou seja, para qualquer número de campos ortogonais em baixa velocidade (como uma carruagem) ou atinge qualquer figura inimiga, pulando a "carruagem" ao executar um movimento de ataque.

Existe também uma versão de Hong Kong, mas praticamente não é diferente da chinesa, exceto que a ordem de antiguidade dos números foi alterada. Decidi me concentrar na versão taiwanesa das regras, como a mais interessante taticamente.

O que devo procurar ao desenvolver um bot?
Em primeiro lugar, o jogo parece muito simples, mas não é. Mesmo se você não considerar as nuances associadas às armas de Taiwan, o custo dos números é contra-intuitivo. Embora o "Conselheiro" possa superar menos números que o "General", ele é o principal protagonista do jogo. Em primeiro lugar, o jogador tem dois conselheiros. Além disso, apenas um general inimigo tem força superior a cada conselheiro, enquanto o general pode ser atacado por até cinco soldados! Pela mesma razão, o custo de um soldado em um jogo é superior ao custo de um general. No final, ele pode vencer a figura mais forte! A segunda consideração importante sugere um dos quebra-cabeças "Canterbury" de Henry Dudeney.


Isso é mais uma tarefa de brincadeira do que um quebra-cabeça completo. Todas as figuras podem ir para um campo adjacente vertical ou horizontalmente. O branco se move primeiro, enquanto o branco e o preto sempre fazem dois movimentos (em peças diferentes)! Nessas condições, o bufão esquerdo nunca pode pegar o burro esquerdo e o bufê direito nunca pode pegar o burro direito (você pode verificá-lo). Obviamente, o bobo da corte direito pode pegar o burro esquerdo sem nenhuma dificuldade. É tudo sobre paridade!

Esse problema me deu alguns pensamentos. Em primeiro lugar, a tarefa do bot, em jogos como BanQi ou DouShouQi, é, antes de tudo, encontrar o caminho mais curto. A partir de cada uma das peças ativas (a própria ou a do oponente), é necessário construir cadeias de movimentos para todos os objetivos possíveis (incluindo as próprias peças, para calcular possíveis trocas). Depois disso, as cadeias precisam ser avaliadas e as seguintes opções são possíveis aqui.

  1. A figura atacante vence a atacada - uma cadeia lucrativa (bônus) estimada pelo custo da figura atacada (menos o custo da figura atacante, se esta estiver protegida), levando em consideração o comprimento da cadeia.
  2. A figura atacante vence a atacada - não uma cadeia lucrativa (penalidade), estimada pelo valor da figura atacante.
  3. As peças se batem (por exemplo, são iguais) - aqui tudo depende da paridade, as cadeias ímpares são vantajosas e as pares devem ser consideradas penalidade (se não houvesse outras figuras em campo, a paridade determinaria completamente o resultado do jogo).

Claro, nem tudo é tão simples. No mínimo, você deve se lembrar do curso específico dos canhões no BanQi de Taiwan (quanto à “Selva”, existem casos ainda mais especiais), mas é aqui que você pode começar. Com um conjunto completo de cadeias avaliadas, você pode avaliar movimentos. O custo da mudança deve consistir no custo das cadeias (bônus e grátis), cuja duração é reduzida.

Primeiro de tudo, é importante entender que é improvável que seja possível usar efetivamente algoritmos minimax aqui. Movimentos que revelam peças ocultas anteriormente mudam radicalmente a estimativa de posição. Não havendo informações sobre peças ocultas, é quase impossível visualizar uma posição com muitos movimentos à frente. Mas toda nuvem tem um lado positivo, mas podemos usar heurísticas muito mais complexas (em termos de computação) para avaliar os próprios movimentos!

Eu já tenho um bot que avalia os movimentos de acordo com sua heurística (necessária para um jogo divertido). Este é um algoritmo muito simples. Todas as jogadas são classificadas em ordem decrescente por heurística (as jogadas com um valor heurístico negativo são geralmente descartadas), após as quais são varridas em ordem. Se o próximo movimento levar a uma posição da qual não há resposta do inimigo, levando a uma vitória imediata, o bot o considera o melhor. Usando esse algoritmo, você não pode se preocupar com a estimativa de posição, mas precisa se preocupar com as heurísticas .

Primeiro de tudo, construímos cadeias
var getChains = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.chains)) { board.chains = []; var pieces = getGoals(design, board); var targets = getTargets(design, board, pieces); _.each(pieces.positions, function(pos) { var goals = pieces; var f = true; var piece = board.getPiece(pos); if (piece === null) return; if (!chinese && (piece.type == 12)) { goals = targets; f = false; } var group = [ pos ]; var level = []; level[pos] = 0; for (var i = 0; i < group.length; i++) { if (_.indexOf(goals.positions, group[i]) >= 0) { //  ... } if ((i > 0) && (board.getPiece(group[i]) !== null)) continue; _.each(design.allDirections(), function(dir) { p = design.navigate(board.player, group[i], dir); while (p !== null) { if (_.indexOf(group, p) >= 0) break; group.push(p); level[p] = level[ group[i] ] + 1; if (f || (board.getPiece(p) !== null)) break; p = design.navigate(board.player, p, dir); } }); } }); } return board.chains; }

Obviamente, eu armazeno em cache todos os dados intermediários no estado do jogo, para não lê-los várias vezes. Além disso, um truque é usado aqui, o que é muito útil no cálculo de áreas conectadas. Eu itero sobre a matriz do grupo , colocando elementos adicionais dentro dela no loop, conforme necessário. Todas as dificuldades estão associadas às armas. Para eles, os objetivos das cadeias não são as figuras em si, mas os campos dos quais as últimas podem ser atacadas.

As cadeias são avaliadas exatamente como eu disse
 var getChainPrice = function(design, board, attacker, attacking, len) { var player = board.getValue(board.player); if ((player === null) || (attacker == null) || (attacking === null)) return 0; if (attacker.player == attacking.player) return 0; var isAttacking = isAttacker(design, attacker.type, attacking.type); var isAttacked = isAttacker(design, attacking.type, attacker.type); if (!chinese && (attacker.type == 12)) { isAttacking = true; isAttacked = (attacking.type == attacker.type) && (len == 1); } var price = 0; var f = (len % 2 == 0); if (attacker.player != player) f = !f; if (isAttacking) { if (isAttacked) { price = f ? (len - design.price[attacker.type]) : (design.price[attacking.type] - len); } else { price = design.price[attacking.type] - len; if (f) price = (price / 2) | 0; } } else { if (isAttacked) { price = len - design.price[attacker.type]; } } return price; }

... dependendo do comprimento e da paridade da cadeia, bem como levando em consideração os custos dos números atacantes e atacados. Mas isso é apenas metade da batalha! É necessário avaliar cada um dos movimentos possíveis usando as correntes construídas. Eu apresento mais uma estrutura intermediária - deseja agregar os dados disponíveis. A avaliação do curso consiste em avaliações de desejos, que satisfazem:

Algo assim
 var addWish = function(board, comment, price, src, dst) { if (_.isUndefined(board.wish[src])) { board.wish[src] = []; } if (_.isUndefined(dst)) dst = src; if (_.isUndefined(board.wish[src][dst])) { board.wish[src][dst] = price; } else { board.wish[src][dst] += price; } } var getWish = function(design, board) { if (_.isUndefined(board.wish)) { ... } return board.wish; } Dagaz.AI.heuristic = function(ai, design, board, move) { var wish = getWish(design, board); if (move.isSimpleMove() && !_.isUndefined(wish[ move.actions[0][0][0] ]) && !_.isUndefined(wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ])) { return wish[ move.actions[0][0][0] ][ move.actions[0][1][0] ]; } return 0; }

Quanto à função getWish em si , a mágica começa aqui (e este é o lugar onde eu provavelmente arado mais de uma vez). Antes de tudo, compartilho a avaliação dos movimentos com base em informações abertas e na introdução de novas peças no jogo. Isso não está totalmente correto, mas até agora não sei como conciliar opiniões tão diversas. Se com base em informações abertas, nenhum desejo foi formado, o bot tenta abrir novas figuras (também existem alguns truques aqui).

  1. Se um canhão inimigo estiver aberto, cercado por figuras fechadas, faz sentido abrir uma das figuras ao lado, pois é provável que ele possa atacar a arma, e a arma não será capaz de vencê-la, em qualquer caso.
  2. Se uma figura diferente de um canhão estiver aberta, você pode tentar abrir uma figura localizada através do "carro", pois há uma chance de que seja um canhão.
  3. Se houver uma corrente de ataque do lado do inimigo, uma das peças pode ser aberta, ao lado da corrente, para interceptar o ataque.
  4. Se você não conseguir proteger a figura, poderá abrir a figura ao lado, tentando reduzir a situação a uma troca.

Obviamente, é útil avaliar a probabilidade de abrir uma figura específica.
 var getShadow = function(design, board) { var player = board.getValue(board.player); if (player === null) return []; if (_.isUndefined(board.shadow)) { board.shadow = []; _.each(design.allPositions(), function(pos) { var piece = board.getPiece(pos); if ((piece !== null) && (piece.type < 7)) { var value = piece.type + 7; if (piece.player != player) { value = -value; } board.shadow.push(value); } }); } return board.shadow; } var isFriend = function(design, x) { return x > 0; } var isPiece = function(design, x, y) { return x == y; } var isAttacker = function(design, x, enemy) { if (x < 0) return false; if ((x == 13) && (enemy == 7)) return true; if (!chinese && (x == 7) && (enemy == 13)) return false; if (!chinese && (x == 12)) return false; return x <= enemy; } var isDefender = function(design, x, enemy, friend) { if (!isAttacker(design, x, enemy)) return false; return design.price[friend] <= design.price[enemy]; } var estimate = function(design, board, p, y, z) { var shadow = getShadow(design, board); if (shadow.length == 0) return 0; var r = 0; _.each(shadow, function(x) { if (p(design, x, y, z)) r++; }); return (100 * r) / shadow.length; }

O jogador pode avaliar as probabilidades acompanhando os números que desistiram do jogo. Em princípio, o bot pode fazer o mesmo, mas existe uma maneira mais fácil - observar os números ainda não abertos a granel e avaliar a probabilidade de abrir o desejado com base nas informações coletadas. Além disso, o sucesso do movimento selecionado não é garantido, mas se a probabilidade de um resultado favorável for baixa, o movimento não será selecionado.

Em princípio, a abordagem valeu a pena, mas ainda há trabalho a fazer.
Enquanto movimentos defensivos não são muito bons. Algumas figuras enfrentam bravamente o inimigo mais forte, em vez de fugir dele (embora, em geral, fugir do caso deles já seja inútil). Além disso, há dificuldades em coordenar as ações de várias figuras (isso pode ser útil para "dirigir" os remanescentes das figuras inimigas). A abordagem em si parece muito promissora, mas as heurísticas ainda precisam ser consideradas.

Heurísticas baseadas em "cadeias" de movimentos podem ser úteis não apenas no BanQi, mas também em muitos outros jogos, com predominância de peças "lentas" (se não como um critério de definição, em seguida, para uma avaliação preliminar da qualidade dos movimentos em algoritmos mais complexos, pelo menos menos). Essa abordagem é especialmente requisitada nos jogos para os quais o uso de algoritmos minimax é difícil ou mesmo impossível (como Yonin Shogi , por exemplo).


Claro, vou continuar trabalhando em jogos com informações incompletas. A imagem mostra o " Jogo dos Generais " das Filipinas, ainda não pronto. Este é o jogo mais fácil de uma família numerosa, incluindo jogos como LuzhanQi e Stratego . E, claro, ainda espero fazer um bot de trabalho para o " Jungle "!

E para aqueles que ainda estão me lendo, posso oferecer outro jogo divertido com informações ocultas:


Toquei na infância, em uma calculadora programável chamada Fox Hunt. Oito raposas são aleatoriamente escondidas no campo, que devem ser encontradas usando o “método de puxão”. Quando você seleciona uma área vazia, o número total de raposas nas oito direções é exibido. É impossível perder, mas você pode competir pelo número mínimo de cliques. E se você toca com fones de ouvido, diminua o som. Talvez eu tenha exagerado com efeitos sonoros.

Source: https://habr.com/ru/post/pt422427/

More articles:


All Articles