Título: Juegos de alcanzabilidad sobre grafos and-or generales.
Director: Víctor Braberman
Jurados: Pablo Barenbaum, Fernando Schapachnik

Zoom: (a definir)

Resumen

Es común representar ciertos juegos determinados de dos jugadores mediante un árbol «and-or». Computar la estrategia ganadora para uno de los jugadores (o determinar que no existe) tiene aplicaciones muy diversas. En este trabajo extendemos el árbol «and-or» a grafos «and-or» generales con dos condiciones de victoria vinculadas a la alcanzabilidad de nodos objetivos. Este tipo de juegos, por ejemplo, tienen aplicación en ingeniería de software y robótica, ya que se los puede utilizar como pasos intermedios para calcular planes de misiones que reaccionan ante eventos de un ambiente que actúa como (jugador) adversario. Como las arenas de estos juegos -aunque descritas de manera compacta- pueden ser grafos enormes si se los desarrolla explícitamente, queremos encontrar conceptos que ayuden a valorar adecuadamente nodos a explorar en un análisis «on-the-fly» del grafo subyacente. Para ello proponemos caracterizar, de manera paramétrica, la condición de victoria de una exploración parcial del juego mediante una fórmula booleana. Primero calculamos está fórmula explícitamente mediante algoritmos de punto fijo, con la ayuda de la estructura de datos ROBDD. Luego, la utilizamos para guiar la exploración on-the-fly mediante heurísticas derivadas de ella. Evaluamos nuestras propuestas y hallamos heurísticas muy prometedoras a pesar de los costos elevados de representación de las fórmulas de victoria.