Algoritmos: MiniMax; Monte Carlo;
📖 Leituras
- (Russell & Norvig): Capítulo 5 ou 6, conforme edição (Procura Adversa)
Bibliografia
⚡ Ação: Quais são as três formas de encarar ambientes multiagente segundo o capítulo?
👉 Economia (agentes em grande número), agentes como parte estocástica do ambiente, e modelação explícita via procura adversa.
⚡ Ação: Porque é inadequado modelar adversários como eventos aleatórios?
👉 Porque adversários têm intenção de derrotar o agente, ao contrário de fenómenos naturais.
⚡ Ação: Que características têm os jogos mais estudados em IA?
👉 Determinísticos, dois jogadores, turn-taking, informação perfeita e soma zero.
⚡ Ação: Quais são os elementos formais que definem um jogo?
👉 Estado inicial, jogador a mover, ações legais, modelo de transição, teste terminal e função utilidade.
⚡ Ação: O que caracteriza um estado terminal?
👉 É um estado onde o jogo termina e a utilidade pode ser avaliada.
⚡ Ação: Qual o papel da função utilidade num jogo?
👉 Atribuir um valor numérico ao resultado final para cada jogador.
⚡ Ação: Qual a diferença entre árvore de procura e grafo do espaço de estados?
👉 A árvore de procura expande sequências de jogadas; o grafo do espaço de estado representa todos os estados possíveis, independentemente de uma sequência de jogo.
⚡ Ação: Porque é que a árvore de procura do xadrez é impraticável de explorar?
👉 Porque tem mais de 10⁴⁰ estados, tornando impossível percorrê-la totalmente.
⚡ Ação: O que significa uma estratégia ótima para MAX?
👉 Uma estratégia que maximiza a utilidade assumindo que MIN joga de forma ótima.
⚡ Ação: O que é o valor minimax de um estado?
👉 A utilidade esperada assumindo jogo ótimo de ambos os jogadores.
⚡ Ação: Qual o valor minimax de um estado terminal?
👉 A utilidade desse estado.
⚡ Ação: O que faz MAX num estado não terminal?
👉 Escolhe a ação cujo sucessor tem maior valor minimax.
⚡ Ação: O que faz MIN num estado não terminal?
👉 Escolhe a ação cujo sucessor tem menor valor minimax.
⚡ Ação: Qual a complexidade temporal do minimax?
👉 O(b^m), onde b é o fator de ramificação e m a profundidade.
⚡ Ação: Porque o minimax puro é impraticável em jogos reais?
👉 Porque o número de estados cresce exponencialmente com a profundidade.
⚡ Ação: Porque o minimax pode não ser a melhor estratégia contra adversários fracos?
👉 Porque pode existir um lance arriscado que explora erros prováveis do adversário.
⚡ Ação: Como se representa a utilidade em jogos com mais de dois jogadores?
👉 Como um vetor com uma componente por jogador.
⚡ Ação: Como um jogador decide num jogo multijogador?
👉 Escolhe o sucessor que maximiza a sua própria componente da utilidade.
⚡ Ação: Porque podem surgir alianças em jogos multijogador?
👉 Porque jogadores fracos podem cooperar para impedir que um jogador forte vença.
⚡ Ação: Porque pode haver cooperação em jogos não soma zero?
👉 Porque existem estados que beneficiam simultaneamente vários jogadores.
⚡ Ação: Qual é a ideia central dos cortes alfa-beta?
👉 Evitar explorar ramos que não podem influenciar a decisão final.
⚡ Ação: O que representa α?
👉 O melhor valor encontrado até agora para MAX ao longo do caminho.
⚡ Ação: O que representa β?
👉 O melhor valor encontrado até agora para MIN ao longo do caminho.
⚡ Ação: Quando ocorre um corte alfa-beta?
👉 Quando o valor atual é pior do que α ou β, tornando inútil explorar mais.
⚡ Ação: Porque a ordem dos sucessores influencia a eficiência do alfa‑beta?
👉 Porque avaliar primeiro movimentos promissores aumenta a probabilidade de cortes, reduzindo drasticamente o número de estados explorados.
⚡ Ação: Qual é a complexidade temporal no melhor caso do alfa‑beta?
👉 O(b^(m/2)), reduzindo a profundidade efetiva para metade em comparação com o minimax puro.
⚡ Ação: O que acontece ao alfa‑beta se os movimentos forem avaliados na pior ordem possível?
👉 O algoritmo degrada-se para o desempenho do minimax, explorando praticamente todos os estados.
⚡ Ação: O que é a killer move heuristic?
👉 Uma técnica que tenta primeiro movimentos que foram bons em situações anteriores, aumentando a probabilidade de cortes.
⚡ Ação: Porque a procura iterativa melhora o alfa‑beta?
👉 Porque as iterações anteriores fornecem uma boa ordenação de movimentos para iterações mais profundas.
⚡ Ação: Para que servem as hashtables?
👉 Para armazenar valores de estados já explorados, evitando recomputações e acelerando a procura.
⚡ Ação: Porque é que jogos como o xadrez beneficiam de hashtables?
👉 Porque diferentes sequências de jogadas podem levar ao mesmo estado, permitindo reutilizar resultados anteriores.
⚡ Ação: Qual a diferença entre estratégias Tipo A e Tipo B?
👉 Tipo A explora largamente até uma profundidade fixa; Tipo B explora profundamente apenas ramos promissores.
⚡ Ação: Em que jogos a estratégia Tipo A é mais adequada?
👉 Em jogos com ramificação moderada, como o xadrez, onde é possível explorar várias jogadas em largura.
⚡ Ação: Porque a estratégia Tipo B é usada em jogos como o Go?
👉 Porque o Go tem ramificação muito elevada, tornando inviável explorar largamente; é preferível aprofundar apenas ramos promissores.
⚡ Ação: O que determina o cutoff test?
👉 Quando parar a expansão, com base na profundidade ou propriedades do estado.
⚡ Ação: Porque uma heurística imperfeita pode induzir erros?
👉 Porque pode avaliar mal estados superficiais, levando a escolhas subótimas.
⚡ Ação: Como o minimax lida com nós de acaso?
👉 Substitui max/min por valor esperado, calculando a média ponderada das utilidades.
⚡ Ação: Porque o alfa‑beta não pode cortar em nós de acaso?
👉 Porque não há jogador a maximizar ou minimizar; não existem limites α ou β aplicáveis.
⚡ Ação: Porque o Monte Carlo lida naturalmente com aleatoriedade?
👉 Porque a simulação já incorpora eventos aleatórios, tornando os nós de acaso apenas mais um passo da política de jogo.
⚡ Ação: Porque é que uma estratégia ótima deve ser condicional e não apenas uma sequência fixa de jogadas?
👉 Porque a jogada ótima depende das respostas do adversário; uma estratégia fixa falharia se o adversário não seguisse o caminho esperado.
⚡ Ação: Em que situação pode ser racional escolher um lance “arriscado” em vez do minimax?
👉 Quando o adversário é fraco ou limitado computacionalmente, aumentando a probabilidade de cometer um erro que beneficie o jogador.
⚡ Ação: Porque aumentar a profundidade de procura melhora a qualidade das decisões?
👉 Porque permite antecipar mais respostas do adversário e evitar armadilhas que só surgem várias jogadas à frente.
⚡ Ação: O que é a explosão combinatória nas árvores de jogo?
👉 O crescimento exponencial do número de estados à medida que a profundidade aumenta, tornando a procura completa impraticável.
⚡ Ação: O que são transposições num jogo como o xadrez?
👉 Situações em que diferentes sequências de jogadas levam ao mesmo estado final, permitindo reutilizar resultados anteriores.
⚡ Ação: Porque as hashtables podem duplicar a profundidade alcançável?
👉 Porque evitam recalcular subárvores inteiras, poupando tempo e permitindo explorar mais profundamente.
⚡ Ação: Porque é importante que a heurística seja estável entre níveis consecutivos?
👉 Porque grandes oscilações podem levar a decisões inconsistentes e cortes prematuros incorretos.
⚡ Ação: O que distingue jogos de informação perfeita de jogos parcialmente observáveis?
👉 Em jogos de informação perfeita, todos os jogadores veem o estado completo; nos parcialmente observáveis, parte do estado é oculta.
⚡ Ação: Porque o valor esperado substitui o minimax em nós de acaso?
👉 Porque não há adversário a escolher; o resultado depende de probabilidades, não de intenções.
Nova pergunta: 🎲
1.9.8