Lights Out

Salamanca García, Ingacio (2017). Lights Out. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Lights Out
Autor/es:
  • Salamanca García, Ingacio
Director/es:
  • Mata Hernández, Águeda
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Enero 2017
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

En este trabajo se estudiará el juego Lights Out, que es un juego con una importante base matemática. El mecanismo del juego, que se describirá ampliamente en la memoria, consiste, básicamente, en un tablero de casillas donde cada una de estas posee una luz y un botón. Si se presiona dicho botón, cambia el estado de la luz de esa casilla y el de las luces de sus casillas vecinas. Una vez que se conocen las reglas del juego, este se analizará matemáticamente. Primero desde una perspectiva basada en conocimientos de álgebra lineal, en la cual se planteará la resolución del juego como un sistema de ecuaciones en el cuerpo ℤ2 (donde 0 representa el botón apagado y 1 el botón encendido). También se plantea el problema como un problema de teoría de grafos, demostrándose algunos teoremas que complementan la perspectiva obtenido con álgebra lineal. Otro análisis del juego se realizará desde un punto de vista mucho menos técnico a nivel matemático. El objetivo de este capítulo será simplificar algunas de las tareas relacionadas con la resolución del juego que implican conocimientos matemáticos en procedimientos o algoritmos que pudiesen ser realizados por un jugador estándar del juego que no tuviese esos conocimientos matemáticos. El mayor ejemplo de esto es el algoritmo Light Chasing que permite resolver el juego sin tener que resolver la ecuación. Para enriquecer el estudio del juego, también se valoró la posibilidad de que no solamente hubiera dos estados de luminosidad, sino que pudiese haber más. Esto significa que hay que buscar otras estructuras algebraicas para poder realizar las operaciones necesarias. Con todas estas operaciones planteadas, el siguiente paso lógico es tratar que la solución sea óptima. En este capítulo entran en juego conocimientos de investigación operativa, como el método simplex, que ayudarán a saber cuál es la solución óptima mediante la resolución de un problema de programación lineal. Concluido el modelo matemático del juego, se realizará una aplicación en Blender que simulará el juego y además lo resolverá. Toda esta implementación se dividirá en 4 fases: construcción del tablero, iluminación del tablero, resolución del tablero e interfaz gráfica. Todas las fases estarán explicadas paso a paso en la memoria como si se tratase de un tutorial.---ABSTRACT---In this Project, Lights Out will be studied. Lights Out is a game that has an important mathematical basis. The mechanism of the game, which will be extensively discussed in the document, consists, basically, on a game board with squares where each one of that has a light and a button. If the button is pressed, the light state of that square and the light state of its neighbour squares change. When the rules of the games are known, this will be analyzed mathematically. Firstly, from a perspective base don algebraic knowledge, with the goal of transforming the game in a system of equations in the field ℤ2 (where 0 represents the button off and 1 represents the buton on). In addition, graph theory also is used in order to help to solve the game. Some theorems that will be demostrated will complement the perspective obtained with linear algebra. Moreover, the game will be analyzed from a non mathematical perspective. The achievement of this chapter will be to simplify the tasks related with the game resolution that involve mathematical knowledge in procedures or algorithms that can be understood by a standard gamer without that knowledge. The best example of that is the algorithm Light Chasing that solve the game without solving the sistema of equations. In order to improve the research, the possibility of existing more tan two light levels was considered. In this point, it is essential to find other algebraic structures that allow to make the necesary operations. With all these operations, the following step is to optimise the solution. In this chapter, operative research plays an important role with methods such as simplex method, which will help to know the optimal solution throught the resolution of a linear programming problem. When the mathematical model concludes, a Blender applicaion will be implemented. This application will simulate the game and, moreover, solve it. All the implementation will divide into four phases: game board building, game board light, game board resolution and graphical interface. All the phases will be explained step to step in the document as it was a tutorial.

Más información

ID de Registro: 47118
Identificador DC: http://oa.upm.es/47118/
Identificador OAI: oai:oa.upm.es:47118
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 12 Jul 2017 10:48
Ultima Modificación: 12 Jul 2017 10:48
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM