对计算机编程以下棋时，如何为棋盘建模？ [英] How do I model a chessboard when programming a computer to play chess?

问题描述

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

What data structures would you use to represent a chessboard for a computer chess program?

推荐答案

对于严肃的国际象棋引擎，使用位板是在内存中表示棋盘的一种有效方法。位板比任何基于数组的表示形式都要快，尤其是在64位体系结构中，位板可以容纳在单个CPU寄存器中。

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.

位板

位板的基本思想是用64位表示每种棋子类型。在C ++ / C＃中，它将为 ulong / UInt64 。因此，您将维护12个 UInt64 变量来表示您的国际象棋棋盘：每种棋子类型分别为两个（一个黑色和一个白色），分别为典当，车子，骑士，主教，女王和国王。 UInt64 中的每一位都将对应棋盘上的一个正方形。通常，最低有效位将是a1平方，下一个b1，然后是c1，依此类推，以行为主。与棋子在棋盘上的位置相对应的位将设置为1，所有其他位都将设置为0。例如，如果在a2和h1上有两个白鸦，则白鸦的位板上将如下所示：

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

例如，现在，如果您想将上一个示例中的车从a2移到g2，您要做的就是对位板进行XOR：

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.

进一步阅读

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

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++.

这篇关于对计算机编程以下棋时，如何为棋盘建模？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！