algorithm - solo - ¿Cómo eficientemente acumular billar para un juego de 8 bolas?

lecciones de pool

Question

Como el almacenamiento de bolas de billar para el juego de 8 bolas se puede hacer bajo múltiples reglas, aquí está el trasiego al que me refiero:

es decir, la bola 8 debe estar en el centro, y a lo largo de los lados las rayas y los sólidos deben alternar. Las dos bolas restantes (una raya y un sólido) no importan.

Asuma que acaba de terminar un juego, junte las bolas, colóquelas en el estante y proceda a organizarlas para comenzar una nueva. Ahora están en un orden aleatorio. ¿Cómo se procede?

_{Descargo de responsabilidad: paint art follows}

Un enfoque simple sería comenzar en orden, arriba -> abajo e izquierda -> derecha.

Entonces, por ejemplo, supondríamos que 1 está en la posición correcta. 5 no lo es, lo cambiamos por 2 , luego cambiamos 4 por 3 (o por 8 ), pero esto ya sería ineficiente porque hemos movido el 4 al centro o el 8 en la posición 4 , es decir, no donde tiene que ser al final.

También está la decisión de qué tipo de bolas queremos en las curvas. ¿Cómo decides eso por adelantado? ¿Debes tener en cuenta cuántas bolas ya están en su lugar? En mi ejemplo, si quieres los grises en las esquinas, ya tienes 3 en su lugar (bolas 1,10,14). Si quieres los blancos en las esquinas, tienes solo 2 en su lugar (2,11). ¿Debería esto importar?

Para formalizar esto, podemos suponer que hay dos tres operaciones que podemos hacer:

• intercambiar dos bolas adyacentes
• intercambiar dos bolas no adyacentes
• girar la rejilla

Como podemos usar ambas manos, supongamos que podemos paralelizar la primera operación (intercambiar 2 pares de bolas al mismo tiempo), mientras que solo podemos intercambiar dos bolas no adyacentes a la vez.

¿Qué enfoque es el más adecuado para esta tarea que minimiza el tiempo (en las unidades de tiempo descritas)? ¿Sería la codicia lo mejor para esto? (Así es como lo hago cuando los acumulo, supongo)

EDITAR: según las respuestas existentes (o anteriores), puede suponer que tener más rayas que sólidos en las esquinas significa que las zancadas preferirán esquinas, sin decir que no es cierto, pero si lo hace, por favor demuéstrelo.

Answer 1

¡NOTA! Esta respuesta se escribió antes del requisito de rotación. Proceda bajo su propia precaución :)

Aquí está mi mirada inicial al problema.

Lo primero que hay que hacer es calcular la paridad del exterior: +1 si cabe "rayas en las esquinas", -1 si cabe "sólidos en las esquinas", +0 si es la bola 8. Esto nos da un rango de +12 a -12, y apuntamos al extremo al que estamos más cerca. (Si es +0, elija +12 o al azar)

Por ejemplo, esto es +1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +0 -1 y por lo tanto es -1 inclinando sólidos en las esquinas:

x o x x o
 x o x o
  8 x o
   o x
    o

Lo siguiente que debes hacer es mover la 8 bola hacia el centro. Si puede hacer dos intercambios adyacentes con él que muevan dos bolas a su posición, en lugar de un solo intercambio adyacente que mueve una sola bola a su posición (o una sola no adyacente si está en una esquina), hágalo.

x o x x o
 x 8 x o
  o x o
   o x
    o

Después de mover la bola 8, todas las combinaciones de dos intercambios adyacentes que comparten una bola pueden ser producidas por un intercambio no adyacente de manera idéntica, por lo que tenemos que considerar mucha menos complejidad a la vez.

Ordene todos los movimientos restantes según esta prioridad:

-Un intercambio entre dos bolas adyacentes en el exterior es ''vale 4'' (2 si es el último)

-Un intercambio entre dos bolas adyacentes, una en el exterior, es ''vale 2'' (1 si es la última)

-Un intercambio entre dos bolas en el exterior es ''vale 2''

-Un intercambio entre dos bolas, una en el exterior, es ''vale 1''

Y realizarlos de arriba a abajo.

Así que movemos la o en la parte superior, izquierda (4), la o en el lado derecho en (2), la o en la parte inferior izquierda en (2) y luego intercambiamos la x arriba con la o en el centro (2) . Terminamos haciendo cinco intercambios en una serie 2-2-1, por lo que tres movimientos.

o x o x o
 x 8 x x
  o o o
   x x
    o

(Notablemente, este se habría resuelto igual de rápido si apuntamos a rayas en las esquinas).

x x o o x
 o 8 o x
  o x o
   x o
    x

Creo que es imposible exigir 4 turnos, pero aún no me lo he probado.

Otro ejemplo trabajado:

Esto tiene una paridad de +1, por lo que apuntamos a rayas en las esquinas:

8 o o o x
 o o o x
  o x x
   x x
    x

intercambia 8 bolas con el centro x (1-)

x o o o x
 o o o x
  o 8 x
   x x
    x

intercambia dos adyacentes en el exterior, 4 puntos (1-1)

x o o o x
 o o o x
  x 8 x
   o x
    x

intercambie el borde adyacente al centro, 2 puntos (1-2-)

x o o o x
 o o x o
  x 8 x
   o x
    x

cambiar de borde a borde, 2 puntos (1-2-1-)

x o x o x
 o o x o
  x 8 x
   o o
    x

3 movimientos.

EDITAR: Esto funciona bastante bien para el ejemplo en el post de apertura, resolviéndolo en dos movimientos:

Esto tiene una paridad de +1, por lo que apuntamos a rayas en las esquinas:

x x o o x
 o o x o
  o o 8
   x x
    x

Cambia 8 con x en el borde y luego con o en el centro (resolviendo dos bordes) (2-)

x x o o x
 o o x o
  o 8 x
   x o
    x

intercambie adyacentes oyx en la parte superior e inferior izquierda (resolviendo cuatro bordes) (2-2-)

x o x o x
 o o x o
  x 8 x
   o o
    x

2 movimientos.

Answer 2

Esta ha sido una pregunta desafiante, profundamente frustrante y divertida a la vez. Mi conjetura es que la siguiente es una solución óptima:

• Elija si las rayas o los sólidos están en las esquinas según el método de paridad de Patashu
• Sin rotaciones
• Cada medida de tiempo, realiza el movimiento que puntúa más alto, excepto cuando un movimiento de +3 puede poner la bola 8 en el centro
• En caso de empate, la elección no importa? Editar: ver nota en la parte inferior. Los lazos son difíciles.

(Estoy anotando movimientos de acuerdo con la diferencia neta en la cantidad de bolas en las posiciones correctas).

Aquí hay dos racks de ejemplo:

    x            8
   x x          o o
  o o x        o o x
 o o x x      o x x x
8 o o o x    o x x o x

Si numeramos las posiciones 1 a 15 yendo de izquierda a derecha, luego de arriba a abajo, el primer estante se resuelve como (2-4 / 3-5) (5-11) (10-13) y el segundo estante se resuelve como (4 -8 / 11-12) (5-10) (1-5).

Mi último intento de prueba tuvo una porción fallada en solo 11 bastidores diferentes hasta la simetría (con los dos mostrados arriba siendo una variación de los que fallaron). Aquí hay dos lemas que encontré en mis intentos, que con suerte ayudarán a otros con pruebas.

Lema 1: las rotaciones no son necesarias

Tenga en cuenta que si necesitamos hacer una rotación en algún punto de nuestra solución, no importa cuándo (rotar no cambia ningún intercambio disponible). Además, solo necesitamos como máximo una rotación, ya que 2 rotaciones en el sentido de las agujas del reloj = 1 en sentido antihorario y viceversa.

Así que vamos a elegir hacer la rotación en nuestro último movimiento si es necesario. En este punto, debido a la simetría rotacional del exterior, el exterior debe ser correcto. Entonces la bola 8 estaría en una de las tres bolas centrales. Si está en el lugar correcto, no necesitamos rotación. De lo contrario, podríamos usarlo, pero tenga en cuenta que un intercambio también completaría el rack. Por lo tanto, no es necesario en una solución óptima.

Lema 2: codicioso es óptimo si resuelve el rack en menos de 3 movimientos

Deje que la estrategia A sea ​​la solución codiciosa y la estrategia B sea ​​cualquier solución no codiciosa que intente ser más rápida. B debe hacer al menos un movimiento no codicioso. Por necesidad, este no puede ser el último movimiento. Por lo tanto, si A toma n giros para completar un rack, B debe realizar su movimiento no codicioso en el turno n-2 o anterior. Esto significa que si A resuelve el estante en 2 vueltas o menos, es óptimo.

Editar: Bueno, acabo de ejecutar mi algoritmo en una prueba programática, y descubrí que no es uniforme. De hecho, parece que los vínculos son muy difíciles de romper. Considere el siguiente rack:

    x
   o o
  x o x
 x 8 o x
x o o x o

Mi algoritmo haría una de las siguientes secuencias de movimientos: (5-8 / 13-14) (7-8 / 10-15), (5-8 / 10-15) (7-8 / 13-14), ( 5-8 / 14-15) (10-13) (7-8), (5-8 / 14-15) (7-8) (10-13), (5-8 / 9-10) (14 -15) (7-13), (5-8 / 9-10) (7-13) (14-15), (5-8 / 9-10) (13-14) (7-15), o (5-8 / 9-10) (7-15) (13-14). Los primeros dos lo resuelven en las 2 medidas de tiempo óptimas, pero los otros lo resuelven en 3 medidas de tiempo. El problema es que los interruptores (14-15) y (9-10) arruinan un posible movimiento de +4 en el segundo turno. Una modificación de este algoritmo probablemente requeriría una inspección previa, que luego se complica rápidamente. Estoy empezando a pensar que no hay una solución "simple", y la solución de @JeffreySax es el camino a seguir. También tenga en cuenta que este rack también derrota a la solución codiciosa. La solución codiciosa haría (13-14 / 10-15) (5-8) (7-8) o (13-14 / 10-15) (7-8) (5-8).

Answer 3

Hay 15!/(7!7!1!)=51480 posiciones posibles. De estos, 4 son finales: las bolas 8 y 9 pueden intercambiarse, y las rayas / sólidos pueden invertirse. Diremos que estas posiciones están en la distancia 0.

Para cada una de estas 4 posiciones, genere todos los movimientos posibles (1 intercambio o 2 intercambios adyacentes). Para cada posición generada por estos movimientos que no se haya visto antes, recuerde qué movimiento se usó para generarla y déles la distancia 1. Haga lo mismo para cada posición en la distancia 1 y otorgue a las nuevas posiciones la distancia 2. Mantenga haciendo esto hasta que no haya más nuevas posiciones.

Esto hace uso del hecho de que, como señaló @PDner, las rotaciones siempre se pueden reemplazar con un movimiento adyacente.

Como los swaps son su propia inversa, el movimiento para pasar de la posición A a la B también es el movimiento que llevará la posición B a A.

Entonces, terminas con una lista de todas las posiciones, y para cada posición que no es una posición final, un movimiento que con certeza la acercará a una posición final.

Encontrarás que hay 232 posiciones que toman al menos 4 movimientos. (EDITAR: Mi tabla de adyacencia contenía un error anterior). Por ejemplo:

      6-9,14-15     2-12       2-5,4-7       1-2
    x           x           x           x           o
   x x         x x         8 x         o x         x x
  x o x   =>  x o o   =>  x o o   =>  o 8 o   =>  o 8 o
 o o o x     o o x x     o o x x     x o x x     x o x x
o 8 o o x   o 8 o x o   o x o x o   o x o x o   o x o x o

No hay posiciones iniciales que requieran más de 4 movimientos.

EDITAR: La estrategia de intercambiar en el 8-ball primero no es óptima. Por ejemplo:

         5-11     12-13,14-15    4-7,6-10
    x            x            x            x
   o o          o o          o o          o o
  o x o   =>   o 8 o   =>   o 8 o   =>   x 8 x
 x o x x      x o x x      x o x x      o o x o
8 x o x o    x x o x o    x o x o x    x o x o x

Pero lo podemos hacer mejor:

         3-11       1-2,3-5
    x            x            o
   o o          o 8          x x
  o x o   =>   o x o   =>   o 8 o
 x o x x      x o x x      x o x x
8 x o x o    o x o x o    o x o x o

El problema es que x es el tipo incorrecto para la esquina, por lo que perdemos un movimiento.

Por el contrario, la estrategia debería ser buscar una bola que esté fuera de lugar, pero que no pueda intercambiarse con una bola adyacente, ya sea porque son del mismo tipo o porque ya están en posición. Las esquinas deben ser preferidas, ya que tienen la menor cantidad de opciones de intercambio adyacentes. Debe cambiarse con una bola del tipo correcto para la posición. Si la bola en la posición final de la primera bola es del tipo incorrecto, se debe elegir una bola adyacente en el lugar equivocado. De esta forma, un intercambio adyacente posterior colocará esas bolas en el lugar final correcto.

En el ejemplo anterior (contador), la bola 8 requiere un intercambio largo para llegar a su posición final. Sin embargo, la x en el n. ° 5 es del tipo incorrecto, por lo que cambiamos con un o adyacente, el segundo en la segunda fila.

El ejemplo anterior con 4 movimientos se resuelve de la siguiente manera:

        11-2         12-5        13-3       9-10
    x           x           x           x           x
   x x         o x         o x         o o         o o
  x o x   =>  x o x   =>  x 8 x   =>  x 8 x   =>  x 8 x
 o o o x     o o o x     o o o x     o o o x     o o x o
o 8 o o x   x 8 o o x   x o o o x   x o x o x   x o x o x

En el primer paso, seleccionamos el o en la esquina inferior izquierda. La primera x está en la posición dos. Luego elegimos el 8 en el # 12, que podemos llevar a casa al # 5. El o en el medio de la fila inferior es el siguiente. Lo intercambiamos con el siguiente erróneamente colocado x en el n. ° 3. Finalmente, intercambiamos el n. ° 9 y el n. ° 10 para obtener el estante final. El camino es diferente al anterior, pero aún lo hicimos en 4 movimientos.

EDITAR: Un punto más: al realizar intercambios adyacentes, se debe dar preferencia a aquellos que no terminen con ambas bolas en su posición final. La razón es que esto significa que se requieren al menos dos movimientos en total, por lo que es mejor hacer el primer movimiento lo antes posible.

Por ejemplo, el rack en la pregunta se puede resolver en dos movimientos: (2-4), (5,6) y (3-6), (12-13). La bola 8 se movió primero a su posición final, a pesar de que la bola blanca con la que se intercambió aún no se encuentra en su posición final. Si las dos permutas de perímetro (2-4), (12-13) se hicieron primero, aún necesita dos movimientos para llegar al estante final, teniendo un total subóptimo de 3 movimientos.

Answer 4

Salut, primero debo decir que este fue un problema muy divertido e interesante, y algo en lo que no pensé cuando hice un trasiego, aunque con 15 bolas totales, algunos movimientos adicionales no serían importantes.

De la descripción e imagen de la estantería obtenemos las siguientes reglas :

1. las esquinas son siempre del mismo tipo
2. el centro de cada lado siempre es del mismo tipo que la esquina
3. cada conjunto de 2 bolas tocando las esquinas es siempre el mismo tipo (y opuesto tipo esquina)
4. dentro del triángulo siempre tiene 8ball, una raya y un sólido (y 8ball está en la parte superior)
5. en los lados, las bolas cerca uno del otro siempre se alternarán

Como @PDenner declaró en el Lemma 1 , las rotaciones no son necesarias porque pueden sustituirse por un intercambio, siempre que el costo sea el mismo. Si eres fanático de Rubick y eliges usarlo, solo necesitarías uno.

¡No se puede resolver en menos de 4 intercambios! ( siempre )

Su imagen de ejemplo es la mejor para probar esto, en cualquier forma que lo tenga, tendrá que desalojar 6 bolas de colores de sus posiciones y el 8ball => eso es 3½ swaps y como un intercambio necesita 2 bolas, redondeemos eso a 4 swaps.
¿Por qué es esto?
Porque no cumple con todas las reglas:

• [5,1,4] [2,6] [11,13] [10,12] no pueden estar cerca unos de otros (se rompe 5)
• 8ball está en un lado y no en el triángulo central (breaks 4)
• [5,4] [6,12] [13,9] no son todos del mismo tipo (quiebres 3), además en el caso de [1,5,4] el conjunto no está enfrente de la esquina (se rompe 3 nuevamente )
• [2] y [11] no son del mismo tipo que las esquinas (descansos 2)

Algoritmo

1er paso: arreglar el 8ball
Cambie el 8ball a su posición. Necesitará estar allí de todos modos.
Esta es la única oportunidad para rotar (en caso de que la bola empiece en el triángulo interior, pero la posición incorrecta)

Count la mayor cantidad de bolas del mismo tipo en las posiciones rojas .
Las bolas de conteo más altas permanecen, el resto de las manchas deben intercambiarse.

IF count is 3 {
    #inside triangle will choose 
    IF inside triangle has 2 of a kind, that type stays (in the red spots)
    ELSE pick random
}

Comience a intercambiar:

• hacer las esquinas (escoger una pelota que necesita cambiar y encontrar la opuesta en una esquina)
• hacer los medios (escoger una pelota que necesita cambiar y encontrar una opuesta en medio de un lado)
• si las esquinas y los medios están terminados, el último intercambio está dentro del triángulo

Demostración en tu ejemplo:

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside is correct, random pick: stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(3)  #move4
Done.

si la selección al azar elegiría sólidos para quedarse:

Pick 6, swap with corners(10)  #move2
Pick 13, swap with corners(1)  #move3
Pick 9, swap with corners(14)  #move4
Done.

Demo2:

cambió 3 por 7, reemplazó ''bola blanca no.8'' con bola no.15

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside has 2 of a kind(stripes) => stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(15)  #move4
Done.

Have fun!

PD: También podría gustarle la variación del algoritmo n. ° 2 que counts las posiciones grises, pero me resultó más fácil para un escenario de la vida real usar las manchas rojas.

Answer 5

Tienes 2 ocho bolas, tramposo.

En el ejemplo dado, la solución requiere 2 movimientos:

2-5, 3-8
3-4, 11-12

Una solución óptima se encuentra mejor configurando el problema para la programación dinámica (DP). Dado que el problema es de múltiples etapas con costos fijos y sin incertidumbres, existirá una matriz DP que resuelve el problema de manera óptima.

Para crear la matriz: nótese que teniendo en cuenta las simetrías, la bola 8 puede estar en una de las 9 posiciones. Los sólidos se pueden organizar en aproximadamente (14 eligen 7) / 2 = 1716 formas diferentes. Eso significa que la cantidad total de configuraciones de rack es aproximadamente 1716 * 9 = 15,444. Por lo tanto, tiene 15,444 estados diferentes posibles. Calcule el costo de ir de cualquiera de estos estados a cualquier otro. Esto da como resultado una matriz con 15,444 * 15,444 células, o aproximadamente un cuarto de mil millones de células. Identifica todas las celdas de estado final. Para resolver la matriz, amplía la búsqueda hacia adelante desde el estado de inicio hasta que alcanza un estado final (o hasta que alcanza un costo total mayor que su costo mínimo actual). Al hacer esto, probablemente haya encontrado todas las rutas de menor costo.

Tenga en cuenta que la solución anterior es algo ingenua y se puede optimizar de varias maneras para obtener una matriz más pequeña. Por ejemplo, puede usar la simetría rotacional para reducir el número de celdas y agregar un costo de 1 (para girar el bastidor) a las rutas correctas, excepto por tener la bola 8 en una de las posiciones bajas del centro.

Pseudocode:

Create DP Matrix:

(1) determine number of possible arrangements, A, of balls
(2) for each arrangement, make a list of possible unique moves  
---- the possible moves are:  
------- rotating right  
------- rotating left  
------- exchanging any pair of balls  
------- exchanging any two pairs of adjacent balls  
(3) for each move in A store a pointer to the resulting arrangement  
(4) for each arrangment make an attribute indicating whether it is an end state  

Solve Problem  
(5) goto arrangement for starting position S  
(6) set best-cost-so-far (BCSF) variable to infinity
(6) breadth search from S, accumulating current cost CC as +1 for each transition
(7) if you reach an end state CC < BCSF, then set BCSF = CC and make solution list contain only the current path
(8) if you reach an end state CC = BCSF, then add path to solution list
(9) if CC > BCSF abandon branch and try next branch

The result will be a list of all possible solutions and the minimum cost BCSF.