Disciplina simultânea para graduação e para pós-graduação
O trabalho para alunos da pós é mais exigente. Alunos da pós também apresentarão seminários.
Alunos da escola de verão - ?
Avaliação: duas provas, trabalho implementado em programação, seminários
Duas aulas introdutórias, a partir da terceira aula começa a parte técnica
http://www.inf.ufpr.br/fabiano/info7017
Algoritmos exatos são adequados para resolver problemas de ordem polinomial, mas não são adequados para resolver problemas de ordem exponencial
Problemas de ordem exponencial são intratáveis com algoritmos exaustivos
Algoritmo de backtrack
espaços de estados gigantescos, mesmo fatorial
Máquinas de busca que conseguem caminhar no espaço de busca
Possibilidade: implementar uma solução para as rotas do 18xx
Humanos frequentemente são capazes de conseguir soluções boas, mas raramente as ótimas
Algoritmos da IA que procuram soluções boas são suficientes
Muitos usam heurísticas
Há a possibilidade de abordar problemas nos quais há mais de um critério métrico?
Objetivo da disciplina: trabalhar com problemas cujo espaço de busca é gigantesco.
Turing, artigo sobre a máquina de Turing
Conectividade, redes neurais
Abordagem conexionista
Abordagem simbólica. Penso que o problema do computador jogar um jogo qualquer está nesta classe.
Uma máquina simbólica pode ser acoplada a uma máquina conexionista?
Como criar máquinas capazes de compreender múltiplas forma de representação do conhecimento?
Lógica clássica → sistemas especialistas
2001 - HAL seria a primeira IA do cinema? Penso que pelo menos Robby (Forbidden Planet) seria uma IA. Assim como a Maschinenmensch (Maria) de Metropolis (1927).
Existe a necessidade de fazer a IA igual à IN?
phys.org blog sobre física e outros assuntos correlatos
Criar um blog com resumos e resenhas sobre Game Studies?
Características da inteligência humana
Aprender com a experiência. Desligar a capacidade de aprender?
Abstração e foco.
Representação do conhecimento, símbolos, linguagem.
Reação. Mas existem indicadores de que há comportamentos não mecânicos que são instintivos — penso nos experimentos sobre reação instintiva em discussões políticas
Inferência
Criatividade. A capacidade de criar problemas :)
Ação. Um agente inteligente tem que ter atuadores na realidade. Penso em Johnny Got His Gun (1971).
Singularidade da consciência
Aula de 21/02
Uma semana de folga após a primeira prova, datas a confirmar
Seminários da pós: antes da primeira prova, complemento de conteúdo apresentado até então. 9/4, 11/4, 16/4
50 min de seminário sobre determinados temas
Trabalho 1: máquinas de busca
Seminário: busca de rotas do 18xx ?
Possivelmente criar um subconjunto semântico para jogos?
Hm… apresentar os resultados em forma de teia e não em forma de lista
Busca de arquivos usando os recursos do BTRFS? Esse ia ser pesado!
Semantic Search na Lib Genesys
Linguagem de implementação: C
PROCURAR ALGORITMOS RECENTES DE BUSCA
Parte da nota: competição entre os trabalhos de implementação
Na graduação:
Trabalho 2: construir um jogador em um jogo adversarista, onde um agente artificial joga contra outro agente artificial
Jogo floodit
Repositório fdroid
Aula de 26/02
Norvig, capítulos 1 e 2
Primeira parte da disciplina: máquinas de busca
Segunda parte: prova de teoremas
IA fraca: o agente age de forma percebida como inteligente
IA forte: o agente pensa
IA fraca: quando o agente resolve bem um determinado problema, deixa de ser percebido como uma IA e passa a ser tratado como o início de uma nova linha de pesquisa. Por exemplo: ELIZA → NLP
Outro: Busca em espaço de estados
Terceira Lei de Clarke: Any sufficiently advanced technology is indistinguishable from magic.
Dois eixos: humanoi/racional, pensamento/comportamento
Redes neurais: propostas em 1951 (Minsky), mas abandonadas; retomadas nos anos 1990 (evolução do hardware?)
Qual é a sequência de passos necessária para levar a máquina do estado inicial para o estado desejado
Muitas soluções em algoritmos de planejamento atendiam a toy problems, ou versões muito simples de problemas intratáveis
Sistemas multiagentes: múltiplos agentes cooperando ou competindo
Ao mencionar a RoboCup (1993), o Fabiano mencionou a importância dos jogos de tabuleiro na pesquisa de IA. Perguntar sobre as limitações indicadas na minha dissertação.
IBM Watson: multiespecialista
2017: AlphaGo
DeepBlue e AlphaGo são baseados em máquinas de busca
AlphaZero: aprende a jogar qualquer coisa, jogando contra si mesmo
Analistas criticando as jogadas de Xadrez e Go do AlphaGo: as jogadas são brilhantes, mas não são humanas!
AlphaGo baseia-se em um banco de jogadas humanas, AlphaZero cria as suas jogadas
Máquinas que passam a criar representações próprias para elementos da vida, ainda que virtuais
Traduções técnicas eram feitas por professores e hoje são tradutores. Antes, os erros eram de tradução; hoje, são técnicos.
Agente racional:
- métrica para avaliar se o agente foi bem sucedido
- qual é o ambiente que define o problema e no qual vai ser resolvido
- atuadores (O), ação do ambiente sobre atuadores (robustos? confiáveis?)
- sensores (I)
Caracterização do ambiente
- observabilidade total/parcial (Xadrez: total)
- determinístico/estocástico (Xadrez: determinístico)
- episódico/sequencial (Xadrez: sequencial)
- estático/dinâmico (Xadrez: semidinâmico, porque todos os estados são conhecidos)
- discreto/contínuo (Xadrez: discreto)
- único agente/múltiplos agentes (Xadrez: dois agentes)
- múltiplos agentes competem/cooperam (Xadrez: competem)
Na aula de Inteligência Artificial. O professor distingue uma forma fraca e uma forma forte de IA. A forma fraca é um agente percebido como inteligente; a forma forte é um agente que pensa.
O interessante é a observação do professor sobre problemas da IA fraca. Por exemplo: desde a década de 1960, uma das principais linhas de pesquisa da IA era o processamento de linguagem natural (PLN) — pense em programas como o ELIZA.
Agora que o PLN tornou-se bem conhecido, isso deixou de ser considerado como IA e criou toda uma nova frente de pesquisas, em IA ou não.
Ao fim e ao cabo, lembra-me da Terceira Lei de Clarke: “Qualquer tecnologia suficientemente avançada é indistinguível da magia”, e lembra-me do adágio usado pelos mágicos de palco: nunca explique os truques,
Aula de 28/02
Exercício: leitura do capítulo 2, trecho sobre Agentes
Um problema de busca é uma busca em um espaço de estados
O objetivo da busca é encontrar um (ou vários) estados dentre os possíveis.
Um espaço de estados não é necessariamente composto pela totalidade dos estados (espaço total), pode ser composto por estados alcançáveis
Para alguns problemas, interessa descobrir o estado final
Para outros, o que interessa é descobrir o caminho para chegar ao estado final
Exemplo: lobo, carneiro, alface, pastor podem ser representados por duas tuplas (A, C, L, P), uma correspondente à margem inicial e a outra correspondente à margem final
Capítulo 3
Conteúdo para a primeira prova
Caracterização de um problema de busca:
. descrição dos estados
. descrição do estado inicial
. teste de objetivos
. especificação das ações possíveis
. modelo de transição: como uma ação aplicada a um estado resulta em outro estado
O espaço de estados definido com estes requisitos consiste em um grafo
Árvore de busca mostra os resultados de todas as ações a partir do estado inicial
Para caminhar em um grafo, o algoritmo é de profundidade ou de largura (ou em amplitude)
Algoritmo de backtrak, implementação recursiva de uma busca em profundidade
Quando estou analisando um nó do grafo, em profundidade, os nós filhos (os nós da “fronteira”) são tratados como uma pilha. Último a ser colocado é o primeiro a ser removido
A busca em profundidade é interrompida ao encontrar a primeira solução. Mas ela pode não ser a melhor, ou mesmo a única.
Modo de implementação: registros duplamente encadeados
Quando estou analisando um grafo em largura, os nós são tratados como uma fila
Na busca em profundidade, os nós visitados vão sendo descartados. Na busca em amplitude, isso não pode ser feito.
Implementar uma fila em prioridades para buscas em profundidade com custos diferentes para os nós
Armazenar o custo total diretamente ao fazer a expansão do nó sendo analisado
Aula de 7/3
Buscas cegas → o algoritmo não tem informações privilegiadas sobre o dado buscado
Existem linguagens de programação que não se prestam bem a recursão
De preferência, colocar a recursão o mais à direita possível
Linguagens imperativas e linguagens funcionais
Em C é mais eficiente gerenciar diretamente a pilha; em outras linguagens pode ser melhor usar backtracking do que usar recursão
Em linguagens funcionais, é melhor deixar que o compilador gerencie a pilha
Hoje, busca informada (Heurística), que aumenta a eficiência do algoritmo
Seção 3.5 do livro
Buscas informadas
Função f(n) que é a medida da “qualidade” do dado encontrado, ainda não final; ou melhor, avalia o caminho que ainda deve faltar até o dado procurado — “quente” ou “frio”
f(n) retorna o custo do caminho a partir deste ponto até o dado procurado
Quanto melhor (menor) f(n), melhor é a busca
Uma f(n) perfeita é ela própria a solução do problema
O custo a pagar deve ser sempre polinomial (tratável) e não exponencial, ou pior
Se o grafo é cíclico, a busca greedy (gulosa) não é completa. Pode haver um loop.
Algoritmo A*
f(n) = h(n) + g(n)
h(n) é uma estimativa da distância de (n) até o estado objetivo (solução)
g(n) é o custo do caminho do estado inicial até n
PRIMEIRO TRABALHO
Usar uma busca A* para o primeiro trabalho
Definir um problema e uma busca h(n) também pode ser o primeiro trabalho
Definição dos seminários
Vasculhar o domínio da minha pesquisa e encontrar um problema no qual a IA possa trabalhar: um espaço de possibilidades intratável
Aplicações de técnicas da IA para os alunos da graduação
Aula de 50 min
Mostrar o problema, mostrar um exemplo, mostrar um algoritmo
Abordar pelo viés do ensino e não da apresentação para um grupo de pesquisa
Possibilidade: um jogo de tabuleiro multijogador
Projetor, USB drive,
General Game Player
Limites da IA para jogos. Contraste entre jogos de tabuleiro e jogos digitais, especialmente os jogos de ação contínua
Para implementações, usar técnicas mais recentes
Possibilidade: Monte Carlo, usada no Alpha Go
Tema para o seminário + problema de busca em um grafo para implementação
Provas conceituais
Aula de 12/03
8-slide puzzle
A partir de um estado, criar os estados-filhos (a fronteira) e avaliar os seus resultados
HAI: criar a função de avaliação, criar a função de avaliação de pontuação, teste objetivo (pontuação = 25)
Métrica das ações: dar dicas tem custo mais caro?
Possibilidade: dar dica custo 2, descartar custo 0.5, jogar custo 1
Alpha-Beta o jogo é beta, cada um dos jogadores em sua vez é alfa
HAI: a distância para a solução depende da quantidade de cartas já jogadas.
HAI: a função de avaliação provavelmente será recursiva, atenção ao número de recursões.
HAI: considerar o jogo como o jogador adversário. O escore mínimo de uma jogada qualquer é a pontuação atual. A jogada de beta é “colocar” uma carta ruim na mão do adversário.
HAI: cada carta pode estar em apenas uma posição. Função para revelar se uma carta está em jogo revela também qual é a chance de estar em cada posição ainda desconhecida.
Quando uma carta de valor alta é descartada, modificar a pontuação máxima para a função de avaliação (dinâmica).
Estrutura de dados. Cada carta tem valor, naipe, ponteiros, CHANCE DE AINDA APARECER (?)
Definir uma boa função de avaliação é a parte mais importante de uma pesquisa de busca
Aula de 19/03
Heurísticas admissíveis. Introdução ao tema na aula anterior.
Busca informada/heurística
- estratégia geral é a busca da melhor escolha (best first) - o melhor candidato na fronteira é o que eu vou seguir
- função de avaliação f(n) é a estimativa de custo da solução que passa pelo estado n
- h(n) em geral é um dos componentes de f(n)
- h(n) é o custo estimado do caminho de menor custo de n até um estado objetivo
- h(n) depende apenas de n
- g(n) é o custo do caminho percorrido do estado inicial até n
- busca best first gulosa de melhor escolha: f(n)=h(n)
- busca best first A* f(n)=g(n)+h(n) - quanto eu já gastei mais quanto eu estimo que será o custo futuro
No caso do HAI, h(n) é fácil de ser calculada: best case scenario é que todas as cartas sejam jogadas na ordem.
Pode ser interessante adaptar h(n) conforme uma estimativa estatística para jogadores mais avançados
Características de h(n)
- Nunca superestima o custo para alcançar o objetivo
- se h(n) não superestima o objetivo, então f(n) também não superestima o custo para alcançar o objetivo
- h(n) ⇐ h*(n), onde h*(n) é o custo exato/ótimo para alcançar o objetivo a partir de n
- geralmente, h*(n) não é conhecido senão após encontrar a solução
Teorema: se h(n) é admissível, a busca A*, aplicada sobre uma árvore de busca, é ótima.
Uma busca é ótima se a primeira solução que ela encontra é a solução ótima do problema.
Isso se aplica a uma árvore de busca e não a um grafo mais geral.
HAI é uma árvore de busca e não um grafo? Não exatamente: há cartas repetidas.
Caso dos grafos
Quando o espaço de busca de A* é um grafo e não uma árvore, h(n) tem que ser admissível e consistente/monótona
h(n) ⇐ c(n,a,n’)+h(n’)
n’ é um filho de n, diretamente por uma aresta a; c(n,a,n’) é o custo de ir de n para n’ passando por a
Próxima aula: cap. 4, procurar exercícios
Aula de 21/03
Capítulo 4
Fazer os exercícios
Algoritmos de subida ou descida de encosta
Averiguar se HAI pode funcionar melhor como um algoritmo de subida de encosta.