O algoritmo deve usar para “melhoramento genético AI”

Question

Primeiro de tudo: Este é não uma pergunta sobre como fazer um jogo programa de cinco em uma fileira. Estado lá, feito isso.

introdutória explicação

Eu fiz um cinco-em-um-fila jogo como um quadro de experimentar com melhoramento genético AI (ouch, que soa terrivelmente pretensioso). Tal como acontece com a maioria dos jogos turn-based a melhor jogada é decidida através da atribuição de uma pontuação para cada movimento possível, e, em seguida, jogando o movimento com a maior pontuação. A função para atribuir uma pontuação para um movimento (um quadrado) é algo como isto:

1. Se o quadrado já tem um símbolo, a pontuação é de 0, já que seria ilegal colocar um novo token na praça.

2. Cada quadrado pode ser uma parte de até 20 linhas vencedoras diferentes (5 horizontal, 5 vertical, diagonal) 10. A pontuação do quadrado é a soma da pontuação de cada uma dessas linhas.

3. A pontuação de uma linha depende do número de amigos e inimigos já fichas na linha. Exemplos:

   • Uma fila com quatro fichas amigável deve ter pontuação infinito, porque se você colocar um sinal lá você ganhar o jogo.
   • A pontuação para uma linha com quatro inimigo fichas deve ser muito alta, pois se você não colocar um sinal lá, o adversário vai ganhar em seu próximo turno .
   • Uma linha com ambas as fichas amigas e inimigas vai marcar 0, uma vez que esta linha nunca pode ser parte de uma linha vencedora.

Diante desse algoritmo, eu declarei um tipo chamado TBrain:

type
  TBrain = array[cFriendly..cEnemy , 0..4] of integer; 

Os valores na matriz indica o marcador de uma fileira, quer com fichas N simpáticos e 0 fichas inimigas, ou 0 fichas simpáticos e N fichas inimigos. Se houver 5 fichas em uma fileira não há nenhuma pontuação desde a linha está cheio.

É realmente muito fácil de decidir quais valores devem ser na matriz. Cérebro [0,4] (quatro fichas amigáveis) deve ser "infinito", o chamado de deixar isso 1.000.000. vBrain [1,4] deve ser muito alta, mas não tão alto que o cérebro prefere bloqueando várias vitórias inimigas ao invés de wining si

concider o seguinte (improvável) placa:

  0123456789
 +----------
0|1...1...12
1|.1..1..1.2
2|..1.1.1..2
3|...111...2
4|1111.1111.
5|...111....
6|..1.1.1...
7|.1..1..1..
8|1...1...1.

Jogador 2 deve colocar o seu em sinal (9,4), ganhar o jogo, não em (4,4), mesmo que ele, então, bloquear 8 potenciais linhas vencedoras para o jogador 1. Ergo, vBrain [1,4] deve ser (vBrain [0,4] / 8) -1. Trabalhando como esta podemos encontrar os valores ideais para o "cérebro", mas, novamente, este é não o que eu estou interessado. Eu quero um algoritmo para encontrar os melhores valores .

Eu tenho implementado neste quadro de forma que é totalmente determinista. Não há valores aleatórios acrescentados à pontuação, e se várias praças têm a mesma pontuação será escolhido o canto superior esquerdo.

problema real

Isso é tudo para a introdução, agora para a parte interessante (para mim, pelo menos)

Eu tenho dois "cérebros", vBrain1 e vBrain2. Como devo iteratively torná-los melhor? Imagino algo como isto:

1. Inicializar vBrain1 e vBrain2 com valores aleatórios.
2. Simular um jogo entre eles.
3. Atribuir os valores do vencedor para o perdedor, em seguida, altere aleatoriamente um deles ligeiramente.

Este não parece trabalho. Os cérebros não obter qualquer mais inteligente. Por quê?

Caso o método-score adicionar alguns valores aleatórios pequenos ao resultado, de modo que dois jogos entre os mesmos dois cérebros seria diferente? Quanto deve os valores mudam para cada iteração? Como deve ser o "cérebro" ser inicializado? Com valores constantes? Com valores aleatórios?

Além disso, isso tem qualquer para fazer com AI ou algoritmos genéticos em tudo?

PS: A questão não tem nada a ver com cinco em uma fileira. Isso é apenas algo que eu escolhi porque eu posso declarar uma forma muito simples "Brain" para experimentar em.

Answer 1

De um modo geral, sim, você pode fazer um cérebro de forma mais inteligente, utilizando técnicas de algoritmos genéticos.

A aleatoriedade, ou mutação, desempenha um papel significativo na programação genética.

Eu gosto deste tutorial, Genetic algoritmos: Cool Nome & Droga simples
. (Ele usa Python para os exemplos, mas não é difícil entendê-los)

Answer 2

Se você quer abordar este problema como um algoritmo genético, você vai precisar de uma população inteira de "cérebros". Em seguida, avaliá-los uns contra os outros, seja cada combinação ou usar um estilo de torneio. Em seguida, selecione o topo X% da população e utilizá-las como os pais da próxima geração, onde filhos são criados através de mutação (que você tem) ou cruzamento genético (por exemplo, linhas de swap ou colunas entre dois "cérebros").

Além disso, se você não vê qualquer progresso evolutivo, você pode precisar de mais do que apenas ganhar / perda, mas chegar a algum tipo de sistema de pontos de modo que você pode classificar toda a população de forma mais eficaz, o que torna a seleção mais fácil.

Answer 3

Dê uma olhada Neuro Evolução de aumentar Tologies (NEAT) . Um acronymn sofisticados que basicamente significa a evolução de redes neurais - tanto a sua estrutura (topologia) e pesos de conexão. Eu escrevi uma implementação do .NET chamado SharpNEAT que você pode querer olhar. SharpNEAT V1 também tem uma experiência Tic-Tac-Toe.

http://sharpneat.sourceforge.net/