我正在开发一个国际象棋引擎,目前正在实现置换表(存储过去移动中已经评估的棋盘位置)。大致思路是,在进行一次移动时,我会检查置换表是否存在相应的位置。如果存在,则跳过昂贵的评估过程,直接从置换表中取出先前计算的结果。如果不存在,则执行所需的计算,再将其添加到置换表中以备将来使用。
对我而言,这听起来像是哈希集或字典的工作。我选择了字典。我想让键表示我棋盘的类,值为遇到该位置的次数的整数计数器。计数的原因是为了检测三次重复和棋局面。如果同一局面出现三次或以上,则玩家可以选择宣布和棋。使用字典而不是哈希集,可以通过将其与我的置换表结合使用,大大简化检测三次重复和棋的过程。
为了做到这一点,我重写了表示棋盘状态的类的Equals()和GetHashCode()方法。它工作得很好,我现在能够追踪游戏之前遇到的所有历史状态。
我的问题是,我需要能够访问字典中键对象的属性。我可以看到是否存在匹配项(使用.ContainsKey(...)方法和我的Equals()/GetHashCode()逻辑),但现在我需要从键中提取前面提到的已计算值(存储为我的棋盘状态对象的公共属性)。
我想到了以下代码:
这个方法虽然可行,但是对我来说感觉很笨拙。转置表的整个目的是为了加速对数百万连续棋盘状态的递归搜索。为每个匹配查询一个字典听起来有些违反直觉。有没有更好的方法来解决这个问题呢?
编辑: 正如所指出的那样,由于有效的棋盘状态数量巨大,我的哈希函数可能不完美。我的Equals()重写检查第二个交替生成的哈希来减少碰撞的可能性。我的上述 "解决方案" 是有缺陷的,因为它依赖于不完美的哈希。我应该使用:
我的疏忽造成了这个错误。但我不喜欢查字典。
对我而言,这听起来像是哈希集或字典的工作。我选择了字典。我想让键表示我棋盘的类,值为遇到该位置的次数的整数计数器。计数的原因是为了检测三次重复和棋局面。如果同一局面出现三次或以上,则玩家可以选择宣布和棋。使用字典而不是哈希集,可以通过将其与我的置换表结合使用,大大简化检测三次重复和棋的过程。
为了做到这一点,我重写了表示棋盘状态的类的Equals()和GetHashCode()方法。它工作得很好,我现在能够追踪游戏之前遇到的所有历史状态。
我的问题是,我需要能够访问字典中键对象的属性。我可以看到是否存在匹配项(使用.ContainsKey(...)方法和我的Equals()/GetHashCode()逻辑),但现在我需要从键中提取前面提到的已计算值(存储为我的棋盘状态对象的公共属性)。
我想到了以下代码:
BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.GetHashCode() == this.GetHashCode());
这个方法虽然可行,但是对我来说感觉很笨拙。转置表的整个目的是为了加速对数百万连续棋盘状态的递归搜索。为每个匹配查询一个字典听起来有些违反直觉。有没有更好的方法来解决这个问题呢?
编辑: 正如所指出的那样,由于有效的棋盘状态数量巨大,我的哈希函数可能不完美。我的Equals()重写检查第二个交替生成的哈希来减少碰撞的可能性。我的上述 "解决方案" 是有缺陷的,因为它依赖于不完美的哈希。我应该使用:
BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.Equals(this));
我的疏忽造成了这个错误。但我不喜欢查字典。