Jogo da Velha(minMax) - Jogada da maquina

[jcrbs]

Eu queria saber como melhorar o jogo do computador. Porque quando eu elevar o nível de jogo no computador em vez disso, deve desempenhar o seu melhor, o que não ocorre. Eu coloquei o movimento em uma lista de árvore aumentando-a cada interação de acordo com a atual diretoria e do nível de dificuldade. Por exemplo, se o nível aumenta gera mais ocorrências de avaliar.

/****

*

* MelhorJogada(): Estima a melhor jogada a ser feita a seguir

*

* Argumentos: tab (entrada) - tabuleiro que representa a raiz da árvore de jogo

* atual

* profundidade (entrada) – a profundidade da árvore de jogo

* jogador (entrada) – o jogador da vez

* novoTab (saída) - tabuleiro original alterado para conter a melhor

* jogada

*

****/

/****

*

* ConstroiArvore(): Retorna um ponteiro para uma árvore de jogo

*

* Argumentos: tab (entrada) - tabuleiro que representa a raiz da árvore

* profundidade (entrada) – a profundidade da árvore

*

* Retorno: ponteiro para a raiz da árvore criada

*

****/

/****

*

* Expande(): Expande um nó da árvore de jogo, gerando todas as posições

* que podem ser obtidas a partir do tabuleiro do nó recebido

* como argumento. Os nós gerados tornam-se filhos do nó

* recebido como argumento. Então, esta função é chamada

* recursivamente usando os nós gerados como argumentos até

* que a profundidade desejada seja atingida.

*

* Argumentos: p (entrada/saída) - ponteiro para o nó a ser expandido

* nivel (entrada) – nível do nó

* profundidade (entrada) – profundidade da expansão

*

****/

/****

*

* GeraFilhos(): Retorna um ponteiro para uma lista de nós que são filhos do

* nó cujo tabuleiro é passado como argumento.

*

* Argumentos: tab (entrada) – tabuleiro do qual serão gerados os nós

*

* Retorno: ponteiro para a lista de nós gerados

*

****/

/****

*

* AcrescentaNaLista(): Acrescenta um nó à lista de nós recebida como argumento

* e retorna um ponteiro para a lista acrescida

*

* Argumentos: lista (entrada/saída) – ponteiro para início da lista de nós

* tab (entrada) – tabuleiro antes da jogada

* linha, coluna (entrada) – a linha e a coluna onde será feita a

* jogada

* jogada (entrada) – a jogada a ser feita (X ou O)

*

* Retorno: ponteiro para a lista acrescida do nó resultante da jogada

*

****/

/****

*

* ProcuraMelhorLance(): Procura a melhor jogada na árvore cuja raiz é

* recebida como argumento

*

* Argumentos: arvore (entrada) – ponteiro para a árvore de jogo

* jogador (entrada) – o jogador (X ou O) que tem a vez

* melhor (saída) – ponteiro para o nó que representa a melhor jogada

* valor (saída) – o valor do melhor nó

*

****/

/****

*

* Avalia(): Avalia estaticamente a posição do tabuleiro para o dado jogador.

* O resultado da avaliação é o número de linhas, colunas e

* diagonais que podem ser preenchidas pelo jogador menos o número

* destas que podem ser preenchidas por seu oponente.

*

* Argumentos: tab (entrada) - o tabuleiro que será avaliado

* jogador (entrada) - o jogador que tem a vez

*

* Retorno: o valor da avaliação

*

****/

* ConstroiArvore (): Retorna um ponteiro para uma árvore de jogo

* Argumentos: guia (entrada) - a placa que representa a raiz da árvore de profundidade (de entrada) - a profundidade da árvore

* Retorno: ponteiro para a raiz da árvore criada

* Expande (): Expande um nó da árvore de jogo, criando todas as posições que podem ser obtidos a partir da placa do nó recebido como argumento. A gerado nos tornamos filhos do nó recebido como argumento. Assim, esta função é chamada recursivamente gerado usando os nós como argumentos, até a profundidade desejada.

* Argumentos: P (entrada / saída) - ponteiro para o nó a ser expandido

* Nível (entrada) - nível de nó

* Profundidae (em) - expansão de profundidade

* GeraFilhos (): Retorna um ponteiro para uma lista de nós que são filhos do nó cujo conselho é passado como argumento.

* Argumentos: guia (entrada) - O Conselho de que serão gerados os nós

* Retorno: ponteiro para a lista de nós gerados

* AcrescentaNaLista (): Adiciona um nó para a lista que recebeu como um argumento e retorna um ponteiro para a lista mais

* Argumentos: lista (entrada / saída) - ponteiro para o início da lista de nós

* Guia (entrada) - a bordo antes da mudança

* Linha, coluna (de entrada) - a linha ea coluna onde o jogo será

* Move (entrada) - o movimento a ser feito (X ou O)

*

* Retorno: ponteiro para o nó lista resultante do jogo aumento

* ProcuraMelhorLance (): Procurando a melhor jogada na árvore cuja raiz é

Recebido como argumento

* Argumentos: árvore (entrada) - ponteiro para a árvore de jogo

* Player (entrada) - o jogador (X ou W), com o

* Melhor (saída) - ponteiro para o nó que representa o melhor jogo

* Valor (output) - o valor da melhor nó

* Avaliar (): Avalia posição estaticamente placa para o jogador.

* O resultado da avaliação é o número de linhas, colunas e diagonais que podem ser preenchidos pelo jogador menos o número destes que pode ser preenchido por seu adversário.

* Argumentos: guia (entrada) - O Conselho que será avaliada

* Player (entrada) - o jogador que tem a vez

* Retorno: O valor da avaliação

#include <stdio.h>
#include <stdlib.h>


typedef enum {VAZIO = ' ', O = 'O', X = 'X'} tConteudo;
typedef enum {MIN, MAX} tTipoDeNo;
typedef enum {FAIL, SUCESS} tValida;
typedef enum {EASY = 1, MEDIUM = 2, HARD = 3} tDificult;


typedef  struct  no
{
    tConteudo tabuleiro[3][3];
    tTipoDeNo tipoDeNo;
    struct  no  *filhoEsquerda;
    struct  no  *proximoIrmao;
} tNo, *tArvore;


tArvore AcrescentaNaLista( tArvore *lista, tConteudo tab[][3],
                           unsigned linha, unsigned coluna, tConteudo jogada )
{
    tArvore   aux;
    unsigned  i, j;
    aux = (tArvore)malloc(sizeof(tNo));

    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            aux->tabuleiro[i][j] = tab[i][j];
    aux->tabuleiro[linha][coluna] = jogada;
    aux->proximoIrmao = *lista;
    aux->filhoEsquerda = NULL;
    *lista = aux;
    return aux;
}



tArvore GeraFilhos(tConteudo tab[][3])
{
    tArvore   listaDeNos = NULL;
    tConteudo quemJoga;
    unsigned  i, j;
    quemJoga =  O;
    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            if (tab [i][j] == VAZIO)
                listaDeNos = AcrescentaNaLista(&listaDeNos, tab, i, j, quemJoga);
    return listaDeNos;
}

void Expande(tArvore p, unsigned nivel, unsigned profundidade)
{
    tArvore filhos;
    if (nivel <= profundidade)
    {
        filhos = GeraFilhos(p->tabuleiro);
        p->filhoEsquerda = filhos;

        while(filhos)
        {
            if (p->tipoDeNo == MAX)
                filhos->tipoDeNo = MIN;
            else
                filhos->tipoDeNo = MAX;

            filhos->filhoEsquerda = NULL;

            Expande(filhos, nivel + 1, profundidade);
            filhos = filhos->proximoIrmao;
        }
    }
}


tArvore ConstroiArvore(tConteudo tab[][3], unsigned profundidade)
{
    tArvore  arvore;
    unsigned i, j;
    arvore = malloc(sizeof(tNo));

    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            arvore->tabuleiro[i][j] = tab[i][j];
    arvore->tipoDeNo = MAX;
    arvore->filhoEsquerda = NULL;
    arvore->proximoIrmao = NULL;
    Expande(arvore,  1, profundidade);
    return arvore;
}

int Avalia(tConteudo tab[][3], tConteudo jogador)
{
    unsigned  i, j;
    tConteudo oponente;
    int valor = 0, valorOponente = 0;

    for (i = 0; i < 3; ++i)
        if ( ((tab[i][0] == jogador) || (tab[i][0] == VAZIO)) &&
                ((tab[i][1] == jogador) || (tab[i][1] == VAZIO)) &&
                ((tab[i][2] == jogador) || (tab[i][2] == VAZIO)) )
            valor++;
    /* Verifica quantas colunas o jogador pode preencher */
    for (j = 0; j < 3; ++j)
        if ( ((tab[0][j] == jogador) || (tab[0][j] == VAZIO)) &&
                ((tab[1][j] == jogador) || (tab[1][j] == VAZIO)) &&
                ((tab[2][j] == jogador) || (tab[2][j] == VAZIO)) )
            valor++;
    /* Verifica quantas diagonais o jogador pode preencher */
    if ( ((tab[0][0] == jogador) || (tab[0][0] == VAZIO)) &&
            ((tab[1][1] == jogador) || (tab[1][1] == VAZIO)) &&
            ((tab[2][2] == jogador) || (tab[2][2] == VAZIO)) )
        valor++;
    if ( ((tab[0][2] == jogador) || (tab[0][2] == VAZIO)) &&
            ((tab[1][1] == jogador) || (tab[1][1] == VAZIO)) &&
            ((tab[2][0] == jogador) || (tab[2][0] == VAZIO)) )
        valor++;
    oponente =  X;

    for (i = 0; i < 3; ++i)
        if ( ((tab[i][0] == oponente) || (tab[i][0] == VAZIO)) &&
                ((tab[i][1] == oponente) || (tab[i][1] == VAZIO)) &&
                ((tab[i][2] == oponente) || (tab[i][2] == VAZIO)) )
            valorOponente++;

    for (j = 0; j < 3; ++j)
        if ( ((tab[0][j] == oponente) || (tab[0][j] == VAZIO)) &&
                ((tab[1][j] == oponente) || (tab[1][j] == VAZIO)) &&
                ((tab[2][j] == oponente) || (tab[2][j] == VAZIO)) )
            valorOponente++;

    if ( ((tab[0][0] == oponente) || (tab[0][0] == VAZIO)) &&
            ((tab[1][1] == oponente) || (tab[1][1] == VAZIO)) &&
            ((tab[2][2] == oponente) || (tab[2][2] == VAZIO)) )
        valorOponente++;
    if ( ((tab[0][2] == oponente) || (tab[0][2] == VAZIO)) &&
            ((tab[1][1] == oponente) || (tab[1][1] == VAZIO)) &&
            ((tab[2][0] == oponente) || (tab[2][0] == VAZIO)) )
        valorOponente++;
    return (valor - valorOponente);
}

void ProcuraMelhorLance(tArvore arvore, tConteudo jogador, tArvore *melhor,
                        int *valor)
{
    tArvore  p, melhor2;
    int      valor2;
    if (!arvore->filhoEsquerda)
    {
        *valor = Avalia(arvore->tabuleiro,jogador);
        *melhor = arvore;
    }
    else
    {
        p = arvore->filhoEsquerda;
        ProcuraMelhorLance(p, jogador, melhor, valor);
        *melhor = p;

        if (arvore->tipoDeNo == MIN)
            *valor = (-1)*(*valor);
        p = p->proximoIrmao;
        while (p)
        {
            ProcuraMelhorLance(p, jogador, &melhor2, &valor2);
            if (arvore->tipoDeNo == MIN)
                valor2 = (-1)*valor2;
            if (valor2 > *valor)
            {
                *valor = valor2;
                *melhor = p;
            }
            p = p->proximoIrmao;
        }
        if (arvore->tipoDeNo == MIN)
            *valor = (-1)*(*valor);
    }
}

void DestroiArvore(tArvore* raiz){

     if(*raiz != NULL){
             if((*raiz)->filhoEsquerda != NULL)
                DestroiArvore(&((*raiz)->filhoEsquerda));
             if((*raiz)->proximoIrmao != NULL)
                DestroiArvore(&((*raiz)->proximoIrmao));
             free(*raiz);
             *raiz = NULL;
     }
}



void MelhorJogada( tConteudo tab[][3], unsigned profundidade, tConteudo jogador,
                   tConteudo novoTab[][3] )
{
    tArvore  arvore, melhorLance;
    unsigned i, j;
    int      valor;

    arvore = ConstroiArvore(tab, profundidade);

    ProcuraMelhorLance(arvore, jogador, &melhorLance, &valor);
    for (i = 0; i < 3; ++i)
        for (j = 0; j < 3; ++j)
            novoTab[i][j] = melhorLance->tabuleiro[i][j];
    DestroiArvore(&arvore);
}

void Apresentacao(void)
{

    char enter;

    printf("Bem-vindo ao Jogo da Velha:\n");
    printf("O jogador comeca!!! \nEscolha se quer ser 'X' ou 'O'\nPronto p/comecar...");
    printf("Aperte ENTER p/ iniciar...");
    scanf("%c", &enter);
    if(enter == '\n')
    {
        system("cls");
    }

}
void InicializaTabuleiro(tConteudo tabuleiro[][3])
{

    unsigned  i, j, nOs = 0, nXs = 0;
    printf("\t\t\t\tTABULEIRO INICIALIZADO\n\n");
    for (i = 0; i < 3; ++i)
    {

        if(i == 1 || i ==2 )
        {
            printf("--- --- ---\n");
        }

        for (j = 0; j < 3; ++j)
        {
            tabuleiro[i][j] = VAZIO;
            if( j ==1)
                printf("| %c |", tabuleiro[i][j]);
            else
                printf(" %c ", tabuleiro[i][j]);
        }

        printf("\n");
    }

}

void ApresentaJogo(tConteudo tabuleiro[][3])
{

    unsigned  i, j;

    for (i = 0; i < 3; ++i)
    {

        if(i == 1 || i ==2 )
        {
            printf("--- --- ---\n");
        }

        for (j = 0; j < 3; ++j)
        {

            if( j ==1)
                printf("| %c |", tabuleiro[i][j]);
            else
                printf(" %c ", tabuleiro[i][j]);
        }

        printf("\n");
    }

}


void EscolheJogada(tConteudo tabuleiro[][3], tConteudo  jogador)
{

    tValida cond = FAIL;
    int opcao;


    do{

            printf("Escolha a jogada 1 a 9:\n");
            scanf("%d", &opcao);


            switch(opcao)
            {
            case 1:
                if(tabuleiro[0][0] == VAZIO)
                {
                    tabuleiro[0][0] = jogador;
                    cond = SUCESS;
                }
                break;
                 case 2:
                if(tabuleiro[0][1] == VAZIO)
                {

                    tabuleiro[0][1] = jogador;
                    cond = SUCESS;
                }
                break;
            case 3:
                if(tabuleiro[0][2] == VAZIO){
                    tabuleiro[0][2] = jogador;
                    cond = SUCESS;
                }
                break;
            case 4:
                if(tabuleiro[1][0] == VAZIO){
                    tabuleiro[1][0] = jogador;
                    cond = SUCESS;
                }
                break;
            case 5:
                if(tabuleiro[1][1] == VAZIO)
                {

                    tabuleiro[1][1] = jogador;
                    cond = SUCESS;
                }
                break;
            case 6:
                if(tabuleiro[1][2] == VAZIO)
                {
                    tabuleiro[1][2] = jogador;
                    cond = SUCESS;
                }
                break;
            case 7:
                if(tabuleiro[2][0] == VAZIO)
                {

                    tabuleiro[2][0] = jogador;
                    cond = SUCESS;
                }
                break;
            case 8:
                if(tabuleiro[2][1] == VAZIO)
                {

                    tabuleiro[2][1] = jogador;
                    cond = SUCESS;
                }
                break;
            case 9:
                if(tabuleiro[2][2] == VAZIO)
                {
                    tabuleiro[2][2] = jogador;
                    cond = SUCESS;
                }
                break;
            }
        }while (cond!= SUCESS);


}

unsigned JogoTerminado(tConteudo  tabuleiro[][3])
    {

        unsigned  i, j;
        tConteudo cont = VAZIO;

        unsigned jogadas =0;
        for (i = 0; i < 3; ++i)
            for (j = 0; j < 3; ++j)
                if (tabuleiro[i][j] == VAZIO)
                {
                    jogadas++;
                }

        return jogadas;
    }


tConteudo EhVencedor(tConteudo Matriz[][3])
{
    int linha, coluna;
    tConteudo vez = X;
    int ct=0;
    while (ct < 2){

     for (linha = 0; linha < 3; linha++){
     if ((Matriz[linha][0] == vez) && (Matriz[linha][1] == vez) && (Matriz[linha][2] == vez))
     return vez;

  for (coluna = 0; coluna < 3; coluna++){
    if ((Matriz[0][coluna] == vez) && (Matriz[1][coluna] == vez) && (Matriz[2][coluna] == vez))
      return vez;
  }
  if ((Matriz[0][0] == vez) && (Matriz[1][1] == vez) && (Matriz[2][2] == vez)){
     return vez;
    }
  if ((Matriz[0][2] == vez) && (Matriz[1][1] == vez) && (Matriz[2][0] == vez)){
    return vez;
}
     }
    vez = O;
    ct++;

}
   return VAZIO;
}



void AtualizaTabuleiro(tConteudo tabuleiro[][3], tConteudo novoTabuleiro[][3]){

        unsigned  i, j;

        for (i = 0; i < 3; ++i)
            for (j = 0; j < 3; ++j)
            tabuleiro[i][j] = novoTabuleiro[i][j];

}




    int main (void)
    {

        tConteudo tabuleiro[3][3];
        tConteudo novoTabuleiro[3][3];
        tConteudo jogador = X;
        tConteudo oponente = O;
        tConteudo campeao = VAZIO;
        tDificult prof = HARD;
        int opcao;
        int flag =  0;

        //Apresentacao();
            //printf("%d", (int)prof);
        InicializaTabuleiro(tabuleiro);
        //InicializaTabuleiro(novoTabuleiro);

        /*
        printf("\nEscolha a Dificuldade:\n 1 - FACIL\n2 - MEDIO\n3 - DIFICIL \n");
        scanf("%d", &prof);*/

        printf("%d", JogoTerminado(tabuleiro));
        printf("\nVc quer Iniciar?:\n 1 - SIM\n0 - não \n");
        scanf("%d", &flag);



        while( JogoTerminado(tabuleiro) > 0)
        {
            printf("Quantidade de jogadas= %d\n", JogoTerminado(tabuleiro));
            if (flag == 1)
            {
                EscolheJogada(tabuleiro, jogador);
                flag = 0;
                //ApresentaJogo(tabuleiro);
            }
            else
            {
                MelhorJogada( tabuleiro, (int)prof,oponente,novoTabuleiro);
                //EscolheJogada(tabuleiro, oponente);
                //
                //ApresentaJogo(novoTabuleiro);
                AtualizaTabuleiro(tabuleiro, novoTabuleiro);

                flag = 1;
            }

            ApresentaJogo(tabuleiro);
            campeao = EhVencedor(tabuleiro);

            if(campeao == O ){
            printf("COMPUTER WIN");
            break;
            }else if(campeao == X){
            printf("YOU WIN!");
            break;
            }


        }


if(campeao == VAZIO){
    printf("DRAW!!!");
}



        system("PAUSE");
        return 0;
}

Edited December 31, 2012 by jcrbs