Zobrist散列

在散列表中，计算散列码的工作是由散列函数完成的。一个好的散列函数往往可以使信息随机、均匀地分布到存储空间内，从而减少发生冲突的概率，以便保存尽可能多的信息。Zobrist散列是一种快速散列函数，它广泛应用于棋类程序的散列表中。

Zobrist散列基本过程如下：如果棋盘上有M个位置，每个位置可以下N种类型的棋子，那么设置一个zobrist数组Z[M][N]。每个数组单元都预先赋于一个随机数，表示该位置出现某类棋子时对应的散列码。对于一个具体的局面，只要根据棋盘各个位置上出现的棋子类型，将相对应的Z[square][disc_type]相加（或者异或），就得到这个局面的散列码。对于另外一些需要反映在散列码上的信息，如下棋方轮换、打劫（围棋）、易位（国际象棋）等信息，也可以分别设置相对应的附加散列码。再根据实际出现情况，将附加散列码叠加到散列码上。

下面通过一个实例来说明Zobrist散列在黑白棋程序上的应用，这里假定散列码为64位。由于黑白棋只有黑、白两种棋子，为了方便起见，这里将zobrist数组分成两个数组，分别代表黑棋和白棋。另外，同一个局面由不同的棋手来下，情况将是不同的。为了反映下棋方轮换情况，还设置了相应的附加散列码。开局时由黑棋先下，如果轮到白棋下时，就需叠加上这个附加散列码。

//各位置上出现黑棋时对应的散列码
unsigned int zobrist_black[BOARD_SIZE][2];
//各位置上出现白棋时对应的散列码
unsigned int zobrist_white[BOARD_SIZE][2];
//反映下棋方轮换的附加散列码
unsigned int zobrist_swap_player[2];

//棋盘上棋子的分布情况
char board[BOARD_SIZE];
//下棋方
int player;

//对zobrist数组初始化
void zobrist_init() {
	zobrist_swap_player[0] = random();
	zobrist_swap_player[1] = random();
	for (int square=A1; square<=H8; square++) {
		zobrist_black[square][0] = random();
		zobrist_black[square][1] = random();
	
		zobrist_white[square][0] = random();
		zobrist_white[square][1] = random();
	}
}

//计算散列码
void get_hashcode(unsigned int hashcode[]){
	hashcode[0] = hashcode[1] = 0;
	//对于每个位置
	for (int square=A1; square<=H8; square++) {
		//如果是黑棋，则叠加该位置上黑棋的散列码
		if (board[square] == BLACK) {
			hashcode[0] ^= zobrist_black[square][0];
			hashcode[1] ^= zobrist_black[square][1];
		//如果是白棋，则叠加该位置上白棋的散列码
		} esle if (board[square] == WHITE) {
			hashcode[0] ^= zobrist_white[square][0];
			hashcode[1] ^= zobrist_white[square][1];
		}
	}
	//如果轮到白棋下，需叠加反映下棋方轮换的附加散列码
	if (player == WHITE) {
		hashcode[0] ^= zobrist_swap_player[0];
		hashcode[1] ^= zobrist_swap_player[1];
	}
}

在上面的实例中，每下一步棋都需要对整个局面重新计算一次，这当然比较费时。而在棋类游戏中，每步棋之间的局面变化一般不大，因此可以使用更高效的增量法来计算散列码。即对于每步棋，只需在原散列码的基础上，叠加因棋子变动而带来的散列码变化量。

//各位置上出现黑棋时对应的散列码
unsigned int zobrist_black[BOARD_SIZE][2];
//各位置上出现白棋时对应的散列码
unsigned int zobrist_white[BOARD_SIZE][2];
//各位置上翻棋时对应的散列码
unsigned int zobrist_flip[BOARD_SIZE][2];
//反映下棋方轮换的附加散列码
unsigned int zobrist_swap_player[2];

//对zobrist数组初始化
void zobrist_init() {
	zobrist_swap_player[0] = random();
	zobrist_swap_player[1] = random();
	for (int square=A1; square<=H8; square++) {
		//因为每步棋都发生下棋方轮换，所以把相应的附加散列码预先叠加在所下棋子上
		zobrist_black[square][0] = random() ^ zobrist_swap_player[0];
		zobrist_black[square][1] = random() ^ zobrist_swap_player[1];
	
		zobrist_white[square][0] = random() ^ zobrist_swap_player[0];
		zobrist_white[square][1] = random() ^ zobrist_swap_player[1];

		zobrist_filp[square][0] = zobrist_black[square][0] ^ zobrist_white[square][0];
		zobrist_filp[square][1] = zobrist_black[square][1] ^ zobrist_white[square][1];
	}
}

//计算散列码
void get_hashcode(unsigned int hashcode[], int move, int n_flipped, int flipped[]){
	//如果这步棋弃权（Pass），需叠加下棋方轮换附加散列码
	if (played == PASS) {
		hashcode[0] = zobrist_swap_player[0];
		hashcode[1] = zobrist_swap_player[1];
		return;
	}
	//如果是黑棋下，则叠加下棋位置上黑棋的散列码
	if (player == BLACK) {
		hashcode[0] = zobrist_black[move][0];
		hashcode[1] = zobrist_black[move][1];
	//否则是白棋下，则叠加下棋位置上白棋的散列码
	} esle {
		hashcode[0] = zobrist_white[move][0];
		hashcode[1] = zobrist_white[move][1];
	}
	//对于每个被翻转的棋子，叠加该位置上翻棋的散列码
	for (int i=0; i<n_flipped; i++) {
		hashcode[0] ^= zobrist_flip[flipped[i]][0];
		hashcode[1] ^= zobrist_flip[flipped[i]][1];
	}
}
页首