Generación y resolución de puzles automática como apoyo a diseñadores de videojuegos

GENERACIÓN Y RESOLUCIÓN DE PUZLES AUTOMÁTICA COMO APOYO A DISEÑADORES DE VIDEOJUEGOS AUTOMATIC PUZZLE GENERATION AND SOLVING AS A SUPPORT FOR GAME DESIGNERS TRABAJO FIN DE GRADO CURSO 2023-2024 AUTOR Es he Babon A cauz DIRECTOR Ismael Sag edo Oli enza GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID GENERACIÓN Y RESOLUCIÓN DE PUZLES AUTOMÁTICA COMO APOYO A DISEÑADORES DE VIDEOJUEGOS AUTOMATIC PUZZLE GENERATION AND SOLVING AS A SUPPORT FOR GAME DESIGNERS TRABAJO DE FIN DE GRADO EN INGENIERÍA INFORMÁTICA AUTOR ESTHER BABON ARCAUZ DIRECTOR ISMAEL SAGREDO OLIVENZA CONVOCATORIA: SEPTIEMBRE 2024 GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID 13 DE SEPTIEMBRE DE 2024 III DEDICATORIA A mi amona V AGRADECIMIENTOS A Guille, Ósca y odos los que han hecho que es e camino sea más lle ade o. VII RESUMEN GENERACIÓN Y RESOLUCIÓN DE PUZLES AUTOMÁTICA COMO APOYO A DISEÑADORES DE VIDEOJUEGOS En es e T abajo de Fin de G ado modelamos, esol emos y gene amos cinco ipos de ompecabezas de la conocida saga de ideojuegos el P o eso Lay on. Pa a ello u ilizamos di e en es écnicas de In eligencia A i icial, como la búsqueda heu ís ica A*, la búsqueda me aheu ís ica de op imización En iamien o Simulado y los algo i mos gené icos. Además inco po amos una in e az g á ica pa a que el usua io pueda ecibi pis as pa a llega a la solución del puzle en iempo eal y pa a que pueda gene a los puzles con di e en es di icul ades. Finalmen e comp obamos que los algo i mos u ilizados son óp imos median e g a icas de medidas de iempos de ejecución y alidez de las soluciones gene adas. Palab as cla e Puzle, IA, Modela , Resol e , Gene a , Heu ís ica, Búsqueda, A*, Gené icos, Algo i mos XV ÍNDICE DE FIGURAS Figu a 1: Wa e Pi che s [43] ..................................................................................................19 Figu a 2: Tiempo gene ación Ja as ......................................................................................23 Figu a 3: Tiempo esolución Ja as .......................................................................................23 Figu a 4: GUI menú Ja as ......................................................................................................24 Figu a 5: GUI esol e Ja as ...................................................................................................24 Figu a 6: GUI esol e Ja as pis a ..........................................................................................25 Figu a 7: GUI gene a Ja as ..................................................................................................26 Figu a 8: A wo m's D eam [33] ...............................................................................................27 Figu a 9: Tiempo gene ación 8/16-puzle ..............................................................................30 Figu a 10: Tiempo esolución 8/16-puzle ...............................................................................30 Figu a 11: GUI menú 8/16-Puzle .............................................................................................31 Figu a 12: GUI esol e 8/16-Puzle ..........................................................................................31 Figu a 13: GUI gene a 8-Puzle ...............................................................................................32 Figu a 14: GUI gene a 16-Puzle .............................................................................................33 Figu a 15: S omp on i ! [34].....................................................................................................34 Figu a 16: Tiempo gene a S omp .........................................................................................36 Figu a 17: Tiempo esol e S omp ..........................................................................................37 Figu a 18: GUI menú S omp ...................................................................................................37 Figu a 19: GUI esol e S omp ................................................................................................38 Figu a 20: GUI gene ación S omp 1 ......................................................................................39 Figu a 21: GUI gene ación S omp 2 ......................................................................................39 Figu a 22: Ge he Ball Ou ! [35] ............................................................................................40 XVI Figu a 23: Tiempo gene ación Pelo a ...................................................................................43 Figu a 24: Tiempo esolución Pelo a .....................................................................................44 Figu a 25: GUI menú Pelo a ...................................................................................................44 Figu a 26: GUI esol e Pelo a 1 .............................................................................................45 Figu a 27: GUI esol e Pelo a 2 .............................................................................................46 Figu a 28: GUI gene a Pelo a 1.............................................................................................46 Figu a 29: GUI gene a Pelo a 2.............................................................................................47 Figu a 30: Ha g am [37] ..........................................................................................................48 Figu a 31: Fi ness Núme o de gene aciones ........................................................................53 Figu a 32: Tiempo ejecución núme o de gene aciones .....................................................54 Figu a 33: Fi ness po amaño de población ........................................................................55 Figu a 34: Tiempo po amaño de población ......................................................................55 Figu a 35: Fi ness po amaño de o neo ..............................................................................56 Figu a 36: Tiempo po amaño de o neo ............................................................................57 Figu a 37: Fi ness po p obabilidad de c uce .......................................................................58 Figu a 38: Tiempo po p obabilidad de c uce .....................................................................58 Figu a 39: Fi ness po p obabilidad de mu ación ................................................................59 Figu a 40: Tiempo po p obabilidad de mu ación ..............................................................60 Figu a 41: Fi ness solución 100 Ha g am................................................................................60 Figu a 42: GUI menú Ha g am ...............................................................................................61 Figu a 43:GUI esol e Ha g am .............................................................................................62 Figu a 44: GUI esol e Ha g am piezas ................................................................................63 XVII Índice de ablas Tabla 1: Ca ac e ís icas PC ....................................................................................................16 Tabla 2: Di icul ades gene ación Ja as ...............................................................................22 Tabla 3: Di icul ades gene ación puzle8/16 .........................................................................29 Tabla 4: Di icul ades gene ación S omp ..............................................................................36 Tabla 5: Di icul ades gene ación Pelo a ..............................................................................43 1 Capí ulo 1 - In oducción 1.1 Mo i ación El campo de la In eligencia A i icial ha ganado mucha a ención en los úl imos años mayo i a iamen e debido a la popula ización y accesibilidad pública de sis emas de cha basados en In eligencia A i icial como Cha GPT o gene ado es de con enido mul imedia como S able Di usion o So a. A medida que a la población se le ha acili ado el uso de es e ipo de he amien as, se ha in e esado más po cómo uncionan y a que o os sec o es se pueden aplica . Sin emba go, exis en múl iples aplicaciones donde el uso de la IA simbólica clásica iene cabida. Po ejemplo, Cha GPT iene p oblemas pa a ealiza cálculos ma emá icos complejos [1], y además es poco e icien e a la ho a esol e de o ma óp ima puzles como el 8-Puzzle o el cubo de Rubik. Conc e amen e, en un es udio ecien e [2] con igu a on LLMs pa a la esolución de puzles, es as LLMs especializadas, conseguían una asa de acie o del 93.2% en el 8-puzle, cuando A* puede esol e es e ipo de puzle en poco iempo y con una asa de acie o del 100%. A pesa de los a ances conseguidos con la u ilización de los LLMs, en es e ipo de p oblemas sigue siendo más con enien e ecu i a la IA simbólica clásica. En es e T abajo de Fin de G ado que emos esol e y gene a puzles o p oblemas de la conocida saga de juegos El P o eso Lay on [3], median e el uso de algo i mos de búsqueda heu ís ica. La saga de ideojuegos del P o eso Lay on se cen a en esol e mis e ios, pa a a anza en la his o ia debemos esol e una mul i ud de puzles de odo ipo y de di e en es di icul ades. Todo ello amenizado po una his o ia que da consis encia a la sucesión de puzles que amos esol iendo. La mo i ación as es e TFG es pe mi i a los diseñado es de juegos de es e ipo, dispone de un asis en e que en el caso de que los jugado es se queden a ascados, les ayude con algún ipo de pis a. La ayuda puede se p opo cionada median e un bo ón que, al 2 se pulsado, p opo ciona al usua io el siguien e paso que debe hace pa a llega a la solución. Pa a puzles más complejos, pod íamos eque i de o o ipo de ayudas como e emos más adelan e. Desde el pun o de is a de diseñado es de ideojuegos, que emos que puedan gene a puzles de mane a au omá ica pa a que puedan usa sus capacidades en o os aspec os del diseño de ideojuegos. Si deciden gene a los puzles ellos mismos, pod án comp oba si son esolubles median e es a he amien a. La gene ación y esolución de ompecabezas es un ema de in e és popula , y se e e lejado en el núme o de a ículos publicados en los úl imos años. Mencionamos y discu imos es os a ículos en el siguien e capi ulo. 1.2 Obje i os El obje i o p incipal de es e abajo de in de g ado es esol e y gene a cie os ipos de puzles o igina ios de la saga de ideojuegos El P o eso Lay on [3], median e écnicas de In eligencia A i icial en un iempo su icien emen e bueno como pa a pode da pis as o soluciones pa ciales al usua io en iempo eal. Pa a pode cumpli el obje i o p incipal, hemos enido que cumpli los siguien es subobje i os: • Modela algunos ipos de puzles de ejemplo. • Pa a cada ipo de puzle, de e mina qué algo i mo de búsqueda es el más óp imo pa a esol e lo. • De e mina los pa áme os ideales de los di e en es modelos pa a que el iempo de ejecución sea el mínimo y la solución sea óp ima. • Pode isualiza los p oblemas y soluciones median e una in e az g á ica. • Gene a los di e en es ipos de puzle con a iedad de di icul ades. 3 1.3 Plan de abajo Oc ub e 2023: • In es iga la exis encia de algo i mos de gene ación de puzles. No iemb e 2023: • In es iga los di e en es ipos de algo i mos de esolución basados en In eligencia A i icial. Diciemb e 2023: • Modela y esol e algunos ompecabezas median e búsqueda heu ís ica. Ene o 2024: • In es iga o os ipos de búsqueda pa a los p oblemas que no se pueden esol e de es a mane a. Feb e o 2024: • Aplica algo i mos gené icos pa a la esolución de uno de los ompecabezas. Ma zo 2024: • Te mina de modela y esol e odos los ompecabezas Ab il 2024: • Gene a median e la alea o iedad los di e en es puzles. 4 Mayo 2024: • Empeza a gene a una in e az g á ica. • Comenza a edac a la memo ia. Junio 2024: • Tes ea y a egla la esolución y la gene ación de los di e en es modelos. Julio 2024: • In es iga y encon a los alo es ideales de los pa áme os del algo i mo gené ico Agos o 2024: • Te mina la in e az g a ica • Saca g a icas de iempo de gene ación y esolución de los di e en es ompecabezas 5 Capí ulo 2 - Es ado de la cues ión La gene ación y esolución au omá ica de puzles o p oblemas ha ganado conside able a ención an o en la indus ia del ideojuego como en la in o má ica. Tal y como se decla a en el a ículo Au oma ic Gene a ion and Analysis o Physics-Based Puzzle Games [4], es o es debido a la en aja que p opo ciona en la apidez de gene ación de es e ipo de con enido. Además de ebaja los cos es de p oducción, in oduce una g an can idad de a iaciones en los juegos. La capacidad de gene a y esol e puzles de o ma au omá ica pe mi e la c eación de con enido adap a i o que puede ajus a se en iempo eal a las habilidades del jugado , p opo cionando una expe iencia de juego pe sonalizada. En es e capí ulo e isamos la li e a u a ac ual sob e los algo i mos y écnicas u ilizados an o en la gene ación como en la esolución de puzles. 2.1 Algo i mos de gene ación de puzles 2.1.1 Algo i mos basados en g a os En el a ículo: Au oma ed maze gene a ion and human in e ac ion [5], Fol in consigue gene a labe in os u ilizando algo i mos basados en g a os. Un labe in o es un pasa iempo que consis e en llega de un pun o o igen a un pun o des ino, su di icul ad eside en que con ienen caminos sin salida y gene almen e, un solo eco ido co ec o. Los algo i mos basados en g a os son aquellos que ienen como ipo de da os un g a o. Un g a o es á de inido po un conjun o de a is as, un conjun o de é ices y una ma iz de adyacencia. La ma iz de adyacencia de ine las conexiones en e los é ices median e las a is as. U iliza los siguien es algo i mos pa a gene a labe in os: 6 • Algo i mo de P im [6]: comienza desde un nodo a bi a io y se expande seleccionando las a is as de meno peso que conec an nodos incluidos con nodos no incluido. De es a mane a encuen a el á bol de expansión mínima en un g a o conec ado y no di igido. Un á bol de expansión mínima, conocido como Minimum Spanning T ee [7], es un subconjun o de un g a o que conec a odos los nodos con el meno cos o posible. • Algo i mo de K uskal [8]: comienza o denando odas las a is as po peso y luego, siemp e que no o men un ciclo, las a añadiendo al á bol. De es a mane a encuen a el á bol de expansión mínima. • Back acking [9]: es una écnica de esolución de p oblemas que cons uye soluciones inc emen ales y e ocede cuando se de e mina que la solución pa cial no puede lle a a una solución comple a álida, explo ando odas las posibles opciones. • Hun and Kill [10]: Es un algo i mo u ilizado en la gene ación de labe in os. Funciona al e nando en e dos ases: "caza ", donde busca una celda no isi ada, y "ma a ", donde ex iende un camino alea o iamen e desde esa celda has a que ya no puede con inua . • Bac e ial G ow h [5]: es e algo i mo simula el c ecimien o de bac e ias, expandiéndose desde un pun o inicial y eplicándose hacia á eas adyacen es, a menudo usado en la gene ación de labe in os o pa ones o gánicos. El análisis es muy exhaus i o, ya que analiza los iempos que a da en gene a los labe in os, el iempo que a da el usua io a llega a la solución, el iempo de la solución óp ima, el camino a la mejo solución, el núme o de mo imien os del usua io y el núme o mínimo de mo imien os pa a llega a la solución. Cabe señala la al a de es udio sob e la di icul ad de los labe in os gene ados. 7 2.1.2 Algo i mo de Tu e [11] En el a ículo Puzzle gene a o s and symme ic puzzle layou [12], log an p oduci de mane a au omá ica puzles cíclicos. Un p oblema es cíclico cuando u ilizamos un mismo conjun o de acciones que aplicamos a cada es ado pa a llega a la solución, que es a su ez el es ado inicial. Un ejemplo de un p oblema cíclico es el conocido cubo de Rubik. El algo i mo u ilizado pa a la gene ación es el algo i mo de Tu e [11]. Es e algo i mo basado en p incipios geomé icos ga an iza que un g a o se pueda dibuja de mane a que odas sus a is as se ep esen an como líneas ec as que no se c uzan, man eniendo así la sime ía y la cla idad del diseño del puzle. La in es igación incluye una implemen ación y explo a cómo se pueden c ea y modi ica los ni eles de di icul ad de los p oblemas. 2.1.3 Algo i mo Answe Se P og amming wi h P oposi ional Schema [13] El a ículo Gene a ing celula puzzles wi h logic p og ams [14] se cen a en la p oducción au omá ica de p oblemas celula es. Los p oblemas celula es son aquellos en los que los alo es de las celdas es án es ingidos po no mas que in oluc an g upos de celdas. Un ejemplo popula de es e ipo de puzles es el Sudoku. El algo i mo u ilizado pa a gene a p oblemas celula es es el de Answe Se P og amming wi h P oposi ional Schema [13], es e se basa en de ini p oblemas a a és de eglas lógicas y encon a espues as alidas que sa is agan las eglas, median e el plan eamien o decla a i o. Median e es e algo i mo se exp esan las es icciones del puzle y se gene an soluciones comple as de o ma alea o ia. Después, eniendo la solución, se u iliza el algo i mo de educción de pis as pa a de e mina el núme o mínimo de pis as necesa ias pa a que el p oblema sea esoluble y único. Siendo las pis as las celdas con alo es p ede inidos. 15 Capí ulo 3 - He amien as En es e capí ulo enume amos las he amien as que han sido indispensables pa a la ealización de es e abajo. Las he amien as que hemos u ilizado son lib e ías de código abie o de Py hon. El código de es e p oyec o ha sido ealizado u ilizando la e sión 3.8.10 de Py hon, puede que u ilizando e siones supe io es no cumpla con las uncionalidades aquí desc i as. 3.1 AIMA [26] El código de la lib e ía AIMA es á basado en el lib o de A i icial In elligence: A Mode n App oach [27] AIMA con iene las uncionalidades necesa ias pa a pode modela un p oblema y esol e lo u ilizando di e en es algo i mos de In eligencia A i icial, en e o as muchas. En nues o caso, lo hemos u ilizado pa a modela p oblemas y esol e los u ilizando en la g an mayo ía de casos, el algo i mo A*. Pa a modela los p oblemas hemos u ilizado la clase P oblem del módulo sea ch. 3.2 Numpy [28] Numpy es una lib e ía de Py hon u ilizada pa a la compu ación cien í ica. P opo ciona un ipo de a ay mul idimensional llamado nda ay. Es e ipo de da os acili a la manipulación de g andes olúmenes de da os numé icos. Incluye ope aciones ec o izadas y unciones ma emá icas y es adís icas. Hemos u ilizado la biblio eca Numpy pa a la manipulación de da os numé icos. 16 3.3 Tkin e [29] Tkin e es una lib e ía de Py hon u ilizada pa a gene a in e aces g á icas. Tkin e [29] pe mi e c ea odos los elemen os g á icos necesa ios pa a gene a una in e az g á ica accesible. Hemos u ilizado Tkin e pa a gene a la in e az g á ica del p oyec o. Con iene menús pa a selecciona que ipo de puzle que emos esol e o gene a , pe mi e al usua io in oduci los da os de los es ados iniciales y obje i os de los p oblemas de una mane a in e ac i a y pe mi e una isualización de los p oblemas gene ados au omá icamen e más amigable con el usua io. Asimismo, empaque a las excepciones que se puedan gene a en el código. 3.4 Time [30] Time es un módulo de Py hon que p opo ciona unciones co espondien es al iempo. Hemos u ilizado la lib e ía ime pa a medi los iempos de ejecución de los di e en es algo i mos de gene ación y esolución que hemos de inido. Las medidas de iempo se han omado en un o denado de sob emesa con encional con las siguien es ca ac e ís icas (Ve Tabla 1): P ocesado AMD Ryzen 7 2700X Eigh -Co e 3.7GHz RAM 16 GB Ta je a g á ica NVIDIA GeFo ce GTX 1050 Ti Sis ema Ope a i o Windows 10 P o 64bi s Tabla 1: Ca ac e ís icas PC 17 3.5 Ma plo lib [31] Ma plo lib es una lib e ía de Py hon que p opo ciona las he amien as de isualización de da os pa a el ecosis ema cien í ico de Py hon. Es a he amien a acili a la explo ación de da os in e ac i a, p oduce esul ados adecuados pa a publicaciones, p opo ciona una in e az g á ica simple, acili a los diag amas habi uales y posibili a isualizaciones complejas. Hemos u ilizado es a he amien a pa a isualiza los iempos de gene ación y esolución de los di e en es modelos, en e o as. 19 Capí ulo 4 - Modelado de p oblemas De odos los p oblemas p esen es en el Doc o Lay on, hemos seleccionado algunos de ellos, en o den c ecien e de complejidad, pa a p oba nues os algo i mos. A con inuación, enume amos los di e en es puzles implemen ados y que algo i mos y heu ís icas hemos u ilizado pa a esol e los. 4.1 Puzle 1: Ja as (Wa e Pi che s) El puzle de las ja as consis e en que hay es ja as de las que sabemos la capacidad máxima de líquido que pueden con ene . Se nos da un es ado inicial y un es ado obje i o, en los que se de e mina la can idad de líquido que iene cada ja a. El juego consis e en llega del es ado inicial al es ado obje i o median e las acciones de mo e el líquido con enido en las di e en es ja as de una a o a. Es e ompecabezas es á incluido en el juego P o esso Lay on and he Cu ious Village [32]. Figu a 1: Wa e Pi che s [43] 20 4.1.1 Algo i mo u ilizado Hemos decidido u iliza el algo i mo de búsqueda heu ís ica A* po que la heu ís ica de inida es admisible y po an o el algo i mo encuen a la solución si exis e. Además, es e algo i mo nos p opo ciona una lis a de las acciones que ha omado pa a llega del es ado inicial al obje i o, po lo que podemos i dando pis as al usua io en iempo eal. 4.1.2 Modelado Pa a modela es e ipo de puzle hemos c eado una ins ancia de la clase P oblem de la lib e ía AIMA [26]. De inimos el nodo es ado como una upla de es posiciones en la que el alo de la p ime a posición es la can idad de líquido que con iene la p ime a ja a, el alo de la segunda posición es la can idad que con iene la segunda ja a y el alo de la e ce a posición es la can idad que con iene la e ce a ja a. Inicializamos la ins ancia de la clase P oblem pasándole po pa áme os el es ado inicial, el es ado obje i o y una upla que indica la can idad máxima que puede con ene cada ja a. Pa a pode u iliza la clase P oblem enemos que de ini ambién las unciones de acciones, esul ados y heu ís ica. 4.1.2.1 Acciones En la unción de acciones de inimos odas las acciones que se pueden oma pa a un es ado. En es e caso, comp obamos pa a cada ja a “a” si con iene líquido, si es así, comp obamos si el es o de las ja as “b” es án al máximo de su capacidad, si no es así añadi emos a la lis a de acciones las acciones de: e e con enido de la ja a “a” en la ja a “b”, pa a odas las combinaciones de ja as que cumplan lo mencionado. 21 4.1.2.2 Resul ados En la unción de esul ados de inimos el es ado que p oduce el aplica las di e en es acciones. Teniendo en cuen a que las acciones son, “ e e el con enido de la ja a “a” en la ja a “b”, calcula emos el mínimo en e el con enido de la ja a “a” y el con enido que cabe en la ja a “b”, eniendo en cuen a su capacidad máxima y la can idad que iene ac ualmen e. Es e mínimo que hemos calculado es la can idad de líquido que se á e ido de la ja a “a” a la ja a “b”. De es a mane a nos asegu amos de que las ja as no desbo den. La unción de esul ado de uel e una upla es ado con los alo es de can idades de líquidos ac ualizados. 4.1.2.3 Heu ís ica Hemos de e minado la heu ís ica como la di e encia absolu a mínima de la can idad de líquido en las ja as en el es ado ac ual espec o al es ado inal. Ejemplo: Tenemos 3 ja as con capacidades máximas de 16,9 y 7 li os, el es ado obje i o es que las p ime as dos ja as con engan cada una exac amen e 8 li os, y el es ado inicial es que la p ime a ja a es á o almen e llena. El alo de la heu ís ica la calculamos de la siguien e mane a: h’ (16,0,0) = min (|16-8|, |0-8|, |0-0|) = 8 La heu ís ica es admisible po que subes ima o iguala el cos e eal desde el es ado ac ual al es ado obje i o. 22 4.1.3 Gene ación Teniendo en cuen a que en los puzles de es e ipo el es ado inicial consis e siemp e en que la ja a 1 con iene su capacidad máxima y las o as dos ja as es án acías, Bas a con gene a núme os alea o ios pa a los alo es de capacidad máxima de cada ja a y después gene a alo es alea o ios desde ce o a la capacidad máxima pa a los alo es del es ado inal de cada ja a. Hemos que ido añadi ambién una a iable de di icul ad, el usua io puede selecciona qué di icul ad iene el p oblema gene ado. La di icul ad del p oblema es á de e minada po el núme o de acciones que hay del es ado inicial al obje i o. Ve Tabla 2. Di icul ad Núme o de pasos has a la solución Fácil 0-7 In e medio 8-14 Di ícil 15-19 Muy di ícil 20-24 Tabla 2: Di icul ades gene ación Ja as 4.1.4 Tiempos En nues o abajo, el iempo que a da el algo i mo en gene a y esol e puzles es impo an e, ya que que emos que el usua io in e ac úe a iempo eal. Es as medidas de iempo mues an ambién, lo bien que hemos modelado el p oblema y de inido la unción heu ís ica. En la Figu a 2, podemos obse a que el iempo en el que gene amos 100 puzles alidos del ipo Ja a es, en el caso peo , de algo más de 1 segundo. 23 Po o o lado, podemos obse a en la Figu a 3, que el iempo de esolución de 100 puzles de ipo Ja a es, en el caso peo , de 0’014 segundos. Es e iempo es lo su icien emen e bueno como pa a pode da al usua io espues a en iempo eal. Figu a 2: Tiempo gene ación Ja as Figu a 3: Tiempo esolución Ja as 30 Figu a 9: Tiempo gene ación 8/16-puzle Figu a 10: Tiempo esolución 8/16-puzle 31 4.2.5 In e az g a ica La in e az g á ica pe mi e al usua io an o esol e como gene a puzles de es e ipo (Ve Figu a 11). Si el usua io quie e esol e un puzle end á que ing esa el es ado inicial y el es ado obje i o, después p ocede á a pulsa en el bo ón de esol e y la in e az mos a a el siguien e paso a la solución jun o con el núme o de pasos que hace al a da pa a llega a ella (Ve Figu a 12). También puede pedi la siguien e pis a has a llega a la solución. Figu a 11: GUI menú 8/16-Puzle Figu a 12: GUI esol e 8/16-Puzle 32 Po o o lado, si el usua io desea gene a es e ipo de p oblemas, selecciona á una di icul ad y la in e az le mos a á an o el es ado inicial como el es ado obje i o del p oblema gene ado. Si escoge las opciones ácil o in e medio, la in e az gene a un puzle-8 en pan alla (Ve Figu a 13), si escoge di ícil o muy di ícil la in e az gene a un puzle-16 (Ve Figu a 14). Figu a 13: GUI gene a 8-Puzle 33 Figu a 14: GUI gene a 16-Puzle 34 4.3 Puzle 4: Flip panels: S omp on i ! Es e ipo de puzle consis e en: dado un able o donde las di e en es posiciones pueden oma dos alo es, dos colo es, consegui o ma la con igu ación de colo es que se da en el es ado obje i o median e la acción de pisa casillas. Al pisa una casilla cambian de colo sus cua o casillas adyacen es y la misma. Es e ompecabezas es á incluido en el juego P o esso Lay on s. Phoenix W igh : Ace A o ney [33] Figu a 15: S omp on i ! [34] 4.3.1 Algo i mo u ilizado Hemos decidido u iliza el algo i mo de búsqueda heu ís ica A* po las mismas azones que los dos ompecabezas an e io es. 4.3.2 Modelado Pa a modela es e ipo de puzle hemos c eado una ins ancia de la clase P oblem de la lib e ía AIMA. De inimos el nodo es ado como un a ay del amaño del able o, los alo es que pueden oma las posiciones del a ay son 0 pa a el colo blanco y 1 pa a el colo neg o. Inicializamos la ins ancia de la clase P oblem pasándole po pa áme os el es ado inicial y el es ado obje i o. 35 Pa a pode u iliza la clase P oblem enemos que de ini ambién las unciones de acciones, esul ados y heu ís ica. 4.3.2.1 Acciones Las acciones consis en en pisa cada posición del able o. 4.3.2.2 Resul ados Los esul ados de las acciones consis en en cambia el alo de las casillas adyacen es a la pisada, si son blancas se ac ualizan a neg o y ice e sa. Las casillas que cambian su alo son la casillas supe io , in e io , de echa e izquie da de la pisada, siemp e que exis an, cumpliendo las es icciones del amaño del able o. 4.3.2.3 Heu ís ica Hemos de inido la heu ís ica como la suma de las piezas que ienen un colo di e en e al del es ado obje i o. 4.3.3 Gene ación Pa a la gene ación de es e puzle, el usua io debe á in oduci una di icul ad. Dependiendo de la di icul ad seleccionada gene amos un able o de un amaño especi ico, en el alea o iamen e asignamos los colo es blanco y neg o a las celdas. Es e able o gene ado se á el es ado inicial del p oblema. Pa a gene a el es ado obje i o aplicamos alea o iamen e un núme o de acciones de la lis a de posibles acciones has a gene a lo. La di icul ad es á de e minada po el núme o de pasos necesa io pa a llega a la solución y el amaño del able o. Ve Tabla 4. 36 Di icul ad Núme o de pasos has a la solución Tamaño del able o Fácil 1-5 3x3 In e medio 6-20 3x3 Di ícil 1-5 4x4 Muy di ícil 6-20 4x4 Tabla 4: Di icul ades gene ación S omp 4.3.4 Tiempos En el caso de es e p oblema, emos que a da más que el p oblema de las ja as en gene a los p oblemas. Aunque sea bas an e supe io nos pa ece un iempo su icien emen e bueno como pa a da espues a en iempo eal al usua io. Ve Figu a 16. Figu a 16: Tiempo gene a S omp 37 En el caso de esol e los p oblemas de es e ipo, podemos obse a que lo hace muy ápido (Ve Figu a 17), es o quie e deci que la heu ís ica que hemos aplicado es admisible. 4.3.5 In e az g á ica El usua io puede escoge si esol e o gene a un puzle de es e ipo en el menú p incipal de la in e az g á ica que hemos gene ado. Ve Figu a 18. Figu a 17: Tiempo esol e S omp Figu a 18: GUI menú S omp 38 Si el usua io escoge esol e el puzle, la in e az pedi á que in oduzca el núme o de ilas y columnas del able o. Se gene an dos able os del amaño indicado po el núme o de ilas y columnas, una pa a desc ibi el es ado inicial y o a pa a desc ibi el es ado obje i o. El usua io desc ibe el es ado pulsando en las di e en es celdas del able o, al pulsa sob e ellas se cambia de colo . Una ez haya e minado pulsa á el bo ón de esol e y se gene a á la solución con la opción de enseña los siguien es pasos. Ve Figu a 19. Po o o lado, si el usua io quie e gene a un puzle de es e ipo, debe selecciona una di icul ad y pulsa en gene a puzle. Se dibuja en pan alla, el es ado inicial y el es ado obje i o del p oblema gene ado. Ve Figu a 20 y Figu a 21. Figu a 19: GUI esol e S omp 39 Figu a 20: GUI gene ación S omp 1 Figu a 21: GUI gene ación S omp 2 46 Po o o lado, si el usua io quie e gene a es e ipo de ompecabezas, debe á selecciona una di icul ad y la in e az mos a á po pan alla el puzle gene ado. Ve Figu a 28 y Figu a 29. Figu a 27: GUI esol e Pelo a 2 Figu a 28: GUI gene a Pelo a 1 47 Figu a 29: GUI gene a Pelo a 2 48 4.5 Puzle 5: Ha g am Es e ipo de puzle consis e en, dado un able o con posiciones acías y posiciones en las que no se pueden pone piezas, y una lis a de piezas de di e en es amaños y o mas, llena el able o u ilizando odas las piezas eniendo en cuen a que las piezas se pueden o a y ol ea . Es e ompecabezas es á incluido en el juego P o esso Lay on and he Unwound Fu u e [36] Figu a 30: Ha g am [37] 4.5.1 Algo i mo u ilizado A la ho a de decidi qué algo i mo u iliza pa a encon a solución a es e ipo de p oblema conside amos u iliza el algo i mo de búsqueda A* pe o decidimos que no e a una buena opción po que el núme o de piezas y las di e en es o aciones ha ían que el espacio de búsqueda uese demasiado g ande como pa a pode esol e lo usando es e algo i mo. Po lo que decidimos que el en oque ap opiado e a usa algo i mos gené icos [25]. Aunque exis en lib e ías de Py hon que implemen an el algo i mo gené ico, decidimos implemen a lo noso os mismos pa a ene más con ol sob e el modelado de los indi iduos, gene ación de la población y los algo i mos de c uce, mu ación y selección u ilizados. El esquema que sigue un algo i mo gené ico es el siguien e: 49 Gene a alea o iamen e una población inicial de amaño X • Calcula la alo ación de cada indi iduo median e la unción i ness • Selecciona Y indi iduos median e la selección po o neo • Aplica el ope ado gené ico de c uce, eniendo en cuen a la p obabilidad de c uce • Aplica el ope ado gené ico de mu ación, eniendo en cuen a la p obabilidad de mu ación Se cicla sob e los pun os supe io es has a que se encuen a una solución, has a que se supe a el núme o de gene aciones p e iamen e de inido o has a que se supe a un iempo de e minado. El ipo de solución que nos b inda un algo i mo gené ico es la solución o al del p oblema, no nos da los pasos in e medios pa a llega a la solución. Es o pod ía supone un p oblema pa a noso os, ya que que emos gene a pis as o pasos pa a el usua io. Hemos decidido que damos como pis a la mane a co ec a de coloca una pieza conc e a. 4.5.2 Modelado Pa a empeza , hemos de inido un a ay que desc ibe el able o, donde las posiciones no álidas oman alo -1 y las posiciones a llena oman alo 0, y una lis a de a ays, que consis e en la lis a de piezas disponibles. Hemos especi icado ambién las o aciones que puede oma una pieza pueden oma alo es del 0 al 7, eniendo es os alo es el siguien e signi icado: • 0: la pieza al y como iene de inida • 1: La pieza gi ada 90º • 2: La pieza gi ada 180º 50 • 3: La pieza gi ada 270º • 4: La pieza ol eada ho izon almen e • 5: La pieza gi ada 90º y ol eada ho izon almen e • 6: La pieza gi ada 180º y ol eada ho izon almen e • 7: La pieza gi ada 270º y ol eada ho izon almen e Pa a cie as piezas algunas o aciones esul an en la misma con igu ación de la pieza, es o no gene a ningún p oblema. Hemos de inido los indi iduos como una lis a de longi ud igual al núme o de piezas a coloca , donde pa a cada pieza, gene amos una lis a que con iene las coo denadas donde se posiciona la pieza y la o ación que oma. 4.5.2.1 Gene ación de la población Al gene a una población, c eamos muchos indi iduos no álidos, sea po que dos piezas se pisan en e ellas o sea po que hay piezas colocadas en posiciones no álidas. Pa a no desca a del odo es os indi iduos, hemos decidido ac ualiza las coo denadas de la pieza a [-1,-1] y deci que no es án colocadas. De mane a que, gene amos alea o iamen e la población, dando alo es a las coo denadas y o aciones de las piezas, después la pasamos po una unción de alidez pa a que ma que las piezas que no se pueden posiciona como no posicionadas. 4.5.2.2 Función i ness La unción de e aluación es ablece una medida numé ica de la bondad de la solución. En el caso de es e p oblema la hemos especi icado como el núme o de casillas del able o que es án ocupadas po piezas di idido en e el núme o de casillas del 51 able o. De es a mane a, damos p io idad a los indi iduos que más piezas del puzle engan colocadas. 4.5.2.3 Selección de indi iduos Hemos op ado po u iliza el mé odo de selección po o neo, conocido como Tou namen Selec ion [38], de es a mane a escogemos los mejo es candida os pa a el c uce de indi iduos. En la selección po o neo escogemos subg upos de amaño p de indi iduos de la población. Los miemb os de cada subg upo se some en a la unción de e aluación pa a e cuál de ellos es el mejo , se elige a un indi iduo de cada subg upo pa a el c uce. Va iando el núme o p de indi iduos que pa icipan en cada o neo se modi ica la p esión de selección. Si p es al o hay muchos indi iduos en cada o neo y la p esión de selección es al a, los peo es indi iduos ienen pocas opo unidades y se cen a la búsqueda de las soluciones en un en o no p óximo a las mejo es soluciones ac uales. Si p es bajo el amaño del o neo es educido y la p esión de selección disminuye, los peo es indi iduos ienen más opo unidades. Se deja el camino abie o pa a la explo ación de nue as egiones del espacio de búsqueda. 4.5.2.4 C uce Una ez seleccionados los indi iduos, és os son ecombinados median e algo i mos de c uce pa a p oduci la descendencia que se inse a á en la siguien e gene ación. Hemos esuel o el c uce en c uce de un pun o, conocido como SPX (Single Poin C osso e ) [39], que consis e en co a los indi iduos po un pun o escogido alea o iamen e, di e enciando así la cabeza y la cola, después in e cambiamos las 52 colas de los dos indi iduos a c uza gene ando de es a mane a dos descendien es que con ienen in o mación de ambos pad es. 4.5.2.5 Mu ación Los algo i mos de mu ación consis en en modi ica unos genes del c omosoma con una p obabilidad (> 10%) pa a ga an iza que ningún pun o del espacio de búsqueda enga una p obabilidad nula de se examinado. Pa a consegui mejo es esul ados hemos decidido u iliza una mu ación di igida. La mu ación di igida in en a solo mu a las pa es de los indi iduos que ienen la capacidad de mejo a la solución. En es e caso calculamos pa a cada pieza la con ibución que hacen al i ness gene al, pa a que las mu aciones se en oquen en las zonas del able o que ienen po encial de mejo a . Mu amos los indi iduos que ienen impac o nega i o. La mu ación de un indi iduo consis e en cambia los alo es del indi iduo alea o iamen e. Hemos u ilizado es a écnica pa a no cae en mínimos locales. Los mínimos locales ocu en cuando los indi iduos de nues a población son pa ecidos en e ellos y no ocupan odo el espacio de soluciones, llegando de es a mane a a la mejo solución den o de un segmen o del espacio de soluciones, pe o que no son la solución óp ima. Median e la mu ación gene amos indi iduos más di e sos explo ando el espacio de soluciones de o ma más amplia, consiguiendo de es a mane a llega a soluciones op imas. Además, la mu ación ayuda a man ene la di e sidad gené ica lo que con ibuye a encon a nue as soluciones. 53 4.5.3 Pa áme os Al algo i mo gené ico diseñado, debemos in oduci le los alo es de los pa áme os de la p obabilidad de c uce, p obabilidad de mu ación, el núme o de gene aciones, el amaño del o neo y el amaño de la población. Pa a que nues o algo i mo gene e en el mínimo iempo posible las mejo es soluciones, amos a busca el alo op imo de es os pa áme os. 4.5.3.1 Núme o de gene aciones El núme o de gene aciones es el pa áme o que de e mina el núme o de eces que e oluciona el algo i mo gené ico. Un núme o de gene aciones mayo puede p opo ciona más y mejo es esul ados, aumen ando el iempo de ejecución. Vemos que el núme o de gene aciones no a ec a en el esul ado de la unción i ness del mejo indi iduo (Ve Figu a 31). Respec o al iempo de ejecución emos en la Figu a 32, que es meno con el alo de 50. Como que emos que el usua io ob enga la espues a en el mínimo iempo posible, el alo que amos a da al núme o de gene aciones es de 50. Figu a 31: Fi ness Núme o de gene aciones 54 Figu a 32: Tiempo ejecución núme o de gene aciones 4.5.3.2 Tamaño de la población El amaño de la población es el pa áme o que de e mina cuan os indi iduos hay en cada gene ación. Un amaño de la población mayo ole a una mayo di e sidad de los indi iduos, educiendo de es a mane a la posibilidad de cae en mínimos locales, y aumen ando el iempo de ejecución po gene ación. En nues o caso emos que el amaño de la población no a ec a en el alo de la unción i ness (Ve Figu a 33). Respec o al iempo de ejecución emos que cuan o mayo es la población, meno es el iempo (Ve Figu a 34). Hemos dicho que, cuan o mayo es el amaño de la población, mayo es el iempo de ejecución po gene ación, pe o en nues o caso, al gene a una población mayo , enemos mayo di e sidad gené ica y podemos llega a la solución con menos gene aciones. Es deci , el iempo de ejecución po gene ación es mayo , pe o hacen al a menos gene aciones pa a llega a la solución po lo que el iempo o al es meno . Como el amaño de la población no a ec a a la calidad de la solución y cuan o mayo es el amaño de la población meno es el iempo de ejecución, decidimos da el alo de 1500 al amaño de la población. 55 Figu a 33: Fi ness po amaño de población Figu a 34: Tiempo po amaño de población 62 Si el usua io decide que quie e esol e es e ipo de puzle, pulsa en el menú del puzle en esol e . La in e az pide que el usua io p opo ciones el núme o de ilas y columnas del able o. El usua io en onces debe desc ibi el able o, poniendo las posiciones no alidas en neg o, las acías en blanco y si hay alguna pieza colocada pin a la de o o colo . Es o se hace como hemos is o en an e io es p oblemas, pulsando las celdas del able o. Po ejemplo, en la Figu a 43, emos que hay posiciones no álidas y hay una pieza ya colocada en el puzle. Figu a 43:GUI esol e Ha g am Cuando el usua io pulsa el bo ón de gua da able o, la in e az pedi á el núme o de piezas a coloca . Pa a cada una de las piezas la in e az pide el núme o de ilas y de columnas que ocupan y hab á que dibuja las, poniendo en neg o las posiciones no alidas. Ve Figu a 44. 63 Figu a 44: GUI esol e Ha g am piezas Una ez el usua io ha desc i o odas las piezas, pulsa en esol e pa a que la in e az le mues e el esul ado. 64 Capí ulo 5 - Conclusión y abajo u u o Como conclusión, hemos conseguido modela , esol e y gene a cinco ipos de puzle de mane a e icaz. Los iempos de esolución son lo bas an e buenos como pa a conside a se en iempo eal. Además, hemos c eado una in e az g á ica sencilla pa a pode p oba es os p oblemas con di e en es ni eles de di icul ad y e como los algo i mos esuel en los puzles y p opo cionan pis as a los usua ios. Po o o lado, hay a ios aspec os del p oyec o que no hemos podido implemen a po al a de iempo. A con inuación, enume amos en o den de p io idad las mejo as que nos gus a ía habe añadido en es e p oyec o: • Respec o a la gene ación de los di e en es p oblemas, los algo i mos que u ilizamos no son óp imos, ya que es án condicionados po la alea o iedad. En los a ículos in es igados sob e la gene ación, u ilizaban algo i mos más p ecisos. Dejamos pa a abajo u u o la in es igación e implemen ación de algo i mos más in o mados pa a la gene ación de los ompecabezas in es igados. • Siguiendo con la gene ación, hemos de inido las di icul ades de los di e en es puzles con nues o p opio c i e io, cada usua io debe ía se capaz de de ini la di icul ad. Po eso, pensamos que se ía con enien e que el usua io pueda escoge el núme o de pasos que se ienen que hace pa a llega a la solución, el amaño del able o y el núme o de ichas del p oblema que gene amos. • Acabando con la gene ación, no hemos podido gene a el ipo de puzle de Ha g am, lo dejamos como abajo u u o. • Respec o a los iempos de esolución de los di e en es p oblemas, opinamos que casi odos son óp imos, el único que di ie e de la de inición de espues a en iempo eal es el ompecabezas de Ha g am. Nos gus a ía mejo a el iempo de esolución del algo i mo gené ico sin sac i ica los alo es adecuados de las soluciones. También, como comen amos en el apa ado de iempo, se puede op a en el juego po inclui un se de puzles p e iamen e esuel os pa a consegui ene la pis a en iempo eal o lanza el cálculo en 65 pa alelo mien as el usua io obse a el puzle, pa a e i a el iempo de espe a de 2 minu os en encon a la solución. • Con elación a los p oblemas modelados, son unos pocos en e cien os, nos ag ada ía modela más ipos de p oblemas o de alguna mane a uni ica la esolución de muchos ipos de p oblema, sin ene que aplica di e en es heu ís icas. • En lo que co esponde a la in e az g á ica, quisié amos hace la más amigable con el usua io. Sob e odo, en los aspec os de in oduci el es ado en el que se encuen a el p oblema. • Po o o lado hubiese sido de g an in e és in es iga el uso de edes neu onales pa a las di e en es aplicaciones de las heu ís icas. Tal y como se comen a en el a ículo mencionado en el es ado del a e. • Pa a inaliza , nos hubiese gus ado usa a ian es de A* más op imas como las desc i as en el es ado del a e, pa a aquellos puzles donde A* no ha podido esol e los en un iempo sa is ac o io y hemos u ilizado algo i mos de búsqueda local. Es o es debido a que A* nos puede p opo ciona la secuencia de pasos, pe o o os algo i mos como el algo i mo gené ico solo nos p opo ciona la solución inal, lo que di icul a la gene ación de pis as pa a el usua io. 66 In oduc ion Mo i a ion A i icial In elligence ield has a ac ed signi ican a en ion o he las ew yea s, mos ly because o he popula iza ion and public access o AI based cha sys ems as Cha GPT o mul imedia con en gene a o s as S able Di usion and So a. As people ha e become mo e amilia wi h hese ools, hey ha e become mo e in e es ed in how hey wo k and o wha o he sec o s may be applied. Howe e , he e is s ill oom o he use o classical symbolic AI in mul iple applica ions. Fo example, Cha GPT has oubles doing complex ma hema ical calcula ions [1], u he mo e, i is no e icien o op imal puzzle sol ing, such as he 8-Puzzle and he Rubik’s cube. In pa icula , in a ecen s udy [2] LLMs we e con igu ed speci ically o puzzle Sol ing, achie ing a 93.2% success in he 8-Puzzle, when A* algo i hm is known o sol e i in Li le ime wi h a 100% success a e. Despi e he ad an ages achie ed wi h he use o LLMs, in his ype o p oblems i s ill is mo e con enien o u n o he classical symbolic AI. In his inal p ojec we wan o sol e and gene a e puzzles om he well-known ideo game saga P o esso Lay on [3], ia he use o heu is ic sea ch algo i hms. The ideo game saga o P o esso Lay on ocuses on Sol ing mys e ies; o mo e o wa d in he s o y, we ha e o sol e a mul i ude o puzzles o all kind and di icul ies. All his enli ened by a s o y ha gi es consis ency o he succession o puzzles ha we sol e. The Mo i a ion behind his P ojec is o allow puzzle game de elope s o ha e an assis an ha in he case ha playe s ge s uck, help hem wi h some kind o hin . This help can be p opo ioned h ough a bu on ha when p essed, p o ides he use wi h he nex s ep i 67 mus do o ge o he solu ion. Fo mo e complex puzzles, we may equi e o he ypes o aids as we will see below. F om game de elope s’ poin o iew, we wan o allow hem Gene a ing puzzles au oma ically, so ha hey can use hei capaci ies in o he aspec s o game designing. I hey decide hey wan o gene a e hei own puzzles, hey can check i he puzzles a e sol able h ough his ool. Puzzle gene a ion and Sol ing is a opic o popula in e es , which is e lec ed in he numbe o a icles published in ecen yea s. We men ion and discuss hese a icles in he nex chap e . Goals The main objec i e o his p ojec is o sol e and gene a e ce ain puzzle ypes om he ideo game saga P o esso Lay on h ough A i icial In elligence echniques in a Good enough ime o be able o gi e clues o pa ial solu ions o he use in eal ime. In o de o achie e he main goal, we had o achie e he ollowing subobjec i es: • Model some ypes o sample puzzles. • Fo each ype o puzzles, de e mine which sea ch algo i hm is he mos op imum one o esol e i . • Es ablish he ideal pa ame e s o he di e en models so ha he execu ion ime is minimum, and he solu ion is op imum. • Being able o display p oblems and solu ions ia a g aphic in e ace. • Gene a e a a ie y o puzzles wi h di e en di icul ies. 68 Wo k plan Oc obe 2023: • S udy he exis ence o puzzle gene a ion algo i hms. No embe 2023: • In es iga e se e al ypes o AI based p oblem Sol ing algo i hms. Decembe 2023: • Model and sol e some puzzles h ough heu is ic sea ch. Janua y 2024: • S udy o he ypes o sea ches o puzzles ha canno be esol ed h ough heu is ic sea ch. Feb ua y 2024: • Apply gene ic algo i hms o esol ing one o he puzzles. Ma ch 2024: • Finish modeling and sol ing all he puzzles. Ap il 2024: • Gene a e ia andomiza ion he di e se ypes o puzzles. 69 May 2024: • S a o gene a e a g aphic in e ace. • S a o d a he disse a ion. June 2024: • Tes ing and ixing he esolu ion and gene a ion o he di e en models. July 2024: • S udy he ideal alues o he gene ic algo i hm pa ame e s. Augus 2024: • Finish he g aphical in e ace. • Ge plo s o he execu ion ime so he solu ion and gene a ion o he di e en puzzles modeled. 71 Conclusions and u u e wo k To conclude, we ha e managed o model, esol e, and gene a e i e ypes o puzzles e icien ly. Mo eo e , he sol ing imes a e Good enough o be conside ed eal- ime. In addi ion, we ha e c ea ed a simple g aphical in e ace o be able o es hese p oblems a di e en di icul y le els and see how he algo i hms sol e he puzzles and p o ide hin s o he use s. On he o he hand, he e a e a ious aspec s o he p ojec we ha e no been able o implemen . Below, we lis in o de o p io i y he imp o emen s we would like o ha e added o he p ojec : • Rega ding he gene a ion o he p oblems, he algo i hms we ha e used a e no op imal due o hei eliance on andomness. On he a icles esea ched abou gene a ion, hey used mo e p ecise algo i hms. We lea e o u u e wo k he in es iga ion and implemen a ion o mo e in o med algo i hms o he gene a ion o he in es iga ed puzzles. • While on he subjec o gene a ion, we ha e de ined he di icul ies o he di e en puzzles wi h ou own c i e ion, each use should be able o de ine he di icul y. The e o e, we hough i would be con enien ha he use can choose he numbe o s eps ha ha e o be done o each he solu ion, he size o he boa d and he numbe o iles o he p oblem gene a ed. • Pu ing an end o he subjec o gene a ion, we ha e no been able o gene a e de puzzle called Ha g am, we lea e i as u u e wo k. • Conce ning esolu ion imes o he di e en p oblems, we hink all o hem a e op imal, he only one ha di e s om he de ini ion o eal- ime Answe is he one o sol ing he Ha g am puzzle. We would like o imp o e he sol ing ime o he gene ic algo i hm wi hou sac i icing he adequa e solu ion alues. Also, as men ioned, he de elope could choose o include a se o p e iously sol ed puzzles in he game o ge he clue in eal ime o o launch he