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.

Description

Title: Lights Out
Author/s:
  • Salamanca García, Ingacio
Contributor/s:
  • Mata Hernández, Águeda
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: January 2017
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

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.

More information

Item ID: 47118
DC Identifier: http://oa.upm.es/47118/
OAI Identifier: oai:oa.upm.es:47118
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 12 Jul 2017 10:48
Last Modified: 12 Jul 2017 10:48
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM