Puzzle League - Tetris Attack

Projeto MC 906 – Introdução a inteligência artificial

André de Vasconcellos 080664Luca Vaccari Gobbi 071552Alberto Arruda de Oliveira 093311Ruda 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

2007 2008 2009 2010 2011 2012 2013 2014 20150

10

20

30

40

50

60

27.930.35

32.835.6

39.543

46.751

55.5

Crescimento do mercado de games mundial (US$ bilhões)

• 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