在编程计算机下棋时如何对棋盘进行建模？

在梵高的星空下 2024-07-11 05:57:52

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

位板

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

0000000000000000000000000000000000000000000000000000000110000000

现在例如，如果您想在上面的示例中将车从 a2 移动到 g2，您所需要做的就是将位板与位板进行异或：

0000000000000000000000000000000000000000000000000100000100000000

位板在移动生成方面具有性能优势。位板表示还具有其他性能优势。例如，您可以使用无锁哈希表，这在并行搜索时具有巨大的优势算法。

进一步阅读

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

For a serious chess engine, using bitboards is an efficient way to represent a chess board in memory. Bitboards are faster than any array based representation, specially in 64-bit architectures where a bitboard can fit inside a single CPU register.

Bitboards

Basic idea of bitboards is to represent every chess piece type in 64 bits. In C++/C# it will be ulong/UInt64. So you'll maintain 12 UInt64 variables to represent your chess board: two (one black and one white) for each piece type, namely, pawn, rook, knight, bishop, queen and king. Every bit in a UInt64 will correspond to a square on chessboard. Typically, the least significant bit will be a1 square, the next b1, then c1 and so on in a row-major fashion. The bit corresponding to a piece's location on chess board will be set to 1, all others will be set to 0. For example, if you have two white rooks on a2 and h1 then the white rooks bitboard will look like this:

0000000000000000000000000000000000000000000000000000000110000000

Now for example, if you wanted to move your rook from a2 to g2 in the above example, all you need to do is XOR you bitboard with:

0000000000000000000000000000000000000000000000000100000100000000

Bitboards have a performance advantage when it comes to move generation. There are other performance advantages too that spring naturally from bitboards representation. For example you could use lockless hash tables which are an immense advantage when parallelising your search algorithm.

Further Reading

The ultimate resource for chess engine development is the Chess Programming Wiki. I've recently written this chess engine which implements bitboards in C#. An even better open source chess engine is StockFish which also implements bitboards but in C++.

回复收藏 0 原文

晚风撩人 2024-07-11 05:57:52

最初，使用 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。

Initially, use an 8 * 8 integer array to represent the chess board.

You can start programing using this notation. Give point values for the pieces. For example:

**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. (Note that the points given above are approximations of trading power of each chess piece)

After you develop the basic backbones of your application and clearly understand the working of the algorithms used, try to improve the performance by using bit boards.

In bit boards, you use eight 8 -bit words to represent the boards. This representation needs a board for each chess piece. In one bit board you will be storing the position of the rook while in another you will be storing the position of the knight... etc

Bit boards can improve the performance of your application very much because manipulating the pieces with bit boards are very easy and fast.

As you pointed out,

Most chessprograms today, especially
those that run on a 64 bit CPU, use a
bitmapped approach to represent a
chessboard and generate moves. x88 is
an alternate board model for machines
without 64 bit CPUs.

回复收藏 0 原文

一张白纸 2024-07-11 05:57:52

简单的方法是使用 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 的机器的替代板模型。

The simple approach is to use an 8x8 integer array. Use 0 for empty squares and assign values for the pieces:

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

Piece moves can be calculated by using the array indexes. For example the white pawns move by increasing the row index by 1, or by 2 if it's the pawn's first move. So the white pawn on [2][1] could move to [3][1] or [4][1].

However this simple 8x8 array representation of has chessboard has several problems. Most notably when you're moving 'sliding' pieces like rooks, bishops and queens you need to constantly be checking the indexes to see if the piece has moved off the board.

Most chessprograms today, especially those that run on a 64 bit CPU, use a bitmapped approach to represent a chessboard and generate moves. x88 is an alternate board model for machines without 64 bit CPUs.

回复收藏 0 原文

木森分化 2024-07-11 05:57:52

120 字节的数组。

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

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

所有设计都是为了简单。但它永远不会像位板那么快。

回复收藏 0 原文

想念有你 2024-07-11 05:57:52

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

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

回复收藏 0 原文

纵情客 2024-07-11 05:57:52

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

在执行 [8][8] 方法时要考虑的事情之一是描述位置。例如，如果您希望描述棋子的有效移动，则需要 2 个字节。而使用 [64] 项数组时，您可以用一个字节来完成。

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

Row= (byte)(index / 8)

Col = (byte)(index % 8)

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

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

亚当·贝伦特

回复收藏 0 原文

鸩远一方 2024-07-11 05:57:52

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

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

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

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

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

回复收藏 0 原文

不…忘初心 2024-07-11 05:57:52

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

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

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

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 函数是一个通用实现。您应该能够相当轻松地模拟其他滑动件的合法移动。

An alternative to the standard 8x8 board is the 10x12 mailbox (so-called because, uh, I guess it looks like a mailbox). This is a one-dimensional array that includes sentinels around its "borders" to assist with move generation. It looks like this:

-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

You can generate that array like this (in 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));
}

Of course, in a real implementation you'd put actual piece objects where the board labels are. But you'd keep the negative ones (or something equivalent). Those locations make move generation a lot less painful because you can easily tell when you've run off the board by checking for that special value.

Let's first look at generating the legal moves for the knight (a non-sliding piece):

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

We know that the valid Knight moves are a fixed distance from the piece's starting point, so we only needed to check that those locations are valid (i.e. not sentinel squares).

The sliding pieces aren't much harder. Let's look at the bishop:

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

Here are some examples:

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

Note that the slide function is a general implementation. You should be able to model the legal moves of the other sliding pieces fairly easily.

回复收藏 0 原文

愿与i 2024-07-11 05:57:52

使用位板是表示棋盘状态的有效方法。基本思想是使用 64 位位集来表示棋盘上的每个方块，其中第一位通常表示 A1（左下方块），第 64 位表示 H8（对角相对的方块）。每个玩家（黑棋、白棋）的每种棋子（兵、王等）都有自己的棋盘，所有 12 个棋盘构成了游戏状态。有关更多信息，请查看这篇维基百科文章。

回复收藏 0 原文

韵柒 2024-07-11 05:57:52

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

因此

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

，board[A][1] 就是棋盘方格 A1。

实际上，您会使用数字而不是字母来帮助保持数学逻辑，以便让棋子变得简单。

I would use a multidimensional array so that each element in an array is a grid reference to a square on the board.

Thus

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

Then board[A][1] is then the board square A1.

In reality you would use numbers not letters to help keep your maths logic for where pieces are allowed to move to simple.

回复收藏 0 原文

活泼老夫 2024-07-11 05:57:52

int[8][8]

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

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

int[8][8]

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

use positive ints for white and negative ints for black

回复收藏 0 原文

亣腦蒛氧 2024-07-11 05:57:52

实际上我不会对棋盘进行建模，我只会对棋子的位置进行建模。
那么你就可以确定棋盘的界限了。

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

I actually wouldn't model the chess board, I'd just model the position of the pieces.
You can have bounds for the chess board then.

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

回复收藏 0 原文

很糊涂小朋友 2024-07-11 05:57:52

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

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

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

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

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

回复收藏 0 原文

我纯我任性 2024-07-11 05:57:52

数组可能没问题。如果您想要更方便的方式“遍历”棋盘，您可以轻松构建方法来抽象数据结构实现的细节。

回复收藏 0 原文

在编程计算机下棋时如何对棋盘进行建模？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（14）

关于作者

相关话题

热门标签

推荐作者

游缘惊梦

小兔几

Glik

生生漫

Luxian

Champion-Ming

友情链接

在编程计算机下棋时如何对棋盘进行建模？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（14）

关于作者

相关话题

热门标签

推荐作者

游缘惊梦

小兔几

Glik

生生漫

Luxian

Champion-Ming

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。