Temas de Tesis de Licenciatura
A continuación listo algunos temas que me interesa actualmente exporar en el contexto de tesis de licenciatura.
Tengo muchos más, si te interesa alguno, mandame un mail.
Machine Learning para Escalar Síntesis de Estrategias Ganadoras
Conocimientos de machines learning, Algoritmos, Lógica, Programación.
Tenemos una herramienta que calcula estrategias ganadoras en juegos de dos jugadores mediante una técnica de búsqueda heurística. A pesar de que la técnica representa una mejora con respecto al estado del arte, aún resulta insatisfactoria en términos de escala. Por ejemplo, dadas ciertas reglas puede resolver un juego para un tablero cuadrado de tamaño hasta 8x8 pero no más. Nos interesa experimentar si es posible guiar mejor la heurística de busqueda utilizando distintas estrategias ganadoras para tableros de 1x1 hasta 8x8, para resolver problemas de dimension mayor. Esta tesis involucra entender un algoritmo de búsqueda sobre grafos, entender la naturaleza de su output, entender la heurística de búsqueda, pensar cómo definir una técnica para mejorarla usando resultados anteriores, implementarlo y probarlo. Esta tesis require haber cursado materias de machine learning.
Heurísticas para Escalar Síntesis de Estrategias Ganadoras
Algoritmos, Lógica, Programación.
Tenemos una herramienta que calcula estrategias ganadoras en juegos de dos jugadores mediante una técnica de búsqueda heurística. La que heurística que utilizamos fue diseñada para ciertas condiciones de ganada de juegos y funciona muy bien. Ahora estamos estudiando juegos con condiciones de ganada más complejas. Aunque la heurística funciona razonablemente bien, nos preguntamos si sería posible definir una heurística mejor. Esta tesis involucra entender un algoritmo de búsqueda sobre grafos, entender la naturaleza de su output, entender la heurística de búsqueda, pensar en una heurística mejor, implementarla y probarla.
Minimización de Estrategias Ganadoras
Algoritmos, Lógica, Programación.
Tenemos una herramienta que calcula estrategias ganadoras en juegos de dos jugadores mediante una técnica de búsqueda heurística. Un problema que tiene es que las estrategias no son mínimas (el jugador para ganar a veces hace jugadas intrascendentes). Queremos desarrollar una técnica que dada una estrategia ganadora pueda recortarla identificando estas jugadas intrascendentes. Esta tesis involucra entender un algoritmo de búsqueda sobre grafos, entender la naturaleza de su output, pensar un nuevo algoritmo de búsqueda sobre grafos (de minimización), implementarlo y probarlo.
Maximización de Estrategias Ganadoras
Algoritmos, Lógica, Programación.
Tenemos una herramienta que calcula estrategias ganadoras en juegos de dos jugadores mediante una técnica de búsqueda heurística. Un problema que tiene es que las estrategias no son maximales. Esto significa que la estrategia sólo incluye, para una posición del tablero, una de las posibles jugadas que acercan al jugador al triunfo. Queremos desarrollar una técnica que dada una estrategia ganadora pueda extenderla identificando estas jugadas ganadoras adicionales. Esta tesis involucra entender un algoritmo de búsqueda sobre grafos, entender la naturaleza de su output, pensar un nuevo algoritmo de búsqueda sobre grafos (de maximización), implementarlo y probarlo.
Síntesis de estrategias ganadoras para juegos “run to completion” de dos jugadores.
Algoritmos, Lógica, Programación.
Tenemos una herramienta que calcula estrategias ganadoras en juegos de dos jugadores. Estos juegos son asimetricos en el sentido de que un jugador (el controlador) puede perder todas las carreras (race conditions) contra el otro jugador. Esta presunción sirve para asegurarse que el controlador va a ganar incluso en ambientes muy difíciles. La contra es que para muchos juegos, no existe una estrategia ganadora bajo esta presunción. En algunas aplicaciones (ej. robótica), la presunción de perder todas las carreras es demasiado fuerte y se tiene sentido pensar un juego de condiciones más simétricas. Hemos definido un tipo de juego nuevo (run to completion) donde asumimos que cada jugador puede hacer “todo lo que necesita” pero siempre debe finalmente ceder el turno al otro. Queremos implementar un algoritmo de síntesis de estrategias para este juego e incorporarlo a nuestra herramienta. Esta tesis involucra entender un paper que define el nuevo tipo de juego, entender otro paper que explica como se computan estrategias para estos juegos, implementar y experimentar.
Traducción automática de problemas de síntesis de la competencia internacional de síntesis a modelos MTSA
Algoritmos, Lógica, Programación.
Tenemos una herramienta, MTSA, que calcula estrategias ganadoras en juegos de dos jugadores. Estos juegos son expresados como una combinación de automatas y una sublógica de la lógica temporal lineal llamada GR(1). La competencia internacional de síntesis adopta un lenguaje distinto para especificar los problemas de síntesis que deben resolverse durante la competencia. Este lenguaje (TLSF) tiene un modelo semántico distinto al de MTSA. Queremos elaborar una traducción de problemas en TLSF a formato de MTSA y probar que esa traducción es correcta y completa (es decir que un problema en TSLF tiene solución si y solo si lo tiene su traducción en MTSA). Además queremos que esa traducción sea “inteligente” produciendo un modelo para MTSA que aproveche las optizaciones que tiene la herramienta. Por último queremos implementar esa traducción dentro de la herramienta MTSA y probar cómo nos va con algunos problemas de la competencia mundial.
Undefined
