Jogo da Velha usando Árvores e MiniMax

[Otávio Palma]

Bom dia amigos, estou precisando de uma ajuda, tenho um trabalho para entregar que precisa seguir a seguinte lógica:

Implementação de um jogo da velha (utilizando Min-Max), o programa precisa ser feito utilizando árvores, uma vez que haverá como escolher o nível de dificuldade, sendo este nível, o número de linhas que a IA percorrerá na árvore (por exemplo: nível máximo -> percorre a árvore toda (nunca perde)).

Meu professor já disponibilizou uma função que cria todas as jogadas possíveis, dessa forma, eu preciso encontrar algum jeito de implementá-la no código, segue o mesmo:

#include<stdio.h>
#define quantidadePossibilidades 9

unsigned int vetorDisponibilidadeJogada[quantidadePossibilidades];
unsigned int vetorJogadas[9];

void imprimeJogada () {
	int i;
	for (i = 0; i < quantidadePossibilidades; i++){
		printf("%d, ", vetorJogadas[i]);
	}
	printf("\n");
	getchar();
}

void funcaoRecursivaPossibilidades (int alturaDaArvore) {
	int i = 0;
	
	if (alturaDaArvore == quantidadePossibilidades){
		printf("Chegou ao fim da Arvore: ");
		imprimeJogada();
	}
	else {
		for (i = 0; i < quantidadePossibilidades; i++){
			
			if (vetorDisponibilidadeJogada[i] == 1){
				vetorDisponibilidadeJogada[i] = 0;
				vetorJogadas[alturaDaArvore] = i;
								
				funcaoRecursivaPossibilidades(alturaDaArvore + 1);
				
				vetorDisponibilidadeJogada[i] = 1;
			}
		}	
	}
}

void inicializaVetorPossibilidades (){
	int i;
	for (i = 0; i < quantidadePossibilidades; i++){
		vetorDisponibilidadeJogada[i] = 1;
	}
}

main () {
	/*inicializando o vetor de possibilidades
	- no inicio, todas as possibilidades de jogada 
	estão disponiveis*/
	inicializaVetorPossibilidades();
	/*funcao recursiva para enumerar todas as possibilidades de jogada*/
	funcaoRecursivaPossibilidades(0);
}

De forma resumida, tenho que criar uma árvore com todas as jogadas possíveis e ao utilizar o min-max fazer a IA escolher as melhores jogadas baseada na dificuldade.

 

Estou utilizando a seguinte estrutura para criação de nós da árvore:

typedef struct no
{
	int minimax;
	struct no *posicao[9];
	int valor;
} node;

Preciso de ajuda para a construção da árvore (implementação da função inserir), espero que possam me ajudar e me perdoem por qualquer erro.

[devair1010]

@Otávio Palma     aqui uma função com todas as posições possíveis do jogo da velha , nela a variável vl_nivel é o nível de dificuldade que pode ser    muito fácil      fácil     médio      difícil     muito difícil   sendo que as posições estão guardadas na matriz  vet [ 3 ] [ 3 ] , com isso você escolhe qual nível de dificuldade e coloca na variável vl_nivel .

int raciocinio(int p){  /*nivel muito fácil*/
    if(vl_nivel > 0){    /*  nivel fácil*/
        if(vet[2][2]==0){
            vet[2][2]=1;
            return 1;
        }
        if(vet[2][2]==p){
            if(vet[1][1]==p){
                if(vet[3][3]==0){
                    vet[3][3]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[1][2]==p){
                if(vet[3][2]==0){
                    vet[3][2]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[1][3]==p){
                if(vet[3][1]==0){
                    vet[3][1]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[2][3]==p){
                if(vet[2][1]==0){
                    vet[2][1]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[3][3]==p){
                if(vet[1][1]==0){
                    vet[1][1]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[3][2]==p){
                if(vet[1][2]==0){
                    vet[1][2]=1;
                    return 1;
                }
            }
        }
        if(vet[2][2]==p){
            if(vet[3][1]==p){
                if(vet[1][3]==0){
                    vet[1][3]=1;
                    return 1;
                }
            }
        }
        if(vl_nivel > 1){     /*nivel medio*/
            if(vet[2][2]==p){
                if(vet[2][1]==p){
                    if(vet[2][3]==0){
                        vet[2][3]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][1]==p){
                if(vet[1][2]==p){
                    if(vet[1][3]==0){
                        vet[1][3]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][1]==p){
                if(vet[2][1]==p){
                    if(vet[3][1]==0){
                        vet[3][1]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][1]==p){
                if(vet[1][2]==p){
                    if(vet[1][3]==0){
                        vet[1][3]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][1]==p){
                if(vet[1][3]==p){
                    if(vet[1][1]==0){
                        vet[1][1]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][2]==p){
                if(vet[1][1]==p){
                    if(vet[1][3]==0){
                        vet[1][3]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][2]==p){
                if(vet[1][3]==p){
                    if(vet[1][1]==0){
                        vet[1][1]=1;
                        return 1;
                    }
                }
            }
            if(vet[1][3]==p){
                if(vet[1][2]==p){
                    if(vet[1][1]==0){
                        vet[1][1]=1;
                        return 1;
                    }
                }
            }
            if(vl_nivel > 2){     /*nivel difícil*/
                srand(time(NULL));
                if(rand()%100 > 20){
                    if(vet[1][3]==p){
                        if(vet[1][1]==p){
                            if(vet[1][2]==0){
                                vet[1][2]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[1][3]==p){
                        if(vet[2][3]==p){
                            if(vet[3][3]==0){
                                vet[3][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[1][3]==p){
                        if(vet[2][1]==p){
                            if(vet[2][3]==0){
                                vet[2][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[2][3]==p){
                        if(vet[1][3]==p){
                            if(vet[3][3]==0){
                                vet[3][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[2][3]==p){
                        if(vet[3][3]==p){
                            if(vet[1][3]==0){
                                vet[1][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][3]==p){
                        if(vet[2][3]==p){
                            if(vet[1][3]==0){
                                vet[1][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][3]==p){
                        if(vet[1][3]==p){
                            if(vet[2][3]==0){
                                vet[2][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][3]==p){
                        if(vet[3][2]==p){
                            if(vet[3][1]==0){
                                vet[3][1]=1;
                                return 1;
                            }
                        }
                    }
                }
                if(vl_nivel > 3){     /*nivel muito difícil*/
                    if(vet[3][3]==p){
                        if(vet[3][1]==p){
                            if(vet[3][2]==0){
                                vet[3][2]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][2]==p){
                        if(vet[3][1]==p){
                            if(vet[3][3]==0){
                                vet[3][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][2]==p){
                        if(vet[3][3]==p){
                            if(vet[3][1]==0){
                                vet[3][1]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][1]==p){
                        if(vet[3][2]==p){
                            if(vet[3][3]==0){
                                vet[3][3]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][1]==p){
                        if(vet[3][3]==p){
                            if(vet[3][1]==0){
                                vet[3][1]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][1]==p){
                        if(vet[2][1]==p){
                            if(vet[1][1]==0){
                                vet[1][1]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[3][1]==p){
                        if(vet[1][1]==p){
                            if(vet[2][1]==0){
                                vet[2][1]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[2][1]==p){
                        if(vet[1][1]==p){
                            if(vet[3][1]==0){
                                vet[3][1]=1;
                                return 1;
                            }
                        }
                    }
                    if(vet[2][1]==p){
                        if(vet[3][1]==p){
                            if(vet[1][1]==0){
                                vet[1][1]=1;
                                return 1;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}