我已经阅读了大量与此问题相关的网页点击,但我仍然没有遇到任何明确的答案。
我想做的是建立一个国际象棋位置数据库,能够识别换位(通常哪些棋子在哪个方格上)。
编辑:它还应该能够识别相似(但不完全相同)的位置。
这是近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或产生任何移动)。
谢谢,阿德里安
板上有32块,有64个方块。方形索引可以用6位数表示,因此要表示每个部分的位置,需要32个六位数,或总共192位,小于4x64。
通过意识到并非所有位置都是可能的(例如,pawn无法到达其自身颜色的最终行)并且在这些情况下使用少于6位的位置,您可以做得更好。此外,已被另一件作品占据的位置使该位置不可用于其他作品。
因为一块也可能完全从棋盘中丢失,你应该从国王的位置开始,因为它们总是在那里 - 然后,编码另一个棋子的位置就像一个国王一样意味着这件作品已被拍摄。
编辑:
对这些部分可能的立场进行简短分析:
因此,这组合法的国际象棋位置可以用零到(64 ^ 12 * 32 ^ 4 * 21 ^ 4 * 26 ^ 4 * 30 ^ 4 * 32 ^ 8)-1或391935874857773690005106949814449284944862535808450559999的整数来简单地描述,适合188位。对此进行编码和解码是非常简单的 - 但是,有多个数字可以解码到相同的位置(例如B1的白骑士1和G1的白骑士2; G1的白骑士1和白骑士2 B1)。
由于没有两个部分可以占据相同的方块,因此存在更严格的限制,但是编码和解码都有点困难,因此在实际应用中可能没用。此外,上面显示的数字非常接近2 ^ 188,所以我不认为即使这种更紧密的编码也适合187位。
在Forsyth-Edwards符号(FEN)上获取战利品。它被描述为here。它也是众所周知的,并得到许多引擎和国际象棋程序的支持。
这是起始位置的FEN:
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
芬分为6个部分。
段1包含碎片。黑色部分为小写,白色部分为大写。
第2段陈述,轮到谁了。 (w或b)
第3部分用于铸造。 KQkq意味着两者都可以城堡。 K = King side white
q = queen side black
段4使用代数表示法的En passant目标平方。如果没有en passant目标方,则为“ - ”。如果一个棋子刚刚进行了两个方格的移动,那么这就是棋子“后面”的位置。无论是否有一个位置进行传球捕获,都会记录此信息
段5 Halfmove时钟:这是自上次捕获或pawn advance以来的halfmoves数。这用于确定是否可以在五十步规则下声明平局。
段6完全移动编号:完整移动的编号。它从1开始,并在Black移动后递增。
您可以使用修改的运行长度编码,其中每个片段编码为片段编号(3位),0y111
用于跳过前面的空格。由于存在许多彼此相邻的情况,您最终会省略位置信息:
All pieces are followed by color bit
0y000c 0 Pawn
0y001c 1 Rook
0y010c 2 Knight
0y011c 3 Bishop
0y100c 4 Queen
0y101c 5 King
0y110 6 Empty space
0y111 7 Repeat next symbol (count is next 6 bits, then symbol)
解码器从a1开始向右移动,在行尾向上移动,因此启动板的编码将是:
12354321 Literal white encoding from a1 to h1 32 bits
7 8 0 repeat white pawn 8 times 13 bits
7 32 6 repeat 32 empty spaces 12 bits
7 8 8 repeat black pawn 8 times 13 bits
9abcdba9 Literal encoding of black 32 bits
---------
102 bits total
话虽这么说,可变长度编码的额外复杂性和不确定性可能不值得节省空间。此外,在某些游戏中,它可能比恒定宽度格式更差。
如果您不需要可解码位置表示进行比较,那么您可以查看Zobrist散列。国际象棋引擎使用它来生成位置的64位单向哈希,用于在搜索树中发现转置。由于它是单向哈希,你显然无法从哈希中反转位置。散列的大小是可调的,但64位似乎是可接受的最小大小,导致很少的冲突。它是一个理想的数据库索引键,固定长度只有8个字节。由于碰撞虽然不常见,但你可以做第二遍,比较实际位置,过滤掉任何已经散列到相同值的位置,如果它是一个问题。我在我自己的一个应用程序(使用SQLite)中使用Zobrist哈希,我用它来管理我的开口,并且它在查找转置方面没有任何问题。
在电路板上最多考虑32件。每件都可以在64个方格中的一个上。以预定顺序独立地表示片段位置需要32 * 6 = 192位。
除此之外,每个棋子都可以升级为车,主教,骑士或女王,所以对于每个棋子,我们需要在3个额外位(4种可能的棋子类型和普通棋子)中对其状态进行编码。
32 * 6 + 16 * 3 = 240位/ 30字节
在许多情况下,您需要有关该位置出现的游戏/变体状态的其他信息:
EnPassent文件:4位(8个文件,无)
Castlerights:4位(短/长白/黑)
sideToMove:1位(白/黑)
最多可加249位/ 32字节。
这可能不是最紧凑的表示,但它很容易进行解码。
我的两分钱
32字节(4 * 64位)是非常少量的数据。 1000万象棋位置可以达到30千兆字节。 192位是24字节,这将达到23千兆字节。可能数据库使用某种压缩,因此磁盘可能少于这些数字。我不知道存储有什么样的限制,但因为这些似乎是非常紧凑的编码,所以尝试最小化更多可能是不值得的。
因为需要找到相似位置的能力,我认为编码应该可以很容易地比较不同的位置。优选地,这可以在不解码的情为了使这个工作,编码应该是恒定长度(不能想到使用可变长度编码这样做的简单方法)。
索引可能会加速相似性搜索。朴素的方法将索引数据库中各个位置的所有位置。这将产生32个索引(也可能是其他信息)。至少在理论上它会使搜索闪电般快速。
索引将占用相当大的空间。可能比实际位置数据更多。他们仍然可能没有那么多帮助。例如,找到黑王所在的位置,或者在e4附近需要使用索引进行9次搜索,然后在30千兆字节的位置信息周围跳跃,这可能需要在随机位置进行磁盘访问。并且可能找到类似的位置不止一件......
如果存储格式有效,则可能仅通过所有位置数据来强制(like this)并按位置检查相似性位置。这将有效地使用CPU缓存。此外,由于长度记录不变,很容易将工作分成多个处理器或机器。
是否使用以片段为中心或基于板的存储格式取决于您如何计算两个位置相互比较的相似性。以件为单位可以轻松计算出一件在两个不同位置的距离。然而,在以片段为中心的方法中,每个片段都是分开识别的,因此在某个位置找到一个棋子并不容易。一个人必须检查每个兵的位置。如果棋子身份不那么重要,那么基于棋盘的存储可以很容易地检查棋子是否在想要的位置。另一方面,无法检查哪个精确的棋子。
有两种简单的方法来存储电路板的信息:通过存储每个部件的位置或通过存储每个正方形的内容。
正如Mitch所解释的那样,有一种方法可以使用RLE进行一点压缩,但是给出的例子是起始位置,这个位置特别容易描述。在另一种情况下,碎片散布在纸板上,你可以有空间和碎片交替,而RLE不会压缩任何东西。因此,除非使用更复杂的算法,否则您将恢复无压缩。
我认为jlahd通过计算两次中心棋子在计算中犯了一个错误,所以实际上存储每个棋子位置所需的空间不是188位而是168位。如果已经提升了典当,你还需要存储。所以事实上,对于棋子来说,有(32 + 4x64)^ 16种可能性。这总共223位= 28字节。
相反,如果我们为每个方格存储其内容,我们需要计算正方形的可能性。对于大多数正方形,有6个可能的白色部分和黑色相同。对于顶行和底行,不能显示一种颜色的pawn。因此,对于中心正方形是13个可能性,对于顶部和底部正方形是12个可能性,因此13 ^ 48×12 ^ 16个可能性。 en-passant的位置是17个可能性。这大约是240位。
总而言之,似乎你可以通过存储片段位置而不是每个正方形的内容来获得12.5%的空间。