Algoritmos para o jogo do galo

[blasted]

Boas. Estou a desenvolver o jogo do galo em Javascript, e após ter criado o jogo para 2 jogadores, e uma AI que joga ao acaso, quis avançar um bocado mais e criar um algoritmo que responda perante determinadas situações.

Ao pensar no assunto e pesquisar, deparei-me com a seguinte situação. Existem diferentes tipos de AI principais, seja ela para jogar com resposta defensiva, ou a jogar com resposta atacante.

Se envergar por uma AI defensiva, a sua estrutura seria mais fácil, menos perfeita com talvez alguma percentagem do jogador ganhar (consoante a complexidade do algoritmo),

se pelo outro lado tentar uma AI atacante, teria mais problemas, e pelo que me referiram, estes seriam relaconados com as probabilidades matemáticas.

Tenho em mente usar matrizes na construção do algoritmo, apesar da minha primeira ideia ter sido explorar todas as opções possiveis, o que decididamente seria um desperdicio de tempo e de linhas de código, e também de CPU.

Decidido então em tentar criar um algoritmo com funcionalidade atacante, necessitava de algumas opiniões e talvez ajuda na resolução deste.

Alguém tem alguma ideia de por onde hei-de começar esta lógica?

Agradeço a vossa ajuda,

Cumprimentos

[shumy]

Pesquisa na arvore de desisão. Mas evitando analisar todos os movimentos. Para o jogo do galo provavelmente se analizares todas as alternativas possiveis vai demorar uns milisegundos. Mas para jogos com caminhos de desisão mais complexos podes informar-te sobre as tecnicas de alpha-beta pruning, Min-Max Search, coisas do genero.

Boa sorte.

[blasted]

boas, obrigado pela ajuda. Após passar o dia todo a estudar as árvores, cheguei à conclusão do seguinte.

vou ter que responder perante 4 situações, que me leva a crer que terei a AI perfeita.

como ainda n construi o programa não consigo afirmar isso de certeza.

os quatro processos da AI são os seguintes por esta ordem, tendo em conta o esquema seguinte:

A|B|C

D|E|F

G|H|I

(exemplo de grelha do jogo do galo)

Em primeiro lugar procurará se pode ou não ganhar o jogo

Em segundo, caso não seja possivel ganhar, procurará se existem falhas na "defesa", caso o jogador esteja numa jogada eminente de ganhar, a AI deverá de tapar essa hipotse.

Em terceiro lugar, se nehuma das duas primeiras hipotses se verificar,  jogará numa casa oposta à do jogador

Se tal também não se confirmar, deverá de jogar à sorte.

Ainda não testei esta teoria, e como tal não passa disto.

de entre os quatro passos o mais dificil deverá de ser a de jogar na casa oposta.

O esquema de verificação das casas, tanto para ataque como para defesa, deverá de constituir em grupos de duas "peças", que possam possivelmente traçar uma vitoria.

Desta forma terei queverificar as seguintes situações para o ataque e para a defesa:

(horizontal)

a+b then c

b+c then a

a+c then b

d+e then f

e+f then d

d+f then e

g+h then i

h+i then g

g+i then h

(vertical)

a+d then g

d+g then a

a+g then d

b+e then h

e+h then b

b+h then e

c+f then i

f+i then c

c+i then f

(diagonal)

a+e then i

e+i then a

a+i then e

c+e then g

e+g then c

o que escrevi em cima não é nenhuma linguagem de programação, apenas uma dedução.

espero ter sido claro, pois isto pdoerá servir de solução para outros casos.

[Hipnoted]

Não seo se isto ajuda mas o neon_prannok e o preotorian fizeram esse jogo em Python.

Vê isto: http://www.portugal-a-programar.pt/index.php?showtopic=5902

[shumy]

Eu orientava-me mais pelo seguinte. Pelo menos no xadrez que é bem mais complexo sei que é assim. 

1. Define o que é uma posição no tabuleiro. como são representados os dados para um estado no tabuleiro.

2. Define uma função que avalie a posição do tabuleiro. Isto é, olhando apenas para a posição estatica, dar uma pontuação para cada jogador. Era bom que fosse uma função do tipo min-max, sedo um empate 0 para ambos e se alguem tiver em vantagem o jogador contrario tem os mesmos pontos mas negativo.

3. Define uma função recursiva que use a função de avaliação estática. Esta função recursiva vai usar o somatorio dos resultados  para cada nivel de profundidade na arvore de pesquisa. Basicamente é a função que percorre as posições possiveis até ao nivel de profundidade definido. 

4. Fase de optimização. Aplica funcionalidade do tipo alpha-beta pruning á tua função recursiva para cortar ramos na arvore de pesquisa. Ordenar os caminhos de decisão por pontuação ajuda bastante no corte da arvore. 

[tiagoagm]

pah eu tenhu o jogo em c n sei s ajuda  👍