4

我正在开发一个国际象棋引擎，我目前正在实施换位表（一组已经评估过的棋盘位置从过去的动作）。一般的想法是，当进行移动时，我会检查换位表中的匹配位置。如果存在，我会跳过代价高昂的评估过程，只从转置表中提取先前计算的结果。如果它不存在，我会进行所需的计算，然后将其添加到转置表中以供将来参考。

对我来说，这听起来像是哈希集或字典的工作。我决定用字典。我希望 key 是代表我的董事会的类，而 value 是遇到该位置的次数的 int 计数。计数的原因是能够检测到三次重复平局。如果相同的位置出现了 3 次或更多次，玩家可以选择平局。使用字典而不是哈希集，我可以通过将它与我的转置表结合起来，大大简化对三重重复绘制的检测。

为了做到这一点，我创建了代表棋盘状态的类覆盖 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));

我的一个愚蠢的疏忽。不过，我不喜欢查询字典。

4

1 回答 1

2

一种选择是只保留对字典值中键的引用，以及字典的实际值，如下所示：

Dictionary<BoardState, Tuple<BoardState, int>>

然后，每当您添加对象时，将与键相同的对象添加到值中：

Dictionary<BoardState, Tuple<BoardState, int>> boards = 
    new Dictionary<BoardState,Tuple<BoardState,int>>();
BoardState board = new BoardState();
boards.Add(board, Tuple.Create(board, 1));

另一种选择（这可能是更好的设计）是将您的电路板状态对象分解为两种不同的类型。有一个确实只代表板子的状态（这应该是不可变的），另一个包含有关该状态的其他信息，包括它发生的时间和可能适用于您的特定应用程序的任何其他可变属性。这将阻止您需要访问字典键。

于 2013-02-11T17:57:54.950 回答