Aula Prática 2 – Procura em ambientes complexos e jogos

Matéria das aulas T5 (procura em ambientes complexos) e T6 (procura com adversários e jogos). O exercício 1 é resolvido no quadro; os restantes são para trabalho autónomo, individualmente ou em grupos de dois. Os exercícios que ficarem por resolver na aula devem ser resolvidos em casa. Os exercícios 1 a 6 são sobre jogos (T6); os exercícios 7 a 9 sobre procura local (T5); o 10 mistura tudo.

Convenções

Toda a terminologia é a do AIMA, 4.ª edição (capítulos 4 e 6 da edição global) e a dos slides T5 e T6.

• Nas árvores de jogo, um triângulo com o vértice para cima é um nó MAX, um triângulo com o vértice para baixo é um nó MIN e um círculo é um nó de acaso. Os números nas folhas são a utilidade para MAX. As árvores percorrem-se da esquerda para a direita.
• O corte α-β é o ALPHA-BETA-SEARCH dos slides: num nó MAX corta-se quando v ≥ β; num nó MIN, quando v ≤ α. Um nó diz-se visitado se o algoritmo lhe chamou MAX-VALUE ou MIN-VALUE (ou, sendo folha, se leu a sua utilidade).
• No minimax esperado, os filhos de um nó de acaso têm a probabilidade escrita no arco; quando não têm, são equiprováveis.
• Na MCTS, o rácio U/N escrito em cada nó conta as vitórias de quem acabou de jogar para chegar a esse nó sobre o número de simulações que passaram por ele, e a política de selecção é o UCB1 com C = 1,4.
• No trepa-colinas sobre um grafo de configurações, maximiza-se o valor escrito junto de cada nó; a vizinhança de um nó são os nós adjacentes; a variante por omissão é a subida mais inclinada (vai-se para o melhor vizinho; em caso de empate, qualquer um dos melhores pode ser escolhido).
• Nas n-rainhas usa-se a formulação de estado completo dos slides: um estado é uma cadeia com a linha da rainha de cada coluna, a linha 1 é a de baixo, um sucessor move uma rainha dentro da sua coluna, e h é o número de pares de rainhas que se atacam (minimiza-se). Em caso de empate entre sucessores, escolhe-se o da coluna mais à esquerda e, dentro dela, o da linha mais baixa.
• Na recristalização simulada usa-se a convenção das animações dos slides: ΔE = VALUE(next) − VALUE(current) e um movimento que piora (ΔE < 0) é aceite com probabilidade e^(ΔE/T). (O livro escreve a diferença ao contrário e e^(−ΔE/T); é a mesma coisa.)

Exercício 1 – Minimax, corte α-β e um nó de acaso

Figura 1 — Uma árvore de jogo de dois níveis. As folhas de B chamam-se b1, b2, b3; as de C, c1, c2, c3; as de D, d1, d2, d3.

(a) Calcule o valor minimax de B, C, D e A. Qual é a jogada óptima de MAX?

(b) Aplique o corte α-β, percorrendo a árvore da esquerda para a direita. Para cada nó, escreva os valores de α e β com que foi chamado e o valor que devolveu; indique as folhas que não são visitadas e, para cada corte, o teste que o disparou.

(c) Existe uma ordem dos filhos da raiz que produza mais cortes? Qual é a melhor ordem, quantas folhas visita, e quantas visitaria a pior ordem?

(d) Suponha agora que C deixa de ser um nó MIN e passa a ser um nó de acaso com os três resultados equiprováveis. Calcule o valor minimax esperado de C e de A. A jogada óptima de MAX muda? Explique, em termos do jogo, porquê.

(e) Volte à árvore original. Se MIN jogar mal em B — por exemplo, escolher b2 —, o que acontece ao resultado de MAX? Que propriedade do minimax é esta?

Exercício 2 – Uma árvore de quatro níveis

Figura 2 — Árvore de jogo para os exercícios 2 e 4. As folhas chamam-se K a V.

(a) Calcule o valor minimax de cada nó não terminal e indique a jogada óptima de MAX.

(b) Percorrendo a árvore da esquerda para a direita, indique as folhas que o corte α-β nunca visita. Para cada corte, diga em que nó ocorre, qual o teste (v ≥ β ou v ≤ α) e os valores de α, β e v nesse momento.

(c) Ignore os valores das folhas. Que nós (internos e folhas) são sempre visitados pelo corte α-β, quaisquer que sejam os valores? Justifique.

(d) Ainda ignorando os valores, diga se existe alguma atribuição de valores às folhas que produza um corte imediatamente antes de visitar cada um dos nós seguintes (isto é, o nó fica por visitar por causa de um corte no seu pai): C, N, P, Q, J, V. Justifique cada resposta.

(e) Existe uma ordem dos filhos da raiz (mantendo tudo o resto) que produza mais cortes do que a ordem da figura? Qual é o mínimo de folhas que se consegue visitar reordenando todos os nós internos da árvore (a ordenação perfeita)? Compare com o O(b^(m/2)) dos slides.

(f) Suponha que B, C e D passam a ser nós de acaso com os filhos equiprováveis. Calcule o valor minimax esperado de cada nó não terminal e a jogada óptima de MAX.

(g) Ainda com B, C e D como nós de acaso: se todas as utilidades forem substituídas por 10 × u + 3, a jogada óptima muda? E se forem substituídas por u²? E no minimax (sem nós de acaso), alguma destas transformações pode mudar a jogada? Justifique com a noção de transformação que preserva a ordem.

Exercício 3 – Formular um jogo: Chomp 3 × 2

Figura 3 — A tablete de Chomp 3 × 2. O quadrado (0, 0), a escuro, é venenoso.

Dois jogadores, MAX e MIN, têm uma tablete de chocolate com 3 × 2 quadrados. Jogam à vez; na sua vez, o jogador escolhe um quadrado que ainda exista e come-o juntamente com todos os quadrados abaixo e à direita dele (o rectângulo cujo canto superior esquerdo é o quadrado escolhido). O quadrado (0, 0) é venenoso: quem o comer perde. MAX joga primeiro.

(a) Formalize o jogo com os componentes dos slides: estado inicial S₀, TO-MOVE(s), ACTIONS(s), RESULT(s, a), IS-TERMINAL(s) e UTILITY(s, p). Sugestão: represente um estado pelo número de quadrados que restam em cada linha.

(b) Quantos estados tem o jogo (contando o tabuleiro vazio)? Desenhe o grafo do espaço de estados — não a árvore de jogo — e diga porque é que aqui o grafo é muito mais pequeno do que a árvore.

(c) Calcule por minimax (com UTILITY = +1 se MAX ganha e −1 se perde) o valor do estado inicial. Quem ganha com jogo óptimo? Indique uma estratégia vencedora completa: a primeira jogada e a resposta a cada jogada possível do adversário.

(d) Aplique o corte α-β à árvore de jogo a partir do estado inicial, com as acções por ordem crescente de (linha, coluna). Quantos nós ficam por visitar?

(e) Sabe-se que todas as utilidades estão em {−1, +1}. Como se aproveita isto no ALPHA-BETA-SEARCH para podar ainda mais? Que parte da árvore fica por visitar se a primeira jogada de MAX for comer o quadrado (1, 2), o do canto inferior direito?

Exercício 4 – Cortar a procura e avaliar

Volte à árvore da Figura 2, mas suponha que só é possível procurar até à profundidade 2 (os nós E a J passam a ser tratados como se fossem terminais) e que uma função de avaliação EVAL dá os seguintes valores:

nó	E	F	G	H	I	J
EVAL	6	15	9	14	10	17

(a) Calcule o H-MINIMAX com este corte e indique a jogada escolhida. Compare com a jogada do exercício 2(a). O que correu mal?

(b) Uma função de avaliação divide as posições em categorias. Numa certa categoria, 72 % das posições são vitórias (+1), 20 % são derrotas (0) e 8 % são empates (½). Que valor deve EVAL devolver para as posições dessa categoria? E porque é que, no xadrez, não se usa mesmo esta abordagem?

(c) Considere a função linear ponderada EVAL(s) = 9·(D − D′) + 5·(T − T′) + 3·(B − B′) + 1·(P − P′), com D, T, B, P o número de damas, torres, bispos e peões de MAX (e com plica os de MIN). Calcule EVAL para duas posições em que (i) MAX tem uma torre e dois peões a mais e (ii) MAX tem uma dama a mais e MIN tem uma torre e dois peões a mais. Que pressuposto sobre as características faz uma função linear, e dê um exemplo (do capítulo, ou seu) em que ele falha.

(d) O que é o efeito de horizonte? Qual a relação com a procura de quiescência? Diga em uma frase o que faz cada uma destas técnicas: extensões singulares, poda para a frente (PROBCUT), tabelas de transposição.

(e) Com um milhão de nós avaliados por segundo, o minimax puro no xadrez chega a cerca de 5 ply. Explique, com os números do capítulo, como se passa disso para 14 ply e para os 30+ ply do STOCKFISH. Distinga as estratégias do tipo A e do tipo B de Shannon.

Exercício 5 – Procura em árvore Monte Carlo

Figura 4 — Estado de uma procura MCTS ao fim de 20 simulações. Na raiz A é a vez das brancas; cada nó mostra U/N: vitórias de quem acabou de jogar para chegar a esse nó sobre o número de simulações que passaram por ele. Só C tem filhos na árvore.

(a) Verifique que os números são coerentes: as vitórias contadas nos filhos de um nó e as contadas no próprio nó devem somar o número de simulações. (Repare que o próprio nó C representa uma simulação que não passou por E nem por F.)

(b) Calcule o UCB1 dos três filhos da raiz, com C = 1,4. Que nó é seleccionado? Porque é que não é o de melhor taxa de vitórias?

(c) No nó seleccionado, calcule o UCB1 dos seus filhos e diga qual é seleccionado. Quem está a jogar nesse nó?

(d) O nó seleccionado em (c) é uma folha da árvore de procura. Descreva os passos de expansão, simulação e retropropagação desta iteração, supondo que a simulação termina numa vitória das pretas. Escreva os novos rácios de todos os nós do caminho, da folha nova até à raiz.

(e) O que mudaria em (b) com C = 0? E com C muito grande (por exemplo, 3)? A que correspondem estes dois extremos?

(f) Se a procura terminasse agora, que jogada devolveria a MCTS na raiz e porquê — a que tem mais simulações ou a de maior taxa de vitórias? Diga uma vantagem e uma desvantagem da MCTS em relação à procura α-β com função de avaliação.

Exercício 6 – Jogos estocásticos

Figura 5 — Uma árvore de jogo com nós de acaso. Depois de MAX escolher B ou C, lança-se um dado viciado que decide o nó MIN seguinte, com as probabilidades escritas nos arcos.

(a) Calcule o valor minimax esperado de todos os nós não terminais e a jogada de MAX.

(b) Suponha que se sabe que todas as utilidades estão no intervalo [0, 15]. Depois de avaliar completamente B e depois o ramo F de C, que intervalo se conhece para o valor de C? O corte α-β poderia saltar o nó G? Justifique.

(c) Ainda com utilidades em [0, 15], suponha que a ordem dos filhos da raiz é trocada: avalia-se primeiro C e só depois B. Depois de avaliar D, qual é o intervalo para B? Para que valores de D (em vez de 4) se poderia saltar E, se o intervalo das utilidades fosse [0, 6]?

(d) Considere uma árvore muito simples: MAX escolhe entre X, um nó de acaso com dois resultados equiprováveis de utilidades 0 e 5, e Y, com utilidade 3 certa. Qual é a jogada óptima? E se todas as utilidades forem elevadas ao quadrado? Que conclusão se tira sobre as funções de avaliação em jogos estocásticos?

(e) No gamão há 21 lançamentos distintos e cerca de 20 jogadas legais por lançamento. Porque é que a profundidade útil da procura é muito menor do que no xadrez? Que alternativas há (dê duas)?

Exercício 7 – Trepa-colinas

Figura 6 — Um espaço de configurações: cada nó é uma configuração, o número é o seu valor (a maximizar) e as arestas ligam configurações vizinhas.

(a) Partindo de A, indique todas as execuções possíveis do trepa-colinas (subida mais inclinada). Em que configuração termina cada uma?

(b) Quais são os máximos locais da paisagem? E o máximo global? Há algum ombro?

(c) Se os empates forem resolvidos ao acaso com igual probabilidade, qual é a probabilidade de o trepa-colinas, partindo de A, terminar no máximo global?

(d) Repita (a) para o trepa-colinas estocástico (em cada passo escolhe-se ao acaso um vizinho estritamente melhor, não necessariamente o melhor). O que ganhou?

(e) Repita (a) permitindo movimentos laterais (para um vizinho de valor igual, sem voltar a um nó já visitado). O que ganhou, e que perigo têm os movimentos laterais numa paisagem com um máximo local plano?

(f) Com recomeços aleatórios a partir de um nó escolhido uniformemente entre os 12, qual é a probabilidade de uma execução terminar em J? E de pelo menos uma de três terminar em J? Quantos recomeços são precisos, em média, para chegar a J?

(g) Aplique a procura local em feixe com k = 2, começando com {A, D}: em cada passo ficam os 2 melhores de entre os estados correntes e todos os seus sucessores. Onde termina? Compare com dois recomeços independentes a partir de A e de D.

Agora as 4 rainhas, na formulação de estado completo (Figura 7).

Figura 7 — O estado (2, 2, 2, 2): a rainha de cada coluna está na linha 2.

(h) Calcule h para este estado e diga quantos sucessores tem.

(i) Preencha, no tabuleiro, o valor de h de cada sucessor (o valor de h do estado em que a rainha dessa coluna passa para essa casa), como na fig. 4.3(b) do livro.

(j) Execute a subida mais inclinada até parar. Onde pára? É uma solução? Se não for, que tipo de ponto da paisagem é?

(k) Repita a partir do ponto onde parou, agora com movimentos laterais. Chega a uma solução? Quantos estados tem o espaço das 4 rainhas nesta formulação, e quantos o das 8?

Exercício 8 – Recristalização simulada

(a) Complete a tabela da probabilidade e^(ΔE/T) de aceitar um movimento que piora:

ΔE	T = 10	T = 5	T = 2	T = 1	T = 0,5
−1
−2
−5
−10

(b) Leia a tabela nas duas direcções: o que acontece quando T desce com ΔE fixo, e quando ΔE piora com T fixo?

(c) Que algoritmo é a recristalização simulada quando T → ∞? E quando T → 0? E se o vizinho proposto tiver exactamente o mesmo valor do estado corrente, como varia a probabilidade de o aceitar quando T desce?

(d) Execute a recristalização simulada na paisagem da Figura 6, a partir de A, com o escalonamento T = 4, 4, 2, 2, 1, 1 (uma proposta por temperatura). Em cada passo o vizinho proposto e o número sorteado uniformemente em [0, 1[ são os da tabela; aceita-se um movimento que piora se o sorteio for menor do que e^(ΔE/T).

passo	1	2	3	4	5	6
T	4	4	2	2	1	1
vizinho proposto	D	H	D	L	K	G
sorteio	0,60	0,20	0,70	0,35	0,50	0,10

Indique, passo a passo, ΔE, a probabilidade de aceitação, a decisão e o estado corrente. Onde está o algoritmo no fim? Que teria acontecido se o escalonamento continuasse com T muito próximo de 0?

(e) O que garante o teorema da recristalização simulada sobre o máximo global, e porque é que essa garantia não serve de muito na prática? O que pode acontecer se a temperatura inicial for demasiado baixa?

Exercício 9 – Algoritmos genéticos

Considere a seguinte população de quatro indivíduos para as 8 rainhas, com a representação e a função de aptidão dos slides (número de pares de rainhas que não se atacam; máximo 28):

indivíduo	cadeia
1	1 3 8 4 5 7 5 7
2	7 6 7 4 6 1 5 3
3	6 2 4 5 5 2 2 8
4	8 2 6 2 7 3 1 5

(a) Calcule a aptidão de cada indivíduo e a probabilidade de cada um ser escolhido pela selecção proporcional à aptidão (como na fig. 4.6). Sugestão: conte os pares que se atacam na mesma linha e nas diagonais.

(b) Cruze os dois indivíduos mais aptos com um ponto de corte a seguir à 3.ª posição e escreva os dois descendentes e as suas aptidões. Algum é melhor do que os pais?

(c) Aplique ao melhor descendente uma mutação à sua escolha que melhore a aptidão. Qual é a melhor mutação de um só gene desse descendente?

(d) Repare na 2.ª posição das quatro cadeias. Que rainhas da coluna 2 nunca poderão aparecer num descendente obtido só por selecção e cruzamento? Que papel tem, então, a mutação? (Compare com a discussão dos «esquemas» dos slides.)

(e) Em que é que um algoritmo genético em que cada descendente tem um só progenitor (ρ = 1, nos «ingredientes de um algoritmo evolucionário» dos slides) difere da procura em feixe estocástica? E o que mantém um algoritmo genético que a recristalização simulada não mantém?

Exercício 10 – Verdadeiro ou falso

Justifique cada resposta em uma ou duas frases.

(a) O corte α-β pode devolver um valor diferente do minimax se a ordem dos nós for má.

(b) Os filhos da raiz nunca são cortados pelo corte α-β.

(c) Se as folhas da subárvore do primeiro filho da raiz tiverem valores todos diferentes, é sempre possível reordenar essa subárvore de modo a que o corte α-β não faça cortes dentro dela. (E se for a subárvore de outro filho da raiz?)

(d) O minimax assume que o adversário joga de forma óptima; por isso, um adversário pode melhorar o seu resultado jogando de forma sub-óptima.

(e) Substituindo os nós MIN de uma árvore por nós de acaso, o valor minimax esperado da raiz é sempre maior ou igual ao valor minimax original.

(f) Na MCTS, a jogada devolvida no fim é a de maior taxa de vitórias entre os filhos da raiz.

(g) O trepa-colinas garante encontrar o máximo global se a função objectivo for consistente.

(h) Se a temperatura descer suficientemente devagar, a recristalização simulada encontra o máximo global com probabilidade que tende para 1.

(i) A procura local em feixe com k estados é equivalente a k recomeços aleatórios em paralelo.

(j) Um algoritmo genético mantém várias soluções candidatas; a recristalização simulada mantém uma só.

(k) No espaço de estados de crença, uma solução para a crença b é também solução para qualquer superconjunto de b.

(l) Um plano cíclico cujas folhas são todas objectivos e de cujos pontos se chega sempre a uma folha resolve garantidamente o problema.