Zobrist散列

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

Zobrist散列基本过程如下:如果棋盘上有M个位置,每个位置可以下N种类型的棋子,那么设置一个zobrist数组Z[M][N]。每个数组单元都预先赋于一个随机数,表示该位置出现某类棋子时对应的散列码。对于一个具体的局面,只要根据棋盘各个位置上出现的棋子类型,将相对应的Z[pos][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 pos=A1; pos<=H8; pos++) {
		zobrist_black[pos][0] = random();
		zobrist_black[pos][1] = random();
	
		zobrist_white[pos][0] = random();
		zobrist_white[pos][1] = random();
	}
}

// 计算散列码
void get_hashcode(unsigned int hashcode[]){
	hashcode[0] = hashcode[1] = 0;
	// 对于每个位置
	for (int pos=A1; pos<=H8; ++pos) {
		// 如果是黑棋,则叠加该位置上黑棋的散列码
		if (board[pos] == BLACK) {
			hashcode[0] ^= zobrist_black[pos][0];
			hashcode[1] ^= zobrist_black[pos][1];
		// 如果是白棋,则叠加该位置上白棋的散列码
		} esle if (board[pos] == WHITE) {
			hashcode[0] ^= zobrist_white[pos][0];
			hashcode[1] ^= zobrist_white[pos][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 pos=A1; pos<=H8; ++pos) {
		// 因为每步棋都发生下棋方轮换,所以把相应的附加散列码预先叠加在所下棋子上
		zobrist_black[pos][0] = random() ^ zobrist_swap_player[0];
		zobrist_black[pos][1] = random() ^ zobrist_swap_player[1];
	
		zobrist_white[pos][0] = random() ^ zobrist_swap_player[0];
		zobrist_white[pos][1] = random() ^ zobrist_swap_player[1];

		zobrist_flip[pos][0] = zobrist_black[pos][0] ^ zobrist_white[pos][0];
		zobrist_flip[pos][1] = zobrist_black[pos][1] ^ zobrist_white[pos][1];
	}
}

// 计算散列码
void get_hashcode(int pos, int flip[], int n_flip, unsigned int hashcode[]){
	// 如果这一步棋跳步(Pass),需叠加下棋方轮换附加散列码
	if (pos == PASS) {
		hashcode[0] = zobrist_swap_player[0];
		hashcode[1] = zobrist_swap_player[1];
		return;
	}
	// 如果是黑棋下,则叠加下棋位置上黑棋的散列码
	if (player == BLACK) {
		hashcode[0] = zobrist_black[pos][0];
		hashcode[1] = zobrist_black[pos][1];
	// 否则是白棋下,则叠加下棋位置上白棋的散列码
	} else {
		hashcode[0] = zobrist_white[pos][0];
		hashcode[1] = zobrist_white[pos][1];
	}
	// 对于每个被翻转的棋子,叠加该位置上翻棋的散列码
	for (int i=0; i<n_flip; ++i) {
		hashcode[0] ^= zobrist_flip[flip[i]][0];
		hashcode[1] ^= zobrist_flip[flip[i]][1];
	}
}