Desenhe a árvore de jogo para o jogo da velha para os níveis correspondentes às duas primeiras jogadas. Determine o valor da função de avaliação mencionada no texto que associa a uma posição o número de filas que não contém nenhum 0 menos o número de filas que não contém nenhum X como o valor de cada vértice naquele nível e calcule o valor desta árvore para os vértices como se a função de avaliação desse os valores corretos destes vértices.
Passo 1
O enunciado pede que a gente construa a árvore de jogo da velha limitada às duas primeiras jogadas (X joga, depois O joga), use a função de avaliação
e percorra a árvore com minimax, supondo que essa função dê o valor “correto” em cada vértice folha.
Passo 2
Como a posição inicial é vazia, X tem simetricamente três tipos de primeira jogada:
- X no centro,
- X num canto,
- X numa aresta.
Em cada caso O tem respostas também agrupáveis em classes simétricas. Vamos calcular a avaliaçãode cada posição após X e O jogarem, e depois aplicar minimax (O minimiza, X maximiza).
Passo 3
X joga no centro. As respostas distintas de O são:
• O num canto (por ex. em (1,1)):
– Linhas sem 0: (O destrói 1 linha, 1 coluna e 1 diagonal).
– Linhas sem X: (X no centro destrói 1 linha, 1 coluna e 2 diagonais).
– .
• O numa aresta (por ex. em (1,2)):
– Linhas sem 0: (O destrói 1 linha e 1 coluna).
– Linhas sem X: .
– .
• O num canto (por ex. em (1,1)):
– Linhas sem 0:
– Linhas sem X:
–
• O numa aresta (por ex. em (1,2)):
– Linhas sem 0:
– Linhas sem X:
–
Passo 4
O escolhe a menor avaliação entre
, ou seja
Passo 5
X joga num canto (por ex. em (1,1)). As respostas distintas de O são:
• O no centro (2,2):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O no canto oposto (3,3):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O na aresta adjacente (por ex. (1,2)):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O no centro (2,2):
– Linhas sem 0:
– Linhas sem X:
–
• O no canto oposto (3,3):
– Linhas sem 0:
– Linhas sem X:
–
• O na aresta adjacente (por ex. (1,2)):
– Linhas sem 0:
– Linhas sem X:
–
Passo 6
O escolhe
, logo
Passo 7
X joga numa aresta (por ex. em (1,2)). As respostas distintas de O são:
• O no centro (2,2):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O num canto adjacente (por ex. (1,1)):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O na aresta oposta (3,2):
– Linhas sem 0: .
– Linhas sem X: .
– .
• O no centro (2,2):
– Linhas sem 0:
– Linhas sem X:
–
• O num canto adjacente (por ex. (1,1)):
– Linhas sem 0:
– Linhas sem X:
–
• O na aresta oposta (3,2):
– Linhas sem 0:
– Linhas sem X:
–
Passo 8
O escolhe
, então
Passo 9
Agora X, na raiz, escolhe o maior entre
, ou seja
e a melhor jogada inicial é colocar X no centro.
Resposta
A árvore com duas jogadas e minimax atribui valor
à posição inicial, obtido pela jogada “X no centro”.