Tic-Tac-Toe -(MinMax) Play Of The Computer

Dev Shed Forums Sponsor:

December 30th, 2012, 02:40 PM

jcrbsa

Registered User

Join Date: Dec 2012

Posts: 2

Time spent in forums: 25 m 52 sec
Reputation Power: 0

Tic-Tac-Toe -(MinMax) Play Of The Computer

Hello!!! I'm a problem how does it algorithm correct for play of the computer ? Where can I change?

Code:

#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 - NAO \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("COMPUTADOR VENCEU"); break; }else if(campeao == X){ printf("VC venceu! PARABENS!!!"); break; } } if(campeao == VAZIO){ printf("EMPATE!!!"); } system("PAUSE"); return 0; }

December 30th, 2012, 04:45 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,364

Time spent in forums: 1 Month 2 Weeks 3 Days 10 h 28 m 48 sec
Reputation Power: 383

Hi! Look at your post. Is it readable? The code tags are good. All on one line is bad.

Here's tic-tac-toe with min/max algorithm.

__________________
[code]Code tags[/code] are essential for python code!

December 31st, 2012, 08:54 AM

jcrbsa

Registered User

Join Date: Dec 2012

Posts: 2

Time spent in forums: 25 m 52 sec
Reputation Power: 0

I wanted to know how to improve play of the computer . Because when I raise the level of play on the computer instead it should play your best, which does not occur. I put the move on a list of tree increasing it each interaction according to the current board and the level of difficulty. For example, if the level increases it generates more occurrences to measure.

main functions
* MelhorJogada (): Estimates the best move to be made following

* Arguments: tab (input) - the board that represents the root of the game tree
* Current
* profundidade (input) - the depth of the game tree
*jogador (input) - the player whose turn
* NovoTab (output) - original board changed to contain the best play

* ConstroiArvore (): Returns a pointer to a game tree

* Arguments: tab (input) - the board that represents the root of the tree depth (input) - the depth of the tree

* Return: pointer to the root of the tree created

* Expands (): Expands a node of the game tree, creating all positions that can be obtained from the board of the node received as argument. The generated we become children of the node received as argument. So, this function is called recursively generated using the nodes as arguments until the desired depth is reached.

* Arguments: p (input / output) - Pointer to the node to be expanded
* Level (entry) - node level
* profundidae (in) - depth expansion

* GeraFilhos (): Returns a pointer to a list of nodes that are children of the node whose board is passed as argument.

* Arguments: tab (input) - the board of which will be generated nodes
* Return: pointer to the list of nodes generated

* AcrescentaNaLista (): Adds a node to the list we received as an argument and returns a pointer to the list plus
* Arguments: list (input / output) - Pointer to the beginning of the list of nodes
* Tab (input) - the board before the move
* Row, column (input) - the row and column where the play will be
* Move (input) - the move to be made (X or O)
*
* Return: pointer to the list node resulting from increased play

* ProcuraMelhorLance (): Looking for the best move in the tree whose root is
Received as argument
* Arguments: tree (input) - pointer to the game tree
* Player (inlet) - the player (X or W) having the
* Better (output) - Pointer to the node that represents the best play
* Value (output) - the value of the best node

* Evaluate (): Evaluates statically board position for the given player.
* The result of the evaluation is the number of rows, columns and diagonals that can be filled by the player minus the number of these that can be filled by your opponent.

* Arguments: tab (input) - the board that will be evaluated
* Player (input) - the player whose turn it is

* Return: The value of the evaluation

Tic-Tac-Toe -(MinMax) Play Of The Computer

Developer Shed Advertisers and Affiliates