IA de jogo de damas

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

IA de jogo de damas

Mensagem por Fuzenrad em Seg 26 Set 2011, 00:23

Sob justificativa de 'treino', decidi fazer um jogo de damas com IA, por ser um jogo (relativamente) simples e sem muitas restrições, assim eu afio um pouco a minha programação, só que surgiu um problema, as regras 'brasileiras' dizem que se houver a possibilidade de capturar uma peça do oponente, ela deverá ser feita obrigatoriamente, até ai tudo bem, eu já fiz essa verificação, mas de 1 única peça, a regra também diz que isso deve ser feito de forma a capturar a maior quantidade de peças possíveis, foi ai que eu travei, como fazer um algoritmo que verifica todas as possibilidades de deslocamento (lembrando que na captura 'múltipla' uma peça pode andar para trás).

Wikipedia escreveu:Damas do Brasil
Dama sem captura: A dama move-se em diagonal, percorrendo as casas vagas que quiser, para diante ou para trás, não tomando no seu percurso qualquer peça de cor contrária e não podendo mudar dessa diagonal.
Dama com captura: Se em sua diagonal houver uma outra peça, sendo essa da cor adversária, a captura só pode ser efetuada se houver uma ou mais casas vazias após a peça adversária, sendo assim, a jogada é obrigatória. A dama não é obrigada a ficar uma casa após a peça capturada.

http://pt.wikipedia.org/wiki/Damas
Em outras palavras, eu procuro ajuda em um algorítimo que faça isso:



Eu só consegui fazer ele verificar pra cima 2 casas de movimento, sempre na diagonal (tanto faz o lado), só que é um algorítimo 'burro', nessa situação por exemplo ele captura 2 peças pretas, ignorando as outras da seqüência.

Eu pensei em fazer de modo 'manual', por exemplo, ao capturar uma peça, a jogada não é passada ao oponente, ela continua sendo a do jogador desde que ainda exista uma possibilidade de captura (em qualquer direção que seja, só 4 na realidade), com isso a programação fica mais 'light', só que novamente volta ao algorítimo 'burro', pois a jogada com a maior quantidade de capturas DEVE ser obrigatória, ou seja, estou procurando por um algorítimo que seja capaz de pular as casas 'procurando' as possibilidades, se não der certo serei obrigado a fazer de modo manual.

Estou usando verificação de 'locais vazios' para a programação, as peças são objetos dinâmicos, ou seja, são os mesmos, mas 'funcionam' de forma diferente. Ao clicar na peça, uma variável ganha o ID dela e pela função with eu consigo capturar e mover peças. Achei relativamente fácil até agora, fiz boa parte das regras do jogo, falta somente essa de capturar 'múltiplas' peças do oponente e a movimentação da 'dama' (que pode se movimentar por mais de 1 casa na mesma diagonal) que creio não será nada complicado.

O código até agora está assim:

Código:
if place_free(x+48,y-48) or place_free(x-48,y-48)
pos_ok=1
else
pos_ok=0

if (pos_ok and aperta) {

if place_free(x+48,y-48) {
op_disp_1=1

if (mouse_x>x+24 and mouse_x<x+72) and (mouse_y<y-24 and mouse_y>y-72)
opcao_1=1 else opcao_1=0

} else { op_disp_1=0; opcao_1=0 }



if place_free(x-48,y-48) {
op_disp_2=1

if (mouse_x<x-24 and mouse_x>x-72) and (mouse_y<y-24 and mouse_y>y-72)
opcao_2=1 else opcao_2=0

} else { op_disp_2=0; opcao_2=0 }

} else {
op_disp_1=0;
opcao_1=0;

op_disp_2=0;
opcao_2=0;
}

if place_meeting(x-48,y-48,obj_pretas) and place_free(x-96,y-96)
captura_1=1 else captura_1=0

if place_meeting(x+48,y-48,obj_pretas) and place_free(x+96,y-96)
captura_2=1 else captura_2=0

if (mouse_x>x+72 and mouse_x<x+120) and (mouse_y<y-72 and mouse_y>y-120) and captura_2
sel_captura_1=1 else sel_captura_1=0

if (mouse_x<x-72 and mouse_x>x-120) and (mouse_y<y-72 and mouse_y>y-120) and captura_1
sel_captura_2=1 else sel_captura_2=0

if (mouse_x>x-24 and mouse_x<x+24) and (mouse_y>y-24 and mouse_y<y+24)
mouse=1
else
mouse=0

Enfim, quem pelo menos entendeu o que eu disse, posta aqui e eu passo o código fonte por MP.

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por PedroX em Seg 26 Set 2011, 00:34

Pra mim, acho que você deveria criar um objeto de checagem, que pulava as casas e cada vez que houver mais de uma possibilidade, ele se duplicava e cada parte ia para um lado. Todas as instâncias deles salvam o movimento de si mesmas (não seriam muitas), depois somavam 1 em suas variaveis de contagem de casas que andaram, depois você via quais 'comeram' mais peças (variavel com maior valor) e fazia o adversário seguir o caminho dessa instância (ela poderia gravar num path).

Se você quiser que eu tente (pois ainda não testei), fala ai.

Até mais!

PedroX

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Seg 26 Set 2011, 11:33

Na realidade o que eu estou fazendo é um 'verificador de posições', nesse caso o termo 'IA' não se refere à 'jogar contra o computador', seria muito complexo fazer uma IA assim, sendo que existe inúmeros programas com várias anos de desenvolvimento e que fazem a mesma coisa, o que eu planejo é um jogo multiplayer de damas com o modo 'learning', que explica as regras, os modos, as posições, movimento das peças etc etc etc.

Por ser multiplayer, eu só preciso programar a ação das peças da parte inferior, pois seria uma trabalho 'dispensável', já que se jogar com as brancas, as brancas ficam embaixo e se jogar com as pretas, as pretas ficam embaixo, ou seja, só preciso 'espelhar' as informações enviadas pelos jogadores.

O sistema multiplayer funciona, mas será refeito, fiz um sistema bastante porco que atualiza cada peça em todos os steps de um alarm, creio que consigo fazer transmitir menos dados entre os jogadores, assim diminuindo significativamente lags, a minha idéia é fazer uma string com as peças codificadas, e essa string será enviada somente na jogada, ou seja, se o jogo tiver 50 rodadas, somente 50 strings serão enviadas. Esquematizando seria algo assim:

1•2•3•4•
•5•6•7•8
9•0•A•B•
•C•D•E•F
G•H•I•J•
•K•L•M•N
O•P•Q•R•
•S•T•U•V


No começo do jogo, o jogador das brancas ocupa as 3 fileiras inferiores, então a 'codificação' da posição inicial será 'klmnopqrstuv' enquanto a das pretas será '1234567890ab'.

Isso inclusive me facilita a criar um tipo de 'replay', onde cada jogada salva uma string em uma lista.

Mas voltando ao problema das capturas múltiplas, eu pensei em um recurso que bloqueia qualquer outro movimento quando a possibilidade de capturar mais de uma peça surge, a vez de jogar será passada ao oponente somente quando todas as peças possíveis forem capturadas, isso resolve o meu problema, já que eu faço o jogador mover as peças, apenas restringindo seu movimento, entretanto ainda sim precisaria de um 'verificador' que indique qual o primeiro movimento a ser feito de modo que a maior quantidade possível de peças seja capturada, seria um algorítimo capaz, por exemplo, de detectar essa situação (em verde) e não a outra (em vermelho).



O verificador não teria que mover a peça automaticamente, isso é trabalho do jogador, ele só destacaria a melhor posição de jogo (em laranja), assim:


Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por saim em Seg 26 Set 2011, 11:50

Acho que a idéia do Pedro Henrique é boa: no início do movimento, crie pra cada peça, um objeto que verifica se tem a possibilidade de comer alguma outra peça. Se sim, ele pula essa peça e marca a peça "comida" numa lista. Verifica de novo, na nova posição. Assim por diante. Se tiver mais de uma posição pra ele ir, ele vai pra um lado (pode ser criada uma ordem de preferência, tipo "sentido horário") e cria outro objeto igual, com a mesma lista de peças comidas, que vai pro outro. Peças que estejam na lista não podem ser consideradas comíveis.
Quando não tiver mais jeito de ir, uma variável "acabaramAsAlternativas" passa a retornar true. Quando todos os objetos estiverem retornando true, verifique aquele com a maior lista. Esse é o que comeu (digo, comeria) mais peças. Em casos de empate, deixa o jogador escolher o caminho mais estratégico.

saim

Ranking : Nota B
Número de Mensagens : 2964
Idade : 38
Data de inscrição : 14/01/2011
Notas recebidas : C-D-A-B
Reputação : 121
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 3

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Seg 26 Set 2011, 12:06

Hmm.. Seria 'tentativa e erro', conhecido também como 'bruta force', antes eu vou tentar fazer com verificação de espaços vazios, dessa maneira pode dar ocasionar um laço infinito (como no primeiro exemplo que eu postei):


Esse objeto pode ficar circulando eternamente entre essas 4 peças pretas.

De qualquer forma isso me deu uma ideia aqui, vou tentar indexar as posições vazias do tabuleiro e associar com a posição da peça selecionada.

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por PedroX em Seg 26 Set 2011, 14:24

Só que então seria preciso checar se já não passou por aquele ponto, se já passou, vai para ele e para de movimentar.

É complexo fazer isso.
Mas não é muito dificil.

Até mais!

PedroX

Ranking : Nota C
Número de Mensagens : 6034
Idade : 21
Data de inscrição : 26/07/2008
Notas recebidas : C+B
Reputação : 286
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   :
   :
   :

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Seg 26 Set 2011, 14:54

Não posso fazer essa restrição, caso contrário ele vai parar de contar se passar por uma casa já contada antes, mesmo que ainda tenha peças para capturar. Nessa situação por exemplo..

.. a última peça preta seria ignorada.

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por saim em Seg 26 Set 2011, 15:55

Não, não, as posições podem repetir. O que não pode ser repetido é a peça comida. Mesmo porque, se você permitir isso, vai cair num loop infinito assim que for possível comer a primeira peça.
Restringir a peça comida (pode até ser por id - aliás, é o único jeito que imagino, no momento) requer que, a cada peça comida, cheque-se uma lista crescente (em progressão aritimética). Mas pra uma checagem local e num universo de, no máximo, 12 peças (total de 78 iterações), acho que qualquer computador dá conta

saim

Ranking : Nota B
Número de Mensagens : 2964
Idade : 38
Data de inscrição : 14/01/2011
Notas recebidas : C-D-A-B
Reputação : 121
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 3

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Ter 27 Set 2011, 17:59

Well.. não consegui, nem com um objeto 'auxiliar' fazendo a verificação. Quem quiser tentar:
http://www.64digits.com/users/FJI/damas.gmk

Obs: Tirei toda a parte 'não funcional' do source, ou seja, tudo lá funciona (tirei a captura das peças, estava com um errinho também), na execução a tecla F1 mostra as jogadas possíveis, ao clicar em uma peça, as opções de movimento se destacam.

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Mr. Kaleb em Ter 27 Set 2011, 21:01

Ow Fiuz, tenta criar uma variável que inabilite a ultima casa, se tiver uma peça na diagonal a baixo, aí continua a sequência. É bom criar num script separado, é melhor de controlar.

EDIT***:
Eita, eu estou quase resolvendo, eu quero saber como funciona a pos_ok e as vars de captura, acho q falta só isso para eu arrumar.

Mr. Kaleb

Ranking : Nota C
Número de Mensagens : 1400
Idade : 19
Data de inscrição : 07/09/2010
Notas recebidas : C
Reputação : 21
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 0
   : 0
   : 0

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Ter 27 Set 2011, 22:06

A variável pos_ok indica se a peça pode ou não ser movida, se for igual à 1, a peça pode mover ou capturar, se for igual à 0, ela não pode se mover de forma alguma, serve só pra fazer a célula ficar verde ou vermelha (indica qual pode se mover), as de captura (laranja), são 4:

captura_1 > Diagonal para esquerda
captura_2 > Diagonal para direita

Essas 2 indicam que uma peça pode capturar uma peça do oponente.

sel_captura_1
sel_captura_2

Essas são só pra formatação, pra você selecionar qual prefere capturar.

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Mr. Kaleb em Ter 27 Set 2011, 22:16

Ah, agora ficou mais fácil, acho que vou conseguir resolver.
Vou ter que criar mais duas vars de captura, para baixo (ou só uma).
Valeu e se eu não conseguir, malz ae :/
Agora só amanha, vou dormir.

Mr. Kaleb

Ranking : Nota C
Número de Mensagens : 1400
Idade : 19
Data de inscrição : 07/09/2010
Notas recebidas : C
Reputação : 21
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 0
   : 0
   : 0

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por saim em Qua 28 Set 2011, 22:20

Fuzen, deu certo, aqui.
Quer dizer, mais ou menos. Funcionar, funciona, mas tem alguns cuidados a serem tomados...
Criei um script que faz isso que foi sugerido:
- checa se tem peça em posição de comer
- se tiver, compara com uma lista de peças comidas
- se não estiver nessa lista, cria um objeto na casa da posição depois de comer
- copia a lista de peças comidas pra esse objeto criado
- faz o mesmo com o objeto criado

Daí, pelo tamanho da lista, você fica sabendo quantas peças o bicho pode comer

O problema é que no objeto criado, a lista parece entrar DEPOIS do create event natural dele, de modo que ele executa o código pra todas as peças - inclusive as já comidas - criando um loop infinito.
Resolvi o problema colocando a execução do script no próprio script.

Daí, o que? Falta ainda fazer algumas coisas que eu deixo pra você:
- considerar que a casa inicial também pode ser usada como posição válida (o script só olha se tem alguma peça lá e, como não houve nenhum movimento ainda, a peça a mover ESTÁ lá)
- marcar as posições visitadas numa lista (afinal, o que interessa são os pontos por onde a peça pode passar, não as peças que ela pode comer)
- finalmente, escolher o objeto com a maior lista pra mostrar pro jogador
- Ah, fazer um script de verdade. Com essa minha mania de jogo genérico, eu uso a função "execute_file", você pode substituir pelo nome do script.

Chega de blablabla, tá aqui o script:
Código:
for(i=0; i<4; i+=1){ //4 direções
   var aComer;
   aComer=instance_position(x+lengthdir_x(dist, i*90+45), y+lengthdir_y(dist, i*90+45), obj_brancas); //a peça visada
   if(aComer){
      if (!variable_local_exists("comidas")){ //se não existe a lista (o script vem de uma peça preta)
         lugar=instance_position(x+lengthdir_x(2*dist, i*90+45), y+lengthdir_y(2*dist, i*90+45), obj_casa); //ah, sim, as casas são objetos
         if (lugar){
            if((lugar).livre==true){ //se vira pra definir "livre". Como era um teste, eu usei só o create. Sugiro usar o final de cada movimento.
               with(instance_create(x+lengthdir_x(2*dist, i*90+45), y+lengthdir_y(2*dist, i*90+45), obj_check)){ //obj_check é o objeto que vai definir o melhor caminho
                  comidas=ds_list_create(); //a lista de peças comidas
                  ds_list_add(comidas, aComer);
                  dist=point_distance(0, 0, 32, 32); //eu usei casas 32x32
                  execute_file(working_directory+"\scripts\escolheCaminho.script")
                  }
               }
            }
         }
         else if (ds_list_find_index(comidas, aComer)==-1){ //se não está na lista
            lugar=instance_position(x+lengthdir_x(2*dist, i*90+45), y+lengthdir_y(2*dist, i*90+45), obj_casa);
            if (lugar){
               if((lugar).livre==true){
                  with(instance_create(x+lengthdir_x(2*dist, i*90+45), y+lengthdir_y(2*dist, i*90+45), obj_check)){
                     comidas=ds_list_create();
                     ds_list_copy(comidas, other.comidas);
                     ds_list_add(comidas, aComer);
                     dist=point_distance(0, 0, 32, 32);
                     execute_file(working_directory+"\scripts\escolheCaminho.script")
                     }
                  }
               }
            }
      }
   }

Edit: ah, e tem um monte de variáveis que poder ser var e eu não pus assim. Só fiz "var" praquelas que eu quero que sejam do código (ou seja, podem ser chamadas de dentro do "with" sem usar "other.").

saim

Ranking : Nota B
Número de Mensagens : 2964
Idade : 38
Data de inscrição : 14/01/2011
Notas recebidas : C-D-A-B
Reputação : 121
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 3

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Fuzenrad em Sex 30 Set 2011, 11:14

Funcionou. Happy Agradeço a ajuda saim.

Mas não pretendo continuar o projeto, quem quiser continuá-lo (o projeto open source agora).

Fuzenrad

Ranking : Nota A
Número de Mensagens : 1026
Idade : 26
Data de inscrição : 04/07/2010
Notas recebidas : A-A-A-A-B
Reputação : 41
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0
Prêmios
   : 1
   : 0
   : 1

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Luca Rodrigues em Qua 12 Out 2011, 12:30

Jogo de Dama? xD que coisa besta!

@EDIT por Grotle
Faça comentários que ajudem na dúvida do autor do tópico, não escreva qualquer bobagem que vier a mente.
Punido por flood, -25%.


@Fuzenrad
Punido com ban porque eu não gostei da piada.

Luca Rodrigues

Número de Mensagens : 4
Data de inscrição : 10/10/2011
Reputação : 1
Insignia 1 x 0 Insignia 2 x 0 Insignia 3 x 0

Voltar ao Topo Ir em baixo

Re: IA de jogo de damas

Mensagem por Conteúdo patrocinado Hoje à(s) 18:36


Conteúdo patrocinado


Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum