¿Cómo puedo modelar un tablero de ajedrez cuando programo una computadora para jugar al ajedrez?

Question

¿Qué estructuras de datos usarías para representar un tablero de ajedrez para un programa de ajedrez de computadora?

Answer 1

El enfoque simple es utilizar una matriz de enteros de 8x8. Usar 0 para los cuadrados vacíos y asignar 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 

pieza se mueve se pueden calcular mediante el uso de 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 representación simple de 8x8 matriz 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 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.

Answer 2

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.

Answer 3

int[8][8] 

0=no piece 
1=king 
2=queen 
3=rook 
4=knight 
5=bishop 
6=pawn 

uso enteros positivos para ints blanco y negativas para el negro

Answer 4

Inicialmente, utilice 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 de potencia comercial de cada pieza de ajedrez)

Después de desarrollar las columnas vertebrales básicas de su aplicación y entender claramente el funcionamiento de los algoritmos utilizado, intente mejorar el rendimiento mediante el uso de tableros de bits.

En tableros de bits, utiliza 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á almacenando la posición de la torre, mientras que en otra almacenará la posición del caballero ... etc.

Las placas de bit pueden mejorar el rendimiento de su aplicación porque manipula las piezas con poco las tablas son muy fáciles y rápidas.

Como usted ha señalado,

mayoría chessprograms hoy, especialmente los que funcionan en una CPU de 64 bits, utilice 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.

Answer 5

Usaría una matriz multidimensional de modo que cada elemento de una matriz sea una referencia de cuadrícula a un cuadrado en la placa.

Así

board = arrary(A = array (1,2,3,4,5,5,6,7,8), 
       B = array (12,3,.... etc... 
       etc...   
       ) 

Entonces junta [A] [1] es entonces la tarjeta de A1 cuadrado.

En realidad, usaría números, no letras, para ayudar a mantener la lógica matemática donde las piezas pueden moverse a lo simple.

Answer 6

Existen, por supuesto, diferentes maneras de representar un tablero de ajedrez, y la mejor manera dependerá de lo que sea más importante para usted.

Sus dos opciones principales están entre la velocidad y la claridad del código.

Si la velocidad es su prioridad, 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 para Crafty (C) y SharpChess (C#).

Answer 7

Bueno, no estoy seguro 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 tenga registros de 64 bit en su hardware de destino.

Answer 8

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 esta Wikipedia article.

Answer 9

En realidad, no modelaría el tablero de ajedrez, solo modelaría la posición de las piezas. Puede tener límites para el tablero de ajedrez entonces.

Piece.x= x position of piece 
Piece.y= y position of piece 

Answer 10

Al crear mi motor de ajedrez principio fuimos con el [8] [8] enfoque, sin embargo, recientemente he cambiado de código para representar el tablero de ajedrez usando una matriz de 64 artículo. 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 las 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.

convertir de una posición en el [64] tablero elemento a un [8] [8] junta puede simplemente usar los siguientes cálculos:

Fila = (byte) (índice/8)

Col = (byte) (índice% 8)

Aunque encontré que nunca tiene que hacer eso durante la búsqueda de movimiento recursivo que es sensible al rendimiento.

Para obtener más información sobre la construcción de un motor de ajedrez, siéntase libre de visitar mi blog que describe el proceso desde cero: www.chessbin.com

Adam Berent

Answer 11

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 se puede mover a este cuadrado). Los centinelas tienen una profundidad de dos para que un caballero no pueda saltar.

Para mover hacia la derecha, agregue 1. Para mover hacia la izquierda, agregue -1. Arriba 10, abajo -10, arriba y derecha diagonal 11 etc. El cuadrado A1 es el índice 21. H1 es el índice 29. H8 es el índice 99.

Todos diseñados para la simplicidad. Pero nunca va a ser tan rápido como los bitboards.

Answer 12

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

idea básica de bitboards 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, a saber, 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, el bitboard de torres blancas se verá así:

0000000000000000000000000000000000000000000000000000000110000000 

Ahora, por ejemplo, si desea mover su torre de A2 a g2 en el ejemplo anterior, todo lo que necesita hacer es XOR que bitboard con:

0000000000000000000000000000000000000000000000000100000100000000 

Bitboards tienen una ventaja de rendimiento cuando se trata de para mover la generación También hay otras ventajas de rendimiento que surgen naturalmente de la representación de bitboards. Por ejemplo, podría usar lockless hash tables, que son una gran ventaja cuando se paralela a su algoritmo de búsqueda.

Lectura adicional

el último recurso para el desarrollo de motores de ajedrez es el Chess Programming Wiki. Recientemente escribí this chess engine, 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++.

Answer 13

Una alternativa al estándar 8x8 board es el buzón 10x12 (llamado así porque, uh, supongo que parece un buzón de correo). Esta es una matriz unidimensional que incluye sentinels alrededor de sus "bordes" para ayudar con la generación de movimientos. Se ve así:

-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 como esto (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 que había puesto pieza real objetos, donde las etiquetas son de mesa . 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.

Veamos primero a la generación de los movimientos legales para el caballero (un no-deslizamiento pieza):

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 válidos Knight movimientos son una distancia fija desde el punto de partida de la pieza, por lo que sólo necesario para verificar que esos lugares sean válidos (es decir, que no sean cuadrados centinela).

Las piezas deslizantes no son mucho más difíciles. Veamos el 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; 
} 

Éstos son algunos ejemplos:

knightMoves("h1", generateEmptyBoard()) => ["f2", "g3"] 
bishopMoves("a4", generateEmptyBoard()) => ["b3", "c2", "d1", "b5", "c6", "d7", "e8"] 

Tenga en cuenta que la función slide es una implementación general. Debería ser capaz de modelar los movimientos legales de las otras piezas deslizantes con bastante facilidad.

Answer 14

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, p. 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 también, p. tablero de ajedrez [120]; (con la matriz centinela y tablero jugando cuadrados correctamente inicializados).

Una y otra vez, para completar esta publicación, siento 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.