Dagaz: Um novo começo

Corre para o sul e circula para o norte, circulando, circulando para correr com o vento
E de acordo com seus circuitos, o vento retorna;
Todos os rios correm para o mar - e o mar não transborda,
Para o lugar onde os rios correm, - Lá eles continuam correndo;

O livro de Eclesiastes

Em 1998, foi desenvolvida uma aplicação completamente única, para a época, que permite reduzir o processo de desenvolvimento de um jogo de tabuleiro abstrato (ou quebra-cabeça) para uma linguagem de descrição de texto pequena, que lembra vagamente o Lisp . Este projeto foi chamado de Zilhões de Jogos . Isso criou um furor entre os fãs de jogos de tabuleiro. Atualmente, mais de 2.000 aplicativos foram criados usando essa tecnologia.

Logo ficou claro que o ZoG tem muitas desvantagens. Eu já escrevi sobre isso em Habr e não vou me repetir. Permitam-me apenas dizer que os desenvolvedores não levaram em conta os recursos de um grande número de jogos existentes e algumas opções importantes foram codificadas, de modo que suas alterações se tornaram extremamente problemáticas. Greg Schmidt, em 2007, tentou corrigir a situação lançando o Axiom Development Kit , mas sua forte integração com o ZoG não permite resolver todos os problemas.

O Projeto Ludi apontou novas fronteiras, usando o “mecanismo” universal de jogos e algoritmos genéticos para automatizar o processo de desenvolvimento de novos jogos de tabuleiro. Infelizmente, essa abordagem foi inicialmente vista como uma simplificação deliberada da mecânica do jogo e do nível da IA ​​empregada. A discussão dos objetivos deste projeto está além do escopo deste artigo, mas algumas de suas soluções técnicas, sem dúvida, serviram como ponto de partida para meu próprio desenvolvimento.

Meu objetivo é o desenvolvimento de um "mecanismo" mais versátil e fácil de usar para a criação de jogos de tabuleiro abstratos. Por quase um ano, estudei a possibilidade do ZoG e do Axiom e aprendi bastante sobre suas limitações. Penso que posso resolver os problemas criando uma solução mais universal e multiplataforma. Sobre o andamento dos trabalhos deste projeto, apresentarei um relatório.

Abertura e modularidade

Talvez a principal desvantagem do ZoG seja o seu fechamento. O produto foi montado "de uma vez para sempre" em uma única plataforma - Windows. Se fosse código de código aberto, poderia-se tentar portá-lo no Linux, Android, iOS ... Outro problema é o seu monolítico.

No ZoG, há o início da modularidade, permitindo a conexão com a DLL dos jogos, incluindo implementações personalizadas da IA. O Axiom vai um pouco mais longe, permitindo que você execute aplicativos no modo de reprodução automática, sem usar o kernel ZoG. Não obstante a séria limitação desta solução (suportando aplicativos apenas para dois players), este exemplo demonstra como a modularidade seria útil! A oportunidade de organizar um jogo com dois bots (usando diferentes configurações de IA) e coletar estatísticas sobre um grande número de jogos não pode ser superestimada. Mas quão melhor seria se o produto fosse totalmente modular!

• Mover módulo de geração
• Mover módulo de execução
• Módulo de controle
• Módulo AI
• Módulo de visualização

Todo o trabalho que descreve os jogos deve ser realizado pelo módulo de geração de movimento. Este é o "coração" do projeto. A transferência de todas as tarefas não conectadas a esta função para outros módulos tornará a tarefa mais simples possível. Você pode melhorar este módulo, sem examinar os problemas de IA e a interação do usuário. Você pode alterar completamente o formato da descrição dos jogos ou adicionar suporte para as descrições no formato ZoG, Axiom e Ludi. A modularidade é a base da flexibilidade da solução!

O módulo de execução de movimentação é o guardião do estado do jogo. As informações sobre o estado atual do jogo são transferidas para todos os outros módulos sob demanda. Pelas razões que apresentarei abaixo, o progresso da execução deve passar pelo módulo de geração, cuja tarefa é a formação de um comando em termos de execução do módulo. Além disso, a tarefa do módulo de geração de movimento é a configuração principal do espaço do jogo, com base na descrição do jogo.

O módulo de controle é, de fato, o próprio aplicativo. Ele solicita ao módulo de geração de movimentos uma lista de movimentos possíveis e altera o estado do jogo, passando o movimento selecionado para o módulo de execução de movimentos. O módulo de controle pode ser conectado para reproduzir um ou mais bots de IA. Quantas você precisar (e possivelmente diferente)! O tipo de unidade de controle é determinado pela divisão de tarefas. Pode ser uma reprodução automática para coletar estatísticas de jogos, servidor de jogos (ele pode controlar várias lojas de estado, liderando um grande número de sessões de jogos) ou aplicativos individuais para jogar offline.

A capacidade de conectar diferentes implementações de IA melhorará a qualidade do jogo. Entende-se que os módulos para o jogo de xadrez e Go devem usar abordagens diferentes. Jogos com informações incompletas e jogos usando dados aleatórios também exigem uma abordagem individual. A implementação universal da IA ​​será igualmente ruim em todos os jogos! A conexão modular AI permitirá comparar a "força" dos algoritmos, incluindo um modo de jogo "entre si". Como a arquitetura da AI é separada do estado de armazenamento do jogo, uma instância do bot de jogo pode suportar um número ilimitado de sessões de jogos simultaneamente.

A visualização do processo do jogo também pode variar. A primeira coisa que vem à mente são implementações 2D e 3D. A plataforma para a qual o aplicativo está sendo desenvolvido também é importante. Menos óbvio é que a visualização pode ser uma parte importante do jogo! Por exemplo, no jogo Surakarta , pegar peças será completamente não óbvio na ausência de animação adequada dos movimentos.


Em geral, a modularidade parece uma boa idéia para esse projeto, e o código-fonte aberto permitirá a todos que desejam participar do projeto. No momento, não me proponho fins comerciais, mas acho que, se desejado, encontrarei uma maneira de ganhar dinheiro sem fechar o código-fonte.

O espaço do jogo

Antes de iniciar o show, você precisa definir o cenário. O tabuleiro não é apenas um lugar onde as peças são organizadas. Além disso, a direção do movimento das peças pode ser determinada (de fato, as conexões entre as posições do tabuleiro) áreas de jogo (por exemplo, áreas de conversão de peças) campos proibidos, etc. Aqui está como a definição do tabuleiro de xadrez se parece na implementação do ZoG:


Você pode perceber que, além das configurações do jogo, aqui estão as configurações associadas à visualização. Estou firmemente convencido de que essas configurações não pertencem aqui. Na implementação de um módulo de visualização, várias configurações podem ser usadas e diferentes configurações podem ser necessárias. Além disso, jogos de simulação podem funcionar sem qualquer módulo de visualização (como a reprodução automática no Axiom). De fato, como o Axiom é usado para visualizar o ZoG, a definição não contém nada de supérfluo:


Infelizmente, o Axiom também não tem como determinar as zonas de jogo (o local das zonas de jogo deve ser determinado manualmente no código). Esta não é a única simplificação do Axiom. A definição do quadro neste projeto não pode conter mais de uma grade e essa grade deve ser bidimensional. A placa, assim definida, é uma matriz unidimensional, mas para a conveniência do programador, sinônimos são definidos para cada um dos espaços da seguinte maneira:


Comparadas com o esquema mais flexível de definição de grade no ZoG, essas restrições são bastante desconfortáveis ​​(especialmente devido ao fato de o esquema de nomeação imposto ter usado esses campos para o próprio objetivo de visualização). Felizmente, é possível definir um quadro de forma arbitrária. Tanto o Axiom quanto o ZoG oferecem uma oportunidade para identificar elementos em cada posição no quadro, além da capacidade de determinar os vínculos entre pares arbitrários de posições. Usando essa abordagem, podemos definir uma placa de qualquer topologia. Sua única desvantagem é a extrema verbosidade e complexidade da descrição.

Além da localização das peças no tabuleiro e na reserva, o sistema deve ter a capacidade de armazenar atributos para peças individuais e para os espaços no tabuleiro. Um bom exemplo da necessidade de usar os atributos de uma regra de " rolar " no xadrez . É uma jogada difícil, que inclui o movimento simultâneo do rei e uma torre permitida, desde que nenhuma dessas peças tenha se movido antes de executar essa jogada. Um atributo pode ser usado para armazenar uma tag booleana mostrando se a peça já foi movida. Os atributos do campo também podem encontrar algumas aplicações interessantes.

Deve-se notar que os atributos não são apenas variáveis, mas parte do estado do jogo. Um valor de atributo pode ser alterado pela execução de um turno (inclusive pelo módulo AI) e deve estar disponível para todos os turnos subsequentes, mas não para turnos realizados em outro ramo do jogo. Atualmente, o ZoG suporta o armazenamento de atributos booleanos de peças. Os atributos de armazenamento do axioma não são suportados, mas você pode adicionar à definição do quadro uma descrição das variáveis ​​e matrizes. Essas variáveis ​​podem ser usadas, como contadores da quantidade de peças capturadas:

 {board 5 18 {grid} {variable} WhitePieces {variable} BlackPieces board} 

Outra limitação do ZoG e do Axiom é a regra de que cada posição do conselho não pode conter mais do que uma peça. Se qualquer peça concluir um movimento para uma posição ocupada por outra peça, a peça que anteriormente ocupava a posição é automaticamente considerada como "comida". Essa regra vai bem com o princípio do "xadrez" de pegar peças e serve para simplificar a descrição desse jogo, mas complica a implementação de jogos como " bashni checkers " e " tavreli ".



Nestes jogos, as peças podem ser organizadas em "colunas". Essa "coluna" pode ser movida todos juntos, como uma única peça. Após algumas reflexões, decidi que era melhor não abandonar a implementação automática da captura “Xadrez”, mas melhorar os mecanismos de movimentação de grupos de peças. De fato, para a implementação dos “pilares”, você sempre pode adicionar para abordar outra dimensão (isso é especialmente fácil, desde que o módulo de visualização esteja separado do módulo de geração de movimento e da IA, você pode usar qualquer lógica que seja para renderizar a placa tridimensional em sua visualização bidimensional). Um argumento adicional a favor dessa decisão foi que o movimento de peças “com muita pilha” não é o único tipo de viagem em grupo. Por exemplo, no cartão “ Pentago ”, os fragmentos podem ser girados juntos com as peças montadas no mesmo.


Resumindo, posso dizer que, para minha estrutura de jogos, decidi pegar o melhor que foi pensado em ZoG, Axiom e Ludi, e acrescentar o que, na minha opinião, não tiver.

Mover geração

A geração de movimento é semelhante à programação não determinística . A tarefa do gerador de movimentos é fornecer, mediante solicitação, uma lista de todos os movimentos possíveis da posição atual. Qual movimento dessa lista será selecionado por um jogador ou a IA não é sua função. Vamos ver como a geração de movimentos é feita no ZoG. Como exemplo, usamos a macro de geração de movimento para uma peça de longo alcance (uma rainha ou bispo). É assim que é usado na determinação de movimentos para essas peças:

 (piece (name Bishop) (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp" Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp") (moves (slide ne) (slide nw) (slide se) (slide sw) ) ) 

Como parâmetro, uma macro é passada na direção do movimento no quadro. Se você não considerar a possibilidade de instalar novas peças no quadro, a geração de uma mudança parecerá simples. Para cada uma das peças no tabuleiro, todos os movimentos possíveis de acordo com as regras são calculados. Então a mágica começa ...

Cada uma das definições pode adicionar à lista uma série de movimentos possíveis! A adição de uma jogada à lista é feita com o comando add (ao mesmo tempo, posicionando cada peça em movimento no quadro). Eu já escrevi sobre como essa solução arquitetônica é extremamente ruim. O comando para a formação do movimento deve ser separado dos comandos que manipulam as peças (como foi feito no Axiom). Vamos ver como a macro funciona:

 (define slide ( $1 (while empty? add $1 ) (verify not-friend?) add )) 

Primeiro, o deslocamento é realizado por uma célula, na direção especificada, depois, em um ciclo, o espaço atingido é verificado quanto à ausência de peças, um movimento é formado e o arranjo prossegue para outra célula na mesma direção. Se você parar por aqui, a peça pode "deslizar" pelas células vazias, mas como você pode pegar as peças inimigas?

Muito simples! Depois de executar o comando check, a verificação de que o campo não é ocupado por uma peça amigável, formamos outro comando add, concluindo a movimentação. Se nesta célula estiver localizada uma peça inimiga, ela será capturada automaticamente (como em um espaço do tabuleiro, ao mesmo tempo, você não poderá ter mais de uma peça). Se a peça foi amigável, o cálculo da movimentação será interrompido com o comando verificar (a violação das condições especificadas neste comando termina imediatamente o cálculo da movimentação atual).

No ZoG e no Axiom, é possível mover apenas as próprias peças (ou melhor, é possível mover as peças do oponente, mas somente se especificado no modo de cálculo de um movimento de uma das peças). Considero isso uma restrição extremamente inconveniente, porque existem muitos jogos em que você pode mover diretamente a peça do oponente (em " Stavropol Chequers ", por exemplo). Seria mais consistente executar o cálculo da movimentação de todas as peças, independentemente de sua afiliação. Na macro que determina a movimentação, seria necessário adicionar apenas uma verificação para permitir mover apenas as próprias peças:

 (define slide ( (verify friend?) $1 (while empty? add $1 ) (verify not-friend?) add )) 

Importante é a capacidade de executar um movimento que consiste em vários movimentos "parciais". Nas implementações de rascunhos, essa capacidade é usada para realizar capturas em "cadeia":

 (define checker-jump ($1 (verify enemy?) capture $1 (verify empty?) (if (not-in-zone? promotion-zone) (add-partial jumptype) else (add-partial King jumptype) ) ) ) 

O comando de movimentação parcial é formado com add-parcial (para este comando, assim como para o comando add, há uma variação da movimentação, com “transformação” das peças). Esse movimento é sempre parte de um movimento maior e "composto". Como regra, para movimentos subsequentes, é definido um "modo", que a continuação deve implementar. Portanto, nas damas, uma captura pode continuar apenas com as seguintes capturas, mas não com um movimento "suave" (sem captura).


Esse sistema de descrição das regras é muito flexível, mas às vezes é necessária uma lógica mais complexa. Por exemplo, se a peça, durante o progresso "parcial", não deve passar novamente por um campo atravessado anteriormente, é lógico usar as bandeiras associadas às posições no quadro. Depois de visitar um espaço, definimos uma bandeira, para que posteriormente não volte a esse espaço:

 (verify (not-position-flag? my-flag)) (set-position-flag my-flag true) 

Além de sinalizadores "posicionais", no ZoG você pode usar sinalizadores globais. Esses recursos não devem ser confundidos com os atributos das peças. Ao contrário do último, estes não fazem parte do estado do jogo. Infelizmente, os atributos de peças e sinalizadores no ZoG podem ser apenas booleanos (no Axiom, os atributos nem são suportados). Essa limitação dificulta a execução de operações associadas aos vários tipos de contagem. Por exemplo, neste pequeno quebra-cabeça, eu tive que usar para "contar" peças, presas em um "garfo", um par de bandeiras booleanas (o número exato de que eu não precisava, desde que as peças fossem mais de uma).

Outra coisa a corrigir é a falta de um "ciclo de vida" claro na execução da mudança. Todos os sinalizadores são redefinidos automaticamente antes de iniciar a movimentação, mas seria mais fácil identificar claramente a fase de inicialização. Na minha opinião, no cálculo da mudança, devem ocorrer as seguintes fases:

1. Inicialização de variáveis ​​e verificação de pré-condições para a movimentação composta
2. Inicialização de variáveis ​​e verificação de pré-condições para a movimentação parcial
3. Geração do movimento parcial
4. Verificando pós-condições da movimentação parcial
5. Gerando, concluindo e verificando pós-condições da movimentação composta
6. Verificando as condições de término do jogo

O grupo de etapas do segundo ao quarto, no movimento composto completo, pode ser repetido várias vezes. A ideia de pré e pós-condições, que chamo de invariantes, tirei do projeto Ludi. Falo mais sobre o uso de invariantes posteriormente.

Sobre a importância da notação

A geração de todos os movimentos possíveis a partir da posição é apenas metade da história. Controlar o estado do jogo requer uma apresentação compacta dos movimentos gerados. No ZoG, para esse fim, a notação ZSG é usada. Aqui está uma descrição de um possível início de um jogo de xadrez desta forma:

 1. Pawn e2 - e4 1. Pawn e7 - e5 2. Knight g1 - f3 2. Knight b8 - c6 3. Bishop f1 - c4 3. Knight g8 - f6 4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0 4. Pawn d7 - d5 5. Pawn e4 x d5 5. Knight f6 x d5 

Este script é próximo à notação usual de xadrez e geralmente amigável ao usuário. Apenas o quarto movimento das brancas pode causar alguma confusão. Assim, no ZSG, parece um roque . A parte da descrição do movimento antes do caractere '@' é bastante clara; é o movimento simultâneo da torre e do rei, mas o que se segue? Assim, no ZSG, parece que é necessário redefinir os atributos das peças para evitar a possibilidade de repetição do enrolamento.


A gravação de um movimento na notação ZSG deve conter informações completas suficientes para alterar corretamente o estado do jogo. Se as informações sobre uma mudança de atributos forem perdidas, em um jogo de acordo com esse registro, uma jogada pode ser repetida incorretamente (por exemplo, o jogador teria a oportunidade de executar novamente o jogo). Infelizmente, nas extensões DLL (como Axiom), informações estendidas não podem ser transmitidas.

Trabalhando com extensões DLL, o ZoG é forçado a fazer uma manipulação bastante esperta ao se posicionar em um movimento selecionado (por exemplo, quando você reverte um movimento). A partir de [cada] posição anterior [trabalhando desde o início do jogo], todos os movimentos possíveis são gerados e, nessa lista, é preciso procurar um movimento com a representação ZSG [correspondente]. Os [efeitos colaterais de cada] movimento gerado são aplicados a [cada sucessivo] jogo, pois é possível executar efeitos colaterais não refletidos na representação ZSG do movimento.

A situação é agravada pelo fato de que a única maneira de chegar ao estado do jogo no momento de uma jogada no passado, é a aplicação consistente de todas as jogadas desde o início do jogo até o estado inicial do tabuleiro. Em casos realmente complexos , esse tipo de navegação não ocorre rapidamente. Outra desvantagem da notação ZSG pode ser ilustrada pela gravação da seguinte jogada no jogo Go :

 1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19 

Aqui, na posição G19, é colocada uma pedra branca que captura um grupo de pedras negras. Como todas as peças envolvidas no desempenho da colocação devem ser mencionadas no desempenho do ZSG, o registro do turno pode parecer muito longo (em Go, uma queda pode capturar até 360 pedras). Para o que isso pode levar, escrevi anteriormente . O tamanho do buffer alocado para gravar a movimentação do ZoG pode não ser suficiente. Além disso, se por algum motivo a ordem de remoção das pedras mudar (no processo de desenvolvimento do jogo acontece), uma tentativa de aplicar uma jogada, de uma antiga ordem de capturas, falhará.

Felizmente, existe uma maneira simples de lidar com todos esses problemas. Vejamos como definir movimentos de peças no ZRF:

 (piece (name Pawn) (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp" Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp") (moves (Pawn-capture nw) (Pawn-capture ne) (Pawn-move) (En-Passant e) (En-Passant w) ) ) 

Os nomes de movimentos, definidos nas macros do ZoG, são inacessíveis como um gerador de movimentos. Mas o que nos impede de desistir de macros e fazer descrições dos movimentos com seus nomes? Aqui está como o registro pareceria um jogo de xadrez:

 1. e2 - e4 Pawn-move 1. e7 - e5 Pawn-move 2. g1 - f3 leap2 n nw 2. b8 - c6 leap2 n ne 3. f1 - c4 slide nw 3. g8 - f6 leap2 n nw 4. e1 - g1 OO 4. d7 - d5 Pawn-move 5. e4 x d5 Pawn-capture nw 5. f6 x d5 leap2 w nw 

Os benefícios desse registro não são óbvios, mas têm uma vantagem importante. Todas as jogadas são descritas de maneira uniforme e essas descrições não contêm nada extra (os nomes das descrições das jogadas, é claro, poderiam ser mais "descritivos"). Na descrição do castling, conseguiu-se se livrar das mudanças de atributos e da descrição da jogada da torre (essa descrição não depende mais dos detalhes de implementação da jogada). Uma utilidade ainda mais clara de tais registros existe no caso do jogo Go:

 1. G19 drop-to-empty White Stone 

E é isso aí! Se as pedras do oponente forem retiradas de acordo com as regras do jogo, não há necessidade de listá-las todas na descrição do movimento. É suficiente indicar o espaço inicial e final do deslocamento (possivelmente com um sinal a ser utilizado), o nome do movimento em execução e a linha de parâmetros passados ​​a ele. Obviamente, para executar um movimento de acordo com esta descrição, para decodificar, é necessário acessar o módulo de geração de movimento, mas o ZoG faz isso!

Outra possibilidade, a qual se deve apoiar, aparece na funcionalidade dos movimentos "parciais". Aqui está um exemplo de " damas russas ":

 1. Checker g3 - f4 1. Checker f6 - g5 2. Checker e3 - d4 2. partial 2 Checker g5 - e3 = XChecker on f4 2. Checker e3 - c5 = XChecker on d4 x d4 x f4 

Aqui os negros, em seu segundo movimento, pegam duas peças em d4 e f4. Uma "transformação" preliminar dessas peças no XChecker é um recurso desta implementação e serve para impedir a retomada de peças "derrotadas" na mesma jogada. A frase "parcial 2" descreve o início do curso "composto", que consiste em dois movimentos "parciais". Essa forma de descrição é inconveniente, porque no momento da geração do primeiro movimento, o comprimento da sequência de movimentos "parciais" pode não ser conhecido. Veja como esta descrição ficará em um novo formato:

 1. g3 - f4 checker-shift nw 1. f6 - g5 checker-shift ne 2. e3 - d4 checker-shift nw 2. + g5 - e3 checker-jump nw 2. + e3 - c5 checker-jump sw 2. + 

Detalhes de implementação relacionados à "transformação" de peças são irrelevantes. A captura de peças também não é especificada, pois em damas, a captura ocorre como um "efeito colateral" do movimento da peça e não de acordo com o "princípio do xadrez". O progresso parcial será codificado com o símbolo "+" no início da linha. Um "+" isolado indica a conclusão de um "movimento composto" (na verdade, este é o movimento "parcial" usual, contendo um movimento ausente, uma sequência vazia).

Assim, usando regras nomeadas para a implementação de movimentos, conseguiu-se criar uma notação universal, satisfazendo totalmente nossos requisitos. Obviamente, isso não tem nada a ver com o xadrez padrão ou com qualquer outra notação, mas acontece que a notação convencional para xadrez, damas e outros jogos também não tem nada a ver uma com a outra. O módulo de visualização sempre pode converter o registro de movimentação em uma forma mais familiar aceita em um jogo específico. A conversão também pode ter alguma forma universal, como SGF (Smart Game Format) .

O ciclo de vida do jogo

Além das informações sobre como colocar as peças no tabuleiro, a sequência de turnos é uma parte importante do estado do jogo, uma variável no processo do jogo. No caso mais simples (e mais comum), para armazenar essas informações, um bit será suficiente, mas o ZoG oferece mais algumas oportunidades para implementar casos mais complexos. Aqui está como uma descrição de uma sequência de movimentos poderia procurar o jogo Splut! :

 (players South West North East) (turn-order South West West repeat North North North East East East South South South West West West ) 

Nesse jogo, cada jogador faz três jogadas de cada vez, mas se você der ao primeiro jogador a oportunidade de fazer três jogadas da posição inicial, ele poderá destruir uma das peças do adversário, o que lhe daria uma vantagem significativa. Por esse motivo, o primeiro jogador deve fazer apenas um movimento (dá a oportunidade de se preparar para atacar um jogador adversário, mas não o atacar), o segundo - dois movimentos (isso também não é suficiente para atacar um jogador adversário), depois onde cada jogador sempre faz três movimentos.


A repetição do rótulo indica o início de uma sequência de movimentos repetidos ciclicamente. Se não aparecer, a descrição inteira será repetida ciclicamente. O ZoG não permite o uso do rótulo repetir mais de uma vez. Outra característica importante é a especificação da ordem dos turnos. Aqui está como uma descrição da sequência de turnos de um jogo em que cada jogador executa dois turnos (o primeiro movimento - peças em movimento, o segundo - capturando as peças do oponente):

 (players White Black) (turn-order (White normal-move) (White capture-move) (Black normal-move) (Black capture-move) ) 

Há mais um recurso associado à descrição de mover as peças de outra pessoa, mas é muito inconveniente de usar. O problema é que essa descrição não tem alternativa. Se a descrição indicar que o movimento deve ser feito por uma peça inimiga, o jogador deve executar esse movimento! No ZoG, é impossível descrever uma escolha de mudar a peça dele ou de outra pessoa. Se tal capacidade for necessária em um jogo (como em " Stavropol Chequers "), é necessário tornar todas as peças neutras (criando para esse fim um jogador que não participe do jogo) e determinar para todos os jogadores a oportunidade para mover uma peça neutra. Eu disse acima que, por padrão, é muito mais fácil permitir que todos os jogadores movam quaisquer peças (tanto as suas quanto as do seu oponente) adicionando as verificações necessárias nos algoritmos de geração de movimento.

Como você pode ver, o leque de opções fornecidas pelo ZoG para descrição da sequência de voltas é extremamente limitado. O Axiom também falha ao adicionar novos recursos, porque (geralmente) é executado no ZoG. Ludi, a esse respeito, é ainda mais pobre. Para maximizar a unificação das regras do jogo (necessária para a possibilidade de usar algoritmos genéricos), neste projeto, todas as capacidades descritivas foram deliberadamente simplificadas, o que provocou a eliminação de camadas inteiras de jogos.


" Bao Swahili " é um bom exemplo de um jogo com um ciclo de vida complexo. Neste jogo, existem duas fases com regras para execução de movimentos que diferem significativamente. No início do jogo, parte das pedras está "na mão" "De cada jogador. Enquanto ainda há pedras" na mão ", pedras são colocadas em poços, uma pedra de cada vez. Quando as pedras" na mão "acabam, a segunda fase do jogo começa, com a distribuição dos Não se pode dizer que este jogo não pode ser descrito no ZRF (a linguagem de descrição do ZoG), mas devido às limitações do ZoG, essa implementação seria extremamente confusa (o que certamente não é o melhor para a qualidade do trabalho de IA). Vamos ver como a descrição de um jogo desse tipo ficaria em um "mundo ideal":

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (label phase-ii) (turn-order (South p-ii-move) (North p-ii-move) ) ) 

Aqui, cada lista de ordem de turno determina sua sequência repetida de movimentos (distinguindo-se pelo modo de execução dos movimentos). O rótulo da palavra-chave define um rótulo para o qual uma transição pode ser feita durante a geração da última jogada. Você pode notar que aqui procedemos da suposição implícita de que essa transição sempre ocorre após a jogada do segundo jogador (caso contrário, isso violaria a sequência de jogadas). Como fazer a transição para a próxima fase em um momento arbitrário?

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (turn-order (labels - phase-ii) (South p-ii-move) (labels phase-ii -) (North p-ii-move) ) ) 

Aqui, os rótulos são transportados no corpo do loop e compreendem dois nomes. Os nomes de marcadores nas listas de marcadores aparecem na ordem de transferência de jogadores na lista de jogadores. O nome usado para a transição é determinado pelo jogador que fez a última jogada. Se esse foi o norte, ele fará a transição para o primeiro rótulo, caso contrário, para o segundo. Se algum dos nomes nos rótulos não for usado, a posição correspondente poderá ser preenchida por um traço.


Um aspecto importante no gerenciamento de movimentos alternados é a capacidade de executar um turno repetido. Em jogos da família Tables , como Nard , Gamão ou Ur , por exemplo, a capacidade de executar turnos repetidos é um elemento importante das táticas de jogo. No ZoG, pode-se usar a passagem de um turno para imitar esse recurso, mas essa abordagem complica significativamente a descrição do jogo (especialmente com mais jogadores). Seria muito mais lógico usar um rótulo para repetir uma vez:

 (players South North) (turn-order (label repeat) South (label repeat) North ) 

Após o jogo ter saltado para a repetição do marcador, o jogador jogará novamente o seu turno (o marcador mais próximo da posição atual na lista de turnos entrará em vigor). Eu gosto da abordagem do Perl em suas definições implícitas. A geração implícita de estruturas de controle pode simplificar significativamente a descrição do jogo. Como movimentos repetidos podem ser usados ​​em muitos jogos, os rótulos se repetem, antecipando a possível repetição de qualquer turno.

 (players South North) (turn-order South North ) 

Além disso, como a sequência de turnos é totalmente consistente com a ordem por escrito dos jogadores na construção dos jogadores, você pode gerar automaticamente toda a frase da ordem dos turnos:

 (players South North) 

Quanto mais fácil a descrição for escrita, melhor.

Invariável quebrável

A principal coisa que eu não gosto no ZoG pode ser expressa com uma palavra - xadrez. À primeira vista, é apenas uma condição (muito comum em jogos da família do xadrez ) que liga o final do jogo à formação de uma situação de companheiro. Infelizmente, em uma análise mais aprofundada, a simplicidade mostra-se enganosa. O uso dessa palavra-chave significa não apenas o desempenho, após cada jogada, de uma verificação para a conclusão do jogo, mas também impõe ao jogador certo "comportamento".


Do Shogi habitual, este jogo difere apenas no número de jogadores. Infelizmente, essa diferença é suficiente para tornar o trabalho de determinar o xeque-mate (e tudo associado a essa palavra "mágica") incorreto. A verificação do cheque é realizada apenas em relação a um dos jogadores. Como resultado, o rei pode estar sob ataque e ser comido [por uma combinação de turnos dos oponentes, mesmo quando não for deixado em "check"]! O fato de isso não ser o ideal será refletido no trabalho da IA.

Se esse problema parece insignificante, vale lembrar que as coalizões geralmente são formadas em jogos de quatro jogadores "par contra par". No caso da formação de coalizões, devemos considerar que peças amigáveis ​​ao rei não o ameaçam! Assim, por exemplo, dois reis amigos podem muito bem residir em espaços vizinhos do tabuleiro.


Torna-se mais complicado do que nunca se um jogador pode ter vários reis. No " xadrez Tamerlane ", o peão real se transforma em um príncipe (na verdade, um segundo rei). Se isso acontecer, você poderá vencer apenas capturando o primeiro rei (um dos dois) e acasalando o segundo. Neste jogo, você pode ganhar até um terceiro rei, o dobro de gastos com a transformação do "peão ​​de peões"! As capacidades expressivas de "xadrez" não são suficientes para descrever adequadamente essa situação.

Outra dificuldade pode ser o próprio processo de dar companheira. Assim, no xadrez mongol ( Shatar ), o resultado da tentativa de acasalamento depende da ordem em que as peças executam o "teste" seqüencial. O resultado pode ser uma vitória ou um empate (como companheiro por peão) ou até mesmo uma derrota (companheiro de cavalo proibido, mas você pode dar um cheque). Um pouco menos exótico, a esse respeito, é o shogi japonês. Neste jogo, é proibido dar companheiro com um peão caído, mas você pode dar check com um peão caído e dar check mate com um peão movido.


Obviamente, é preciso separar a lógica da verificação do final do jogo do teste, para que o rei tenha caído em xeque, que é uma regra invariável que é checada após cada turno. A violação da regra torna impossível executar a movimentação (a movimentação é removida da lista de movimentações disponíveis). Portanto, um teste (simplificado) para um rei estar sob controle pode ser assim para o "xadrez Tamerlane":

 (verify (or (> (count (pieces my? (is-piece? King))) 1) (= (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

É importante entender que esse teste deve ser realizado apenas para os próprios reis (usei o predicado my?, Porque o predicado amigo ?, com apoio às coalizões, será satisfeito não apenas pelas próprias peças, mas também pelas peças de todos os jogadores amigáveis). Aceitável (e desejável, [se houver vários reis amigos]) é a situação em que o rei inimigo fica sob controle, após um movimento, mas pelo próprio rei. Esta situação deve ser impossível [a menos que haja vários reis amigos]! Tendo fornecido suporte para verificar essas regras, verificar a conclusão do jogo pelo xeque-mate se torna trivial. Se não houver movimentos possíveis e o [único] rei estiver em xeque, o jogo terminará [se esse rei pertencer ao último jogador sobrevivente da segunda última coalizão sobrevivente]:

 (loss-condition (and (= (count moves) 0) (= (count (pieces my? (is-piece? King)) 1) (> (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

A capacidade de determinar invariantes será útil em outros jogos, como em damas . A maior dificuldade na implementação de jogos dessa família está ligada à implementação da “regra da maioria”. Em quase todos os jogos de rascunho, a captura é obrigatória. Além disso, na maioria dos jogos desta família, há uma conclusão característica de “capturas em cadeia” em um único turno. O verificador, tendo capturado, continua a pegar outras peças, se possível. Na maioria dos jogos, o jogador é obrigado a realizar capturas em cadeia até o fim, mas há exceções a essa regra, por exemplo, Fanorona .


Usando o mecanismo de movimentos parciais, implementar uma “captura de cadeia” é bastante simples. Dificuldades surgem quando, além disso, impõe-se uma condição sob a qual, de todas as opções possíveis, é preciso escolher uma cadeia na qual um número máximo de peças é capturado. No ZoG, essa lógica deve ser implementada do zero no nível de "codificação":

 (option "maximal captures" true) 

Essa configuração é adequada para " damas internacionais ", mas nas " damas italianas " a regra da maioria é formulada de maneira diferente. Nesta versão do jogo, se houver várias opções para o mesmo número de capturas, você deverá selecionar uma opção que capture o maior número de damas transformadas (reis). Os desenvolvedores do ZoG forneceram isso. Você insere a seguinte configuração:

 (option "maximal captures" 2) 

Nesta configuração, conta-se não apenas o número de peças capturadas, mas também seu tipo. Infelizmente, nem tudo pode ser previsto. Veja como a "regra da maioria" é formulada em "damas francesas antigas":

Se por uma série de capturas for possível capturar o mesmo número de damas com um homem simples ou com um rei, o jogador deve usar o rei. No entanto, se o número de damas for o mesmo em ambos os casos, mas em um houver um rei inimigo (ou houver mais), o jogador deverá escolher esta opção, mesmo que a captura seja feita usando o verificador simples, e não usando o rei.

É claro que, atualmente, quase ninguém joga essa versão de damas, mas sua própria existência demonstra claramente as deficiências da implementação "codificada". O uso do mecanismo de invariantes permite todas as opções possíveis para a “regra da maioria” de maneira universal. Para a implementação das " antigas damas francesas ", seria a seguinte:

 (verify (>= capturing-count max-capturing-count) ) (if (> capturing-count max-capturing-count) (let max-capturing-count capturing-count) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= capturing-sum max-capturing-sum) ) (if (> capturing-sum max-capturing-sum) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= attacking-value max-attacking-value) ) (let max-attacking-value attacking-value) 

Aqui, assumimos que as regras para geração de captura preenchem corretamente [as seguintes] variáveis ​​locais:

• contagem de captura - total de peças capturadas
• soma de captura - número de reis capturados
• valor de ataque - valor da captura da peça

Associado a cada uma dessas variáveis ​​está um acumulador de valores, armazenado em uma variável com o prefixo max. As três verificações são executadas em série. A violação de qualquer uma das condições de verificação interrompe imediatamente a geração da próxima opção de turno (a captura não é armazenada na lista de turnos possíveis). Como as verificações executadas estão associadas a valores variáveis, não é suficiente [testar apenas a nova opção de captura atual]. Cada teste gera uma "regra flexível" associada à captura gerada [que pode revisar o valor máximo acumulado]. Após cada alteração em qualquer acumulador, todas as regras associadas devem ser verificadas novamente [para todas as opções na lista]. Se alguma das condições for violada para uma opção gerada anteriormente, essa opção deverá ser removida da lista de possíveis opções de turno.

Conclusão

Esta é a tradução do meu artigo de 2014 ano. Desde então, repensei muito e o projeto Dagaz se tornou realidade, mas não mudei quase nada no texto. Este artigo foi traduzido por meu amigo Howard McCay e sou grato a ele pelo trabalho realizado.