我正在为一个国际象棋变种引擎调试我的换位表,其中可以放置碎片(即最初不在板上).我需要知道我经常遇到关键的碰撞.我正在保存每个表索引中的片段列表以及通常的哈希数据.我确定两个位置是否相等的简单解决方案是转换失败,因为我是线性比较两个列表.
请不要建议我应该以板为中心而不是以件为中心进行存储.由于可放置和捕获的碎片的独特性,我必须存储碎片清单.这些状态中的碎片就像它们占据了重叠且无位置的位置.请查看存储片段的说明.
// [Piece List]
//
// Contents: The location of the pieces.
// Values 0-63 are board indexes; -2 is dead; -1 is placeable
// Structure: Black pieces are at indexes 0-15
// White pieces are at indexes 16-31
// Within each set of colors the pieces are arranged as following:
// 8 Pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 Queen, 1 King
// Example: piece[15] = 6 means the black king is on board index 6
// piece[29] = -2 means the white rook is dead
char piece[32];
甲换位发生时片以不同的顺序被移动,但最终的结果是相同的板的位置.例如,以下职位是相同的:
1) first rook on A1; second rook on D7
2) first rook on D7; second rook on A1
以下是非优化的通用算法 ; 内环类似于另一个普遍问题,但增加了约束,0-63中的值只会发生一次(即每平方只有一个).
for each color:
for each piece type:
are all pieces in the same position, disregarding transpositions?
由于换位,以下比较不起作用.我需要的是一种检测转置相等的方法,只报告实际上不同的位置.
bool operator==(const Position &b)
{
for (int i = 0; i < 32; i++)
if (piece[i] != b.piece[i])
return false;
return true;
}
性能/内存是一个考虑因素,因为每个表的每次点击超过100K(键相等),典型的表有100万个项目.从此以后,我正在寻找比复制和排序列表更快的东西.
有很多关于计算机国际象棋的研究,并且为一个位置创建唯一哈希的方法是一个众所周知的问题,几乎每个国际象棋引擎都使用通用解决方案.
你需要做的是使用Zobrist Hashing创建一个独特的(不是真正独特的,但我们稍后会看到为什么这在实践中不是问题)关键是每个不同的位置.这里解释了应用于国际象棋的算法.
当你启动程序时,你创建了我们称之为zobrist键的东西.这些是每个片/方对的64位随机整数.在C中你会得到一个像这样的2维数组:
unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];
每个密钥都使用一个好的随机数生成器初始化(警告:随gcc或VC++提供的随机数生成器不够好,使用Mersenne Twister的实现).
当电路板为空时,你随意将它的散列键设置为0,然后当你在电路板上添加一块时,在A1上说一个Rook,你也可以通过使用散列键对A1上的一个小车的zobrist键进行异或来更新散列键.董事会.像这样(在C中):
boardHash = boardHash ^ zobKeys[ROOK][A1];
如果你以后从这个方块中移除了车,你需要反转你刚刚做的事情,因为可以通过再次回应来反转XOR,你可以在删除它时再次使用相同的命令:
boardHash = boardHash ^ zobKeys[ROOK][A1];
如果你移动一块,说A1上的车就行到B1,你需要做两次XOR,一次去除A1上的车和一辆在B2上添加一辆车.
boardHash = boardHash ^ zobKeys[ROOK][A1] ^ boardHash ^ zobKeys[ROOK][B1];
这样每次修改电路板时都会修改散列.它非常有效.您还可以通过xoring与电路板上所有部件对应的zobKeys来计算每次scatch的哈希值.你还需要对可以采用的pawn的位置进行异或,以及双方的炼制能力的状态.您可以通过为每个可能的值创建zobris键来以相同的方式执行此操作.
这个algotitm并不保证每个位置都有一个独特的哈希值,但是,如果你使用一个好的伪随机数发生器,发生碰撞的几率很低,即使你让你的引擎终身玩,也几乎没有机会发生过碰撞
编辑:我只是红色,你试图实现这个国际象棋的变种,有车外件.Zobrist散列仍然是适合您的解决方案.您必须找到一种方法将这些信息合并到散列中.例如,您可以为板上部件提供一些按键:
unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE];
如果你有2个爪子离开棋盘并将其中一个棋子放在a2上,你将需要做2个操作:
// remove one pawn from the off-the-board
boardHash = boardHash ^ offTheBoardZobKeys[WHITE_PAWN][numberOfWhitePawsOffTheBoard];
// Put a pawn on a2
boardHash = boardHash ^ zobKeys[WHITE_PAWN][A2];
为什么不在数据库中保留与棋盘布局相对应的64字节字符串？每种类型的作品,包括"无作品"代表一个字母(两种颜色的不同大写,即黑色的ABC,白色的abc).董事会比较归结为简单的字符串比较.
一般来说,从棋盘的角度来看,而不是片段的角度,将摆脱你的换位问题!
“不建议我应该以板为中心而不是以件为中心进行存储”。
你太专注于不这样做，以至于错过了显而易见的解决方案。比较特定于板的。要比较两个位置列表L1和L2，请将 的所有元素放在L1（临时）板上。然后，对于 的每个元素L2，检查它是否存在于临时板上。如果 L2 的元素不存在于棋盘上（因此也不存在于 中L1），则返回不相等。
如果删除 的所有元素后L2，棋盘上仍然剩下棋子，则L1必定有元素不存在L2，并且列表相等。L1和L2仅当临时板随后为空时才相等。
L1一种优化是首先检查和的长度L2。这不仅可以快速发现许多差异，而且还消除了从 baord 中删除元素的需要L2以及最后的“空板”检查。L1只需要捕获的真正超集的情况即可L2。如果L1和L2具有相同的大小，并且L2是 的子集L1，则L1和L2必须相等。