¿Cuál es la mejor estructura de datos para representar un tablero de damas cuando la velocidad es la principal preocupación?

Question

Actualmente estoy implementando algo bastante similar a las damas. Entonces, tengo este juego de mesa y hay piezas blancas y negras. Donde no hay piezas blancas o negras, no tienes piezas.

Actualmente estoy haciendo el método GetValidMoves() que devolverá todos los movimientos actuales que uno puede hacer con la placa actual.

Por lo tanto, me pregunto cuál podría ser la mejor manera de representar a la junta. El enfoque ingenuo sería tener una matriz con 0's 1's y 2's (para ninguna pieza, pieza blanca y pieza negra).

Otra idea sería, en lugar de una representación matricial de la placa, tener 2 listas (o cualquier otra estructura de datos): una para piezas negras, otra para blanco.

Estoy implementando este juego para probar algunos algoritmos de IA, por lo que mi principal preocupación es la velocidad. Básicamente pondré a 2 jugadores de IA jugando entre sí, por cada turno cada jugador debería tener una lista de todos sus movimientos válidos y luego elegirá qué movimiento hacer, esto siempre sucederá hasta que el juego termine (algún jugador gana o hay un jugador). Corbata).

PS: No estoy preguntando por el algoritmo de AI, sólo quiero saber cuál sería la mejor estructura de datos para manejar el tablero, por lo que hace que sea fácil de

1. Busque todas las movimientos válidos para el jugador actual
2. Hacer un movimiento
3. Verificar que el juego no haya terminado (se termina cuando un jugador perdió todas sus piezas o un jugador llegó al otro lado del tablero).

Answer 1

Considere usar un mapa de bits: dos entradas de 64 bits sin signo, una para blanco y otra para negro. A continuación, puede representar los movimientos y las posiciones de la placa como una función desde (W x B) -> (W x B) donde W, B representan el conjunto de posibles posiciones blancas y negras posibles, respectivamente.

Luego, la mayor parte de la posición de la placa se puede hacer con aritmética entera, que es lo más rápida que se puede obtener.

Answer 2

También usaría un mapa de bits para esto. Las funciones para verificar 1, 2 y 3 serán un poco intuitivas de escribir, pero deberían ser muy rápidas.

Por supuesto, tendrá que tener cuidado con los casos de borde y una solución rápida probablemente implicará un número entero y una aritmética modular en los índices.

Answer 3

Una forma común de hacerlo es con una representación binaria del tipo long para cada jugador.
(ya que hay 64 cuadrados en el tablero) .. Como Charlie ya dijo ...
Aquí hay un muy bueno (pero generalmente general) wiki article.

El uso es simple; por ejemplo, si desea comprobar si todas las piezas se pueden mover hacia arriba y hacia la derecha, cambie la represntación de las piezas del jugador 7 bits hacia la izquierda y compruebe si hay piezas oponentes allí, luego cámbielas 7 bits restantes y compruebe si esos cuadrados están claros ...
Lo usé en una competencia de Reversi una vez, y puedo decir que la implementación no fue muy difícil.
HTH.

Answer 4

En términos de listas, recomendaría no usar una estructura que use listas enlazadas en esta situación. Es probable que ya conozca las posiciones que desea investigar (coordenadas x y y), por lo que una lista vinculada requeriría O(n) tiempo para simplemente tomar el valor del espacio de tablero de ajedrez. Como otras respuestas han mencionado, un mapa de bits o enfoque largo sería ideal.

En términos de cómo organizar los datos, me imagino que una implementación donde tanto el blanco como el negro se almacenan en la misma estructura sería ideal. Tendrá algunos gastos generales ya que almacenar 2 y 3 en formato binario requiere la misma cantidad de memoria, aunque si está escribiendo cheques, es probable que necesite almacenar datos "emparejados" de todos modos. Tener la capacidad de verificar si un espacio está abierto realizando una única búsqueda debería proporcionar un beneficio significativo en el rendimiento.

Espero que esto ayude.

Answer 5

En primer lugar, vale la pena señalar que en las damas, la mitad de los cuadrados en los tableros nunca se pueden usar, por lo que realmente solo necesitas una colección de 32 elementos, no 64. Tomando reyes en cuenta, obtienes posibilidades de 0 a 4 en lugar de 0 a 2 (aunque cuando lo hice, me resultó más fácil usar -3 a +3, por lo que los valores para rojo y negro tienen la misma magnitud y signos opuestos).

Answer 6

Depende de lo que vayan a hacer los algoritmos de su IA. La mayoría de los algoritmos de IA realizarían algún tipo de búsqueda sobre las posibles movidas al menos varios pasos adelante. En ese caso, estará haciendo muchas copias de su representación en la pizarra y tiene sentido tratar de mantenerlo pequeño ya que el tiempo para copiar su estructura de datos dominará el tiempo para obtener una lista de movimientos posibles, así como también limitar la profundidad a que puedes buscar

Sin embargo, si no está buscando, crearía una Pieza de clase y almacenaría el color, la ubicación y si la pieza es un rey. Luego tendría una matriz bidimensional de 8 por 8 referencias a Piezas y una lista enlazada de piezas negras y una lista enlazada de piezas rojas. Cada elemento de la matriz apuntaría a una pieza de la lista roja o negra o a una pieza "vacía" (nulo funcionaría para esto). Cuando mueve una pieza, simplemente actualiza el objeto Piece en la lista y mueve la referencia desde su ubicación actual a la nueva ubicación, configurando la ubicación anterior en la pieza vacía. Por un ligero aumento en el costo de una actualización, se obtiene una forma eficiente de iterar sobre cualquiera de las partes laterales y una búsqueda de tiempo constante del estado de cualquier punto en particular en el tablero.

Tendría que repetir la lista completa para eliminar una pieza muerta, sin embargo, esto también puede hacerse eficiente con un ligero cambio en la pieza. Puede almacenar un bool "muerto" en el objeto Pieza. Cuando se mata una pieza, establezca su valor verdadero y elimínelo del tablero reemplazando la referencia con la pieza vacía. Cuando iteras a través de una lista de piezas, simplemente elimina cualquier pieza marcada como muerta de la lista.