高效存储象棋位置 [英] efficient storage of a chess position

问题描述

我已经读过与这个问题相关的大量网络点击，我还没有遇到任何明确的答案。

我想做什么是建立棋位置数据库，能够识别转置（通常哪些棋子在哪个棋子上）。

编辑：它也应该能够识别类似不完全相同）。

这是几乎20年前的讨论（当空间是问题）：
https://groups.google.com/forum/#!topic /rec.games.chess.computer/wVyS3tftZAA

其中一个讨论者谈论了在方阵上编码片段，使用4 x 64位加上一些位更多的额外信息（castling，en passant等）：
有六件（Pawn，Rook，Knight，Bishop，Queen，King）加一个空的正方形，这将是3位（2 ^ 3）

总共会有4个64位，每个都有一些额外的信息。

问题：有没有其他更有效的 方法来存储国际象棋的位置

？

我应该提到这个问题是以数据库为中心，而不是以游戏为中心我唯一的兴趣是有效地存储和检索，而不是创建任何AI或产生任何动作）。

谢谢，
Adrian

解决方案

板上有32块，64块。方形索引可以用6位数表示，因此要表示每个片段的位置，您需要32个6位数字，或总共192位，小于4x64。

你可以通过意识到不是所有的位置都是可能的（例如，一个pawn不能到达自己的颜色的结束行），并且在这些情况下使用少于6位的位置，可以做得更好。此外，已经被另一个棋子占据的位置使得该位置对于其他棋子不可用。

由于棋子也可能完全缺少棋子，

编辑一个国王的位置，因为它们总是在那里，然后，编码另一个位置作为一个国王的意思。 ：

对这些作品的可能位置进行简短分析：

<

• 主教限制在32个位置


• Pawns是限制为21，26，30，32，32，30，26和21个位置（AH列）。

法律棋位置的集合可以用从零到（64 ^ 12 * 32 ^ 4 * 21 ^ 4 * 26 ^ 4 * 30 ^ 4 * 32 ^ 8）-1或391935874857773690005106949814449284944862535808450559999的整数简单地描述， 188位。对位置进行编码和解码是非常简单的 - 但是，有多个数字解码到相同的位置（例如白色骑士1在B1和白色骑士2在G1;白色骑士1在G1和白色骑士2在B1）。

由于没有两个可以占据相同的平方，所以有一个更严格的限制，但它有点难以编码和解码，所以可能在实际应用中没有用。此外，上面显示的数字非常接近2 ^ 188，所以我不认为即使这个更紧密的编码也适合187位。

I've read tons of web hits related to this issue, and I still haven't come across any definitive answer.

What I'd like to do is to make a database of chess positions, capable of identifying transpositions (generally which pieces are on which squares).

EDIT: it should also be capable to identify similar (but not exactly identical) positions.

This is a discussion almost 20 years ago (when space was an issue): https://groups.google.com/forum/#!topic/rec.games.chess.computer/wVyS3tftZAA

One of the discussants talk about encoding pieces on a square matrix, using 4 x 64 bits plus some bits more for the additional information (castling, en passant etc): there are six pieces (Pawn, Rook, Knight, Bishop, Queen, King) plus an empty square, that would be 3 bits (2^3), and one more bit for the color of the piece.

In total, there would be 4 numbers of 64bits each, plus some additional information.

Question: is there any other, more efficient way of storing a chess position?

I should probably mention this question is database centric, not game centric (i.e. my sole interest is to efficiently store and retrieve, not to create any AI or to generate any moves).

Thanks, Adrian

解决方案

There are 32 pieces on the board, and 64 squares. Square index can be represented with a 6-bit number, so to represent the locations of each piece you need 32 six-bit numbers, or a total of 192 bits, which is less than 4x64.

You can do a bit better by realizing that not all positions are possible (e.g. a pawn cannot reach the end row of its own color) and using less than six bits for the position in these cases. Also, a position already occupied by another piece makes that position unavailable for other pieces.

As a piece may also be totally missing from the board, you should start with the kings' positions, as they are always there - and then, encoding another piece's position as the same of a king would mean that the piece has been taken.

Edit:

A short analysis of the pieces' possible positions:

• Kings, queens, knights and rooks can be anywhere on the board (64 positions)
• Bishops are restricted to 32 positions each
• Pawns are restricted to 21, 26, 30, 32, 32, 30, 26, and 21 positions (columns A-H).

Thus, this set of legal chess positions can be described trivially with an integer from zero up to (64^12 * 32^4 * 21^4 * 26^4 * 30^4 * 32^8)-1, or 391935874857773690005106949814449284944862535808450559999, which fits into 188 bits. Encoding and decoding a position to and from this is very straightforward - however, there are multiple numbers that decode into the same position (e.g. white knight 1 at B1 and white knight 2 at G1; and white knight 1 at G1 and white knight 2 at B1).

Due to the fact that no two pieces can occupy the same square, there is a tighter limit but it is a bit difficult to both encode and decode, so probably not useful in a real application. Also, the number shown above is pretty close to 2^188, so I don't think even this tighter encoding would fit into 187 bits.

这篇关于高效存储象棋位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！