chess - una - programa para resolver problemas de ajedrez
¿Cómo modelo un tablero de ajedrez cuando programo una computadora para jugar al ajedrez? (14)
¿Qué estructuras de datos usarías para representar un tablero de ajedrez para un programa de ajedrez de computadora?
Bueno, no estoy seguro de si esto ayuda, pero Deep Blue usó un solo número de 6 bits para representar una posición específica en el tablero. Esto le ayudó a ahorrar espacio en el chip en comparación con su competidor, que usó un bitboard de 64 bits.
Esto podría no ser relevante, ya que es posible que ya tengas registros de 64 bits en tu hardware objetivo.
El enfoque simple es usar una matriz de enteros de 8x8. Use 0 para cuadrados vacíos y asigne valores para las piezas:
1 white pawns
2 white knights
3 white bishops
4 white rooks
5 white queens
6 white king
Black pieces use negative values
-1 black pawn
-2 black knight
etc
8| -4 -2 -3 -5 -6 -3 -2 -4
7| -1 -1 -1 -1 -1 -1 -1 -1
6| 0 0 0 0 0 0 0 0
5| 0 0 0 0 0 0 0 0
4| 0 0 0 0 0 0 0 0
3| 0 0 0 0 0 0 0 0
2| 1 1 1 1 1 1 1 1
1| 4 2 3 5 6 3 2 4
-------------------------
1 2 3 4 5 6 7 8
Los movimientos de piezas se pueden calcular utilizando los índices de matriz. Por ejemplo, los peones blancos se mueven al aumentar el índice de fila en 1 o en 2 si es el primer movimiento del peón. Entonces el peón blanco en [2] [1] podría moverse a [3] [1] o [4] [1].
Sin embargo, esta simple representación de matriz de 8x8 tiene tablero de ajedrez. Tiene varios problemas. Lo más notable es que cuando mueves piezas "deslizantes" como torres, obispos y reinas, necesitas estar constantemente revisando los índices para ver si la pieza se ha movido del tablero.
La mayoría de los programas de ajedrez hoy en día, especialmente los que se ejecutan en una CPU de 64 bits, utilizan un enfoque de mapa de bits para representar un tablero de ajedrez y generar movimientos. x88 es un modelo de placa alternativa para máquinas sin CPU de 64 bits.
Inicialmente, use una matriz de enteros 8 * 8 para representar el tablero de ajedrez.
Puede comenzar a programar usando esta notación. Da valores de puntos para las piezas. Por ejemplo:
**White**
9 = white queen
5 = white rook
3 = bishop
3 = knight
1 = pawn
**black**
-9 = white queen
-5 = white rook
-3 = bishop
-3 = knight
-1 = pawn
White King: very large positive number
Black King: very large negative number
etc. (Tenga en cuenta que los puntos indicados anteriormente son aproximaciones del poder de negociación de cada pieza de ajedrez)
Después de desarrollar las estructuras principales de su aplicación y entender claramente el funcionamiento de los algoritmos utilizados, intente mejorar el rendimiento mediante el uso de tableros de bits.
En tableros de bits, usa ocho palabras de 8 bits para representar las tablas. Esta representación necesita un tablero para cada pieza de ajedrez. En una placa de bit, estarás almacenando la posición de la torre, mientras que en otra estarás almacenando la posición del caballero ... etc.
Los tableros de bits pueden mejorar mucho el rendimiento de su aplicación porque manipular las piezas con tarjetas de bit es muy fácil y rápido.
Como usted señaló,
La mayoría de los programas de ajedrez actuales, especialmente los que se ejecutan en una CPU de 64 bits, utilizan un enfoque de mapa de bits para representar un tablero de ajedrez y generar movimientos. x88 es un modelo de placa alternativa para máquinas sin CPU de 64 bits.
Una matriz probablemente estaría bien. Si deseaba medios más convenientes para "atravesar" el tablero, podría crear fácilmente métodos para abstraer los detalles de la implementación de la estructura de datos.
Utilizaría una matriz multidimensional para que cada elemento de una matriz sea una referencia de cuadrícula a un cuadrado en la pizarra.
Así
board = arrary(A = array (1,2,3,4,5,5,6,7,8),
B = array (12,3,.... etc...
etc...
)
Entonces el tablero [A] [1] es entonces el tablero cuadrado A1.
En realidad, utilizaría números, no letras, para ayudar a mantener su lógica matemática donde las piezas pueden moverse a lo simple.
int[8][8]
0=no piece
1=king
2=queen
3=rook
4=knight
5=bishop
6=pawn
utilice las entradas positivas para las notas blancas y negativas para las negras
De hecho, no modelaría el tablero de ajedrez, solo modelaría la posición de las piezas. Puedes tener límites para el tablero de ajedrez entonces.
Piece.x= x position of piece
Piece.y= y position of piece
Usar un bitboard sería una forma eficiente de representar el estado de un tablero de ajedrez. La idea básica es que use bitsets de 64 bits para representar cada uno de los cuadrados en el tablero, donde el primer bit generalmente representa A1 (el cuadrado inferior izquierdo), y el bit 64 representa H8 (el cuadrado diagonalmente opuesto). Cada tipo de pieza (peón, rey, etc.) de cada jugador (negro, blanco) tiene su propia tabla de bits y las 12 de estas tablas conforman el estado del juego. Para obtener más información, consulte este artículo de Wikipedia.
Al crear mi motor de ajedrez, al principio opté por el enfoque [8] [8], sin embargo recientemente cambié mi código para representar el tablero de ajedrez usando una matriz de 64 elementos. Descubrí que esta implementación era aproximadamente 1/3 más eficiente, al menos en mi caso.
Una de las cosas que desea considerar al hacer el enfoque [8] [8] es describir posiciones. Por ejemplo, si desea describir un movimiento válido para una pieza de ajedrez, necesitará 2 bytes para hacerlo. Mientras que con el conjunto de elementos [64] puedes hacerlo con un byte.
Para convertir desde una posición en el tablero de elementos [64] a un tablero [8] [8], puede simplemente usar los siguientes cálculos:
Fila = (byte) (índice / 8)
Col = (byte) (índice% 8)
Aunque descubrí que nunca tienes que hacer eso durante la búsqueda recursiva de movimientos, que es sensible al rendimiento.
Para obtener más información sobre la construcción de un motor de ajedrez, no dude en visitar mi blog que describe el proceso desde cero: www.chessbin.com
Adam Berent
Matriz de 120 bytes.
Este es un tablero de ajedrez de 8x8 rodeado de cuadrados centinela (por ejemplo, un 255 para indicar que una pieza no puede moverse a este cuadrado). Los centinelas tienen una profundidad de dos para que un caballero no pueda saltar.
Para moverse hacia la derecha, agregue 1. Para mover hacia la izquierda, agregue -1. Arriba 10, abajo -10, arriba y diagonal derecha, etc. El cuadrado A1 es el índice 21. H1 es el índice 29. H8 es el índice 99.
Todo diseñado por simplicidad. Pero nunca va a ser tan rápido como los bitboards.
Por supuesto, hay varias formas diferentes de representar un tablero de ajedrez, y la mejor manera dependerá de lo que sea más importante para ti.
Sus dos opciones principales son entre la velocidad y la claridad del código.
Si la velocidad es su prioridad, entonces debe usar un tipo de datos de 64 bits para cada conjunto de piezas en el tablero (por ejemplo, peones blancos, reinas negras, peones en passant). A continuación, puede aprovechar las operaciones de bit a bit nativas al generar movimientos y probar la legalidad de movimiento.
Si la claridad del código es la prioridad, entonces olvídate de barajar los bits e ir por tipos de datos abstractos como otros ya han sugerido. Solo recuerda que si vas por este camino, probablemente alcanzarás un techo de rendimiento antes.
Para comenzar, mire el código de Crafty (C) y SharpChess (C #).
Para un motor de ajedrez serio, usar bitboards es una forma eficiente de representar un tablero de ajedrez en la memoria. Los bitboards son más rápidos que cualquier representación basada en arreglos, especialmente en arquitecturas de 64 bits donde un bitboard puede caber dentro de un único registro de CPU.
Bitboards
La idea básica de las tablas de bits es representar cada tipo de pieza de ajedrez en 64 bits. En C ++ / C # será ulong/UInt64 . Por lo tanto, mantendrá 12 variables UInt64 para representar su tablero de ajedrez: dos (una negra y una blanca) para cada tipo de pieza, es decir, peón, torre, caballero, alfil, reina y rey. Cada bit en un UInt64 corresponderá a un cuadrado en el tablero de ajedrez. Típicamente, el bit menos significativo será a1 cuadrado, el próximo b1, luego c1 y así sucesivamente en una fila de mayor moda. El bit correspondiente a la ubicación de una pieza en el tablero de ajedrez se establecerá en 1, todos los demás se establecerán en 0. Por ejemplo, si tiene dos torres blancas en a2 y h1, entonces el tablero de bits de torres blancas se verá así:
0000000000000000000000000000000000000000000000000000000110000000
Ahora, por ejemplo, si quieres mover tu torre de a2 a g2 en el ejemplo anterior, todo lo que tienes que hacer es XOR tu bitboard con:
0000000000000000000000000000000000000000000000000100000100000000
Los bitboards tienen una ventaja de rendimiento cuando se trata de mover la generación. También hay otras ventajas de rendimiento que surgen naturalmente de la representación de bitboards. Por ejemplo, puede usar tablas hash sin bloqueo que son una gran ventaja cuando se paralela a su algoritmo de búsqueda.
Otras lecturas
El último recurso para el desarrollo del motor de ajedrez es la Wiki de programación de ajedrez . Recientemente escribí este motor de ajedrez que implementa bitboards en C #. Un motor de ajedrez de fuente abierta aún mejor es StockFish que también implementa bitboards pero en C ++.
Una alternativa a la placa estándar de 8x8 es el buzón de 10x12 (llamado porque, uh, supongo que parece un buzón de correo). Esta es una matriz unidimensional que incluye centinelas alrededor de sus "fronteras" para ayudar con la generación de movimiento. Se parece a esto:
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, "a8", "b8", "c8", "d8", "e8", "f8", "g8", "h8", -1,
-1, "a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7", -1,
-1, "a6", "b6", "c6", "d6", "e6", "f6", "g6", "h6", -1,
-1, "a5", "b5", "c5", "d5", "e5", "f5", "g5", "h5", -1,
-1, "a4", "b4", "c4", "d4", "e4", "f4", "g4", "h4", -1,
-1, "a3", "b3", "c3", "d3", "e3", "f3", "g3", "h3", -1,
-1, "a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2", -1,
-1, "a1", "b1", "c1", "d1", "e1", "f1", "g1", "h1", -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Puede generar esa matriz de esta manera (en JavaScript):
function generateEmptyBoard() {
var row = [];
for(var i = 0; i < 120; i++) {
row.push((i < 20 || i > 100 || !(i % 10) || i % 10 == 9)
? -1
: i2an(i));
}
return row;
}
// converts an index in the mailbox into its corresponding value in algebraic notation
function i2an(i) {
return "abcdefgh"[(i % 10) - 1] + (10 - Math.floor(i / 10));
}
Por supuesto, en una implementación real colocaría objetos reales donde están las etiquetas de la placa. Pero mantendrías los negativos (o algo equivalente). Esos lugares hacen que la generación de movimiento sea mucho menos dolorosa porque usted puede saber fácilmente cuándo ha salido del tablero al buscar ese valor especial.
Primero veamos cómo generar los movimientos legales para el caballero (una pieza no deslizante):
function knightMoves(square, board) {
var i = an2i(square);
var moves = [];
[8, 12, 19, 21].forEach(function(offset) {
[i + offset, i - offset].forEach(function(pos) {
// make sure we''re on the board
if (board[pos] != -1) {
// in a real implementation you''d also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
});
});
return moves;
}
// converts a position in algebraic notation into its location in the mailbox
function an2i(square) {
return "abcdefgh".indexOf(square[0]) + 1 + (10 - square[1]) * 10;
}
Sabemos que los movimientos válidos de Knight están a una distancia fija del punto de partida de la pieza, por lo que solo necesitamos verificar que esos lugares sean válidos (es decir, que no sean cuadrados centinela).
Las piezas deslizantes no son mucho más difíciles. Miremos al obispo:
function bishopMoves(square, board) {
var oSlide = function(direction) {
return slide(square, direction, board);
}
return [].concat(oSlide(11), oSlide(-11), oSlide(9), oSlide(-9));
}
function slide(square, direction, board) {
var moves = [];
for(var pos = direction + an2i(square); board[pos] != -1; pos += direction) {
// in a real implementation you''d also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
return moves;
}
Aquí hay unos ejemplos:
knightMoves("h1", generateEmptyBoard()) => ["f2", "g3"]
bishopMoves("a4", generateEmptyBoard()) => ["b3", "c2", "d1", "b5", "c6", "d7", "e8"]
Tenga en cuenta que la función de slide es una implementación general. Debería ser capaz de modelar los movimientos legales de las otras piezas deslizantes con bastante facilidad.
Sé que esta es una publicación muy antigua con la que me he topado varias veces cuando busco en Google la programación de ajedrez, pero creo que debo mencionar que es perfectamente posible modelar un tablero de ajedrez con una matriz 1D, por ejemplo, un tablero de ajedrez [64];
Yo diría que este es el enfoque más simple para la representación de tablero de ajedrez ... pero, por supuesto, es un enfoque básico.
¿Es una estructura de matriz de tablero 1D más eficiente que una matriz 2D (que necesita un bucle anidado para acceder y manipular los índices)?
También es posible usar una matriz 1D con más de 64 cuadrados para representar cuadrados OffBoard, por ejemplo, tablero de ajedrez [120]; (con la matriz centinela y tablero jugando cuadrados correctamente inicializados).
Finalmente, y para completar esta publicación, creo que debo mencionar la representación de la matriz 0x88. Esta es una forma bastante popular de representar un tablero de ajedrez que también cuenta con cuadrados externos.