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
\text{eval}(P)=\bigl(\#\text{linhas sem 0 em }P\bigr)\;-\;\bigl(\#\text{linhas sem X em }P\bigr)
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:
  1. X no centro,
  2. X num canto,
  3. X numa aresta.
    Em cada caso O tem respostas também agrupáveis em classes simétricas. Vamos calcular a avaliação \text{eval} de 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: 8-3=5 (O destrói 1 linha, 1 coluna e 1 diagonal).
– Linhas sem X: 8-4=4 (X no centro destrói 1 linha, 1 coluna e 2 diagonais).
\text{eval}=5-4=1.
• O numa aresta (por ex. em (1,2)):
– Linhas sem 0: 8-2=6 (O destrói 1 linha e 1 coluna).
– Linhas sem X: 8-4=4.
\text{eval}=6-4=2.

Passo 4

O escolhe a menor avaliação entre \{1,2\}, ou seja
\text{valor}\bigl(\text{X@centro}\bigr)=\min\{1,2\}=1.

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: 8-4=4.
– Linhas sem X: 8-3=5.
\text{eval}=4-5=-1.
• O no canto oposto (3,3):
– Linhas sem 0: 8-3=5.
– Linhas sem X: 8-3=5.
\text{eval}=5-5=0.
• O na aresta adjacente (por ex. (1,2)):
– Linhas sem 0: 8-2=6.
– Linhas sem X: 8-3=5.
\text{eval}=6-5=1.

Passo 6

O escolhe \min\{-1,0,1\}=-1, logo
\text{valor}\bigl(\text{X@canto}\bigr)=-1.

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: 8-4=4.
– Linhas sem X: 8-2=6.
\text{eval}=4-6=-2.
• O num canto adjacente (por ex. (1,1)):
– Linhas sem 0: 8-3=5.
– Linhas sem X: 8-2=6.
\text{eval}=5-6=-1.
• O na aresta oposta (3,2):
– Linhas sem 0: 8-2=6.
– Linhas sem X: 8-2=6.
\text{eval}=6-6=0.

Passo 8

O escolhe \min\{-2,-1,0\}=-2, então
\text{valor}\bigl(\text{X@aresta}\bigr)=-2.

Passo 9

Agora X, na raiz, escolhe o maior entre \{\,1,\,-1,\,-2\}, ou seja
\text{valor}(\text{raiz})=\max\{1,-1,-2\}=1,
e a melhor jogada inicial é colocar X no centro.

Resposta

A árvore com duas jogadas e minimax atribui valor 1 à posição inicial, obtido pela jogada “X no centro”.

Exercícios de Livros Relacionados