gpt4 book ai didi

c++ - 将玩家转入 Zobrist 哈希

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:59:25 26 4
gpt4 key购买 nike

我目前正在用 Chinese Checkers minimax 算法实现换位表。在中国西洋跳棋中,没有棋子被捕获,棋盘在功能上有 81 格。玩家轮流在棋盘上移动棋子。

该过程的一部分涉及为棋盘状态创建哈希。到目前为止,我已经有了一个有效的方法,可以为每个棋盘状态创建一个(希望如此)唯一的哈希值:

 myHash = 0;
//randoms[81][3] is an array filled completely with pseudorandom values
for (int x = 0; x < 81; x++) {
myHash ^= randoms[x][board[x]];
//board[x] is the piece at space x (1=player1 piece, 2=player2 piece, 0=empty)
}

更重要的是,我在 applyMove 函数(和 undoMove 函数)中逐步执行此操作:

applyMove(int to, int from) {

//Undo the 'from' piece in the hash
myHash ^= randoms[from][board[from]];
// Apply the move
std::swap(board[from], board[to]);
//Add the 'to' piece to the hash
myHash ^= randoms[to][board[to]];

// Update whose turn it is
swapTurn();
}

之所以可行,是因为 XOR 函数的可逆性。

我现在遇到的问题是,哈希函数不存储轮到谁。也就是说,您可以有两个相同的游戏板,但它们会在 minimax 算法中返回不同的值,因为一个试图最大化分数,而另一个试图最小化它。

基本上,我的问题是:如何将玩家的回合存储在递增生成的哈希函数中,同时保持完美(最好是廉价地)反转它的能力?假设玩家的回合是整数而不是 bool 值,因为游戏最终将有 6 名玩家而不是两名玩家。

最佳答案

您可以使用充满伪随机值的 turns[6] 数组:

unsigned n = 6;  // number of players;

myHash ^= turns[active_player]; // 'undo' the old active player
active_player = (active_player + 1) % n; // new active player's index
myHash ^= turns[active_player]; // 'add' new active player

这类似于棋子位置增量更新并且适用于n ∈ [2, 6]。


作为旁注...

通常 Zobrist 散列是通过扫描 block 的位置来完成的,排除 空方 block 。空白方 block 的位置未明确散列。

因此您可以使用更小(对缓存更友好)的数组。像这样的东西:

std::uint64_t randoms[81][2];  // two players

for (unsigned x(0); x < 81; ++x)
if (board[x])
myHash ^= randoms[x][board[x]];

关于c++ - 将玩家转入 Zobrist 哈希,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29666995/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com