sábado, 6 de agosto de 2016

Jogo do Galo e algumas variantes

É um jogo que já mete nojo de fazer nesta Internet, mas que serve para experimentar algoritmos como o minimax com corte alfa-beta, que já não vale a pena explicar. Vendê-lo é impensável com tanta oferta livre.

Vale a pena explicar a interface geek, que apesar de ser linha de comandos é fácil de mexer e pode-se tornar atraente para várias pessoas. Mostrar que uma GUI não é tudo e que se pode fazer muita coisa com a tabela ascii! Os meus primeiros jogos eram assim já no secundário. A universidade ensina outras coisas melhores como a tão importante inteligência artificial com o minimax com corte alfa-beta.





















Este é um exemplo de execução no modo de jogo 5x5. Nos modos de jogo 4x4 e 5x5 o utilizador tem de fazer uma linha de 4 para ganhar.

no modo de jogo 3x3 é preciso fazer uma linha de 3 para ganhar. Escolha um número com o teclado para jogar e prima mudança de linha ou ENTER.

Há ainda a hipótese de jogar contra outro. Digam as jogadas pelo Skype e insiram cada um para depois jogarem um contra o outro.Pode notar a existência de 2 línguas (português e inglês).

As opções permitem mudar de modo de jogo e língua. Se quer ser nerd pode sempre editar os ficheiros de configuração, mas não aconselho a ninguém fazer isso.

Se há outros algoritmos para o jogo do Galo?

A resposta é sim: negamax, negascout, negascout com memória, SSS* e MTD-f.



Só se usa variantes do minimax?

Não! É possível usar o algoritmo de Monte Carlo seguinte disponível em vários jogos do CIG do IEEE.

Como o jogo é discreto não há necessidade de discritizar o espaço com foi no caso do pacman. A ideia é montar vários planos de jogo que são guardados num ficheiro para o programa poder competir com o jogador humano. Pretende-se que o algoritmo simule vários jogos com a seguinte estratégia:



1. Coloca uma marca X ou O de todas as opções disponíveis usando um número aleatório.

2. Repete o passo 1 para os jogadores X e O alternativamente. Quando não existe posições para colocar uma marca. ou um jogador ultrapassou uma dada profundidade, o jogo acaba.

3. Associa pontos ao fim do jogo (tipicamente dando 1 ponto para o vencedor e zero pontos para o perdedor)

4. A pontuação média é determinada pela repetição dos passos 1 até 3 várias vezes.



As melhores jogadas (determinadas por uma fórmula da entropia) servem para expandir os nós na árvore que têm mais sucesso nas simulações e assim o algoritmo vai melhorando a sua estratégia. Aconselho a introduzir uma melhoria inspirada no A* para delimitar o número de nós gerados aleatoriamente. O A* é famoso pela sua introdução de heurísticas numa árvore de procura, o que tornará o jogo mais atractivo para um hard core gamer.

Sem comentários:

Publicar um comentário