Considere o jogo HexSemDezLinha de 11x11. Este jogo é o clássico jogo do Galo, em que cada lado coloca a sua marca num espaço vazio à vez (marca 'x' e marca 'o'), sendo o objetivo obter 5 marcas em linha (em vez do original 3 em linha). O tabuleiro é hexagonal, existindo portanto 6 direções. No jogo em cima, o jogador “x” ganha devido a ter feito 5 em linha, marcado aqui a negrito e rasurado para destacar. Caso todo o tabuleiro seja preenchido, e nenhum jogador tiver feito 5 em linha, o jogo é considerado empatado.

Questão Aberta - Inteligência Artificial e Busca Adversarial

Esta questão aborda o tema de Busca Adversarial (Jogos), focando na implementação do algoritmo MiniMax e no desenvolvimento de funções heurísticas para jogos complexos como o Hex5emLinha.

Resumo da Resposta

A solução exige definir uma função heurística que avalie linhas potenciais de vitória para ambos os jogadores e aplicar o algoritmo MiniMax com limite de profundidade devido ao alto fator de ramificação. A execução das 10 primeiras iterações envolve expandir nós alternando entre maximização (jogador 'x') e minimização (jogador 'o').

Análise Detalhada

a) Procuras Adversariais e Otimizações

No contexto de jogos como este, onde o espaço de estados é enorme ($11 \times 11$ células iniciais), não é possível buscar até o fim do jogo.

Tipos de Otimizações Interessantes:

• Limite de Profundidade (Depth Limit): Em vez de buscar até um estado terminal (vitória/derrota), busca-se até uma certa profundidade $d$. Isso garante que o tempo de computação seja finito.
• Corte Alfa-Beta: Embora a alínea (b) peça para ignorar isso na cálculo, ele é fundamental na prática para podar ramos da árvore que não influenciarão a decisão final.
• Ordenação de Movimentos: Tentar explorar movimentos mais promissores primeiro aumenta a eficiência dos cortes.

Função Heurística ($h(n)$):
A função deve estimar a utilidade de um estado sem chegar ao fim. Para o Hex5, ela pode ser baseada na contagem de linhas abertas.
$$ H(n) = \sum (\text{linhas favoráveis ao 'x'}) - \sum (\text{linhas favoráveis ao 'o'}) $$
Os pesos dessas linhas dependem do comprimento (ex: 4 peças alinhadas valem mais que 2).

b) Execução do Algoritmo MiniMax

O algoritmo MiniMax alterna entre níveis de MAX (tentando maximizar a pontuação) e MIN (tentando minimizar a pontuação do oponente).

Passo a passo para as 10 iterações:

1. Raiz: Estado inicial do tabuleiro 6x6.
2. Expansão: Gerar todos os filhos possíveis (espaços vazios).
3. Avaliação: Aplicar a função heurística nos estados folha alcançados dentro do limite de profundidade.
4. Backpropagation: Subir os valores pela árvore (MAX escolhe o maior valor filho, MIN escolhe o menor).

Tabela Comparativa de Valores:

Conclusão
A resolução deste problema depende da definição clara de como a heurística pondera as ameaças de vitória iminentes. As 10 iterações representam a expansão inicial da árvore de busca, permitindo que o sistema tome decisões baseadas em avaliações locais antes de considerar consequências longas.