Pesquisa aplicada ao jogo Tetris
Contents
1. if isGameOver int tmp tg updateHiScore if tmp gt 0 tg saveHiScore cpuName tmp if tmp 0 Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris hiScoreLabel setText tg hiScore 0 score private void clearOld for int j 0 Position 3 lt 4 JFF cells f arrY j f offsetYLast f arrX j f o ITE cells f arrY j f offsetYLast f arrX j f o y createLineBorder Color LIGHT GRAY private void paintNewPosition for int j 0 cells f arrY j f offsetY f arrX j 3 cells f arrY j f offsetY f arrX j 4 j lt 4 j BevelBorder BevelBorder RAISED private void paintTG int i 0 Color c for int arr tg gLines for int j 0 j lt arr length j if arr j 0 switch arr j case Figure I c Figure COL I case Figure T c Figure COL T case Figure O c Figure COL O case Figure J c Figure COL J case Figure L c Figure COL L case Figure S c Figure COL S default c Figure COL Z break 04 ffsetXLast setBackground Color NH ffsetXLast setBorder BorderFactor f offsetX setBackground f getGolor cells i j setBackground c f offsetX setBorder BorderFactory create break break break break break break cells i jl setBorder BorderFactory createBevelBorder BevelBorder R2. new JPanel setLayout new BoxLayout jp BoxLayout LINE AXIS add score add Box createHorizontalGlue add jp D ps jp add Box createRigidArea ra D Pe new JPanel setLayout new BoxLayout jp BoxLayout LINE AXIS add new JLabel LINES add Box createHorizontalGlue add jp D Da jp add Box createRigidArea ra D Ps ines new JLabel 0 ines setForeground Color BLUE new JPanel setLayout new BoxLayout jp BoxLayout LINE AXIS add lines add Box createHorizontalGlue add jp D ps jp add Box createRigidArea ra ip p new JPanel setLayout new BoxLayout jp BoxLayout LINE AXIS add new JLabel LEVEL add Box createHorizontalGlue add jp D P jp add Box createRigidArea ra p p evelLabel new JLabel 1 velLabel setForeground Color BLUE p new JPanel p setLayout new BoxLayout jp BoxLayout LINE AXIS p add Box createRigidArea ra p add levelLabel Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris jp add Box createHorizontalGlue r add jp p new JPanel p setLayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra jp add new JLabel TIME p j add Box createHorizontalGlue r add jp time new JLabel 00 00 00 time setForeground Color BLUE jp new JPanel jp setL
3. 7 lookahead e na pior das hip teses em 0 401 00kahead O n lookahead Como guarda a cada itera o todos os movimentos ir consumir exactamente a mesma mem ria Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris 4 Ambiente de desenvolvimento Este projecto foi desenvolvido utilizando a linguagem Java com o suporte do IDE Eclipse 3 4 2 e com JRE 6 Update 13 Como software extra e que serviu como base foi utilizado um jogo chamado Jetris uma implementa o em Java do jogo Tetris mas que suporta apenas a componente de um jogador controlado por um humano Desta forma poss vel aproveitar a interface gr fica deste projecto para acrescentar os m dulos de intelig ncia artificial Ao n vel das m quinas utilizadas foram v rias e apenas se verificou diferen as ao mudar de sistema operativo sendo usado o Windows XP e Vista denotando se algumas limita es no ltimo 5 Avalia o do programa Os factores mais importantes em intelig ncia artificial aplicada a jogos s o a sua performance e desempenho em rela o aos objectivos do jogo em quest o No caso do Tetris ap s a realiza o de v rios testes em condi es iguais como base de compara o e selec o seria o n mero m dio de linhas e ou pontos feitos por jogo visto que o objectivo deste jogo pontuar o m ximo poss vel at se ultrapassar as mais famosas 20 linhas da hist ria dos videojogos Nos videojogos em parti
4. Universidade do Porto F EUP engenharia Intelig ncia Artificial Pesquisa aplicada ao jogo Tetris Relat rio Final Francisco Pinto Jo o Xavier Jo o Ribeiro Maio 2009 Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto ndice MEA EE 2 2 MOLIVA O eC Em 2 Mpeg 3 3 1 Funcionalidades erben evisos ERE ee teg laxare peser USE Pea eae 3 3 2 Estrutura do Programa sese sese eee eee eee 5 3 3 Esquemas de Representa o do Conhecimento eee ee eee eee 7 3 4 Implementa o dos Esquemas de Representa o do Conhecimento 8 3 5 An lise da complexidade dos algoritmos 9 4 Ambiente de desenvolvimento ee eee eee eee eee 10 5 Avalia o d s eT v T 10 6 Resultados Experimentais sees ee ee eee eee eee 10 dos CONCIUS O TTT 12 8 ecd 12 O Bibliografidi oie re ote eie tob tada vara atenda muta O exu Ob ceca cu oat eg a PUE Pa DV are aee GR FER E 13 10 ApendiC8s iscing ee ien iege ue SARAU a ao eger dv aene n aa e eese dl bass Tn 14 Manual do utilizadot reete a etn tene a iar acre cens 14 ll Exemplo de Uma execu o niente taie etae etae e toad de rade eo rn sae de rhe da enne 15 Il Listagem e iier tttm aerea ne Andre ande dora divs aee ddr ses 17 IV Nome dos elementos do grupo eesesesesee eese eene enne ena 37 Faculdade de Engenharia da Unversidade do Porto
5. code KeyEvent VK LEFT moveLeft else if code KeyEvent VK D code KeyEvent VK RIGHT moveRight else if code KeyEvent VK S code KeyEvent VK DOWN moveDown else if code KeyEvent VK W code KeyEvent VK UP rotation else if code KeyEvent VK SPACE moveDrop i addKeyListener keyHandler font new Font Dialog Font PLAIN 12 tg new TetrisGrid tg addChallenge challengeLines ff new FigureFactory nextBg new Color 238 238 238 initMenu JPanel all new JPanel new BorderLayout all add getLeftPanel BorderLayout WEST next piece all add getPlayPanel BorderLayout CENTER all add getMenuPanel BorderLayout EAST score level time all add getCopyrightPanel BorderLayout SOUTH setDefaultCloseOperation JFrame EXIT ON CLOSE this getContentPane add all BorderLayout CENTER pack this setResizable false for int i 0 i nSteps i fNext add ff getRandomFigure dropNext ActionListener taskPerformer new ActionListener public void actionPerformed ActionEvent evt if movement null return int mov movement getInstruction switch mov case Constants LEFT moveLeft break case Constants RIGHT moveRight break case Constants ROTATE rotation break case Constants DROP moveDrop break Pesquisa aplicada ao jogo Tetris Fa
6. mov new Movement xM 0 i search temp level 1 mov setScore cpuName temp countHoles temp getHeight temp averageHeight temp deltaHeight temp variance temp numPiecesOverload temp weightedHeight movement Temp add mov temp new TetrisGrid old nextX 4 nextY 0 f resetRotation f setOffset 4 0 else for int i 0 i maxRotation i for int h 1 h lt xM h moveRightDummy f temp for int j 0 j i J rotationDummy f temp mov new Movement 0 xM i search temp level moveDropDummy f temp mov setScore cpuName temp countHoles temp getHeight temp averageHeight temp deltaHeight temp variance temp numPiecesOverload temp weightedHeight movementTemp add mov temp new TetrisGrid old nextX 4 nextY 0 f resetRotation f setOffset 4 0 Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto for int i 1 i maxRotation i for int h 1 h lt 5 h for int 5 0 5 i j rotationDummy f temp for int k 0 k h k moveRightDummy f temp mov new Movement 0 h i search temp level 1 moveDropDummy f temp mov setScore cpuName temp countHoles temp getHeight temp averageHeight temp deltaHeight temp variance temp numPiecesOverload temp weightedHeight
7. rotations An retval Score score An return retval public int compareTo Movement m if this score lt m score return 1 else if this score m score return 0 else return 1 Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto IV Nome dos elementos do grupo Francisco Hernani Teixeira Pinto 060509055 Jo o Crist v o Afonso Sampaio Xavier 060509116 Jo o Pedro Matos Ribeiro 060509019
8. Francisco Pinto Jodo Ribeiro Jodo Xavier Figura 7 menu da janela Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto HI Listagem do c digo Ficheiro 1 lartrisMainFrame java ainda que este ficheiro n o seja da nossa autoria foi alvo de modifica es profundas pelo que inclu do nesta sec o package main iartris import javax imageio ImagelO import javax swing import javax swing border BevelBorder import javax swing border EtchedBorder import res ResClass import java awt import java awt event ActionEvent import java awt event ActionListener import java awt event AdjustmentEvent import java awt event AdjustmentListener import java awt event KeyAdapter import java awt event KeyEvent import java awt event KeyListener import java awt event WindowEvent import java awt event WindowFocusListener import java io BufferedInputStream import java util ArrayList import java util LinkedList public class IartrisMainFrame extends JFrame private static final long serialVersionUID 1L private static final String NAME iarTris 1 0 private static final int CELL H 24 private Font font private JPanel playPanel private JLabel score private JLabel lines private JLabel time private JLabel cpuNameLabel private JLabel scrollerLabel private JLabel levelLabel private JLabel hiScoreLabel private String cpuNa
9. a todas as jogadas s o guardadas num ArrayList lt Movement gt e retirada a melhor jogada No caso de ser uma heur stica que verifica o movimento a seguir primeiro repete se o processo com o tabuleiro obtido para a pe a seguinte e soma se a pontua o da melhor segunda jogada pontua o da primeira Este processo repete se recursivamente dependendo do n mero de pe as a ver frente Embora seja suportado virtualmente qualquer n mero de pe as frente a ter em conta a partir da 32 pe a a gera o da rvore torna se morosa e devido ao facto de esta gera o n o ser feita em concorr ncia com o jogo este atrasa se ao inv s de simplesmente demorar a jogar da que se optou por simplesmente implementar uma heur stica que v uma s pe a frente da actual 3 5 An lise da complexidade dos algoritmos A n vel de heur sticas todas percorrem o tabuleiro de igual modo portanto para um valor C de comprimento 10 colunas e L de largura correr as 7 heur sticas ter uma complexidade temporal de O C L 7 O n e uma complexidade espacial de O 1 pois n o gerado nenhum contentor para al m do tabuleiro existente O algoritmo de pesquisa usado tem dois factores importantes a ter em conta sendo estes o n vel de lookahead sendo que 2 ver uma pe a frente e os movimentos que dependendo da pe a podem ser da ordem de 10 20 ou 40 Em termos temporais o algoritmo processa em m dia em O 40 3 20 3 10
10. new JMenuItem Exit miartris add iartrisExit setKeyAcceleratorMenu iartrisExit KeyEvent VK ESCAPE 0 iartrisExit addActionListener mH iartrisExit setMnemonic X Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris private void setKeyAcceleratorMenu JMenultem mi int keyCode int mask KeyStroke ks KeyStroke getKeyStroke keyCode mask mi setAccelerator ks private JPanel getPlayPanel playPanel new JPanel playPanel setLayout new GridLayout 20 10 playPanel setPreferredSize new Dimension 10 CELL H 20 CELL H cells new JPanel 20 10 for int i 0 i lt 20 itt for int j 0 j lt 10 j cells i j new JPanel cells i jl setBackground Color WHITE cells i j setBorder BorderFactory createLineBorder Color LIGHT GRAY playPanel add cells i j return playPanel private JPanel getLeftPanel JPanel r new JPanel BoxLayout rL new BoxLayout r BoxLayout Y AXIS r setLayout rL r setBorder new EtchedBorder Dimension ra new Dimension 5 0 next new JPanel 4 4 JPanel nextP new JPanel nextP setLayout new GridLayout 4 4 Dimension d new Dimension 4 18 4 18 nextP setMinimumSize d nextP setPreferredSize d nextP setMaximumSize d for inti 0 i lt 4 itt for int j j lt 4 j next ill new JPanel nextP add next i 5 0
11. 6 3 8 10 8 1 com a qual se completaram 34 linhas ligeiramente melhor mas com muitos buracos pelo meio Por esse motivo a solu o seguinte 12 6 4 2 3 5 1 penalizava mais os buracos criados Com esta conseguiram se 44 linhas Ainda assim o espa o do tabuleiro n o era muito bem gerido Por outro lado verificou se que seria proveitoso que a estrat gia utilizada variasse para diferentes estados do tabuleiro Foi ent o criada uma nova verifica o assim que a coluna mais alta do tabuleiro passasse as 10 unidades de altura os pesos das fun es heur sticas seriam diferentes dando se prioridade a diminuir rapidamente a altura do tabuleiro em detrimento dos pontos efectuados e de poss veis buracos criados despair mode Ent o e utilizando agora um esquema do g nero H1 H2 H3 H4 H5 H6 H7 D1 D2 D3 D4 D5 D6 D7 com a solu o 12 6 5 2 3 7 1 6 12 5 2 3 7 1 foi poss vel atingir as 132 linhas Depois de algumas mudangas sucessivas dos valores 50 25 3 5 5 1 1 35 70 2 10 5 1 1 foi a solu o com que se obteve o melhor resultado 218 linhas Passou se ent o a considerar a pe a seguinte no c lculo da melhor jogada utilizando a solu o obtida anteriormente conseguindo se completar 286 linhas At ao momento o melhor resultado conseguido foi 589 linhas Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris 7 Conclus o Ap s a realiz
12. Descri o 3 1 Funcionalidades 3 1 1 Conceito O jogo consiste num tabuleiro de 20 linhas por 10 colunas portanto 200 c lulas que podem estar preenchidas ou vazias H sete tipos de pe as que s o todas as combina es poss veis de 4 blocos ortogonalmente adjacentes Vulgarmente atribui se nomes de letras s pe as atendendo sua forma sendo estas O I S Z L J T Um exemplo da sua representa o na implementa o realizada BEM Figura 1 Pe as do jogo Tetris O I S Z L J T As pecas podem efectuar 5 tipos de movimentos distintos sendo estes transla o esquerda uma casa transla o direita uma casa transla o para baixo uma casa transla o total para baixo todas as casas poss veis rota o no sentido dos ponteiros do rel gio Qualquer uma destas jogadas est limitada pela exist ncia de casas ocupadas a bloquear o caminho e pelas paredes Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris Se em algum momento o tabuleiro tiver uma ou mais linhas preenchidas estas s o imediatamente removidas atribuindo uma pontua o ao jogador baseada no n mero de linhas apagadas de uma vez em fun o do n vel A fun o usada de c lculo da pontua o a seguinte baseado nas vari veis lines score e level If lines 1 score score 100 5 level If lines 2 score score 400 20 level If lines 3 score scor
13. i lines data i 1 3 rtg hiScore i name JTable table new JTable data colNames table setAutoResizeMode JTabl AUTO RESIZE OFF table setBackground new Color 230 255 255 table setEnabled false hiScorePanel add table BorderLayout CENTER private class MenuHandler implements ActionListener public void actionPerformed ActionEvent e try JMenultem tmp JMenultem getSource if tmp iartrisRestart restart else if tmp iartrisPause pause else if tmp iartrisHiScore showHiScore else if tmp iartrisExit System exit 0 catch Exception exc exc printStackTrace System out Movement search TetrisGrid old int level if level lookup return null Figure f fNext get level TetrisGrid temp new TetrisGrid old ArrayList lt Movement gt movementTemp new ArrayList Movement Movement mov int maxRotation switch f getGridVal case Figure I case Figure S case Figure Z maxRotation 2 break case Figure O Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris maxRotation 1 default maxRotation 4 for int xM 4 xM lt 5 xM if xM lt 0 for int i 0 i maxRotation i for int h 0 h xM h moveLeftDummy f temp for int j 0 j i j rotationDummy f temp moveDropDummy f temp
14. jogo cont m m todos que possibilitam a rota o e transla o das pe as obter a pr xima pe a da fila pr ximo movimento e reiniciar o jogo Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto A interface conta com fun es que est o encarregues de lidar com todos os menus bot es e pain is estado de jogo tabela de pontua es e redesenho do tabuleiro A gera o da rvore de pesquisa efectuada por um m todo cuja recurs o est directamente ligada ao n vel de lookup da pe a seguinte isto o n mero de pe as que o programa sabe que existem a contar com a pe a actual auxiliado por outro m todo que permite retornar a melhor solu o dependendo da heur stica que est a ser utilizada 3 3 Esquemas de Representa o do Conhecimento Como representa o do estado de jogo e pe as optou se por manter a implementa o em LinkedList de int a guardar as cores das figuras 0 c lula vazia pois fazia parte da base do trabalho Para guardar as informa es das jogadas e suas pontua es usa se a classe Movement que cont m tr s inteiros correspondentes ao n mero de jogadas esquerda direita e rota es um float para armazenar a pontua o e um filho da mesma classe De modo a percorrer todas as jogadas poss veis optou se por gerar uma rvore de pesquisa atrav s de uma fun o recursiva simples limitada pelo n vel de jogadas frente utilizando pesquisa em prof
15. o registo das que j sa ram embora esta informa o n o seja disponibilizada ao utilizador 3 2 4 TetrisGrid Nesta classe feita a representa o do estado do jogo assim como a leitura e escrita das melhores pontua es HiScore valida es de jogadas elimina o de linhas adi o de linhas e avalia o do estado do tabuleiro tendo em conta as heur sticas previamente estabelecidas Para este fim s o frequentemente manipulados objectos do tipo Figure 3 2 5 HiScore M dulo respons vel pelo registo das tr s melhores pontua es escritas para e lidas do ficheiro iartris DAT chamada uma leitura a este ficheiro aquando da inicializa o do programa e nele escritas quando este mesmo acaba com as modifica es feitas no decorrer do programa 3 2 6 Movement M dulo que trata exclusivamente da avalia o e heur sticas Guarda as informa es da jogada efectuada passando parte de c lculo da pontua o dado um objecto do tipo TetrisGrid A pontua o calculada com base em diferentes pesos das fun es heur sticas chamadas sobre o tabuleiro e somada com a pontua o da pr xima melhor jogada se esta estiver a ser computada 3 2 7 IartrisMainFrame M dulo gen rico que tem a seu cargo m ltiplas fun es abrangendo a l gica do jogo a interface com o utilizador o controlador do jogo humano teclado e computador automatizado e a gera o da rvore de pesquisa A n vel da l gica do
16. 1 gt 0 if temp isNextMoveValid f f offsetX 1 f offsetY nextX f setOffset nextX nextY private void moveRight if isGameOver isPause return if f getMaxRightOffset 1 lt 10 if tg isNextMoveValid f f offsetX 1 f offsetY nextX nextMove private void moveRightDummy Figure f TetrisGrid temp Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris if isGame0Over isPause return if f getMaxRightOffset 1 lt 10 if temp isNextMoveValid f f offsetX 1 f offsety nextX f setOffset nextX nextY private synchronized void moveDown if isGameOver isPause return nextY nextMove private synchronized void moveDrop if isGameOver isPause return f offsetYLast f offsetY f offsetXLast f offsetX clearOldPosition while tg isNextMoveValid f f offsetX f offsetY f setOffset f offsetX f offsetYt1 tg addFigure f paintTG dropNext nextMove private synchronized void moveDropDummy Figure f TetrisGrid temp if isGameOver isPause return f offsetYLast f offsetY f offsetXLast f offsetX while temp isNextMoveValid f f offsetX f offsetY f setOffset f offsetX f offsetYt 1 temp addFigure f private synchronized void rotation if isGameOver isPause return for int 5 0 j lt f arrX length j
17. AISED else cells i jl setBackground Color WHITE cells i j setBorder BorderFactory createLineBorder Color LIGHT GRAY itt private void showNextFigures for int i 0 i nSteps showNext fNext get 1 private void showNext Figure f for inti 0 for int j next i j 3 next i 4 lt My i 0 J lt 4 5 i setBackground nextBg setBorder BorderFactory createEmptyBorder Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto for int j 0 J lt f arrX length Jtt next f arrY 5 f arrX 5 setBackground f getGolor next f arrY 5 f arrX 5 setBorder BorderFactory createBevelBorder Bevel Bord er RAISED private void dropNext if isGameOver return nextX 4 nextY 0 score setText tg getScore lines setText tg getLines levelLabel setText tg getLevel 20 f fNext getFirst fNext addLast ff getRandomFigure showNextFigures movement search tg 0 fNext removeFirst isGameOver tg isGameOver f isNewFigureDroped true private void moveLeft if isGameOver isPause return if nextX 1 gt 0 if tg isNextMoveValid f f offsetX 1l f offsetY nextX nextMove private void moveLeftDummy Figure f TetrisGrid temp if isGameOver isPause return if nextX
18. GHT DESPAIR VALUE holes Constants GREEDY HOLES DESPAIR VALUE else score height Constants GREEDY MAX HEIGHT VALUE holes Constants GREEDY HOLES VALUE else if height gt Constants DESPAIR LINE score height Constants MAX HEIGHT DESPAIR VALUE holes Constants HOLES DESPAIR VALUE average Constants AVERAGE HEIGHT DESPAIR VALUE delta Constants DELTA HEIGHT DESPAIR VALUE variance Constants VARIANCE HEIGHT DESPAIR VALUE overload Constants PIECE OVERLOAD DESPAIR VALUE weight N Constants WEIGHTED HEIGHT DESPAIR VALUE else score height Constants MAX HEIGHT VALUE holes Constants HOLES VALUE average Constants AVERAGE HEIGHT VALUE delta Constants DELTA HEIGHT VALUE variance Constants VARIANCE HEIGHT VALUE overload Constants PIECE OVERLOAD VALUE weight z Constants WEIGHTED HEIGHT VALUE if child null score child score public int getInstruction if rotations 0 Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris rotations return Constants ROTATE if leftM 0 leftM return Constants LEFT if rightM 0 rightM return Constants RIGHT return Constants DROP public String toString String retval An retval Left leftM n retval Right rightM hn retval Rotation
19. Pesquisa aplicada ao jogo Tetris 1 Objectivo O objectivo deste trabalho consiste na implementa o de um jogo Tetris que utilize intelig ncia artificial de modo a cumprir as metas do jogo em quest o A intelig ncia artificial tem como base variantes de algoritmos de pesquisa entre os quais alguns de pesquisa inteligente que atrav s de uma fun o de heur stica baseada em regras e estrat gias inerentes ao Tetris avalia e escolhe a jogada mais apropriada de modo a atingir os objectivos do jogo limpar linhas fazendo a melhor pontua o poss vel 2 Motiva o Em termos acad micos a realiza o deste trabalho em particular a implementa o dos v rios algoritmos de pesquisa propostos com respectivos testes e compara o ter como principal prop sito conhecer a sua aplicabilidade e diferente grau de efic cia Al m disso poder servir como base para outros problemas da mesma tem tica videojogos ou de reas diferentes onde necess rio encontrar o melhor conjunto de escolhas para optimiza o do resultado final A realiza o deste projecto trouxe outros benef cios uma vez que o Tetris considerado como um bom est mulo para actividade cerebral a implementa o de um tipo de intelig ncia artificial para este jogo tornou se num agrad vel desafio despertou interesse e perspectivas para problemas na mesma rea Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto 3
20. Text cpuName gameSettingsMenu new JPanel null gameSettingsMenu setLayout new GridLayout 3 0 JRadioButton greedyButton new JRadioButton Greedy false greedyButton addActionListener new RadioListener greedyButton setActionCommand Greedy JRadioButton hOButton new JRadioButton Skilled true h0Button addActionListener new RadioListener hOButton setActionCommand Skilled JRadioButton hlButton new JRadioButton Lookahead false Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris h1iButton addActionListener new RadioListener hiButton setActionCommand Lookahead JRadioButton humanButton new JRadioButton Human false humanButton addActionListener new RadioListener humanButton setActionCommand Human ButtonGroup bgroup new ButtonGroup bgroup add greedyButton bgroup add h0Button bgroup add hlButton bgroup add humanButton JPanel radioPanel new JPanel radioPanel setLayout new GridLayout 2 1 radioPanel add h0Button radioPanel add greedyButton radioPanel add hlButton radioPanel add humanButton int min 0 max 11 scroller new Scrollbar Scrollbar HORIZONTAL 0 1 min max scroller addAdjustmentListener new ScrollerListener scrollerLabel new JLabel Challenge Mn starting with 0 extra line s gameSettingsMenu add radioPanel gameSettingsMenu add scrollerLabe
21. a o deste trabalho poss vel concluir que a implementa o de uma intelig ncia artificial capaz atingir os objectivos de um jogo pode se tornar complexa e necessitar de um profundo conhecimento das regras e estrat gias a ele associadas A fase de testes foi essencial para determinar quais os aspectos a ter conta no tabuleiro alguns destes menos bvios e que antes eram dados como irrelevantes na estrat gia de jogo e a sua melhor combina o de import ncia pesos para aperfei oar a fun o de heur stica Ao longo da fase de implementa o foi gratificante ao melhorar os valores e par metros da fun o de heur stica verificar um aumento na capacidade de decis o e respectivamente a obten o de melhores resultados Conclui se ap s a realiza o deste trabalho que o desenvolvimento de agentes uma tarefa que se pode tornar bastante rdua e complexa principalmente quando confrontada com a dificuldade de obten o de dados exactos em ambientes com alguma complexidade ou como neste caso n o conhecidos a priori Desde que se estabele a uma forma de atacar o problema um agente pode proporcionar bons resultados o que bastante gratificante dando a sensa o que se conferiu intelig ncia a uma m quina 8 Melhoramentos Em perspectiva futura este trabalho poder evoluir para um jogo onde existir o dois advers rios competindo directamente por uma melhor pontua o Estes advers rios poder o ser humano
22. ayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra jp add time jp add Box createHorizontalGlue r add jp JLabel cpuLabel new JLabel n0 cpuLabel setForeground Color GREEN jp new JPanel jp setLayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra jp add new JLabel ALGORITHM jp add Box createHorizontalGlue r add jp cpuNameLabel new JLabel cpuName cpuNameLabel setForeground Color BLUE jp new JPanel jp setLayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra jp add cpuNameLabel jp add Box createHorizontalGlue r add jp r add Box createVerticalGlue BUTTONS r add Box createRigidArea new Dimension 0 10 jp new JPanel jp setLayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra JButton restartBut new JButton Restart restartBut setToolTipText Press R restartBut setFocusable false restartBut addKeyListener keyHandler restartBut addActionListener new ActionListener public void actionPerformed ActionEvent arg0 restart Dimension d new Dimension 90 30 restartBut setMinimumSize d restartBut setPreferredSize d restartBut setMaximumSize d jp add restartBut jp add Box createHorizontalGlue r add jp r add Box createRigidArea new Dimension 0 5 jp new JPane
23. cells f arrY j f offsetY f arrX j f offsetX setBackground Color WHITE cells f arrY j f offsetY f arrx 5 f offsetX setBorder BorderFactory create LineBorder Color LIGHT GRAY f rotationRight if tg isNextMoveValid f f offsetX f offsetY f rotationLeft nextMove private synchronized void rotationDummy Figure f TetrisGrid temp if isGameOver isPause return f rotationRight Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto if temp isNextMoveValid f f offsetX f offsetY f rotationLeft private synchronized void pause isPause isPause private void restart for int i 0 i lt 20 itt for int 5 0 j lt 10 jt t tg gLines get i j 0 cells i jl setBackground Color WHITE cells i j setBorder BorderFactory createLineBorder Color LIGHT GRAY paintTG ff resetCounts isGameOver false fNext clear for int i 0 i nSteps i fNext add ff getRandomFigure tt resetTime time setText 00 00 00 tg resetStats lookup 1 challengeLines 0 showAiSelector tg addChallenge challengeLines paintTG isPause false dropNext nextMove private void showAiSelector cpuName Skilled lookup 1 if cpuNameLabel null cpuNameLabel new JLabel cpuName else cpuNameLabel set
24. coluna multiplicada por 0 a 22 por 2 a 32 por 4 e assim sucessivamente at ltima Embora tenham sido propostos v rios algoritmos de pesquisa como pesquisa em profundidade largura bidireccional ou A a situa o foi estudada cautelosamente e chegou se conclus o que pesquisas que necessitassem um caso final seriam imposs veis de implementar Tendo em conta que a pesquisa principal a incluir no trabalho A necessita de ter em conta para al m de valores heur sticos o peso de cada aresta do grafo cujo custo todo id ntico considerou se na fun o f x g x h x onde f x o resultado da avalia o do algoritmo A para um peso g x e uma heur stica h x g x O Dado que a fun o de pesquisa est limitada ao valor heur stico optou se pela implementa o de uma nica pesquisa em profundidade e a dedicar maior trabalho a n vel de diferentes heur sticas que t m infer ncia directa na qualidade de jogo do computador Desta forma para a pe a actual s o geradas todas as combina es poss veis de movimentos e rota es O 10 10 transla es 1 rota o l S Z 20 10 transla es 2 rota es T J L 40 10 transla es 4 rota es Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto simulado para cada jogada que a pe a cai no tabuleiro e procede se a uma avalia o deste com diferentes pesos nas heur sticas descritas acima Para cada pe
25. contra um advers rio artificialmente inteligente com diferentes graus de dificuldade consoante a complexidade da heur stica e algoritmo de pesquisa utilizado ou ent o o computador controlar ambos os advers rios em competi o onde poss vel observar em tempo real as diferen as vantagens e desvantagens de um algoritmo em rela o a outro neste tipo de problema Uma boa ideia para melhorar as penaliza es nas heur sticas seria desenvolver um algoritmo gen tico que gerasse popula es de solu es e fosse evoluindo para encontrar uma solu o ptima ou pr xima dela Em termos de efici ncia do programa esta poderia ser melhorada com a cria o de um thread para gera o da rvore de pesquisa e c lculo da fun o de heur stica e posteriormente reduzir o n mero de n s da pesquisa atrav s de uma gera o de casos espec fica para cada tipo de pe a Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto 9 Bibliografia Site do projecto Jetris consultado em Abril de 2009 http jetris sourceforge net T cnicas de Tetris consultado em Abril de 2009 http www angelfire com pa5 b g stuhan Tetris html P ginas da Wikipedia referentes aos algoritmos a utilizar consultadas em Abril de 2009 http en wikipedia org wiki A http en wikipedia org wiki Breadth first search http en wikipedia org wiki Depth first search http en wikipedia org wiki Greedy algorithm http en wikipedia
26. cular a interface tem sempre um papel determinante no caso deste projecto foi conseguida a partir de uma base acima referida uma interface limpa e de f cil uso 6 Resultados Experimentais De modo a aperfei oar as fun es heur sticas utilizadas foram realizados diversos testes ao programa utilizando sempre a mesma seed de gera o de pe as aleat rias para se poder comparar directamente os resultados obtidos por duas solu es diferentes Para facilitar a compara o das solu es utilizadas isto dos pesos das diferentes heur sticas a sua representa o ser a seguinte H1 H2 H3 H4 H5 H6 H7 Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto Neste esquema podem ver se os pesos dos valores das heur sticas H1 a H7 consultar sec o 3 3 Durante a implementa o do algoritmo greedy ap s v rias modifica es os valores ficaram 60 40 O O O 0 conseguindo assim limpar 42 linhas Este foi o caso base de compara o para as modifica es seguintes Inicialmente n o foi utilizada a possibilidade de ter em conta a pe a seguinte para melhorar tanto quanto poss vel a jogada simples Come ou se ent o pela solu o 30 15 0 0 0 0 1 obtendo se 33 linhas limpas Com o ltimo valor a 1 tentou se que o computador encostasse as pe as ao lado esquerdo Seguidamente e para come ar a utilizar as outras fun es dispon veis foi utilizada a solu o 9
27. culdade de Engenharia da Unversidade do Porto new Timer Constants PC PLAYING TIME MS taskPerformer start GridThread gt new GridThread tt new TimeThread gt start tt start paintTG addWindowFocusListener new WindowFocusListener public void windowGainedFocus WindowEvent arg0 public void windowLostFocus WindowEvent arg0 isPause true Dimension screenSize Toolkit getDefaultToolkit getScreenSize setLocation screenSize width 2 getWidth 2 screenSize height 2 getHeight 2 setVisible true private void initMenu MenuHandler mH new MenuHandler JMenuBar menu new JMenuBar setJMenuBar menu JMenu miartris new JMenu menu add miartris miartris setText Menu miartris setMnemonic J iartrisRestart new JMenultem Restart miartris add iartrisRestart setKeyAcceleratorMenu iartrisRestart R 0 iartrisRestart addActionListener mH iartrisRestart setMnemonic R iartrisPause new JMenuItem Pause miartris add iartrisPause setKeyAcceleratorMenu iartrisPause P 0 iartrisPause addActionListener mH iartrisPause setMnemonic P miartris addSeparator iartrisHiScore new JMenuItem HiScore miartris add iartrisHiScore setKeyAcceleratorMenu iartrisHiScore H 0 iartrisHiScore addActionListener mH iartrisHiScore setMnemonic H miartris addSeparator iartrisExit
28. dTime sectt if sec 60 sec 0 min if min 60 min 0 hours Pesquisa aplicada ao jogo Tetris private void resetTime hours min sec 0 public void run try while true Thread sleep 50 if isGameOver Graphics g Font font Font BOLD 24 g setFont font g drawString GAME OVI else if isPause Faculdade de Engenharia da Unversidade do Porto playPanel getGraphics new Font g getFont getFontName ER 47 250 time setText PAUSED else if count gt 1000 count 0 incSec time setText this toString else count t 50 catch Exception e e printStackTrace public String toString StringBuffer sb if hours lt 10 sb append 0 sb append hours sb append if min 10 sb append 0 sb append min sb append if sec lt 10 sb append 0 sb append sec return sb toString public IartrisMainFrame super NAME nSteps 3 fNext new LinkedList lt Figure gt setIconImage loadImage icon jpg lookup 1 challengeLines 0 showAiSelector new StringBuffer Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris keyHandler new KeyAdapter public void keyPressed KeyEvent e int code e getKeyCode if code KeyEvent VK A
29. e 900 45 level If lines 4 score score 1600 80 level As pe as efectuam com o decorrer do tempo uma transla o para baixo de uma unidade O tempo que esta transla o demora a acontecer diminui linearmente enquanto o n vel sobe H um m ximo de 20 n veis e um novo n vel antes do n vel m ximo alcan ado a cada 10 linhas removidas do tabuleiro O objectivo do jogo ent o pontuar o m ximo poss vel antes que o tabuleiro de jogo fique obstru do de tal forma que n o possibilite a coloca o da pe a seguinte 3 1 2 Aplica es relevantes O jogo data do ano de 1985 e desde ent o in meras implementa es para v rios sistemas operativos e plataformas de jogos t m sido desenvolvidas umas mais bem sucedidas e reconhecidas que outras A primeira vers o foi programada para o sistema Elektronika 60 J em 1989 foram atribu dos direitos de autor Nintendo que distribu u o jogo na sua consola da altura a NES Ainda nos dias de hoje esta das vers es mais conhecidas Em 1993 uma das vers es mais conhecidas do jogo para o sistema operativo Windows saiu com o Microsoft Entertainment Pack Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto 3 1 3 Funcionalidades adicionais O programa ao ser corrido oferece ao utilizador um menu com v rias op es que o permitem decidir se ele que vai jogar ou se o computador assim como a heur stica e o n mero de li
30. jl JPanel jp new JPanel jp setLayout new BoxLayout jp BoxLayout LINE AXIS jp add Box createRigidArea ra jp add new JLabel NEXT jp add Box createHorizontalGlue r add jp r add nextP r add Box createRigidArea new Dimension 100 10 return r private JPanel getMenuPanel JPanel r new JPanel BoxLayout rL new BoxLayout r BoxLayout Y AXIS r setLayout rL r setBorder new EtchedBorder Dimension ra new Dimension 5 0 Pesquisa ap licada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto JPanel jp new JPanel 7 j j j d h h j j j j j r j j j j j r S S E E E fe Ee E eg p setLayout new BoxLayout jp BoxLayout LINE AXIS p add Box createRigidArea ra p add new JLabel HI SCORE p add Box createHorizontalGlue add Jp iScoreLabel new JLabel tg hiScore 0 score iScoreLabel setForeground Color RED p new JPanel p setLayout new BoxLayout jp BoxLayout LINE AXIS p add Box createRigidArea ra p add hiScoreLabel p add Box createHorizontalGlue add jp add Box createVerticalStrut 5 p new JPanel p setLayout new BoxLayout jp BoxLayout LINE AXIS p add Box createRigidArea ra p add new JLabel SCORE p add Box createHorizontalGlue add jp core new JLabel 0 core setForeground Color BLUE
31. l jp setLayout new BoxLayout jp BoxLayout LINE AXIS Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto jp add Box createRigidArea ra JButton pauseBut new JButton Pause pauseBut setToolTipText Press P pauseBut setFocusable false pauseBut addActionListener new ActionListener public void actionPerformed ActionEvent arg0 pause pauseBut setMinimumSize d pauseBut setPreferredSize d pauseBut setMaximumSize d jp add pauseBut jp add Box createHorizontalGlue r add jp return r private JPanel getCopyrightPanel JPanel r new JPanel new BorderLayout BoxLayout rL new BoxLayout r BoxLayout LINE AXIS r setLayout rL r setBorder new EtchedBorder r add Box createRigidArea new Dimension 75 0 JLabel jL new JLabel IART 2009 Francisco Pinto Jo o Ribeiro Jo o Xavier jL setFont font r add jL r setAlignmentX CENTER ALIGNMENT return r static Image loadImage String imageName try Image im ImagelO read new BufferedInputStream new ResClass getClass getResourceAsStream imageName return im catch Exception e e printStackTrace System out return null private synchronized void nextMove f setOffset nextX nextY if tg addFigure f dropNext f setOffset nextX nextY else clearOldPosition paintNewPosition
32. l gameSettingsMenu add scroller JOptionPane showMessageDialog this gameSettingsMenu Game Settings JOptionPane PLAIN MESSAGE private class ScrollerListener implements AdjustmentListener public void adjustmentValueChanged AdjustmentEvent arg0 challengeLines arg0 getValue scrollerLabel setText Challenge Mn starting with argO getValue extra line s private class RadioListener implements ActionListener public void actionPerformed ActionEvent ae cpuName ae getActionCommand cpuNameLabel setText cpuName if cpuName Human lookup 0 else if cpuName Skilled cpuName Greedy lookup 1 else if cpuName Lookahead lookup 2 private void showHiScore setHiScorePanel JOptionPane showMessageDialog this hiScorePanel HI SCORE JOptionPane PLAIN MESSAGE new ImageIcon loadImage splash32 png hiScorePanel null Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto private void setHiScorePanel hiScorePanel new JPanel new BorderLayout String colNames Place Points Lines Name String data new String tg hiScore length 1 colNames length data 0 colNames for int i 0 i lt tg hiScore length i data i 1 new String colNames length data i 1 0 i 1 data i 1 1 tg hiScore i score data i 1 2 tg hiScore
33. me private Scrollbar scroller private Movement movement private JPanel cells private TetrisGrid tg private JPanel next private int nextX private int nextY private int elapsedTime private Figure f private LinkedList Figure fNext private int nSteps private int lookup private int challengeLines private FigureFactory ff private boolean isNewFigureDroped private boolean isGameOver Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris private boolean isPause private Color nextBg private TimeThread tt private KeyListener keyHandler menu private JMenultem iartrisRestart private JMenultem iartrisPause private JMenultem iartrisHiScore private JMenuItem iartrisExit private JPanel hiScorePanel private JPanel gameSettingsMenu private class GridThread extends Thread private int count 0 public void run try while true if isGameOver isPause Thread sleep 50 else if isNewFigureDroped isNewFigureDroped false count 0 nextMove continue else Thread sleep 50 drop speed count 50 if count 50 tg getLevel gt 1100 count 0 nextY nextMove catch Exception e e printStackTrace private class TimeThread extends Thread private int hours private int min private int sec private int count private void incSec elapse
34. movementTemp add mov temp new TetrisGrid old nextX 4 nextY 0 f resetRotation f setOffset 4 0 return getBest movementTemp Movement getBest ArrayList lt Movement gt movementTemp Movement best null float bestScore Float MAX VALUE for Movement m movementTemp if m getScore lt bestScore bestScore m getScore best m return best Ficheiro 2 Constants java package main iartris public final class Constants despair line public static final int DESPAIR LINE 10 skilled height lt DESPAIR LINE public static final int HOLES VALUE 50 public static final int MAX HEIGHT VALUE 25 public static final int AVERAGE HEIGHT VALUE 3 public static final int DELTA HEIGHT VALUE 5 public static final int VARIANCE HEIGHT VALUE 5 public static final int PIECE OVERLOAD VALUE 1 Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris public static final int WEIGHTED HEIGHT VALUE 1 greedy height DESPAIR LINE public static final int GREEDY HOLES VALUE 60 public static final int GREEDY MAX HEIGHT VALUE 30 skilled height DESPAIR LINE public static final int HOLES DESPAIR VALUE 35 public static final int MAX HEIGHT DESPAIR VALUE 70 public static final int AVERAGE HEIGHT DESPAIR VALUE 2 public static final int DELTA HEIGHT DESPAIR VALUE 10 p
35. nhas inicial Dentro do jogo poss vel pausar consultar a tabela dos maiores pontuados e reiniciar o jogo actual quer atrav s de um menu quer de bot es na interface Quando o jogador n o tem a janela do jogo como selec o o jogo automaticamente pausado Al m destas fun es de controlo poss vel ao utilizador jogar em qualquer altura mesmo intervir se for o computador a jogar at aparecer o ecr de fim de jogo quando n o poss vel colocar mais nenhuma pe a 3 2 Estrutura do Programa O programa de modo a um maior aproveitamento das potencialidades das linguagens orientadas a objectos e ao polimorfismo encontra se subdividido em alguns m dulos sendo estes 3 2 1 Figure Este o m dulo mais b sico de todo o projecto uma classe abstracta que garante capacidade aos seus filhos de realizar opera es simples de movimento como transla es e rota es esquerda e direita 3 2 2 Figures Cont m todas as 7 pe as do jogo Tetris que estendem as funcionalidades do m dulo Figure As fun es de rota o e as cores s o diferentes para cada pe a assim como a sua apar ncia Estas informa es s o guardadas na classe m e para preservar o polimorfismo modular Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris 3 2 3 FigureFactory A aplica o deste m dulo muito importante na l gica do jogo pois devolve aleatoriamente qualquer uma das 7 pe as e guarda
36. org wiki lterative deepening depth first search http en wikipedia org wiki Bidirectional search Site com visualiza o da aplica o de alguns dos algoritmos consultado em Abril de 2009 http el tramo be software jsearchdemo consultado em Abril de 2009 Relat rio de uma implementa o de intelig ncia artificial para o jogo Tetris consultado em Abril de 2009 http www cs cmu edu afs cs project ACRL www TetrisReports RodriguezLindzeyTeschHW1 pdf F rum sobre intelig ncia artificial aplicada ao jogo Tetris consultado em Abril de 2009 http www gamedev net community forums topic asp topic id 391139 Artigo que descreve como um computador pode jogar o jogo Tetris consultado em Abril de 2009 http www colinfahey com tetris tetris_en html Vis o geral de uma poss vel arquitectura de Tetris http cslibrary stanford edu 112 Tetris Architecture html Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris 10 Ap ndices I Manual do utilizador I 1 Instruc es de compilac o O ficheiro make bat cont m a instru o necess ria compila o do jogo sendo esta jar cvfm iarTris jar manifest mf lartrisMain iartris DAT main iartris res score iartris supondo que se est na pasta de origem do projecto 1 2 Instru es de execu o Correr o ficheiro execut vel iarTris jar gerado pela execu o do passo anterior L3 Instruc es de jogo Ir surgir um ecr que pe
37. rmite escolher se o computador a jogar e sua heur stica ou um humano necess rio escolher tamb m o n mero de linhas com que o tabuleiro come a Este ecr ir surgir de cada vez que se reiniciar um jogo Para al m dos bot es e da interface em menu as teclas fazem as seguintes opera es W T rodar a peca no sentido dos ponteiros do rel gio A deslocar a peca uma casa para a esquerda D 5 deslocar a peca uma casa para a direita S d deslocar a pe a uma casa para baixo ESPA O deixar cair a pe a no tabuleiro R reiniciar o jogo P pausar recome ar o jogo ESC sair do jogo Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto II Exemplo de uma execuc o Iniciando o programa nos mostrado o menu de configura o do jogo Figura 2 onde podemos escolher se o computador que joga e que m dulo de intelig ncia artificial utilizar ou se antes o utilizador a jogar tamb m poss vel comecar em modo Challenge seleccionando linhas extra que come am j no tabuleiro completamente ocupadas excep o de um espa o Figura 3 Lera H SCORE 85550 SCORE 0 LINES 0 LEVEL 0 20 TIME 00 00 00 ALGORITHM Skilled Skilled Greedy C Lookahead Human Challenge starting with 4 extra line s th Figura 2 ecr de configura o tt IART 2009 Francisco Pinto Jo o Ribeiro Jo o Xavier Fig
38. ublic static final int VARIANCE HEIGHT DESPAIR VALUE 5 public static final int PIECE OVERLOAD DESPAIR VALUE 1 public static final int WEIGHTED HEIGHT DESPAIR VALUE 1 greedy height gt DESPAIR LINE public static final public static final int GREEDY HOLES DESPAIR VALUE 20 int GREEDY MAX HEIGHT DESPAIR VALUE 80 instructions public static final int LEFT 0 public static final int RIGHT 1 public static final int ROTATE 2 public static final int DROP 3 pc playing public static max number public static time in miliseconds final int PC PLAYING TIME MS 100 of highscores final int HIGHSCORE N 5 Ficheiro 3 Movement java package main iartris public class Movement implements Comparable lt Movement gt int leftM int rightM int rotations float score private private private private private Movement child public Movement int leftM movement int rightM int rotations Movement this leftM leftM this rightM rightM this rotations rotations this child movement public float getScore return score Pesquisa aplicada ao jogo Tetris Faculdade de Engenharia da Unversidade do Porto public void setScore String cpuName int holes int height float average float delta float variance int overload float weight if cpuName Greedy if height gt Constants DESPAIR LINE score height Constants GREEDY MAX HEI
39. undidade S o usados v rios m todos de c lculo de pontua o heur sticas que determinam o qu o longe o tabuleiro est do estado ideal vazio H1 N mero de buracos casas livres por baixo de pe as no tabuleiro H2 Altura m xima do tabuleiro H3 Altura m dia do tabuleiro H4 Diferen a entre a altura m xima e m nima do tabuleiro H5 Desvio padr o das alturas do tabuleiro H6 N mero de pe as por cima de buracos H7 Distribui o pesada das alturas do tabuleiro Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris 3 4 Implementa o dos Esquemas de Representa o do Conhecimento H1 calcula todos os espa os vazios no tabuleiro que se encontram numa posi o inferior a c lulas preenchidas H2 percorre todas as colunas retornando o n mero de blocos da maior delas a contar do fundo do tabuleiro H3 soma as alturas de todas as colunas dividindo pelo n mero total de colunas 10 retornando a m dia H4 devolve a diferen a entre a altura m xima e a altura m nima de todas as colunas no tabuleiro H5 calcula a soma dos m dulos da dist ncia entre a altura de cada coluna e a m dia das alturas H6 calcula a carga de cada coluna ou seja conta todas as pe as que se encontram acima do primeiro buraco de cada coluna H7 retorna a soma das alturas de todas as colunas depois de as multiplicar um factor que vai aumentando linearmente a cada coluna Neste caso a altura da 12
40. ura 3 in cio do jogo Ap s algum tempo de execu o o tabuleiro poder ter um aspecto semelhante ao observ vel na Figura 4 HI SCORE 0 SCORE 145410 LINES 570 LEVEL 20 20 TIME 00 12 37 ALGORITHM Lookahead Restart IART 2009 Francisco Pinto Jo o Ribeiro Jo o Xavier Figura 4 jogo em execu o Faculdade de Engenharia da Unversidade do Porto Pesquisa aplicada ao jogo Tetris Terminando o jogo mostrada a mensagem GAME OVER no ecr Figura 5 A qualquer momento da execu o pode se pressionar R para recome ar o jogo sendo mostrado o menu de configura es novamente H para mostrar o ecr de highscores Figura 6 P para fazer pause ou ESC para encerrar a aplica o Todas estas fun es podem tamb m ser acedidas pelo menu da janela Figura 7 acts 10 HI SCORE 149610 SCORE 149610 HI SCORE ees LINES 589 LEVEL 20120 TIME 00 13 04 ALGORITHM Lookahead Points Lines Name 149610 589 Lookahead 38560 198 Lookahead 29650 165 Lookahead 6060 49 Lookahead 700 7 Skilled Figura 6 ecr de highscores Restart Pause IART 2009 Francisco Pinto Jo o Ribeiro Jo o Xavier Figura 5 jogo terminado 0 SCORE 100 e LINES T 1 LEVEL 0 20 TIME PAUSED ALGORITHM Skilled Restart R HI SCORE Pause P Restart Pause IART 2009
Download Pdf Manuals
Related Search