{"id":60445,"date":"2023-07-17T10:12:54","date_gmt":"2023-07-17T16:12:54","guid":{"rendered":"http:\/\/mickyandoniehn.com\/radio\/2023\/07\/17\/el-tetris-lleva-decadas-entreteniendo-a-millones-de-personas-el-mit-acaba-de-darle-carpetazo-matematicamente\/"},"modified":"2023-07-17T10:12:54","modified_gmt":"2023-07-17T16:12:54","slug":"el-tetris-lleva-decadas-entreteniendo-a-millones-de-personas-el-mit-acaba-de-darle-carpetazo-matematicamente","status":"publish","type":"post","link":"https:\/\/mickyandoniehn.com\/radio\/2023\/07\/17\/el-tetris-lleva-decadas-entreteniendo-a-millones-de-personas-el-mit-acaba-de-darle-carpetazo-matematicamente\/","title":{"rendered":"El Tetris lleva d\u00e9cadas entreteniendo a millones de personas. El MIT acaba de darle carpetazo (matem\u00e1ticamente)"},"content":{"rendered":"<\/p>\n<p>Ni las horas de carretera, ni las colas para comprar un refresco, ni siquiera las peleas para hacerse con una parcelita de arena en la que plantar la sombrilla y extender la toalla. Si hay un desaf\u00edo realmente duro en las escapadas de verano a la playa es apa\u00f1\u00e1rselas para que la nevera, palas, cubos y dem\u00e1s equipaje veraniego entren en el maletero del coche. O as\u00ed era hasta ahora. En el MIT acaban de dar con\u00a0<a href=\"https:\/\/news.mit.edu\/2023\/chore-packing-just-got-faster-and-easier-0706\">una f\u00f3rmula<\/a>\u00a0para llenar tu maletero o cualquier otro lugar, por m\u00e1s reducido que sea su espacio y voluminosa la carga, con la pericia de un maestro del Tetris.<\/p>\n<p>De juego, eso s\u00ed, tiene muy poco.<\/p>\n<p><strong>\u00bfC\u00f3mo puedo meter esto ah\u00ed?<\/strong>\u00a0La pregunta quiz\u00e1s parezca simple. La respuesta, no. Lo de buscar la forma m\u00e1s eficiente de almacenar objetos en un espacio limitado es algo que te planteas t\u00fa al trastear con los cajones de la cocina, el frutero cada vez que apila manzanas y naranjas y los domingueros cuando tienen que llenar sus mochilas, pero eso no significa que sea una cuesti\u00f3n sencilla. Ni mucho menos. Hace ya bastante tiempo, en 1611, el mism\u00edsimo\u00a0<a href=\"https:\/\/es.wikipedia.org\/wiki\/Johannes_Kepler\">Johannes Kepler<\/a>\u00a0le daba vueltas a cu\u00e1l era la forma m\u00e1s inteligente de apilar bolas de ca\u00f1\u00f3n.<\/p>\n<p>Han pasado de aquello m\u00e1s de cuatro siglos y si bien ya sabemos c\u00f3mo agrupar esferas de forma uniforme, lo de apilar de manera \u00f3ptima objetos tridimensionales de diferentes tama\u00f1os y formas sigue siendo todo un reto. Tanto, de hecho, que el MIT recuerda que en teor\u00eda de la complejidad computacional se considera un\u00a0<a href=\"https:\/\/es.wikipedia.org\/wiki\/NP-hard\">\u00abNP-hard\u00bb<\/a>, es decir, un problema que no podemos resolver ni siquiera de forma aproximada sin pasarnos a\u00f1os o d\u00e9cadas haciendo c\u00e1lculos.<\/p>\n<div class=\"article-asset-image article-asset-normal article-asset-center\">\n<div class=\"asset-content\">\n<div class=\"base-wrapper-image\"><\/div>\n<\/div>\n<\/div>\n<p><strong>\u00bfY c\u00f3mo solucionarlo?<\/strong>\u00a0Esa es la pregunta que se han hecho un grupo de investigadores del MIT e\u00a0<a href=\"https:\/\/inkbit3d.com\/\">Inkbit<\/a>, una compa\u00f1\u00eda de Massachusetts que trabaja con\u00a0<a href=\"https:\/\/www.ibm.com\/es-es\/topics\/computer-vision#:~:text=La%20visi%C3%B3n%20artificial%20es%20un,en%20funci%C3%B3n%20de%20esa%20informaci%C3%B3n.\">visi\u00f3n artificial<\/a>. Para solucionarlo desarrollaron un m\u00e9todo computacional, una t\u00e9cnica que han bautizado \u00abSSP\u00bb \u2014del ingl\u00e9s \u00abDense, intelocking-free and Scalable Spectral Packing\u00bb\u2014 y prev\u00e9n presentar el mes que viene durante la conferencia internacional\u00a0<a href=\"https:\/\/s2023.siggraph.org\/\">SIGGRAPH 2023<\/a>. Antes y a modo de anticipo han preparado un art\u00edculo que puede consultarse ya a trav\u00e9s de\u00a0<a href=\"https:\/\/inkbit3d.com\/wp-content\/uploads\/2023\/06\/spectralPacking_optimized.pdf\">las webs de Inkbit<\/a>\u00a0y\u00a0<a href=\"https:\/\/news.mit.edu\/2023\/chore-packing-just-got-faster-and-easier-0706\">el MIT<\/a>.<\/p>\n<p><strong>\u00abEs como el Tetris\u00bb.\u00a0<\/strong>La expresi\u00f3n es de\u00a0<a href=\"https:\/\/cdfg.csail.mit.edu\/wojciech\">Wojciech Matusik<\/a>, profesor del MIT y cofundador de Inkbit, y capta bastante bien la filosof\u00eda del m\u00e9todo que acaban de desarrollar. El \u00abSSP\u00bb trabaja b\u00e1sicamente con una lista de objetos tridimensionales y un contenedor que se encarga de dividir en\u00a0<a href=\"https:\/\/es.wikipedia.org\/wiki\/V%C3%B3xel\">v\u00f3xeles<\/a>, cubos que se representan en una cuadr\u00edcula 3D y ayudan a visibilizar con exactitud qu\u00e9 partes est\u00e1n ocupadas y cu\u00e1les vac\u00edas. \u00abCada uno puede tener un tama\u00f1o de apenas un mil\u00edmetro c\u00fabico\u00bb, apunta el MIT. Con las piezas que hay que apilar se sigue un proceso similar.<\/p>\n<p>\u00abPara conocer el espacio disponible, el algoritmo calcula una cantidad llamada m\u00e9trica de colisi\u00f3n en cada v\u00f3xel. Para ello, coloca el centro del objeto en cada v\u00f3xel del contenedor y cuenta el n\u00famero de v\u00f3xeles ocupados con los que el objeto se solapa o \u2018colisiona\u2019. El objeto solo puede colocarse en lugares donde el solapamiento sea cero, es decir, donde no haya colisiones\u00bb,\u00a0<a href=\"https:\/\/news.mit.edu\/2023\/chore-packing-just-got-faster-and-easier-0706\">se\u00f1ala<\/a>.<\/p>\n<p><strong>\u00bfY el siguiente paso?<\/strong>\u00a0Consiste en cribar las diferentes ubicaciones posibles y decidir cu\u00e1l es la mejor posici\u00f3n para el objeto. El proceso, claro est\u00e1, no se deja al azar ni la intuici\u00f3n. Los investigadores calculan una nueva m\u00e9trica para cada v\u00f3xel que se encarga de \u00abmaximizar la densidad de empaquetamiento\u00bb. B\u00e1sicamente, se encarga de medir los huecos entre el objeto y la pared del contenedor o el resto de las piezas apiladas. El objetivo es muy sencillo: minimizar los huecos que quedan libres, igual que en\u00a0<a href=\"https:\/\/www.xataka.com\/videojuegos\/tetris-vive-lucha-sigue-como-fanatico-espanol-videojuegos-retro-organiza-campeonatos-clasico\">el popular juego<\/a>\u00a0lanzado en los a\u00f1os 80 por Pajitnov.<\/p>\n<p>El proceso es algo m\u00e1s enrevesado, ya que el ordenador juega con m\u00faltiples orientaciones para un mismo objeto. Cuando al fin ha dado con la mejor posici\u00f3n el algoritmo SSP se encarga de confirmar luego que el objeto entra en el lugar que se le asigna y podr\u00e1 separarse del resto una vez se desempaquete. \u00abEl embalaje debe estar \u2018libre de enclavamientos\u2019, una condici\u00f3n para evitar configuraciones como los anillos entrelazados\u00bb,\u00a0<a href=\"https:\/\/news.mit.edu\/2023\/chore-packing-just-got-faster-and-easier-0706\">se\u00f1ala el MIT<\/a>. Con el prop\u00f3sito de facilitar los c\u00e1lculos, el equipo us\u00f3 la\u00a0<a href=\"https:\/\/es.wikipedia.org\/wiki\/Transformada_r%C3%A1pida_de_Fourier\">transformada r\u00e1pida de Fourier<\/a>\u00a0(FFT), una t\u00e9cnica matem\u00e1tica que asegura que no se hab\u00eda utilizado antes en embalajes.<\/p>\n<div class=\"article-asset-video article-asset-normal\">\n<div class=\"asset-content\">\n<div class=\"\">\n<div class=\"js-dailymotion\">\n<div class=\"dailymotion-player-root dailymotion-player-xbl2m\">\n<div class=\"dailymotion-player-wrapper\"><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p><strong>\u00bfY cu\u00e1nto tarda?<\/strong>\u00a0Un tiempo digno de un maestro del Tetris. Durante una demostraci\u00f3n el algoritmo logr\u00f3 apilar de forma eficiente 670 piezas en solo 40 segundos. Para colocar 6.596 fueron necesarias dos horas. En el primer caso la densidad de empaquetamiento fue del 36% y en el segundo de poco m\u00e1s del 37%. \u00abLas densidades, cercanas al 40%, son significativamente mejores que las logradas por los algoritmos tradicionales y tambi\u00e9n son m\u00e1s r\u00e1pidas\u00bb,\u00a0<a href=\"https:\/\/news.mit.edu\/2023\/chore-packing-just-got-faster-and-easier-0706\">reivindica Matusik<\/a>.<\/p>\n<p>\u00abLa soluci\u00f3n que se propone maximiza la densidad de empaquetamiento y tiene potencial para encontrar aplicaciones en muchas \u00e1reas pr\u00e1cticas, desde la rob\u00f3tica a la fabricaci\u00f3n \u2014abunda Bedrich Benes, profesor de inform\u00e1tica en la\u00a0<a href=\"https:\/\/www.purdue.edu\/\">Universidad Purdue<\/a>\u2014. Adem\u00e1s, las soluciones sin interbloqueo son adecuadas para entornos controlados por ordenador\u00bb. No son sus \u00fanicas aplicaciones. El m\u00e9todo del MIT puede resultar \u00fatil en almacenes y empresas de transporte o impresi\u00f3n 3D.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ni las horas de carretera, ni las colas para comprar un refresco, ni siquiera las peleas para hacerse con una parcelita de arena en la que plantar la sombrilla y extender la toalla. Si hay un desaf\u00edo realmente duro en las escapadas de verano a la playa es apa\u00f1\u00e1rselas para que la nevera, palas, cubos &hellip;<\/p>\n","protected":false},"author":0,"featured_media":60446,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-60445","post","type-post","status-publish","format-standard","has-post-thumbnail","","category-noticias"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/mickyandoniehn.com\/radio\/wp-content\/uploads\/2023\/07\/450_1000-luIuRg.jpeg","_links":{"self":[{"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/posts\/60445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/comments?post=60445"}],"version-history":[{"count":0,"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/posts\/60445\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/media\/60446"}],"wp:attachment":[{"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/media?parent=60445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/categories?post=60445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mickyandoniehn.com\/radio\/wp-json\/wp\/v2\/tags?post=60445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}