你会使用哪些数据结构来代表计算机国际象棋程序中的棋盘？
14个回答
18
对于一个严肃的国际象棋引擎，使用位棋盘是一种有效的方式来在内存中表示棋盘。位棋盘比任何基于数组的表示方法都要快，特别是在64位体系结构中，一个位棋盘可以适合单个CPU寄存器。
位棋盘
位棋盘的基本思想是用64位来表示每种棋子类型。在C++/C#中，它将是ulong/UInt64。因此，您将维护12个UInt64变量来表示您的棋盘：对于每种棋子类型，即兵、车、马、象、后和王，均有两个（一个黑色和一个白色）。 UInt64中的每个位将对应于棋盘上的一个方格。通常，最低有效位将是a1方格，接下来是b1，然后是c1等等按行优先方式。与棋盘上棋子位置相对应的位将设置为1，所有其他位将设置为0。例如，如果您在a2和h1上有两个白色车，则白色车的位棋盘将如下所示：
0000000000000000000000000000000000000000000000000000000110000000
例如，在上面的例子中，如果您想将您的车从a2移动到g2，则只需将您的位棋盘与以下内容进行异或操作：
0000000000000000000000000000000000000000000000000100000100000000
当涉及到移动生成时，位棋盘具有性能优势。从位棋盘表示自然而然地出现其他性能优势。例如，您可以使用 无锁哈希表，这是并行搜索算法的巨大优势。
进一步阅读
国际象棋引擎开发的终极资源是国际象棋编程Wiki。我最近用C#编写了这个实现了位棋盘的国际象棋引擎。一个更好的开源国际象棋引擎是StockFish，它也在C++中实现了位棋盘。
- bytefire
3
6位棋盘比数组表示更快，但不是因为你所说的原因。它们并不像你声称的那样轻量级（一个8x8字符数组仅有64字节），而且单个移动也并不真正更快。主要优点在于使用位掩码和移位可以在单个操作中分析多个棋盘位置。这样可以更快地生成和评估棋步。 - interjay
无锁哈希表的链接已失效。如果有其他好的参考资料就更好了！ - henrycjc
1@henrycjc 谢谢你让我知道。我在网上找不到确切的链接。这是由 Robert Hyatt 编写的，他编写了 Crafty 棋引擎。我写了一篇关于同样事情的文章：https://binarydebt.wordpress.com/2013/09/29/lockless-transposition-tables/ - bytefire
13
一开始，使用一个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的机器的替代棋盘模型。
- Niyaz
2
5如果主教和骑士都用整数3来表示，你如何区分它们？ - postfuturist
不，它们并不是用数字3来表示的。它们的材料价值相同（主教和骑士都价值约为3个兵）。 - Philipp Claßen
9
最简单的方法是使用一个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的机器的替代棋盘模型。
- slm
2
1在这个模型中，如何跟踪特定的国王或车是否已经移动，以便于王车易位？关于吃过路兵的兵的移动如何处理？ - postfuturist
1+1 steveth45。显然，所有现有的国际象棋程序都具有用于表示单个棋子的标识符，而不仅仅是表示其字符、类型或价值的整数。当然，棋子也有价值，但最重要的是它们具有唯一的ID。 - Daniel Daranas
6
120字节的数组。
这是一个8x8的棋盘，周围被哨兵方块包围（例如255表示该位置无法移动）。哨兵具有两个深度，因此马不能跳过。
向右移动加1。向左移动加-1。上10，下-10，向右上对角线11等。A1方格的索引为21。H1的索引为29。H8的索引为99。
所有设计都是为了简单性。但它永远不会像位棋盘一样快速。
- David Plumpton
4
创建我的国际象棋引擎时，我最初采用了[8][8]的方法，但最近我改变了代码，使用一个64项数组来表示国际象棋棋盘。我发现这种实现方式至少在我的情况下更有效率，效率提高了约1/3。
当使用[8][8]方法时，你需要考虑的其中一件事是描述位置。例如，如果您希望描述棋子的有效移动，则需要使用2个字节。而使用[64]项数组，您只需使用一个字节即可完成。
要将[64]项板上的位置转换为[8][8]板，您可以简单地使用以下计算：
行=（byte）（索引/ 8）
列=（byte）（索引％8）
尽管我发现在递归移动搜索期间从未必须执行该操作，因为这会影响性能敏感度。
欲了解有关构建国际象棋引擎的更多信息，请随时访问我的博客，该博客从头开始描述了该过程: www.chessbin.com 亚当·伯伦特
当使用[8][8]方法时，你需要考虑的其中一件事是描述位置。例如，如果您希望描述棋子的有效移动，则需要使用2个字节。而使用[64]项数组，您只需使用一个字节即可完成。
要将[64]项板上的位置转换为[8][8]板，您可以简单地使用以下计算：
行=（byte）（索引/ 8）
列=（byte）（索引％8）
尽管我发现在递归移动搜索期间从未必须执行该操作，因为这会影响性能敏感度。
欲了解有关构建国际象棋引擎的更多信息，请随时访问我的博客，该博客从头开始描述了该过程: www.chessbin.com 亚当·伯伦特
- Adam Berent
4
当然，有很多不同的方法来表示棋盘，最好的方法取决于您最关心什么。
您有两个主要选择：速度和代码清晰度之间的平衡。
如果速度是您的优先考虑因素，则必须为棋盘上每组棋子（例如白兵、黑后、过路兵）使用64位数据类型。然后，您可以在生成移动和测试移动合法性时利用本地位操作。
如果代码的清晰度是优先考虑因素，则忘记位移操作，转而采用像其他人已经建议的漂亮抽象数据类型。只需记住，如果您选择这种方式，您可能会更快地达到性能瓶颈。
为了帮助您入门，请查看Crafty（C）和SharpChess（C#）的代码。
您有两个主要选择：速度和代码清晰度之间的平衡。
如果速度是您的优先考虑因素，则必须为棋盘上每组棋子（例如白兵、黑后、过路兵）使用64位数据类型。然后，您可以在生成移动和测试移动合法性时利用本地位操作。
如果代码的清晰度是优先考虑因素，则忘记位移操作，转而采用像其他人已经建议的漂亮抽象数据类型。只需记住，如果您选择这种方式，您可能会更快地达到性能瓶颈。
为了帮助您入门，请查看Crafty（C）和SharpChess（C#）的代码。
- Ed Guiness
4
嗯，不确定这是否有帮助，但Deep Blue使用单个6位数字来表示棋盘上的特定位置。与使用64位位板的竞争对手相比，这有助于在芯片上节省占用空间。
由于您的目标硬件可能已经具有64位寄存器，因此这可能与您无关。
- Esa
3
标准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函数是一个通用实现。您应该能够相当容易地模拟其他滑动棋子的合法移动。- Wayne
2
使用位棋盘是一种有效的表示国际象棋棋盘状态的方法。基本思想是使用64位位集(bitset)来表示棋盘上每个方格，其中第一个位通常表示A1(左下角方格)，第64个位表示H8(对角线对面的方格)。每个玩家(黑色、白色)的每种棋子(兵、王等)都有自己的位棋盘，这12个位棋盘组成了游戏状态。更多信息请查看此维基百科文章。
- Nixuz
1
我会使用多维数组，以便于每个数组中的元素都是棋盘上一个方格的网格引用。因此，
board = arrary(A = array (1,2,3,4,5,5,6,7,8),
B = array (12,3,.... etc...
etc...
)
那么 board[A][1] 就是棋盘上 A1 格。
实际上，为了保持移动棋子的位置逻辑简单，您会使用数字而不是字母。
- Binarytales
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接