Estruturas de Dados - Árvores para Jogos

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Árvores para jogos
Árvores
● O conceito de árvores genéricas que 
vimos recentemente pode ser usado para 
a implementação de programas que 
lidam com jogos, nos quais os 
movimentos são feitos alternadamente 
por cada jogador, tais como o jogo da 
velha e o xadrez
Árvores
● O jogo da velha por exemplo, é jogado 
por dois jogadores em um tabuleiro 
(board) bem simples de 9 casas:
| |
---------------------
| |
---------------------
| |
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| |
---------------------
| X |
---------------------
| |
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| |
---------------------
| X |
---------------------
| | O
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| |
---------------------
| X |
---------------------
 X | | O
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| | O
---------------------
| X | 
---------------------
 X | | O
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| | O
---------------------
| X | X
---------------------
 X | | O
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| O | O
---------------------
| X | X
---------------------
 X | | O
Árvores
● Um jogador é representado por X e o 
outro por O e o objetivo é fechar uma 
linha, ou coluna ou diagonal:
| O | O
---------------------
 X | X | X
---------------------
 X | | O X ganha!
Árvores
● Dada uma configuração do tabuleiro, são 
possíveis várias jogadas (para X): 
X| O | 
----------
 | X |
----------
 | | O 
X| O | X X| O | X| O | X| O | X| O |
---------- ---------- ---------- ----------- ----------
 | X | | X | X | X | | X | X| X |
---------- ---------- ---------- ----------- ----------
 | | O | | O | X | O X| | O | | O 
Árvores
● Cada configuração (ou posição) de 
tabuleiro pode ser representada assim:
struct treenode {
 char board[3][3];
 int turn;
 struct treenode *son;
 struct treenode *next;
};
Árvores
●
A
B C D
E F G
 
De forma semelhante à árvore genérica vista na aula anterior
s i n
s i n
s i n
s i n s i n
s i n s i n
A
B DC
E F G
Árvores
● Neste nó temos duas informações, a 
saber, board[3][3] e turn (veremos adiante)
board[0][0] board[0][2]
| O | O
---------------------
 X | X | X
---------------------
 X | | O 
board[2][0] board[2][2]
 board[1][1] board[2][1] 
Árvores
● A escolha de uma jogada requer uma 
estratégia de avaliação.
● Uma primeira abordagem seria verificar 
quantas linhas, colunas ou diagonais 
ainda estão disponíveis para serem 
fechadas pelos jogadores (X ou 0) e optar 
pelo caminho que dará mais chances ao 
jogador da vez.
Árvores
● Dada uma configuração do tabuleiro, são 
possíveis várias jogadas (para X): 
X| O | 
----------
 | X |
----------
 | | O 
X| O | X X| O | X| O | X| O | X| O |
---------- ---------- ---------- ----------- ----------
 | X | | X | X | X | | X | X| X |
---------- ---------- ---------- ----------- ----------
 | | O | | O | X | O X| | O | | O
 2 2 2 2 1 
Árvores
● O que é interessante é que, pelo critério 
anterior, a jogada que tem menos valor é 
melhor! Isso acontece em jogos já adiantados, e 
não se observou que a última opção X fechará o 
jogo... O critério proposto sozinho funciona bem 
apenas no início do jogo.
● Deve-se então acrescentar outro critério mais 
forte, que atribui o valor 9 (maior que qualquer 
outra possibilidade) para opções que 
terminarão o jogo.
Árvores
● Uma estratégia mais inteligente (para X):
 
X| O | 
----------
 | X |
----------
 | | O 
X| O | X X| O | X| O | X| O | X| O |
---------- ---------- ---------- ----------- ----------
 | X | | X | X | X | | X | X| X |
---------- ---------- ---------- ----------- ----------
 | | O | | O | X | O X| | O | | O
 2 2 2 9 9 
Árvores
● Que as duas últimas são melhores nós vemos, 
mas a questão é como fazer o computador 
“ver“ isso.
● Nos vemos porque já estamos olhando para a 
próxima jogada. Podemos fazer isso também, e 
não necessariamente vendo todas as 
possibilidades adiante.
● Podemos definir, portanto, um nível n de 
previsão para verificar as próximas n jogadas
Árvores
● Veja para o nodo inicial com duas jogadas adiante:
 | | 
 ------------
 | |
 ------------
 | | 
 1 
 X| | | | | X | 
 ---------- ---------- ----------
 | | | X | | | 
 ---------- ---------- ----------
 | | | | | | 
●
● -1 1 -2 
●
●
X| O | X| | X| | X| | X | | O| | | O | O| X | | X | | X | | X | | X | 
---------- ---------- ---------- ----------- ---------- ----------- ---------- ---------- ----------- ---------- ------------ -------------
 | | | | | | | | | O | | X | | X | | | O| | | | | | | O | 
---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ----------- ---------- ------------ --------------
 | | O| | | O | | | O | | | | | | | | | | O| | | O | | | 
 1 0 1 0 -1 1 2 -1 0 -1 0 -2 
Árvores
● Esse método é chamado de estratégia Mini-max
● Seus princípios são:
– na folha utiliza-se uma função estatística para 
averiguar a melhor opção (no nosso caso 
nossas possibilidades – possibilidades “dele“) 
– na nossa escolha vale o caminho de maior 
valor
– na escolha “dele“ vale o de menor valor (ele 
optará pelo pior para nós...)
Árvores
● Em outras palavras, nossa estratégia é 
defensiva e nós optamos pelo caminho “menos 
pior“, quando é nossa vez de optar e “ele“ opta 
pelo pior caminho para nós
● Na estratégia são calculados os valores das 
folhas e os valores são projetados para cima na 
árvore, dependendo de quem vai fazer a 
jogada: se for ele, sobe o pior valor, se formos 
nós, sobe o melhor valor, daí o nome Mini-max
Árvores
● Na árvore do exemplo a profundidade é três – dá para 
escolher o primeiro passo olhando o segundo como folha.
● É possível aprofundarmais e garantir melhor 
desempenho
● Na função de avaliação por mim implementada com 3 
passos adiante consegue-se um bom desempenho e os 
dois jogadores empatam, com 6057 avaliações de folhas
● Com 8 passos, X ganha, e são feitas 409110 avaliações 
(deve haver um bug na implementação, caso contrário 
eles empatariam)
Árvores
● A abordagem para a implementação de um simulador de 
jogo é a seguinte:
– gera-se uma árvore para a raiz do jogo, que 
representa o tabuleiro vazio
– a partir da raiz produz-se as subárvores das três 
escolhas possíveis (são mais que três, mas há várias 
equivalências...)
– para cada subárvore gera-se suas possíveis escolhas
– a árvore completa terá a profundidade de consulta 
escolhida – na figura-exemplo, 3.
Árvores
● A abordagem... (continuação):
– Estando pronta a árvore a partir da raiz faz-se o 
calculo do melhor caminho a partir da mesma
– Feita a escolha, cria-se uma árvore de consulta com a 
profundidade escolhida, agora partindo da 
configuração de tabuleiro da escolha feita – na 
simulação, a segunda escolha será feita pelo outro 
jogador, que agora pode ver uma posição adiante.
– Após a jogada de 'O', nova avaliação será feita, agora 
para 'X', gerando as subárvores a partir da 
configuração das duas jogadas prévias. E assim vai...
Árvores
● A arquitetura de implementação deve permitir várias 
montagens:
– Simulação do jogo completo
– Fazer o computador jogar como 'X' e ter uma interface 
para um humano jogar como 'O'
– Vice-versa
– Estrutura para aconselhamento
– Estrutura para justificativa da jogada
Árvores
● Para dar flexibilidade, o projeto deve ser modular e 
possuir vários procedimentos ou funções que permitam a 
montagem das facilidades requeridas
● A minha implementação de teste faz a simulação do jogo 
completo
● O programa principal inicia gerando o tabuleiro vazio (em 
board) e buscando a melhor opção para o jogador X
● Ele faz isso chamando a função nextmove, que recebe o 
tabuleiro board, calcula a melhor opção, devolvida no 
tabuleiro newboard:
 nextmove(board,4,player,newboard);
Árvores
● O cerne do procedimento main vai a seguir:
 for (k=9;k>0;k--) {
 if (player=='O') player='X';
 else player='O';
 printf("\nProximo movimento player %c:\n\n",player);
 nextmove(board,4,player,newboard); // 4 é a profundidade de consulta
 printboard(newboard);
 ...
 for (i=0;i<3;i++) for (j=0;j<3;j++) board[i][j]=newboard[i][j];
 }
● Repare que nextmove é chamada até 9 vezes, alternando o player entre X e 
O
● Após cada chamada, o newboard é impresso e atribuido a board, para ser o 
ponto de partida para a próxima chamada
● Em verdade é preciso verificar outras coisas antes de chamar de novo, tais 
como ver se o jogador ganhou a partida... veja o código completo:
Árvores
● for (k=9;k>0;k--) {
● if (player=='O') player='X';
● else player='O';
● printf("\nProximo movimento player %c:\n\n",player);
● nextmove(board,4,player,newboard);
● printboard(newboard);
● contamov++;
● winner=somebodywon(newboard);
● if (winner!=' ') {
● if (winner=='V')
● printf("\nDeu velha!...\n\n");
● else 
● printf("\n%c ganhou!\n\n",winner);
● printf("\n\nTotal de movimentos:%d\n",contamov);
● printf("Total de avaliações:%d\n\n",contaeval);
● return (0);
● }
● for (i=0;i<3;i++) for (j=0;j<3;j++) board[i][j]=newboard[i][j];
● }
Árvores
● printboard e somebodywon são procedimentos relativamente simples
● printboard gera um visão do tabuleiro, bem simples, em uma shell
● somebodywon verifica condições de término, isso é, se algum dos jogadores 
fechou uma linha, coluna ou diagonal, ou se não há mais jogadas possíveis, 
isso é, o jogo deu “velha“ (empatou)
● Segue printboard, só para ilustrar:
void printboard(char board[][3]){
 int i,j;
 for (i=0;i<3;i++) {
 for (j=0;j<3;j++)
 if (j<2) printf(" %c |",board[i][j]);
 else printf(" %c ",board[i][j]);
 if (i<2) printf("\n --------\n");
 else printf("\n");
 }
}
Árvores
● O procedimento nextmove tem uma missão bem mais complexa: ele usa o 
procedimento buildtree, para criar uma árvore a partir do board e depois 
aplica bestbranch para encontrar a melhor opção de desvio (que filho de 
board é o mais indicado)
● A saída de nextmove é newboard, o filho escolhido
void nextmove(char board[][3], int looklevel, char player, 
 char newboard[][3]) {
 NODEPTR ptree, best;
 int i, j, value;
 ptree=buildtree(board,looklevel);
 bestbranch(ptree, player, &best, &value);
 for (i=0; i<3; i++)
 for (j=0; j<3; j++)
 newboard[i][j]=best->board[i][j];
}
Árvores
● O procedimento buildtree, criar o nodo raiz, a partir do board e chama o 
procedimento expand, que se chama recursivamente para ir criando e 
linkando os filhos, netos, etc., da raiz dependendo da profundidade. 
NODEPTR buildtree(char board[][3],int looklevel) {
 NODEPTR ptree;
 int i,j;
 //cria a raiz e inicializa
 ptree=malloc(sizeof(struct treenode)); 
 for (i=0; i<3; i++)
 for (j=0; j<3; j++)
 ptree->board[i][j]=board[i][j];
 //por definicao a raiz é um nó do jogador +
 ptree->turn=1;
 ptree->son=NULL;
 ptree->next=NULL;
 expand(ptree, 0, looklevel); // cria o resto da arvore do jogo
 return (ptree);
}
Árvores
● O procedimento expand, é mostrado a seguir. Seu segredo é chamar 
generate, que vai criando e linkando, um a um, os filhos do nodo p, que foi 
passado como parâmetro. Feito isso, para cada filho, verifica se a 
profundidade máxima não foi atingida, e chama expand de novo!
void expand(NODEPTR p, int plevel, int depth) {
 NODEPTR q;
 if (plevel<depth) { // p nao esta'no nivel maximo
 q=generate(p->board);
 p->son=q;
 while (q!=NULL) { // percorre a lista de nos
 if (p->turn==1)
q->turn=-1;
 else
q->turn=1;
 q->son=NULL;
 expand(q, plevel+1, depth);
 q=q->next;
 }
 }
}
Árvores
● O procedimento generate é capcioso – é preciso gerar um irmão para cada 
casa em branco do tabuleiro – irmão de quem? depende do número de 
casas marcadas...
NODEPTR generate(char board[][3]){
 NODEPTR list,new;
 int i,j,marcados=0;
 char marca='X';
 list=NULL;
 for (i=0;i<3;i++)
 for (j=0;j<3;j++)
 if (board[i][j]!=' ') marcados++;
 if (marcados%2) marca='O'; // numero de marcas impar -> O
 for (i=0;i<3;i++)
 for (j=0;j<3;j++)
 if (board[i][j]==' ') {
new=malloc(sizeof(struct treenode));
new->next=list;
list=new;
int m,n;
for (m=0; m<3; m++)
 for (n=0; n<3; n++)
 list->board[m][n]=board[m][n];
list->board[i][j]=marca;
 }
 return (list);
}
Árvores
● Pronto! Não, agora já temos nossa arvore de possibilidades, mas falta 
avaliá-la. Para isso temos bestbranch:
void bestbranch(NODEPTR pnode, char player, NODEPTR *pbest, int *pvalue) {
 NODEPTR p, pbest2;
 int val;
 if (pnode->son==NULL) { // pnode é folha
 *pvalue=evaluate(pnode->board, player);
 *pbest=pnode;
 }
 else { // não é folha, atravessar a lista de filhos...
 p=pnode->son;
 bestbranch(p, player, pbest, pvalue);
 *pbest=p;
 if (pnode->turn==-1) *pvalue=-*pvalue;
 p=p->next;
 while (p!=NULL) {
 bestbranch(p,player, &pbest2, &val);
 if (pnode->turn==-1) val=-val;
 if (val>*pvalue) {
*pvalue=val;
*pbest=p;
 }
 p=p->next;
 }
 if (pnode->turn==-1) *pvalue=-*pvalue;
 }
}
Árvores
● E bestbranch precisa de evaluate, para avaliar as folhas e ir 
subindo com os valores de melhores escolhas; evaluate é 
relativamente simples, mas é longa. Vou mostrar só umas partes:
int evaluate(char board[][3], char player) {
● char other;
● int i,j,k, b,totplayer=0,totother=0;
●contaeval++;
● if (player=='X') other='O';
● else other='X';
● for (i=0;i<3;i++) { // soma linhas livres para player
● k=0;b=0;
● for (j=0;j<3;j++){
● if ((board[i][j]==player)|(board[i][j]==' ')) k++;
● if (board[i][j]==' ') b++;
● }
● if (k==3) {
● if (b==1) return (6);
● totplayer++;
● }
● }
● for (i=0;i<3;i++) { // soma linhas livres para other
● k=0;b=0;
● for (j=0;j<3;j++) {
● if ((board[i][j]==other)|(board[i][j]==' ')) k++;
● if (board[i][j]==' ') b++;
● }
● if (k==3) {
● if (b==1) return(-8);
● totother++;
● }
● }