Determinar si dos posiciones de ajedrez son iguales

Question

Actualmente estoy depurando mi tabla de transposición para un motor de variante de ajedrez donde las piezas se pueden colocar (es decir, originalmente no en el tablero). Necesito saber con qué frecuencia estoy golpeando colisiones clave. Estoy guardando la lista de piezas en cada índice de tabla, junto con los datos hash habituales. Mi solución simple para determinar si dos posiciones son iguales está fallando en las transposiciones porque estoy comparando linealmente las listas de dos piezas.

Por favor, no sugiera que deba ser almacenado por centrado en la placa en lugar de centrado en la pieza. Tengo que guardar la lista de piezas debido a la naturaleza única de las piezas aplacables y capturadas. Las piezas en esos estados son como si estuvieran ocupando una ubicación superpuesta y sin posición. Mire la descripción de cómo se almacenan las piezas.

// [Piece List] 
// 
// Contents: The location of the pieces. 
//   Values 0-63 are board indexes; -2 is dead; -1 is placeable 
// Structure: Black pieces are at indexes 0-15 
//   White pieces are at indexes 16-31 
//   Within each set of colors the pieces are arranged as following: 
//   8 Pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 Queen, 1 King 
// Example: piece[15] = 6 means the black king is on board index 6 
//   piece[29] = -2 means the white rook is dead 
char piece[32]; 

A transposición ocurre cuando las piezas se mueven en un orden diferente, pero el resultado final es el mismo posición del tablero. Por ejemplo las siguientes posiciones son iguales:

1) first rook on A1; second rook on D7 
2) first rook on D7; second rook on A1 

La siguiente es una no optimizado algoritmo general; y el bucle interno es similar a otro general problem, pero con la restricción adicional de que los valores en 0-63 solo ocurrirán una vez (es decir, solo una pieza por casilla).

for each color: 
    for each piece type: 
     are all pieces in the same position, disregarding transpositions? 

La siguiente comparación no no funciona debido a transposiciones. Lo que necesito es una forma de detectar las transposiciones como iguales y solo informar posiciones realmente diferentes.

bool operator==(const Position &b) 
{ 
    for (int i = 0; i < 32; i++) 
     if (piece[i] != b.piece[i]) 
      return false; 
    return true; 
} 

Rendimiento/memoria es una consideración porque la tabla recibe más golpes 100K (donde las claves son iguales) por turno y una mesa típica tiene 1 millón de artículos. De ahora en adelante, estoy buscando algo más rápido que copiar y ordenar las listas.

Answer 1

"no sugiero que deba ser almacenado por board-centric en lugar de piece-centric".

Estás tan concentrado en no hacer eso, que echas de menos la solución obvia. Comparar específico de la placa. Para comparar dos listas de posiciones L1 y L2, coloque todos los elementos de L1 en una placa (temporal). Luego, para cada elemento de L2, verifique si está presente en la placa temporal. Si un elemento de L2 no está presente en la placa (y por lo tanto en L1), devuelve desigual.

Si después de quitar todos los elementos de L2, todavía hay piezas sobre el tablero, entonces debe haber tenido L1 elementos no presentes en L2 y las listas son iguales. L1 y L2 son iguales cuando la tabla temporal está vacía después.

Una optimización es verificar primero las longitudes de L1 y L2.Esto no solo detectará muchas discrepancias rápidamente, sino que también elimina la necesidad de eliminar los elementos de L2 del baord y la verificación de "placa vacía" al final. Eso solo es necesario para detectar el caso en el que L1 es un superconjunto verdadero de L2. Si L1 y L2 tienen el mismo tamaño, y L2 es un subconjunto de L1, entonces L1 y L2 deben ser iguales.

Answer 2

¿Por qué no mantener una cadena de 64 bytes en su base de datos que corresponde al diseño del tablero de ajedrez? Cada tipo de pieza, incluyendo 'ninguna pieza', representa una letra (mayúsculas diferentes para ambos colores, es decir, ABC para negro, abc para blanco). La comparación de la Junta se reduce a una simple comparación de cadenas.

En general, si se compara desde la perspectiva del tablero de ajedrez, en lugar de la perspectiva de la pieza, se eliminará el problema de la transposición.

Answer 3

Desde la perspectiva pieza que podría hacer esto:

for each color: 
    for each piece type: 
     start new list for board A 
     for each piece of this piece type on board A 
      add piece position to the list 
     start new list for board B 
     for each piece of this piece type on board B 
      add piece position to the list 
     order both lists and compare them 

optimizaciones pueden venir en diferentes formas. Su ventaja es: tan pronto como note una diferencia: ¡listo!

Por ejemplo, podría comenzar con un control rápido y sucio sumando todos los índices para todas las piezas, para ambos tableros. Las sumas deben ser iguales. Si no, hay una diferencia.

Si las sumas son iguales, puede comparar rápidamente las posiciones de las piezas únicas (Rey y Reina). Luego, podría escribir (en enunciados if algo complicados) las comparaciones para las piezas que están en pares. Todo lo que tienes que hacer es comparar los peones usando el método mencionado anteriormente.

Answer 4

Y una tercera opción (la verdad es que espero publicar 3 respuestas a una pregunta es aceptable, stackoverflow-sabia;)):

Siempre mantenga sus piezas del mismo tipo en el índice de orden, es decir, el primer peón en la lista siempre debe tener el índice más bajo. Si se produce un movimiento que rompe esto, solo voltea las posiciones de los peones en la lista. El uso no verá la diferencia, un peón es un peón.

Ahora, al comparar posiciones, puede estar seguro de que no hay un problema de transposición y puede simplemente usar su propuesta for-loop.

Answer 5

Teniendo en cuenta su elección de representación del estado del juego, debe ordenar los índices de los peones negros, los índices de los peones blancos, etc., de una manera u otra. Si no lo haces durante la creación de un nuevo estado de juego, tendrás que hacerlo en la comparación. Debido a que solo necesita ordenar un máximo de 8 elementos, esto puede hacerse bastante rápido.

Hay algunas alternativas para representar sus estados de juego:

• representar cada tipo de pieza como un campo de bits. Los primeros 64 bits significan que hay una pieza de este tipo en esa coordenada de la placa; luego hay n bits de "ubicables" y n bits de ranuras "muertas", que deben llenarse desde un lado (n es el número de piezas de este tipo).

o

• Dé a cada tipo de pieza una identificación única, por ejemplo, peones blancos podrían ser 0x01. Un estado del juego consiste en una matriz de 64 piezas (el tablero) y dos listas ordenadas de piezas "ubicables" y "muertas". Mantener el orden de estas listas se puede hacer bastante eficiente al insertar y eliminar.

Estas dos alternativas no tendrían un problema de transposición.

De todos modos, tengo la impresión de que estás jugando con micro-optimizaciones cuando deberías hacerlo funcionar.

Answer 6

Hay mucha investigación hecha en ajedrez de computadora y la manera de crear hash único para una posición es un problema bien conocido con una solución universal utilizada por virtualmente cada motor de ajedrez.

Lo que necesita hacer es usar Zobrist Hashing para crear una clave única (no realmente única, pero veremos más adelante por qué esto no es un problema en la práctica) para cada posición diferente. El Algorithm applied to chess is explained here.

Cuando inicia su programa, crea lo que llamamos claves zobrist. Estos son enteros aleatorios de 64 bits para cada pieza/par cuadrado. En C que tendría una matriz de 2 dimensiones como esto:

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES]; 

Cada una de esta llave se inicializan con un buen generador de números aleatorios (Advertencia: el generador de números aleatorios proporcionado con gcc o VC++ no son lo suficientemente buenos, utilice una implementación del Mersenne Twister).

Cuando la placa está vacía, configura arbitrariamente la tecla hash en 0, luego cuando agrega una pieza en la pizarra, digamos una Torre en A1, también actualiza la tecla hash haciendo una XOR de la clave zobrist para una torre en A1 con la tecla hash del tablero. Como esto (en C):

boardHash = boardHash^zobKeys[ROOK][A1]; 

Si más adelante quita la torre de esta plaza se necesita para revertir lo que acabas de hacer, ya que un XOR puede ser revertido por applaying de nuevo, sólo tiene que utilizar el mismo comando de nuevo cuando se quita la pieza:

boardHash = boardHash^zobKeys[ROOK][A1]; 

Si se mueve una pieza, dicen que la torre en goest A1 a B1, lo que necesita hacer dos XOR, uno para eliminar la torre en A1 y en añadir una torre en B2.

boardHash = boardHash^zobKeys[ROOK][A1]^boardHash^zobKeys[ROOK][B1]; 

De esta manera cada vez que modifique la placa también modificará el hash. Es muy eficiente También puede calcular el hash del scatch cada vez que escribe las zobKeys correspondientes a todas las piezas del tablero. También necesitarás XOR la ​​posición del peón que se puede tomar de pasada y el estado de las capacidades de rooking de ambos lados. Lo haces de la misma manera, creando claves zobris para cada valor posible.

Este algotitmo no garantiza que cada posición tenga un hash único, sin embargo, si usa un buen generador de números pseudoaleatorios, las probabilidades de una colisión son tan bajas que incluso si deja que su motor funcione toda su vida allí prácticamente no hay posibilidades de que se produzca una colisión.

corregir: Estoy rojo que usted está tratando de implementar esto para una variante de ajedrez que tiene piezas fuera del tablero. El hash de Zobrist sigue siendo la solución adecuada para ti. Deberá encontrar una forma de incorporar esta información en el hash.Por ejemplo, podría tener algunas claves para las piezas fuera de la mesa:

unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE]; 

Si usted tiene 2 patas del tablero y poner uno de este peón de a2, que tendrá que hacer 2 operaciones:

// remove one pawn from the off-the-board 
boardHash = boardHash^offTheBoardZobKeys[WHITE_PAWN][numberOfWhitePawsOffTheBoard]; 

// Put a pawn on a2 
boardHash = boardHash^zobKeys[WHITE_PAWN][A2]; 

Answer 7

Su principal objeción a almacenar los estados a bordo es que tiene una bolsa de piezas sin posición. ¿Por qué no mantener un tablero + un vector de piezas? Esto cumpliría con sus requisitos y tiene la ventaja de que es una representación canónica para sus estados. Por lo tanto no es necesario la clasificación, y se utiliza ya sea esta representación interna o convertir a ella cuando es necesario comparar:

Piece-type in A1 
... 63 more squares 
Number of white pawns off-board 
Number of black pawns off-board 
... other piece types