
Uma captura de tela do mesmo jogo em flash ainda dá as boas-vindas a toox.com/jeux/jeux-de-cartes/coinche
Declaração do problema e sua relevância
Quosh, Belote e Tarot são jogos nacionais franceses. De acordo com as regras, isso é quase o mesmo que um jogo de preferência em privado, e um par é jogado por um par, então por quantos subornos e em qual trunfo seu parceiro se propõe a anunciar o jogo durante a negociação, você pode entender aproximadamente quais cartas ele tem. O jogo é longo e a existência de uma IA capaz de, de alguma forma, encerrar o jogo nele é simplesmente vital, porque um dos jogadores pode simplesmente deixar a mesa decidindo que está perdendo irremediavelmente, e o vencedor naturalmente quer empurrá-lo para a pontuação final no placar. Nesse caso, a IA vence para o jogador perdido. Mas já que temos IA, por que não permitir que comecemos o jogo irritando o AI-shki em espaços vazios. Então, lançamos esses grandes jogos para as massas e rapidamente descobrimos que existem basicamente duas opções de como os franceses gostam de jogar.Aproximadamente metade de todas as mesas estão esperando para serem preenchidas com pessoas ao vivo até a vitória, e metade vem para baixo e começa o jogo contra três IA, como na imagem acima.
Em princípio, como o jogo está fechado, as pessoas estão prontas para perdoar os robôs por pequenos erros de cálculo e talentos alternativos. Principalmente porque as cartas do robô não podem ser vistas. "Sob o jogador com simak", "sob a vistuza com o ás" e regras simples semelhantes que sacudi do nosso cliente francês permitiram-nos fazer o mínimo de lançador aceitável. Foi maluco em uma semana logo depois. Por outro lado, o jogo é jogado "dois por dois", os pontos são contados para um par e, naturalmente, o jogador não quer que seu parceiro estúpido entre "do segundo rei", isto é, tendo um rei em suas mãos e alguma outra carta pequena, ele faz uma jogada para este naipe, em vez de deixar o oponente jogar um ás, deixá-lo passar com uma pequena carta e fazer a próxima jogada neste naipe com seu rei. (Na verdade, nesses jogos, a segunda carta mais antiga é 10,mas a seguir falarei em termos que sejam compreensíveis para o russo). Mas se o ás por algum motivo deixou o jogo, e você tem uma Dama e outra coisa pequena, então é quase como o segundo rei. Especialmente se você pré-encomendar os trunfos. E você, por exemplo, não está jogando Belote, onde se usa 32 cartas, mas Tarot, em que o jogo é jogado com um baralho de 78 cartas (o mesmo que algumas pessoas acham). E aí, em alguns casos, nem mesmo a terceira rainha, mas o quarto valete, pode receber o suborno. Em geral, tudo isso dá origem a tantos casos extremos que um manequim estúpido em ifs torna-se de alguma forma completamente inaceitavelmente complexo. E aí eu falei: “Bah! Eu li muitopor exemplo, você não está jogando Belote, que usa 32 cartas, mas Tarot, em que o jogo é jogado com um baralho de 78 cartas (o mesmo que algumas pessoas adivinham). E aí, em alguns casos, nem mesmo a terceira rainha, mas o quarto valete, pode aceitar o suborno. Em geral, tudo isso dá origem a tantos casos extremos que um manequim estúpido em ifs torna-se de alguma forma completamente inaceitavelmente complexo. E aí eu falei: “Bah! Eu li muitopor exemplo, você não joga Belote, onde são usadas 32 cartas, mas Tarot, em que o jogo é jogado com um baralho de 78 cartas (o mesmo que algumas pessoas adivinham). E aí, em alguns casos, nem mesmo a terceira rainha, mas o quarto valete, pode aceitar o suborno. Em geral, tudo isso dá origem a tantos casos extremos que um manequim estúpido em ifs torna-se de alguma forma completamente inaceitavelmente complexo. E aí eu falei: “Bah! Eu li muitoResumidamente e impressionado! " Então, fugi do escritório por alguns dias, sentei-me com um laptop em um café e alguns dias depois gerou algo.
Ideias chave
Em que o Prolog é baseado declarativamente? Sobre fatos, por exemplo:
('', '').
('', '').
e em termos ou regras, por exemplo, se A é a mãe B, então A é uma menina:
() :- (, ).
Claro, eu entendo que em nossa época nem tudo é tão simples, e em geral é até um pouco indecente dizer isso, mas na época em que as pessoas acreditavam na lógica formal, não havia nada de repreensível nesses exemplos. Digamos para tolerância:
(A, B) :- (A, B).
(, ) :- (, ), (, ).
E então você me pergunta assim:
?- (X, '')
E o Prólogo terrivelmente lógico responde a você:
X = ''
X = ''
A ideia era que o usuário não esquentasse a cabeça pela sequência e em que quantidade o sistema de prólogo aplicaria as regras aos fatos para chegar a uma resposta. Mas, claro, não é tão simples. O prólogo está coberto de muletas, acréscimos funcionais, cortadores de vários ramos de raciocínio e coisas do gênero, e ainda assim regularmente corre para uma recursão infinita.
No livro daquele Bratko muito inspirador, um capítulo inteiro foi dedicado a como a máquina de prólogo é realizada por dentro. Em suma, ele percorre a árvore de todas as regras em profundidade, tentando aplicar cada uma das regras por vez ao conjunto de todos os fatos e variáveis conhecidas para obter um novo estado, e se a regra não puder ser aplicada, ele volta para a etapa anterior e tenta outra opção.
Além disso, se você conseguir juntar algo útil, a máquina pega a lista de regras e começa na próxima etapa para procurar regras a serem aplicadas desde o início da lista. Além disso, se uma variável ocorrer nas regras, a máquina lembra quais estados dessas variáveis, levando em consideração as regras já aplicadas, podem estar. Isso é chamado de desenvolvimento. Se ele puder encontrar uma instanciação das variáveis que tornam a pergunta verdadeira, ele imprime essa instanciação. Então ela pode ir em busca da próxima concretização e assim por diante. No exemplo artificial acima, o sistema encontrou duas concretizações que satisfazem as condições.
Eu gostaria de formular as regras do jogo de maneira semelhante, mas é claro que não literalmente. Tendo alguma experiência em depuração de programas no Prolog, eu não estava nem um pouco ansioso para enfrentar essa depuração e esses custos indiretos em meu produto.
Primeiro, tudo isso deve funcionar não em um monte de fatos dispersos, mas na árvore de estado do jogo - um modelo e aplicar os resultados de seu trabalho à mesma árvore também. Em segundo lugar, quero escrever as regras de modo que um valor específico, uma variável e uma expressão aritmética possam estar na mesma posição, e o sistema deve lidar com isso de acordo sem fazer perguntas adicionais ao programador e sem exigir sintaxe adicional. Em terceiro lugar, é claro, é de vital importância abandonar a recursão infinita, mas alguma repetição da aplicação das regras ainda precisa ser deixada. Em quarto lugar, o sistema de regras deve ser escrito em algum formato legível muito conveniente, de modo que à primeira vista fique claro o que o autor queria dizer. E finalmente, em quinto lugar,tudo isso precisa ser aparafusado em alguma ferramenta de registro e depuração conveniente para que seja fácil seguir o raciocínio deste sistema e entender por que certas regras não funcionam ao contrário das expectativas.
Isso, é claro, não é um solucionador lógico de predicado universal de primeira ordem, mas simplesmente um sistema declarativo conveniente de regras de jogo. O que, na prática, também é muito bom. Para isso, inventei o nome Logrus muito mais tarde em um dos projetos a seguir. Descreverei a versão final de uma vez, contornando todos os estágios intermediários do desenvolvimento do motor.
A sintaxe resultante da biblioteca Logrus
Haverá muita sintaxe.
1) Em runtime, a árvore de decisão fica armazenada na forma de algumas classes, mas a primeira coisa que anexei a ela, assim que funcionou, foi Importar e Exportar em JSON. Descobriu-se que isso também é conveniente porque se sua estrutura de dados não mudou muito, você pode atualizar as regras do arquivo sem recompilação. Escrever na forma de JSON acabou sendo tão conveniente que em um dos seguintes projetos, quando os programadores estavam com pressa, às vezes em vez de escrever um comando normal, eles simplesmente faziam
state.AplayJSON("...");
e nele a ação necessária foi inserida como uma string JSON. Isso, é claro, não teve um efeito muito bom no desempenho, mas se não regularmente e apenas em resposta aos cliques do usuário, então não é assustador ... Todo o resto eu ilustrarei imediatamente com JSON. Eu reproduzo JSONs aproximadamente de memória, porque foi muito tempo. A rigor, JSON não garante a ordem dos nós no objeto, mas a maioria das bibliotecas ainda a respeita, e aqui e abaixo a ordem dos nós é usada ativamente.
2) A Regra se tornou a principal unidade estrutural do motor. Uma regra consiste em uma condição e uma ação. Normalmente, as regras vinham em matrizes e eram aplicadas uma a uma a cada vez:
[{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
3) Cada regra contém uma condição - este é um modelo de árvore, possivelmente contendo variáveis. O sistema verificará se a árvore de estado corresponde ao modelo para algum valor das variáveis. E se encontrar tal concretização, desencadeará uma ação. Por exemplo:
{"condition":{
"player":{
"$X":{"gold" : "<20", "name":"$NAME"}
}},
"action":{}}
Tal construção significará que para desencadear uma ação na árvore, deve haver um nó "jogador" no nível superior no qual um ou mais nós filhos, cada um dos quais com campos "ouro" com um valor menor que 20 e "nome". Se tal condição for atendida, então a ação será chamada, e como dado de entrada será passada na variável X - a chave do nó, e na variável NAME o nome do jogador. Se houver vários nós adequados e, consequentemente, houver várias instanciações possíveis, a ação será chamada várias vezes com cada uma das instanciações encontradas na entrada.
4) Inicialmente, tudo era um pouco menos flexível, mas então Valyard, que muitas pessoas conhecem em inúmeras palestras em conferências sobre a Unity, nos ferrou um analisador que transforma expressões aritméticas em uma árvore de decisão inteligente e a flexibilidade finalmente floresceu em uma cor violenta.
5) Os nomes das variáveis C $ começam. Eles podem aparecer como uma chave, como $ X, e então várias instanciações serão selecionadas, como um valor de folha, como $ NAME, pode ser inserido em expressões aritméticas: por exemplo: {"gold": "<$ X * 10" } E então ele pode ser usado para verificar as condições, apenas aqueles jogadores que têm mais ouro do que seu número ordinal multiplicado por 10 passarão na verificação e, finalmente, eles podem ser calculados diretamente em alguma expressão, por exemplo: {"ouro": "$ X = 3 + $ this "} onde $ este é o valor do ponto atual em que o cálculo foi executado. A passagem deste nó concretiza o valor da variável $ X como 3 + a quantidade de ouro que o jogador possui. Das possibilidadesque veio à mente não foi implementado, havia apenas um - a variável não pode aparecer primeiro à direita de uma expressão aritmética, isso será um erro, na hora em que for usada como argumento já deve estar concretizada de uma das várias outras maneiras.
6) Uma variável em uma expressão pode ocorrer quantas vezes você quiser, enquanto a primeira menção a especifica, e as próximas serão uma verificação de igualdade. Por exemplo, tal construção pegará o primeiro jogador, verificará se há dinheiro nele e então procurará outro jogador para quem o primeiro seria o alvo. Se não o encontrar, voltará ao ponto de concretização X escolherá o próximo jogador, verificará o dinheiro, e assim por diante até passar por todas as opções possíveis X e Y. Ao trocar as linhas, o programador mudará a ordem dos cheques, mas não o resultado final:
{ "player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}
}}
7) A ação também é um modelo de árvore que pode conter variáveis e expressões aritméticas, e a árvore de estado do jogo será alterada para corresponder a ela. Por exemplo, este modelo atribuiria ao jogador X um oponente na forma do jogador Y, mas se por alguma razão o jogador Y não existisse, ele seria criado. E o player "supérfluo" será removido por completo. Na hora de criar o jogo a partir da captura de tela, o sinal de deletar era nulo, mas depois o substituí por uma palavra reservada, caso alguém precise inserir um valor em branco por chave. Em geral, o princípio, eu acho, é claro, e o significado das ações realizadas com o jogo é basicamente o mesmo.
{
"condition":{
"player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}}},
"action":{
"$X":{"target":"$Y"},
"superfluous":"@remove"}
}
8) Uma ação também não pode ser um modelo de árvore, mas um conjunto de regras. Cada um deles será verificado não do zero, mas com a instanciação inicial com a qual a ação foi chamada. Ou seja, pode haver todo um grupo de regras e todas elas usarão a variável X.
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
}
9) A regra filha pode ser aplicada não a partir da raiz da árvore de estado, mas a partir de algum ponto alcançado durante a aplicação da ação. Nesse caso, todas as condições e todas as ações usarão esse ponto como raiz. Se parece com isso:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"@rules":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]}
}
10) A repetição da regra poderia ser definida como mais um nó, conseguindo-se, se necessário, recursão de profundidade limitada. Mas, na prática, essa decisão geralmente não era necessária. Ele também pode ser usado para repetir um monte de regras conforme necessário, colocando-o em uma ação:
{
"condition":{},
"action":{},
"repeat":5
}
11) A árvore de regras pode ser carregada de vários arquivos JSON, sua estrutura de árvore foi simplesmente sobreposta uma à outra. Era conveniente quebrar as regras em blocos significativos separados. Provavelmente algum Include também seria útil, agora não me lembro como foi combinado conosco.
12) Registro! Qualquer regra poderia ter um "@log": nó verdadeiro, o que levou ao fato de que essa regra começou a aparecer em grandes detalhes no log que descreve o processo de solução. Que concretizações tentamos, que ramos de raciocínio são suprimidos e por quê. O log era hierárquico, ou seja, a regra aninhada poderia ser "@log": false e tudo o que acontece nele e abaixo não será logado. Idealmente, eu gostaria que este nó pudesse ser deixado em qualquer lugar na árvore de condições, a fim de observar apenas o que está acontecendo em um nível do modelo, mas parece que não concluí essa extensão. Talvez a depuração tenha corrido bem sem ele, então foi adiado para "algum dia".
13) Digitação. O brinquedo era tão antigo que alguns dos programadores de hoje nem haviam nascido. Ele foi escrito em ActionScript2, que possuía tipagem dinâmica e herança por meio de protótipos disponíveis em tempo de execução. Das linguagens modernas que são ouvidas, apenas Python funciona dessa maneira. Entretanto, amarrar-se a essa ideia não é particularmente difícil. Eu faria isso usando o símbolo de chave ':' assim: "$ X: int", mas pode ser complicado se a primeira ocorrência da variável não tivesse nenhum do tipo especificado. Além disso, pode haver confusão com o operador ternário.
Como se costuma dizer, era liso no papel, mas o uso prático exigia várias muletas diferentes. Aqui estão os que eu me lembro:
14) Um único nó pode ser verificado não por um, mas por várias condições. Por exemplo, tal condição primeiro verificava se havia mais de 20 dinheiro e, em seguida, especificava a variável na qual essa quantidade de dinheiro estava representada. O símbolo de serviço '@' se não estiver no início da linha significava a reentrada no nó, o identificador de reentrada indo além não era útil de forma alguma. Talvez tenha sido utilizado um símbolo de serviço e algum outro, mas nada, na minha opinião, impede que você use este:
{
"player":{
"$X":{"gold":"<20", "gold@cnt":"$COUNT"}
}
}
15) Foram necessárias operações aritméticas que poderiam ser realizadas sem o uso de nenhum nó. De acordo com a tradição do prólogo, eles foram designados '_' e pode haver muitos deles:
{
"_":"$SUM=$A+$B",
"_@check":"@SUM <20"
}
16) Como existe uma passagem de verificação para cima na árvore, foi feita uma descida, feita através da palavra-chave "@parent". Isso, é claro, não aumentava a legibilidade, mas não funcionava sem ela. Aqui, é claro, algum análogo da função path sugere-se diretamente, o que redirecionaria para o local especificado na árvore, mas não me lembro se consegui implementá-lo no final ou não:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"rules":[
{
"condition":{
"@parent":{"@parent":{"…":"…"}}
}
]},
}
}
17) A ação agora tem a capacidade de puxar diretamente algum método de classe. Este é um chute no estômago da legibilidade, e eu preferiria algum análogo de #include, mas como é, você não pode jogar fora as palavras da música. Será que posso passar sem isso na prática se reanimo a biblioteca agora em C #?
18) A regra agora tem uma configuração adicional para repetir a ação não para todas as concreções encontradas, mas apenas para a primeira. Não me lembro agora como era chamada, mas por algum motivo essa muleta foi útil para algumas regras.
Resultados de uso
Assim que a biblioteca começou a ser usada ativamente, todos os AI-shki foram rapidamente transferidos para ela, e isso tornou possível ter o dobro de IA inteligente e gastar três vezes menos recursos de programação. O fato de os dados intermediários da escala de IA serem armazenados diretamente na árvore ajudou muito. Em particular, as próprias regras escreveram informações sobre as cartas de cada naipe que deixaram o jogo diretamente na árvore de estado do jogo.
Já no próximo projeto, verificar as regras do jogo e possibilitar movimentações de cada posição movida para o mesmo motor. E, em geral, não apenas para prototipagem rápida, mas também para jogos em que simplesmente existem muitas regras, isso seria muito útil. No final, os JSONs para download com lógica podem substituir metade do que os programadores fazem com o código e também ganhar em flexibilidade.
Claro, em termos de velocidade de execução, tudo isso foi notavelmente inferior à bagunça dos ifs, especialmente na implementação no AS2 com seus protótipos e objetos dinâmicos, mas não tanto que não pudesse ser implementado em produção.
A próxima etapa foi transferir a verificação de regras e determinar a ação do AI para o computador cliente. Para que os jogadores verifiquem uns aos outros. E eu até criei esse algoritmo para fazer isso, apesar do fato de que os valores das cartas inimigas não são conhecidos por nós, mas essa era uma história completamente diferente.
Muitos anos se passaram, mudei de emprego uma dúzia de vezes e, sempre que atualizava meu currículo, ia a toox.com e ficava surpreso ao descobrir que meu emprego ainda estava em serviço. Até parei para jogar outro jogo. E uma vez em Belot, acidentalmente me deparei com um conjunto de cartas que dá o maior número possível de pontos. A probabilidade de obter tal conjunto é de uma em três milhões.
Algum dia irei reunir minha vontade e fazer um remake moderno de Logrus para C # e Unity3d, por exemplo, para o estrategista hexagonal com quem sonho. Mas não vai ser hoje, hoje vou para a cama. O dever de divulgar ideias que valham a pena ser divulgadas foi cumprido com sucesso.
Em conclusão, algumas anedotas
Estávamos localizados em Novosibirsk Academgorodok. Alugamos um escritório no instituto. E o cliente é francês, totalmente desconhecido dos costumes locais. E assim, no terceiro ou quarto mês de trabalho conjunto, ele vem nos visitar, para nos conhecer. Fiz o check-in no final de semana no hotel local "Zolotaya Dolina" e na segunda-feira, ele diz ao gerente, vamos nos encontrar em um táxi às dez da manhã, iremos com os programadores para nos conhecermos. E leva Vovchik e vem às 10. Em geral, eles vão de carro até o instituto, batem na porta, e do outro lado vem a avó do vigia e olha para eles completamente sem entender por trás da porta trancada. Em uma data tão antiga, não havia cientistas ou programadores alugando escritórios no prédio. Eles literalmente a acordaram.
E aqui está outro caso. De alguma forma o nosso Sebastian Pereira liga para o gerente e diz que eles milagrosamente conseguiram entrar na TV e em breve seremos exibidos na TV com o nosso site. Após cerca de 8 horas. Então, o que você faz lá para que funcione de forma mais confiável ... No relógio em 2 de janeiro ... Não importa a hora ... E então Vovchik pega um táxi, começa a reunir programadores em dormitórios e apartamentos, completamente em estado de sujeira, e os leva para o escritório. Naquele dia, vi nosso administrador de sistema pela primeira vez em minha vida. Até este ponto, ele fazia tudo exclusivamente remotamente. E assim torcemos cada um que podia. Em particular, quebrei todo esse sistema colocando um monte de ifs em seu lugar de volta e aqui estamos nós, olhando para o gráfico de atendimento e de repente vemos como ele começa a subir. Em algum lugar na marca x15, o servidor travou. Mas o administrador disse que está tudo bem, caiu suavemente,agora ele vai subir. O servidor travou mais três vezes naquele dia.