A la pregunta de Wirth y cadenas

Algoritmos + estructuras de datos = programas - Virt N.

"Tuvimos una maravillosa oportunidad de realizar un ejercicio táctico pequeño pero extremadamente instructivo"

A pesar del primer epígrafe de esta publicación, me permito estar en desacuerdo con el autor e intentar mostrar que, en algunos casos, la elección correcta de la estructura de datos puede ser más significativa que la elección correcta de los algoritmos. Para ilustrar una tesis tan sediciosa, consideremos una tarea simple pero prometedora para estudiar el juego "Cadena".

Primero, sobre las reglas del juego: dos jugadores juegan, la posición inicial consiste en N objetos ubicados cerca. El siguiente movimiento es eliminar uno o dos objetos ubicados cerca (puede intentar dar una definición formal de "ubicación cercana", pero es comprensible en un nivel intuitivo). El jugador que retira el último objeto gana: el juego directo, o el que debe (no puede omitir el movimiento) recoger el último objeto, gana el juego inverso. Dado que en esta versión de las reglas, un juego directo será simplemente poco interesante (más sobre eso más adelante), se introduce una restricción adicional: solo se puede eliminar un objeto en el primer movimiento.

En primer lugar, determinamos que el juego es finito, porque con cada movimiento el número de objetos disminuye estrictamente y el juego termina cuando se alcanza el número de objetos calculado por cero, por lo tanto, tenemos el derecho de contar con el éxito en el estudio de este juego. Además, es obvio que el juego no puede durar más de N movimientos, recordemos este hecho.

El estudio del juego consiste en determinar si para un número inicial específico de objetos el jugador que realiza el primer movimiento está ganando (ya que este es un juego con suma cero, de lo contrario está perdiendo) con un juego óptimo en ambos lados y en qué número mínimo de movimientos se logra la ganancia (o por cuál es el número máximo de movimientos que la pérdida aleja).

Para algunos de H, la respuesta es obvia: con un objeto, el primero gana un juego directo en un turno y también pierde un juego inverso (P1 = 1, I1 = -1). Con dos objetos, el primer jugador pierde en dos movimientos en un juego directo y gana en dos movimientos en sentido inverso (P2 = -2, I2 = 2), lo que puede dar lugar a una hipótesis sobre la simplicidad de evaluar este juego, que se confirma por el caso de tres objetos (P2 = 3, I3 = -3). Afortunadamente (de lo contrario, esta publicación no se habría publicado), un juego con cuatro objetos cambia un poco la imagen (P4 = -4, pero I4 = -3), por lo que es realmente necesario investigar el juego.

Para algunos de H y para un cierto tipo de juego, existen algoritmos heurísticos que dan una recompensa garantizada. Por ejemplo, para un juego directo con una H inicial extraña, se puede garantizar que ganas si quitas el objeto central con el primer movimiento y luego repites los movimientos del oponente usando un lugar central como eje de simetría, entonces tenemos la garantía de recoger el último objeto y ganar. La misma estrategia funcionaría con un número par de objetos, si no fuera por las restricciones en el primer movimiento, lo que hace que el juego no sea tan trivial. En términos generales, el uso de estrategias simétricas es una ocurrencia bastante común en los juegos de conteo, pero no una panacea, porque, por ejemplo, en nuestro juego inverso esta estrategia falla. Cabe señalar que las heurísticas dan un algoritmo ganador pero no dan una estimación precisa de la posición, ya que puede haber estrategias que conduzcan a ganancias más rápidas (este es el caso de este juego en particular).

¿Cómo podemos dar una evaluación del juego? Exactamente como recibí las estimaciones anteriores para 1-4 objetos; el método se llama búsqueda exhaustiva de arriba a abajo; debemos considerar el árbol completo del juego, es decir, todos los movimientos posibles para ambos lados y evaluar cada posición, incluyendo fuente, de acuerdo con ciertas reglas. Cabe señalar que la existencia de heurísticas exitosas no nos garantiza una evaluación precisa, ya que responde solo la primera mitad de la pregunta: quién gana, pero no da el número mínimo requerido de movimientos.

Esto significa que debemos construir un árbol de juego completo, pero antes de continuar con la construcción, debemos crear un modelo del objeto en estudio, en nuestro caso, el juego.

¿Por qué me concentro en esta etapa? Porque no podemos explorar el objeto en su materialización. No, puramente teóricamente esto es posible ("poco es posible en el mundo en general, puramente teóricamente") y puedo imaginar una imagen en la que una gran cantidad de robots juegan muchos juegos en el mundo real, pero el costo de material para tal solución al problema de evaluar el juego excede el cantidades, por lo que nos vemos obligados a emprender el camino de modelar objetos reales con sus contrapartes de software. Y aquí es muy importante seguir una línea fina, combinando un nivel suficiente de adecuación del modelo y la simplificación necesaria.

Pero primero, un poco de matemática para evaluar la complejidad de la tarea: necesitamos clasificar todos los movimientos posibles en el juego (la atención no es todas las posiciones posibles, este es el tema de otro método, a saber, los movimientos) y nos gustaría evaluar la cantidad requerida de recursos antes de comenzar el trabajo, para determinar el orden de la tarea. En el primer movimiento, tenemos la oportunidad de eliminar cualquier chip (continuaré llamando objetos) de H disponible, en el siguiente movimiento: cualquiera de los H-1 restantes o dos chips que estén cerca (no habrá más de esos pares que H-2), que da el número total de opciones Hx (H-1 + H-2). Es fácil ver que después del tercer movimiento tenemos Hx (H-1 + H-2) x (H-2 + H-3 + Δ) y así sucesivamente.

Si nos restringimos en cada paréntesis solo a los primeros términos de la suma, entonces obtenemos una estimación del número total de movimientos como H!, Lo que nos da una estimación en cuadraturas de H ^ H.

Este es un resultado muy desagradable, que afirma que tendremos problemas muy grandes con H significativo, por lo que lo más probable es que el modelado "frontal" conlleve costos computacionales significativos. Por ejemplo, para 16 fichas en la posición inicial, tendremos que considerar aproximadamente 16! = 1013 movimientos, y si un movimiento es de 10E-9 segundos (estimación bastante optimista), entonces el tiempo total será de aproximadamente 10E4 segundos o casi 3 horas, lo que es un poco mucho , pero aceptable, pero para solo 20 chips, el tiempo de cálculo esperado es de 77 años, lo cual es claramente inaceptable. Factorial está creciendo muy rápido y no hay nada que hacer al respecto.

Llamamos la atención sobre el hecho de que el número de movimientos excede significativamente el número de posiciones posibles, que es solo 2 ^ N, y es obvio que caeremos en una posición separada para 16 fichas 10E (13-5) = 10E7 veces, lo cual es un hecho bastante cotidiano para tareas de búsqueda Recuerde este hecho, nos será útil más tarde.

Sin embargo, comenzaremos a escribir un programa, para el cual determinaremos el modelo. Primero, numeramos los chips del 1 al H, luego creamos una matriz con el número de elementos H y determinamos que el número 1 en el elemento de la matriz con índice n significa la presencia del número de chip n, y el número 0, su ausencia en una posición específica. Dicho modelo es adecuado, simple, intuitivo y le permite hacer efectivas las operaciones de eliminación de virutas, así como determinar la condición de "proximidad".

Ahora que tenemos un modelo (estructura de datos), podemos comenzar a extraer (búhos en el mundo) el algoritmo de este modelo. El algoritmo de enumeración completa con retorno es simple en el diagrama de bloques y consta de dos partes independientes: la enumeración real y la evaluación de posiciones, para comenzar implementaremos la primera parte. Tenga en cuenta que este algoritmo no se implementa mejor dentro del marco del paradigma de programación estructural y sería algo más efectivo si nos permitiéramos usar una transición o repetir el código, pero incluso sin estas desviaciones del estilo, la implementación no es pretenciosa (la complejidad ciclomática es bastante aceptable) . Como todavía no hemos introducido una evaluación y nos gustaría obtener el resultado del programa, simplemente derivamos las posiciones bajo consideración y las examinamos con nuestros ojos para evaluar la implementación correcta y asegurarnos de que los resultados correspondan a los esperados.

Ahora agreguemos una estimación de posición: por supuesto, el código bien escrito es autodocumentado (aunque hay diferentes opiniones con respecto a esta declaración), pero esta parte se describe mejor en palabras. La idea es que proporcionemos una evaluación inequívoca de las posiciones finales (en nuestro caso, es única y consiste en cero fichas), en función de las reglas del juego, y en todas las demás posiciones damos una evaluación neutral preliminar, y luego comenzamos a refinarla moviendo la estimación hacia arriba del árbol . Al retroceder, la estimación de la posición actual cambia en uno en la dirección de cero, luego se invierte y se transfiere a la posición anterior, donde se combina con la estimación anterior de acuerdo con las siguientes reglas:

1. la evaluación neutral cambia a una nueva,
2. una calificación positiva cambia a una positiva más pequeña,
3. una evaluación negativa cambia a una gran negativa o positiva.

Después de haber pasado por todos los movimientos, la evaluación de la posición inicial es final.

Agregamos estimaciones a nuestro procedimiento para generar todas las posiciones y podemos admirar los resultados del análisis, que se muestran en una tabla, agregar un contador de progreso y un medidor de tiempo para el análisis. En el compilador gcc (en modo de optimización -O2) en una máquina con un procesador, obtuve una tabla que confirma completamente nuestras suposiciones iniciales sobre el orden factorial de complejidad de la tarea. De la misma tabla, vemos que dejé de esperar resultados con H superior a 11, porque el tiempo de cálculo se volvió inaceptable (para mí, tal vez esté listo para esperar media hora) y nuestra suposición sobre el curso y el nanosegundo no corresponde a la realidad (tiempo promedio consideración de la posición es de 100 nseg). Surge la pregunta: ¿qué debemos hacer si queremos tener una estimación de más de 11 fichas en la posición inicial?

Podríamos tomar el camino de pequeñas optimizaciones, jugar con transiciones y banderas, entrar en insertos de ensamblador, aplicar operaciones de vectores difíciles del sistema de instrucciones de nuestro procesador, y de esta manera puede ganar velocidad de manera inequívoca a veces, en un orden de magnitud, tal vez dos órdenes de magnitud. - es muy poco probable, pero necesitamos una ganancia de muchos órdenes de magnitud, ya que el orden (e incluso más) consumiremos un aumento de H en uno sobre 10. Por cierto, si solo activa la optimización del compilador, hará algo por nosotros y el tiempo de ejecución disminuirá Tengo 4 veces - no está mal del todo y en línea con nuestras expectativas.

Por lo tanto, primero debemos tratar de mejorar los algoritmos aplicados, y la primera de estas mejoras (y la principal) es el método de corte de fuerza bruta o el "procedimiento alfa-beta". Su idea principal parece bastante robusta y consiste en el hecho de que si calificamos una determinada posición como ganadora, dejamos de mejorar la calificación para esta y volvemos al árbol. Este enfoque puede aumentar considerablemente la velocidad del algoritmo, especialmente si investigamos movimientos exitosos (que conducen a una victoria) en primer lugar. Pero también puede aumentar el tiempo, ya que se agrega la verificación de la evaluación actual y el procedimiento para elegir el curso es complicado, es muy difícil estimar la influencia de este método de antemano, es necesario realizar un experimento. Y una consideración más: no debemos olvidar que en el caso de una búsqueda con un límite, en el caso de una posición ganadora, damos una estimación verdadera, pero no precisa, ya que no consideramos parte de las opciones, y podrían dar una victoria en menos movimientos. Si tal disminución en la precisión nos conviene, entonces, ¿por qué no usar este método, pero para una evaluación precisa, nada más que una búsqueda exhaustiva no funciona?

Los resultados de la enumeración de recorte se muestran en la siguiente tabla, y vemos que hay una ganancia de rendimiento y un aumento significativo, pero no suficiente para estudiar grandes valores de N. En qué dirección continuaremos nuestra investigación: primero veremos otra estructura de datos, bueno, y luego, lo has adivinado (es bueno tratar con una audiencia astuta) es otro algoritmo.

Prestemos atención al hecho de que la estructura de datos adoptada por nosotros hace que los chips sean únicos y, por ejemplo, un solo chip (que no tiene adyacente) en posición no es equivalente a un solo chip en la posición n + 2, lo cual es completamente incorrecto. Seleccionamos el elemento clave de la posición del juego: el grupo de fichas ubicado junto a él y determinamos su característica principal: la cantidad de fichas en el grupo. Es esta información la que determina de manera única cualquier posición en el juego, y debemos presentarla en una forma conveniente para la programación. Elegimos la estructura de datos más simple y obvia: comenzamos una matriz de elementos H y almacenamos en el elemento n de la matriz el número de grupos con exactamente n chips. Entonces, por ejemplo. Para la posición inicial con 3 fichas, tendremos la representación {0,0,1}. El procedimiento de ejecución para la presentación dada sigue siendo simple y efectivo, aunque, por supuesto, más complicado que en la primera versión. Después del primer movimiento (de los cuales había dos en lugar de tres) obtenemos las posiciones {0,1,0} y {2,0,0}.

Tratemos de estimar la ganancia esperada en el número de movimientos para una estructura de datos dada. Para el primer movimiento, tenemos opciones (H-1) / 2 + 1, para el segundo (dividimos el grupo H en my N-m-1) (m-1) / 2 + (N-m-1-1) / 2 (tomar 1 chip) + (m-2) / 2 + (N-m-1-2) / 2 (tomar 2 chips) = (H-3) / 2 + (H-5) / 2 y por analogía , concluimos que en cada paso ahorramos al menos la mitad de los movimientos. Entonces nuestra ganancia debería ser al menos 2 ^ H, lo cual es muy, muy bueno para la gran H. De hecho, la ganancia será aún mayor, por ejemplo, para la posición {8,0 ...} en la primera realización, necesita ordenar 8 movimientos, y en la segunda solo 1 y la ganancia en este caso será 8 veces. Por lo tanto, podemos contar firmemente con 2 ^ H, pero esperamos mucho más, lo cual comprobaremos. Y seguro, para el programa de acuerdo con esta representación, obtenemos la Tabla 4, la última línea muestra la ganancia de rendimiento al cambiar a la segunda versión de la estructura de datos (calculada a mano). El crecimiento es simplemente colosal y con confianza (llegamos al fondo) rompimos el límite de la posibilidad de análisis de hasta 20 chips en la posición inicial a un costo de tiempo razonable.

Además, podemos realizar una optimización sutil del algoritmo para una estructura de datos determinada y obtener incluso una ganancia en el rendimiento, pero no obtendremos un crecimiento tan dramático (por orden de magnitud), que una vez más indica que Wirth estaba equivocado. Por ejemplo, en el programa anterior, el procedimiento para crear el próximo candidato para el movimiento no fue deliberadamente óptimo y su corrección obvia (dejémoslo al lector curioso) aumentará la velocidad en 3 veces, pero esto es un poco, aunque agradable.

Prestemos atención a los resultados y veamos algunas cosas no obvias. Por ejemplo, el programa afirma que una ganancia garantizada en un juego directo de 9 fichas no se logra en 9 movimientos, como se deduce del algoritmo simétrico heurístico, sino en solo 7, y el primer movimiento coincide con el heurístico (y, además, es la única posición ganadora ), pero el tercero y los siguientes no deben repetir los movimientos del oponente, como se desprende del algoritmo ingenuo, y la clave aquí es {1,0,0,1}, que tiene una calificación de +4. Ahora que hemos dado una evaluación precisa del juego, podemos hacer preguntas interesantes con respecto a la presencia de posiciones con una evaluación estable (en la que podemos dejar que el oponente se valga por nosotros mismos), la presencia de posiciones clave en el árbol de enumeración, encontrar posiciones con el único movimiento correcto, y así sucesivamente (y incluso obtener respuestas a estas preguntas y las correctas).

Aquí está la tabla resumen de calificaciones

Papas fritas	Directo	Retroalimentación	Posiciones / Tiempo	Posiciones / Tiempo
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4 4	-4	-3	82/0	20/0
5 5	5 5	4 4	463/0	71/0
6 6	5 5	-5	3032/0	263/0
7 7	7 7	6 6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9 9	7 7	-7	1798427 / 0.1	24,283 / 0
10	9 9	8	18634228 / 0.8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0.1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3.84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

Sin embargo, vemos que la estimación del tiempo de operación se mantuvo factorial, aunque con una disminución significativa en la tasa de crecimiento. Busquemos otras formas de explorar el árbol del juego.

Hemos perfeccionado el algoritmo de arriba hacia abajo (bueno, por supuesto, no lo terminamos en la forma fea que dibujé en la parte posterior del sobre, puede mejorar significativamente el rendimiento al reescribir cuidadosamente los procedimientos básicos, y esto seguramente se hará, pero el problema no es cardinal decide), así que vamos a la inversa: de abajo hacia arriba. La idea de este método es intuitivamente simple y comprensible, pero muy difícil para el uso humano: comenzamos desde la posición final, que se estima de acuerdo con las reglas del juego, y comenzamos a transferir la estimación hacia arriba en el árbol de acuerdo con las mismas reglas que para la búsqueda de arriba hacia abajo. Por supuesto, al mismo tiempo estamos considerando no posibles movimientos hacia abajo desde la posición actual, pero estamos considerando todas las posiciones desde las cuales podríamos entrar en el movimiento actual en uno. Transferimos la estimación de acuerdo con las reglas anteriores. Además, aplicamos este procedimiento de forma iterativa y cuando deja de producir resultados, es decir, en la siguiente ronda, ni una sola posición cambió la evaluación, la tarea se completa y la evaluación de la posición inicial es correcta y precisa. Este enfoque le permite reducir en gran medida el tiempo de búsqueda, especialmente si realiza algunas mejoras, pero tiene un fuerte inconveniente (y esto es un clásico: cambiamos el tiempo de memoria), lo que limita significativamente su alcance: requisitos de memoria altos, ya que debemos almacenar estimaciones , ( ).En el caso del juego en cuestión, el método de representación de bits para la primera estructura de datos sugiere que existen otros métodos que pueden reducir la cantidad de memoria requerida (almacenando solo los tres niveles de árbol considerados con la excepción de la capa inferior), pero, por supuesto, degradando el rendimiento, ya que la búsqueda se vuelve muy poco trivial. Sin embargo, para H no mayor que 20, el número total de posiciones no será mayor que 2 ^ 20, y una matriz de este tamaño en la memoria para elementos que contienen un número de -20 a 20, es decir, un número de 8 bits, soy bastante capaz de imaginar y su implementación no será difícil. Por lo tanto, es bastante posible escribir un programa para dicho algoritmo y evaluar el rendimiento resultante, pero no nos apresuremos y hagamos estimaciones. El tipo de memoria que tendremos que asignar no es difícil de determinar, pero con parámetros temporales es algo más complicado.Supongamos que creamos inmediatamente todas las posiciones posibles, serán M, entonces el número promedio de movimientos desde una posición puede estimarse como no más de 2 * N (una estimación muy aproximada). Luego, en cada iteración, necesitamos realizar no más de M * 2 * H de transferencia de la estimación, y dado que en cada ciclo mejoraremos la estimación de al menos una posición, el tiempo de trabajo total será del orden M * 2 * H * M.

Luego, para la primera forma de presentar los datos, obtenemos 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (enfatizamos una vez más que esta estimación es muy fuerte desde arriba) y, por ejemplo, para H = 20, la estimación del tiempo de búsqueda desde arriba -down será 20! ~ 10E18, y para la búsqueda de abajo hacia arriba tenemos 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14, es decir, para 20 fichas ganamos a tiempo al menos 10E6 veces, lo cual es muy bueno. También contaremos con 9 fichas iniciales, obteniendo 9! ~ 10E6 para la búsqueda superior, y 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6 para la evaluación de abajo hacia arriba, es decir, a partir de este número, la búsqueda de la línea de fondo gana. La última declaración es un tanto apresurada, ya que el procedimiento para evaluar la siguiente posición se ha vuelto significativamente más largo; tendremos que buscarlo entre los ya generados, pero para esta representación particular en forma de matriz de bits, este procedimiento se realiza en O (1).

Para la segunda presentación, es necesario evaluar el número de posiciones diferentes, que es una tarea del campo de la combinatoria. Como ejemplo, considere un juego con 9 fichas iniciales, para las cuales el número total de diferentes posiciones será: 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39.
Luego, una estimación por el mismo método conducirá al valor H * M * M = 39 * 39 * 9 ~ 10E4, que es dos órdenes de magnitud mejor en velocidad en comparación con la primera representación, y a medida que H aumenta, la ganancia solo aumentará. En comparación con ir por encima para la segunda vista, también debe esperar una mejora significativa en el rendimiento, pero es más difícil de evaluar, por lo que es más fácil intentarlo.

Por lo tanto, si realiza un programa de análisis de abajo hacia arriba, entonces para la segunda presentación. No daré el programa, necesito dejar algo para que los lectores hagan el análisis del hogar. Deberíamos obtener resultados para H significativo en un tiempo muy razonable. Otra ventaja de romper desde abajo es que podemos ahorrar significativamente al fijar la estimación para la mitad inferior de las posiciones (que tiene un número menor de fichas que N / 2), ya que una vez que la mitad inferior estimada se transfiere sin cambios para el siguiente número de fichas, lo que nos dará una ganancia adicional en 2 veces

— , , . , , ( ) .

Bueno, en conclusión, la explicación necesaria para aquellos que tomaron mi publicación demasiado en serio y arden con indignación (justa): no estoy completamente seguro de que especificar los algoritmos como el primer término en la fórmula de definición del programa confirme su mayor importancia, estoy completamente de acuerdo en que En algunas situaciones específicas, un algoritmo seleccionado correctamente puede dar un aumento ordenado de la productividad, y no iba a incriminar a Dijkstra (a quien respeto con respeto) por errores. Todo fue una frase para llamar la atención, y la publicación trata sobre otra cosa: que la estructura de datos también es extremadamente importante en términos de rendimiento y no quería que me olvidaran de esto en el proceso de diseño.

PS.Aquí me dicen desde la audiencia (hola Max) que hay otro método para investigar el juego: matemático y, dada la hipótesis del doble apellido de que la mayoría de los juegos de conteo se reducen al juego de Nim, entonces solo necesitamos calcularlo: la suma la posición inicial (en mi opinión, la declaración es dudosa), y también puede convertir el juego original en juegos en el gráfico (no hay objeción), por lo que puede esperar una estimación de 1.878 ^ N para el momento del trabajo (aunque el número específico me desconcertó un poco). Probablemente, estas consideraciones tienen derecho a la vida, al menos los artículos de este contenido parecen convincentes, pero soy un practicante puro y dejo estas opciones nuevamente para lectores curiosos (ars longa, vita brevis).