Puzzle League Tetris Attack
Projeto MC 906 – Introdução a inteligência artificial
André de Vasconcellos 080664
Luca Vaccari Gobbi 071552
Alberto Arruda de Oliveira 093311
Ruda Robson de Oliveira Paula 084107
Introdução
• Tetris (1984)
• Objetivo
• Tetris attack (Puzzle league) (1996)
• Nintendo
Motivação
• Participação do mercado de software mobile
• Liberdade de implementação dos conceitos de IA
• Diferenças entre IA focada para jogos e as estudadas em
MC906
Funcionamento
• Cursor
• Linha de blocos inativos
• Stop
• Marathon
• VS
• Puzzle
Funcionamento
• Combo
• Chains
Desenvolvimento
• Linguagem
• Metodologia
• Agenda
• Visão de mercado
• Aplicabilidade em outros escopos
Desenvolvimento
• Linguagem

• Metodologia
• Agenda
• Visão de mercado
• Aplicabilidade em outros escopos
Linguagem
• Python
• Pygames
• Vantagens/Desvantagens
Desenvolvimento
• Linguagem
• Metodologia

• Agenda
• Visão de mercado
• Aplicabilidade em outros escopos
Metodologia
• Métodos de busca sem fator multiplicante
• Heurística para construção de percursos
• Lista Tabú
• Método de busca baseado em caminho ótimo (com fator
multiplicante)
Metodologia
• Métodos de busca sem fator multiplicante 
• Heurística para construção de percursos
• Lista Tabú
• Método de busca baseado em caminho ótimo (com fator
multiplicante)
Método de busca sem fator multiplicantes
• Grafos
• Fator multiplicante (Chains)
• Busca em Largura
• Busca em profundidade
• Implicações
Método de busca sem fator multiplicantes
Metodologia
• Métodos de busca sem fator multiplicante
• Heurística para construção de percursos 
• Lista Tabú
• Método de busca baseado em caminho ótimo (com fator
multiplicante)
Heurística para construção de percursos
• Três ou mais blocos iguais consecutivos
• Dois blocos consecutivos
• Analise de vizinhança
• Implicações
Metodologia
• Métodos de busca sem fator multiplicante
• Heurística para construção de percursos
• Lista Tabú

• Método de busca baseado em caminho ótimo (com fator
multiplicante)
Lista Tabú
• Hash table
• Matrizes linearizadas
• Minimização de ciclos nos grafos
• Armazenamento de caminhos promissores e ruins
• Implicações
Metodologia
• Métodos de busca sem fator multiplicante
• Heurística para construção de percursos
• Lista Tabú
• Método de busca baseado em caminho ótimo
(com fator multiplicante) 
Método de busca baseado em caminho
ótimo (com fator multiplicante)
• Regra – Fator multiplicante
• Expansão de estados
• Implicações
Desenvolvimento
• Linguagem
• Metodologia
• Conceitos envolvidos
• Agenda 
• Visão de mercado
• Aplicabilidade em outros escopos
Agenda
Desenvolvimento
• Linguagem
• Metodologia
• Conceitos envolvidos
• Agenda
• Visão de mercado

• Aplicabilidade em outros escopos
Visão de mercado
• Lucro estimado em 2010 no setor de TIC : US$165,69 bilhões
Visão de mercado
Visão de mercado
Visão de mercado
Crescimento do mercado de games
mundial (US$ bilhões)
60
55.5
51
46.7
50
43
39.5
40
30
27.9
30.35
32.8
35.6
20
10
0
2007
2008
2009
2010
2011
2012
2013
2014
2015
• Porcentagem mercado de games do mercado de TIC : 20%
Desenvolvimento
• Linguagem
• Metodologia
• Conceitos envolvidos
• Agenda
• Visão de mercado
• Aplicabilidade em outros escopos

Aplicabilidade em outros escopos
• Desenvolvimento educacional
• Desenvolvimento profissional (Simuladores)
• Treinamentos militares
• Exercicios físicos
Trabalhos correlatos
• Artificial intelligence in games – James Wexler – University of
Rochester
• Games Research group – University of Alberta
Melhorias
• Heurísticas
• IA dedicadas a chains ativas
• Novos modos de jogos
Desafios
• Alinhamento dos conceitos de IA tradicionais aos utilizados
em jogos
• Tecnicas e conceitos novos
• Desenvolvimento do jogo
• Inexistencia de guidelines
• Escasso números de trabalhos correlatos
Desafios
• Analise de estados
• Expansão de estados
• Tempo de execução