PlaceIt
Un artículo revisado por pares que resuelve un juego de ordenación online perfecta: la mejor estrategia gana el 0,0134 % de las veces.
A Mathematical Analysis of PlaceIt: A Game of Perfect Online Sorting, con Casey Chock y Bernardo Subercaseaux (Carnegie Mellon University). Presentado en Computers and Games 2024 y publicado en Lecture Notes in Computer Science de Springer, vol. 15550, pp. 185–196 (2025).
En el juego de un jugador PlaceIt llegan veinte números aleatorios del 1 al 999, uno a uno, y cada uno debe colocarse en una de veinte casillas antes de ver el siguiente, de modo que las casillas acaben ordenadas. Un mal paso al principio y la partida está perdida. Calculamos la estrategia óptima y demostramos que, incluso jugando perfectamente, se gana con una probabilidad de aproximadamente .
El código es una pequeña librería, onsort, para la ordenación online óptima de números extraídos de una distribución conocida: un cálculo semisimbólico de la probabilidad exacta de ganar el juego discreto original, una implementación en C++ y la variante continua en . Puedes jugar a PlaceIt online y ver hasta dónde llegas.