Olá!



Estamos em nosso primeiro ano de estudos de graduação em Matemática Aplicada e Informática no HSE de São Petersburgo. Enquanto trabalhava em um projeto de equipe semestral em C ++, decidimos escrever uma versão para computador do Intellector com um bot - um jogo de xadrez em um tabuleiro hexagonal com figuras especiais.



Neste artigo vamos falar sobre como foi o desenvolvimento do jogo, como domar um tabuleiro hexagonal, como desenhar na linha de comando e também como fizemos um bot que quase não conseguimos derrotar.







Há 3 pessoas em nossa equipe: Yura Khudyakov, Valera Golovin, Misha Savrasov. Para cada um de nós, este é o primeiro projeto da equipe, portanto, no processo de trabalho, não apenas escrevemos sobre os profissionais, mas também aprendemos a trabalhar em equipe e a usar sistemas de controle de versão (no nosso caso, git). Há uma série de esquisitices no projeto, em particular bicicletas - há boas soluções prontas que podem ser usadas. Porém, o objetivo do nosso projeto era ganhar experiência, então inventamos e implementamos muito nós mesmos.

O que é um Intellector?

Para começar, vale a pena explicar que tipo de jogo escrevemos.



O jogo "Intellector" apareceu recentemente e ainda está ganhando popularidade. O primeiro campeonato aberto foi realizado em São Petersburgo este ano .





O intelecto difere do xadrez na estrutura do campo, nas regras e no conjunto de peças. No entanto, muitos elementos são semelhantes: por exemplo, há uma figura Progressor no jogo, que atua como um peão. Ela caminha apenas para frente e pode se transformar em outra figura quando atinge a fileira extrema.



O rei aqui é uma figura chamada Intelector. O objetivo do jogo é cortar esta peça, não xeque-mate (embora seja quase a mesma coisa).



As diferenças na mecânica do jogo surgem das especificidades do campo. O campo Intelecto é simétrico, o que o distingue significativamente do xadrez com seu lado do rei e lado da rainha.



Para entender este artigo, o conhecimento das regras e a habilidade de jogar não são necessários.

Arquitetura geral

O que queremos em nosso aplicativo?

Para que o jogo funcione, você precisa implementar seu principal componente: a lógica do jogo. Inclui um modelo de tabuleiro e regras de movimentação. Além disso, por conveniência, vale a pena manter o histórico de movimentos e implementar desfazer / refazer.



O tabuleiro precisa ser exibido e permitido ao usuário jogar. Isso é feito pelo componente gráfico do jogo - a interface. Uma interface amigável deve ter menus e configurações.



Afinal, você precisa de um oponente para jogar. Decidimos fazer um bot para esses fins para que o jogador possa competir com o computador. Nesse caso, a complexidade do bot deve ser ajustável.

Plano de aplicação:

1. Lógica do jogo
   • Modelo de placa hexagonal
     
     armazenado como uma matriz bidimensional de células hexagonais
   • Regras para mover peças
     
     Verificar a validade de uma jogada, obter todas as jogadas disponíveis para uma peça, para um jogador
   • Mover histórico
     
     Desfazer e refazer um movimento
2. Interface
   
   planejada 2 interfaces: ncurses e Qt. Apenas ncurses é implementado no projeto, consulte a seção Interface para obter detalhes.
   • Exibindo um campo Renderizando
     
     e atualizando um campo no console
   • Mova o cursor com as teclas do teclado, jogue sem o mouse
   • Exibindo texto histórico de movimentos
   • Exibindo o menu principal
3. O bot
   • Bot aleatório
   • Bot ganancioso
   • Alpha-beta bot
     
     Otimizado para iterar em todos os movimentos

Como isso é feito?

Uma arquitetura de aplicativo muito simplificada é descrita por este diagrama:





A seção de jogos é responsável por toda a lógica do jogo e armazena o tabuleiro.



Quando o jogo com o computador é ligado, o Jogo interage com o bot do



Controlador do Bot , pega os dados sobre o jogo do Jogo e os transfere para a Interface para exibição aos jogadores. A Interface, por sua vez, retorna o resultado da interação do usuário de volta ao Jogo por meio do Controlador.



O link intermediário na forma de um controlador é útil quando existem várias interfaces (inicialmente planejamos fazer 2 interfaces: console e gráfica). Todos eles se comunicam com o jogo de maneira uniforme através do controle, ao invés de cada um fazer de forma diferente.

Detalhes técnicos

Modelo de jogo

Placa hexagonal

Considere a seção Jogo do diagrama acima. Ele deve armazenar o tabuleiro e lidar com toda a lógica do jogo.



Para um melhor entendimento, você pode ler o artigo do qual tiramos esta ideia.



Armazenaremos todo o tabuleiro em uma matriz bidimensional de células, cujos elementos são indexados por pares de coordenadas, (w,h)conforme mostrado na figura abaixo. Tal escolha de coordenadas parece natural, mas é inconveniente para descrever o movimento das formas (observe, por exemplo, como as coordenadas mudam ao se mover ao longo da diagonal).





^{Coordenadas das células ao longo dos eixos horizontal we verticalh}



Para a conveniência de descrever o movimento das figuras, usaremos coordenadas tridimensionais. Vamos escolher alguma célula como célula de referência com coordenadas {0,0,0}(por conveniência, ela coincidirá com a célula do (0, 0)array).





^{Coordenadas tridimensionais de células em relação à célula central com coordenadas O{0,0,0}}



deslocamento ao longo da diagonal "da direita para a esquerda, de baixo para cima" é designado pela coordenada x, o deslocamento de baixo para cima pela coordenada ye o deslocamento ao longo da diagonal "da esquerda para a direita, de baixo para cima" pela coordenada z. Ao mover para uma célula adjacente, a coordenada correspondente mudará em um. Assim, cada célula recebe três coordenadas, conforme a figura acima.



Neste caso, as células são numeradas de forma ambígua. Por exemplo, se da célula central com as coordenadas {0,0,0}movermos para a esquerda para baixo e depois para cima, obteremos as coordenadas da célula {0,1,-1}. Mas a mesma célula tem coordenadas {1,0,0}se você chegar a ela diretamente da célula central, como pode ver na figura anterior.





^{Outra opção para especificar as coordenadas da célula {1,0,0}.}



Percorrer qualquer célula em um ciclo "esquerda para baixo" - "para cima" - "direita para baixo" nos leva à mesma célula, mas adiciona um vetor às suas coordenadas {-1,1,-1}, a soma de cujas coordenadas é -1. Fazendo mentalmente esse tipo de caminhada na mesma ou na direção oposta várias vezes, podemos mudar as coordenadas de qualquer célula para outras equivalentes, que serão diferentes por um vetor proporcional {-1,1,-1}. Para se livrar da ambigüidade, em cada classe de equivalência, escolhemos como representante um triplo de coordenadas, cuja soma é igual a zero. Esta escolha de coordenadas é única (prove!).



Deixe-nos descrever mais detalhadamente o algoritmo para converter de coordenadas bidimensionais em coordenadas tridimensionais e vice-versa dentro da classe Position.

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

Observe que o construtor produz coordenadas (x,y,z)que somam zero. Neste caso, a conversão de coordenadas (x,y,z)em (w,h)funciona corretamente para qualquer conjunto de coordenadas (a soma não precisa ser zero).



Como encontramos todas essas fórmulas? Por método científico de busca: analisando a mudança nas coordenadas tridimensionais quando uma das coordenadas bidimensionais é deslocada por 1(construtor) e na direção oposta (métodos).



Usando coordenadas tridimensionais, podemos facilmente verificar se as células são colineares. Por exemplo, para verificar se duas células estão na mesma diagonal z, você precisa encontrar um vetor conectando essas células e verificar se sua classe de equivalência contém um vetor da forma{0, 0, z}... Z pode ser qualquer coisa - esse número fornece a distância entre as células. Será muito simples implementar a verificação da correção da movimentação e localizar todas as células disponíveis para a movimentação.



Em uma matriz bidimensional que representa o tabuleiro, armazenaremos informações sobre a posição das figuras. Em cada célula, se houver uma peça de xadrez, armazenaremos seu tipo e cor.



Em nossa implementação na classe de tabuleiro, armazenamos apenas os tipos de peças nas células. Precisamos de uma classe que possa encontrar todos os movimentos possíveis para as peças neste tabuleiro e verificar a exatidão dos movimentos.

Movimentos para peças

Fizemos uma classe FigureMoveValidatorque tem 6 herdeiros para cada tipo de figura (era possível prescindir de herdeiros, se em cada método fizéssemos um caso de troca para o tipo de figura). O construtor da classe possui 2 parâmetros: posição e referência da placa. Também na classe existem dois métodos allMovese checkMove.



Vamos considerar o método allMoves. Para encontrar todos os movimentos, vamos compor um array de vetores de possíveis deslocamentos e percorrê-lo. Para peças que se movem um degrau, precisamos verificar se não saltamos do tabuleiro e não entramos na célula onde está nossa peça. Para figuras que movem várias células em uma linha reta, adicione um vetor de movimento enquanto a condição anterior passa.



AgoracheckMove... Lembramos que sabemos verificar se as figuras estão na mesma linha reta. Se verificarmos que não há outras peças nesta linha, obtemos um método pronto para o Dominador (análogo da torre). Se as peças estiverem em uma linha reta, então podemos encontrar a distância entre elas e obter métodos para o Progressor (peão), Defensor (anda como um rei), Inteligência (o rei, só não pode cortar) e Libertador (pode andar de uma célula para qualquer lado). Ainda existe um agressor (um análogo de um elefante), que se move para as células diagonalmente em seis direções da atual (da célula {0, 0, 0}para {0, 1, 1}, para {0, 2, 2}, etc.: Veja as células cinzas na imagem abaixo). Para esta figura, você pode tentar zerar uma das coordenadas e verificar se as 2 coordenadas restantes são iguais em valor absoluto (graças às coordenadas tridimensionais).





^{Possíveis movimentos para o agressor}



Agora precisamos descobrir o que fazer com os movimentos. Vamos criar uma classe Move que armazenará todas as informações necessárias para a movimentação. Decidimos armazenar 2 posições e 4 peças: a posição de onde a peça se move, a posição de onde ela virá e as informações sobre quais peças estavam em cada uma dessas células e quais ficarão após a aplicação do movimento. Isso tornará mais fácil implementar o sistema de histórico de movimentação e reversão de movimentação.

Interface

Arquitetura

O aplicativo é escrito na biblioteca do console ncurses (aqui está um tutorial para ele ) . Esta biblioteca permite criar pseudo gráficos no console. Por exemplo, Midnight Commander e Nano são baseados nele .



A escolha pode parecer muito estranha: existem muitas outras bibliotecas, mais bonitas, convenientes e multiplataforma. Está relacionado com o fato de que inicialmente planejamos fazer 2 interfaces: console e gráfica. Não conseguimos escrever 2 interfaces no momento em que o projeto foi entregue e, em vez disso, criamos mais recursos na versão do console. Embora arquitetonicamente, o aplicativo ainda é projetado para interfaces diferentes.



Existem 2 entidades principais: display e controlador... Os mapeamentos mostram a imagem aos jogadores, e o controlador faz a mediação entre os diferentes mapeamentos e o modelo interno do jogo.



O display lida com todas as interações do usuário: posição e movimento do cursor, seleção de forma, destaque dos campos disponíveis, conclusão do jogo e muito mais. As ações que afetam a placa referem-se ao controlador e enviam / recebem as informações necessárias de / para o modelo.



O display cria sua própria versão do tabuleiro, mas com parâmetros adicionais necessários, como a posição do cursor e a cor das células. Esses parâmetros não podem ser adicionados ao modelo principal, pois mapeamentos diferentes precisam de parâmetros diferentes. Por exemplo, na interface do console, você precisa armazenar a posição do cursor, mas não na interface gráfica, já que a seleção e o movimento da figura são feitos com o mouse.



Eis o que acontece se um jogador quiser saber os campos disponíveis para a jogada:

1. O jogador move o cursor para o campo da figura e pressiona a barra de espaço
2. O campo com a forma está marcado como selecionado
3. A interface se refere a um método selectCellno controlador
4. Método selectCellrefere-se ao método do allFigureMovesmodelo
5. allFigureMovescria FigureMoveValidatorque calcula todos os movimentos disponíveis
6. allFigureMoves transferências encontradas voltam para o controlador
7. O controlador os passa para a interface
8. A interface redesenha o campo, destacando os campos disponíveis

^{O cursor está no meio do tabuleiro: em um quadrado azul claro. Antes de movê-lo para esta posição, o usuário selecionou uma forma. Os movimentos disponíveis são realçados em verde e a célula selecionada em si é roxa.}

Como o campo é desenhado?

A interface do console é renderizada em uma janela retangular com linhas de texto. Se você colocar símbolos nos lugares certos e colori-los, você terá uma imagem:





^{(Evil Pacman, desenhado com as letras "o")}



Uma função move(int y, int x)em ncurses muda a posição atual, e a função addch(chtype c)adiciona um caractere e muda a posição atual 1 para a direita ( x —> x+1).



Uma imagem complexa pode ser armazenada como uma matriz bidimensional e exibida linha por linha: quando a linha terminar, mova a posição atual para o início da próxima linha. O princípio é muito semelhante ao de uma máquina de escrever.



No computador do usuário, o campo em nosso jogo será colorido se o terminal suportar cores e outros atributos de texto.



Ncurses permite ao desenvolvedor alterar os atributos do texto quando ele é enviado para o console (cor, negrito, piscar). Para fazer isso, escreva no código:

attron( *attributes* );
addch(c);
attroff( *attributes* );

Cada símbolo tem sua própria cor e cor de fundo. Os consoles modernos suportam um máximo de 256 cores, então você tem que trabalhar com um conjunto limitado : bastante triste em termos de design de cores.



As imagens para saída podem ser armazenadas em código (como fizemos inicialmente) ou podem ser armazenadas em arquivos separados e lidos deles quando o programa é iniciado. Para isso, criamos nosso próprio formato de arquivo *.btn.



Ele armazena uma imagem de texto que o jogo irá ler e exibir. Por exemplo, uma forma ou a inscrição "As brancas ganham" / "As pretas ganham" ou um botão de menu. Nesse caso, às vezes você pode precisar de transparência para não sobrescrever o que foi desenhado anteriormente. Para fazer isso, você pode adicionar um hash na primeira linha #e após a lista de símbolos "transparentes" que serão ignorados na saída.



Por exemplo, digamos que temos 3 retângulos desenhados na tela:





Adicione um retângulo do seguinte arquivo ao centro:

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

E temos a seguinte imagem:





^{(destacado em amarelo para maior clareza)}



Este formato foi especialmente útil ao desenvolver menus.

Cardápio

O jogo também possui um menu que contém configurações e é desenhado antes do início do jogo e após seu término.



Os botões do menu são lidos dos arquivos *.btn. Esses botões devem ter um texto grande e bonito. Não sabemos como desenhar lindamente usando caracteres ASCII, mas figlet , um utilitário para exibir texto ASCII em fontes diferentes, pode:





Os botões enquadram os rótulos lidos do arquivo:





Eles são então centralizados e produzidos sequencialmente:





Em alguns menus, você pode falhar e, por exemplo, ajustar a complexidade e a cor do bot:





A parte mais interessante de projetar um sistema de menu é combinar seus elementos em um sistema. Isso é feito por um elemento separado do sistema, que chamamos de multiplexador. O nome é inspirado em multiplexadores de terminal .



O multiplexador aceita a tecla pressionada pelo usuário e a envia para todos os menus exibidos no momento. Cada menu decide por si mesmo o que fazer com a chave: ignorar ou processar de alguma forma. O resultado do processamento do menu é devolvido ao multiplexador, que decide o que fazer a seguir: fechar o menu, criar um novo, alterar as configurações, fechar o aplicativo ...



Esta abordagem revelou-se conveniente para as nossas necessidades, embora em geral possa não ser suficiente: 2 menus diferentes podem reagir à mesma tecla, e o usuário deve ser capaz de escolher qual menu deve reagir. A solução seria um atalho de teclado especial que permite alternar entre menus diferentes. Por exemplo, como no tmux . Mas isso é um exagero e não era necessário.

O bot

Como mencionado acima, nosso jogo possui um bot. Tentamos torná-lo interessante tanto para um iniciante quanto para um jogador experiente.



Antes de descrever os bots, gostaria de falar sobre alguns detalhes de implementação. Atribuímos algum peso a cada forma. Quanto maior for, mais valiosa será esta figura. Determinamos o quão boa é uma posição no tabuleiro usando a fórmula (soma dos pesos das peças brancas) - (soma dos pesos das peças pretas). É benéfico para o branco maximizar esta expressão e para o preto minimizar.



Um cálculo completo de toda a árvore de movimentos é uma tarefa muito difícil, então nós calculamos apenas os primeiros movimentos (olhando para frente, direi que acabou sendo calculado 6 movimentos à frente). Consideramos todos os estados no tabuleiro em uma certa profundidade como folhas da árvore de travessia.



Existem três tipos diferentes de bots no jogo:

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

Quando começamos a fazer experiências com otimizações, percebemos que não poderíamos passar sem testes de unidade para o bot, então criamos um irmão gêmeo para AlphaBetaBot'a', que nomeamos OptimizedAlphaBetaBot. Testamos todas as ideias de otimização OptimizedAlphaBetaBote os testes de unidade ajudaram a garantir que os dois irmãos gêmeos encontrassem o mesmo movimento útil. RandomBot nos serviu bem, gerando padrões aleatórios no quadro. Para isso, bastava pedir RandomBote ir várias dezenas de vezes para os dois lados.



No total OptimizedAlphaBetaBot , 3 otimizações principais foram implementadas (aqui, elas são apresentadas em ordem decrescente de utilidade):

• Usando rollbacks. Após essa otimização, não era mais necessário copiar o tabuleiro muitas vezes para fazer uma jogada.
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

Além de grandes otimizações, também houve outras menores. Por exemplo, se, antes da classificação, você calcula todos os valores das posições no tabuleiro, levando em consideração uma determinada jogada, então você não precisa mais classificar objetos complexos Move, mas simplesmente ints.



Inicialmente, foi planejado implementar vários conjuntos de funções de avaliação: por exemplo, uma figura ameaçada por um inimigo é estimada pela metade do custo. Mas descobriu-se que o bot joga de forma bastante "limpa", perdendo poucas peças, então uma simples quantidade acabou sendo mais eficaz.



No entanto, a arquitetura do bot ainda suporta a adição de novas funções de avaliação. Para fazer isso, você precisa definir apenas três coisas:

1. Função se você precisar calcular o custo "do zero" para um determinado arranjo de figuras
2. Função delta, que deve recalcular rapidamente o custo de um determinado movimento.
3. O número desse conjunto de funções para o construtor da classe personalizada FunctionSet.

Você pode ativar a batalha de bots e assistir o processo.





^{Um jogo de 2 bots com a mesma dificuldade (nível 4 de 6 possíveis). O cursor fica no centro do campo durante todo o jogo}

Conclusão

Implementamos um jogo semelhante ao xadrez, mas com regras diferentes e um tabuleiro incomum. Nossa implementação tem espaço para se expandir. O próprio Intellector também está se desenvolvendo e mudando: recentemente houve uma atualização das regras, que ainda não suportamos em nosso aplicativo. Por exemplo, agora você não pode cruzar a linha central nas 2 primeiras voltas.



Além disso, existem várias funcionalidades que planejamos inicialmente, mas não conseguimos implementar até o momento do projeto. Por exemplo, neste aplicativo, eu realmente gostaria de ver um jogo em rede. Além disso, uma boa interface de plataforma cruzada, por exemplo, no Qt, não faria mal.



Talvez tudo ou parte disso apareça em um futuro próximo. Até então, obrigado pela leitura!



Repositório Github