• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

blasted

[Dúvidas] Min Max Search

5 mensagens neste tópico

Boas, mais uma vez vim pedir ajuda, e esclarecer alguams dúvidas.

Desta forma, tornou-se do meu interesse, tentar conhecer e aprofundar este sistema de "procura".

Estive a pesquisar sobre o assunto, e estou ainda a tentar compreender como funciona, mas nisto tudo, encontrei este exemplo de código:

int MinMax(int depth)

{

    if (SideToMove() == WHITE)    // White is the "maximizing" player.

        return Max(depth);

    else                          // Black is the "minimizing" player.

        return Min(depth);

}



int Max(int depth)

{

    int best = -INFINITY;



    if (depth <= 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft()) {

        MakeNextMove();

        val = Min(depth - 1);

        UnmakeMove();

        if (val > best)

            best = val;
    }

    return best;

}



int Min(int depth)

{

    int best = INFINITY;  // <-- Note that this is different than in "Max".



    if (depth <= 0)

        return Evaluate();

    GenerateLegalMoves();

    while (MovesLeft()) {

        MakeNextMove();

        val = Max(depth - 1);

        UnmakeMove();

        if (val < best)  // <-- Note that this is different than in "Max".

            best = val;
    }

    return best;

}

fonte: http://www.seanet.com/~brucemo/topics/minmax.htm

Corrigem-me se estiver errado, mas pelo que entendi, esta função "emula" todas as jogadas restantes (isto num exemplo de jogo, como o jogo do galo), com uma função constituida maioritariamente por talvez um for e um while, e que quando verificar uma combinação de jogadas que atribue a victória, assinala esse caminho, e joga, portanto, na casa especifica.

Quanto mais se aproximar da victoria, menos tempo demorará a processar a informação.

Estou bem encaminhado para o meu raciocinio?

Obrigado pela atenção

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi o raciocínio dessas funções, uma vez que chamam demasiadas funções à parte que não estão mostradas.

Se queres fazer um sistema de AI para o jogo do galo, eu faria o seguinte:

Tens 9 casas, o que dá um total de 9! jogos diferentes. (podes sempre eliminar rotações, mas complicar o código com tão poucas variações parece-me desnecessário)

Imagina uma matriz "m", 9x9! (9x362880), em que guardas todas as diferentes formas em que um jogo se pode desenvolver.

m[0][0]=1; m[0][1]=2; m[0][2]=3; etc

Indica que uma jogada possível é o primeiro jogador jogar na 1ª casa, o 2º jogador na segunda, o 1º jogador na terceira, e por aí adiante.

Numa outra matriz (de tamanho 9x9! também), podes guardar algo semelhante:

m2[555][5], diz-te quantas maneiras diferentes de ganhar existem, se as 5 primeiras jogadas tiverem sido iguais às do "jogo número 555".

Desta forma, é sempre possível escolheres qual a jogada que te dá uma maior hipótese de sucesso.

Isto num sistema simples, que se pensares bem não se torna muito complicado de programar, onde a maior parte do cálculo era feito à priori, e depois o teu programa só consultava a tabela em cada jogada para ver qual seria a melhor. Era tudo feito em pré-processamento.

Podes, depois, numa fase mais avançada, atribuir pesos às jogadas.

Uma jogada que te permita ganhar imediatamente, tem um peso infinito (se jogares ganhas, é mesmo aquela a escolher), uma que te permita ganhar em 2 peças, um peso infinito também. (afinal, tanto faz ganhar agora como daqui a bocadinho), uma que te permita ganhar em duas jogadas, dependendo da jogada do adversário, talvez já tenha um peso 10000x maior do que outra que te deixa ganhar na última cruz do tabuleiro. Uma que te faz perder peso 0.

Sei que não respondi à tua pergunta, mas esta talvez fosse uma das minhas implementações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, o jogo já o tenho feito, com AI a funcionar, mas tenho muitas linhas de código, a AI foi feita de forma muito primitiva, com bastantes condições e um pouco imperfeito. Para tal queria aprender a trabalhar com o que me foi sugerido no outro tópico... não sei se estou bem encaminhado, mas vou tentar aprender a trabalhar com este sistema, pois parece-me bastante útil, não so a nivel de AI de um jogo mas como também em outras variadas situações.

De qualquer maneira agradeço a tua ajuda.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

As funções min e max são funções recursivas que usam uma função de avaliação para uma determinada posição do tabuleiro. A função de avaliação é Evaluate(). As funções min e max vão se chamar a si proprias até um nivel de profundidade "depth", que representa a profundidade de pensamento, basicamente quantas jogadas á frente está a analizar. Encontras o conceito de profundidade bem explorado nos jogos de xadrez.

As funções vão percorrer as jogadas possiveis  "GenerateLegalMoves()" para cada nivel de profundidade. Sempre que existe um caminho na arvore de pesquisa onde a pontuação é máxima esse será o caminho optimo até ao momento, e guarda-o "best = val".

A pesquisa chama-se min max porque quando é a vez do jogador que está a avaliar a pontuação do seu jogo, o resultado é somado ao valor do caminho, e quando é o adversario a pontuação é subtraida. Isso quer dizer que se nivel pensamento "depth" estiver por exemplo em 4 jogadas. Um possivel resultado da recursividade será: 1. +50    2. -5    3. +30    4. -5 isto dá um resultado de 70, positivo ao fim de 4 jogadas. Mas se a 5 jogada que não for analisada tiver um peso de -100 então o algoritmo está perante uma jogada que vai gerar uma catastrofe eminente. Evidente será dizer que quanto maior o nivel de profundidade melhor o pensamento do algoritmo, mas também mais lento. Exitem tecnicas que cortam a arvore de pesquisa e consequentemente permitem atingir maiores niveis de profundidade, mas isso é outro assunto.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mais uma coisa. Os conceitos de recursividade e backtracking usados nestes algoritmos são bastante uteis se forem bem entendidos.

Para aprender a trabalhar com estes conceitos nada melhor do que aprender Prolog. A linguagem em si na minha opinião, não é grande coisa, mas explora bem estes conceitos que são uteis.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora