chess - 在编程计算机下棋时如何为棋盘建模？

Question

您将使用哪些数据结构来表示计算机国际象棋程序的棋盘？

score 15 · Accepted Answer

对于一个严肃的国际象棋引擎，使用位板是一种在内存中表示棋盘的有效方法。位板比任何基于数组的表示都快，特别是在 64 位架构中，位板可以放入单个 CPU 寄存器中。

位板

位板的基本思想是用 64 位表示每种棋子类型。在 C++/C# 中，它将是ulong/UInt64. 因此，您将维护 12 个UInt64变量来表示您的棋盘：每种棋子类型有两个（一个黑色和一个白色），即典当、车、马、主教、皇后和国王。a 中的每一位UInt64都将对应棋盘上的一个正方形。通常，最低有效位将是 a1 平方，下一个是 b1，然后是 c1，以此类推，以行优先的方式。与棋盘上棋子位置对应的位将设置为 1，所有其他将设置为 0。例如，如果您在 a2 和 h1 上有两个白车，那么白车位将如下所示：

0000000000000000000000000000000000000000000000000000000110000000

现在例如，如果你想在上面的例子中将你的车从 a2 移动到 g2，你需要做的就是 XOR 你的位板：

0000000000000000000000000000000000000000000000000100000100000000

在移动生成方面，位板具有性能优势。还有其他性能优势也可以从位板表示中自然而然地产生。例如，您可以使用无锁哈希表，这在并行化您的搜索算法时是一个巨大的优势。

延伸阅读

国际象棋引擎开发的终极资源是国际象棋编程维基。我最近编写了这个用 C# 实现位板的国际象棋引擎。一个更好的开源国际象棋引擎是StockFish，它也使用 C++ 实现了位板。

score 13 · Accepted Answer

最初，使用一个8 * 8 整数数组来表示棋盘。

您可以使用此符号开始编程。给出碎片的点值。例如：

**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

等（请注意，上面给出的点是每个棋子的交易能力的近似值）

在您开发了应用程序的基本主干并清楚地了解所使用算法的工作原理后，请尝试使用位板来提高性能。

在位板中，您使用八个 8 位字来表示板。这种表示需要每个棋子都有一个棋盘。在一个位板上，您将存储车的位置，而在另一个板上，您将存储骑士的位置......等等

位板可以极大地提高您的应用程序的性能，因为使用位板操作部件非常容易和快速。

正如你所指出的，

今天的大多数国际象棋程序，尤其是那些在 64 位 CPU 上运行的程序，都使用位图方法来表示棋盘并生成棋步。x88 是没有 64 位 CPU 的机器的备用板模型。

score 9 · Accepted Answer

简单的方法是使用 8x8 整数数组。对空方格使用 0 并为棋子赋值：

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

棋子移动可以通过使用数组索引来计算。例如，白色棋子通过将行索引增加 1 来移动，如果这是棋子的第一步，则增加 2。因此，[2][1] 上的白兵可以移动到 [3][1] 或 [4][1]。

然而，这个简单的 8x8 数组表示有棋盘有几个问题。最值得注意的是，当您移动“滑动”棋子（如车、主教和皇后）时，您需要不断检查索引以查看棋子是否已移出棋盘。

今天的大多数国际象棋程序，尤其是那些在 64 位 CPU 上运行的程序，都使用位图方法来表示棋盘并生成棋步。x88 是没有 64 位 CPU 的机器的备用板模型。

score 6 · Accepted Answer

120 字节的数组。

这是一个 8x8 的棋盘，周围环绕着哨兵方格（例如，255 表示棋子无法移动到该方格）。哨兵的深度为二，因此骑士无法跳过。

向右移动加1。向左移动加-1。向上 10，向下 -10，上下对角线 11 等。正方形 A1 是索引 21。H1 是索引 29。H8 是索引 99。

一切都是为了简单而设计的。但它永远不会像位板一样快。

score 4 · Accepted Answer

当然，有许多不同的方式来表示棋盘，最好的方式取决于对你来说最重要的方式。

您的两个主要选择是在速度和代码清晰度之间。

如果速度是您的首要任务，那么您必须为棋盘上的每组棋子使用 64 位数据类型（例如白棋子、黑棋子、过路棋子）。然后，您可以在生成移动和测试移动合法性时利用本机按位运算。

如果代码的清晰性是优先考虑的，那么忘记位改组并像其他人已经建议的那样选择很好的抽象数据类型。请记住，如果您采用这种方式，您可能会更快地达到性能上限。

首先，请查看Crafty (C) 和SharpChess (C#) 的代码。

score 4 · Accepted Answer

好吧，不确定这是否有帮助，但 Deep Blue 使用了一个 6 位数字来表示棋盘上的特定位置。与使用 64 位位板的竞争对手相比，这有助于它节省芯片上的占用空间。

这可能不相关，因为很有可能您的目标硬件上已经有 64 位寄存器。

score 4 · Accepted Answer

创建国际象棋引擎时，我最初使用 [8][8] 方法，但最近我更改了代码以使用 64 项数组来表示棋盘。我发现这种实现效率提高了大约 1/3，至少在我的情况下是这样。

在执行 [8][8] 方法时，您要考虑的一件事是描述职位。例如，如果你想描述一个棋子的有效移动，你将需要 2 个字节来这样做。而使用 [64] 项目数组，您可以用一个字节来完成。

要将 [64] 项目板上的位置转换为 [8][8] 板上的位置，您可以简单地使用以下计算：

行=（字节）（索引/ 8）

Col =（字节）（索引 % 8）

尽管我发现在对性能敏感的递归移动搜索期间您永远不必这样做。

有关构建国际象棋引擎的更多信息，请随时访问我的博客，该博客描述了从头开始的过程：www.chessbin.com

亚当·贝伦特

score 3 · Accepted Answer

标准8x8 板的替代品是10x12邮箱（所谓的因为，呃，我猜它看起来像邮箱）。这是一个一维数组，包括围绕其“边界”的哨兵，以协助移动生成。它看起来像这样：

-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

您可以像这样（在 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));
}

当然，在实际实现中，您会将实际的块对象放在板标签所在的位置。但是你会保留负面的（或同等的）。这些位置使移动生成变得不那么痛苦，因为您可以通过检查该特殊值轻松判断何时跑出棋盘。

让我们首先看一下为骑士生成合法移动（非滑动棋子）：

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;
}

我们知道有效的骑士移动距离棋子起点的距离是固定的，所以我们只需要检查这些位置是否有效（即不是哨兵方格）。

滑动件并不难。让我们看看主教：

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;
}

这里有些例子：

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

请注意，该slide函数是通用实现。您应该能够相当容易地模拟其他滑动件的合法移动。

score 2 · Accepted Answer

使用位板将是表示棋盘状态的有效方法。基本思想是使用 64 位位集来表示板上的每个方格，其中第一位通常表示 A1（左下方格），第 64 位表示 H8（斜对面方格）。每个玩家（黑、白）的每种类型的棋子（棋子、国王等）都有自己的位棋盘，所有 12 个棋盘构成游戏状态。有关更多信息，请查看此 Wikipedia文章。

score 1 · Accepted Answer

我将使用多维数组，以便数组中的每个元素都是对板上正方形的网格引用。

因此

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

那么board[A][1]就是棋盘正方形 A1。

实际上，您将使用数字而不是字母来帮助保持您的数学逻辑，以使您可以将部分移动到简单的位置。

score 0 · Accepted Answer

int[8][8]

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

对白色使用正整数，对黑色使用负整数

score 0 · Accepted Answer

我知道这是一个非常古老的帖子，我在谷歌国际象棋编程时偶然发现了几次，但我觉得我必须提到用一维数组对棋盘进行建模是完全可行的，例如 chessboard[64]；

我会说这是棋盘表示的最简单方法......但当然它是一种基本方法。

一维棋盘数组结构是否比二维数组更有效（需要嵌套的 for 循环来访问和操作索引）？

也可以使用超过 64 个方格的一维数组来表示 OffBoard 方格，例如 chessboard[120]；（正确初始化阵列哨兵和棋盘游戏方块）。

最后，为了这篇文章的完整性，我觉得我必须提到 0x88 板阵列表示。这是一种非常流行的表示棋盘的方式，它也考虑了棋盘外的方格。

score 0 · Accepted Answer

我实际上不会为棋盘建模，我只是为棋子的位置建模。那么你可以为棋盘设置界限。

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

score -4 · Accepted Answer

一个数组可能会很好。如果您想要更方便的“遍历”板子的方法，您可以轻松地构建方法来抽象出数据结构实现的细节。

chess - 在编程计算机下棋时如何为棋盘建模？

14 回答 14

Related

Reference