毕业设计(论文)外文资料翻译
附件
1：外文资料翻译译文
转置表的替换方案
摘要：几乎每个棋程序都使用转置表，通常实现为大哈希表。 即使这个表通常可能会做得很大，但是受制于内存约束，会发生冲突。 然后必须做出一个在表中保留或更换的状态的选择，使用一些替换方案。本文比较了7种替换方案在一些棋中间状态上的转置表大小的函数的性能。用一个二级表，使用子树中的节点数作为搜索决定标准，暂时推荐表现最好的替换方案。
介绍
表来搜索，事实上，一个状态可以进行几个排序的动作。这样的结果状态被称为棋程序分析状态，同时创建树。但是，仔细看来搜索空间可以更好地利用图转置。当再次遇到该状态时，搜索树的大小可以显着减小，如果此状态的先前结果仍然可用。此信息可以存储在大直接访问表，转置表（Greenblatt，1967; Slate和Atkin，1983）。转置表中的输入的相关信息包括状态的得分，最佳移动和被搜索的子树的深度。因为我们采取alpha;-beta;搜索（Knuth和Moore，1975），得分不一定是真实值，而可以是较低或较高界。当使用迭代深化和最小窗口搜索时，转置表的搜索效率显著降低（Ebeling，1986; Berliner和Ebeling，1989; Schaeffer，1989; Hyatt，1990），特别是在赛局上几乎没有棋子的时候。
关于转置表的文献主要是教程（例如，Marsland（1986）），只有几个详细讨论的讨论了它的性能（例如，Ebeling（1986），Schaeffer（1989））。一个经常引用的性能观察是，尺寸加倍的表减少了搜索树的大小。这是一个明显的结果，因为越多表中的信息，转置的机会越大。据我们所知，已在文献中出版中，转置表其他方面的性能分析，例如要替换的状态，都没有。
转置表的最常见的实现是大的哈希表。即使这个表通常做得尽可能大，受限于内存约束，冲突（参见第3节）必然会发生。当发生冲突时，当发生碰撞时，必须进行是否更换或保持表中的状态的选择。此选择由替换方案控制。从文献和与计算机象棋实践者的讨论，看起来最常见的冲突解决形式是采用较浅的搜索结果。这有一个直观的吸引力，但没有得到实验支持。
本文比较了七种碰撞解决方案在十八个棋中间状态的表现。令人惊讶的是，我们发现传统的实现（每个条目一个表格状态）和保留深层搜索结果的偏好不是最好的。我们采用Ebeling（1986）提出的方案：一个两级表。我们检查了搜索的子树的深度和节点数作为替换标准。一般来说，后者在测试的状态中表现最好。
与实施转置表有关的细节在第2节中描述。第3节识别使用转置表时出现的问题。在我们的实验中使用的象棋程序的实现的相关细节在第4节中给出。在第5节中讨论了我们的测试状态集。实验的设计在第6节中描述。我们的实验结果提出并与第7节中的文献中的结果进行比较。最后，在第8节中给出了未来研究的结论和建议。
实现转置表
在理想情况下，将保留搜索过程中遇到的每个状态及其所有相关信息。不幸的是，随后所需的存储器超过了大多数现代计算机的可用容量。因此，在实践中，转置表通常被实现为哈希表（Knuth，1973）。通过使用一些散列方法将状态转换为足够大的大小（散列值）的数量。国际象棋程序员使用的最流行的方法在Zobrist（1970）中描述。
如果转置表由2n个条目组成，则哈希值的n个低位被用作哈希索引。 剩余的位（密钥）用于区分映射到相同散列索引（即，转置表中的相同条目）上的不同板状态。 因此，应当选择足够大的比特总数。
变换表通常被实现为一个表，每个条目具有固定数目（传统上为一个）表状态（Slate和Atkin，1983）。有时，溢出区域用于处理有限数量的冲突。
转置表中的条目应至少包含以下信息（Marsland，1986; Hyatt et al。，1990）：
- 键：哈希值的位比哈希索引的位更重要。 需要密钥来区分具有相同散列索引的不同板状态。
- 移动：最好的状态。 这个移动，引起了截断值，或者获得了最高分。
- 得分：某状态的最佳移动的分数。 因为我们采用alpha;-beta; 搜索，得分
可能是真实值，上限或下限。
- 旗：包含关于分数的信息，指示其是真实值，上限还是下限。
- 深度：搜索的子树中的相对深度。当进行n层搜索并且状态存储在树的层m时，深度为n -m。
来自转置表的错误
将转置表实现为哈希表引入了两种类型的错误，早在1970年由Zobrist识别。第一种类型的错误（称为Zobrist（1970）的类型1）是更重要的。由于可用的散列值的数量远小于国际象棋中状态的总数，因此必然发生两个不同的状态产生相同的散列值。这是一个严重错误，因为当发生类型1错误时，此条目中的信息将用于错误的状态，如果是这样，将引入搜索错误。通常可以通过测试来自转置表的移动来检测该误差，从而有效地降低误差率。如果移动是非法的，则表条目必须涉及被调查的另一个状态。注意，如果移动是合法的，状态仍然可能偏差。可以通过增加散列值中的比特数来降低类型1错误的发生概率。
当两个不同的板状态映射到转置表中的相同条目时，发生第二类型的错误（称为类型2，或者Zobrist（1970）的冲突）。即相同的散列索引。这通常被称为碰撞（Knuth，1973）。当发生碰撞时，必须选择所涉及的两个状态中的哪一个应该保留在转置表中。这种选择基于替换方案。几个替换方案在第6.1小节中讨论。可以通过增加散列索引中的比特数（即转置表中的条目的数量）来降低发生冲突的概率。
实现的结构
测试程序AliBaba是一个简单的国际象棋程序，设计为容易由其他研究人员重现。这种再现性促进了一个统一的研究平台。AliBaba的主要部分构成本节的剩余部分，即搜索引擎（4.1），移动排序启发法（4.2），评价函数（4.3）和转置表（4.4）的实现。
4.1 搜索引擎
AliBaba使用alpha; - beta;算法搜索游戏树（Knuth和Moore，1975）。当在内部节点检查最佳移动时，期望切割的可能性增加。因此，迭代深化（Scott，1969）被应用，等于全宽搜索到增加的深度。从先前迭代收集的信息可以用于在当前迭代中重新排序在内部节点处的移动，增加将最佳移动放在当前移动列表的前面的可能性。
另一个实现的增强是最小窗口，基于这样的事实，其相对容易地示出移动比迄今为止发现的最佳移动更差。所得的算法称为迭代加深，最小窗口，主变量搜索（PVS;详情参见Marsland（1986））。
此外，AliBaba使用aspiration搜索（有关描述，请参阅Marsland（1986））。在每个新迭代开始时，窗口的上界和下界分别被设置为从先前迭代得到的得分加上和减去Pawn的值。 如果搜索失败（分数不在alpha; - beta;窗口内），则当失败低时将窗口调整为（-infin;，分数），或者当失败高时调整为（分数， infin;）。
在评估节点时，它们应该是“相对静止的”（Shannon，1950）。并非所有的叶节点都是，因此必须通过静态搜索进一步调查，在这个搜索中，只考虑捕获移动和促销移动，我们注意到，当移动的玩家不在检查中时，可以提前终止静止搜索，即，一旦变得清楚，将产生所有移动将是不利的。
在我们的转置表实验中不使用其他搜索扩展，以避免可能的搜索异常。
4.2移动排序启发法
在任何情况下，AliBaba只会产生合法动作，不包括违法动作，例如将自己的王放在或留在检查中。由于移动的排序对于算法的效率是重要的，因此实现了以下排序启发法。
反驳表（Akl和Newborn，1977）。 对于根状态中的每次移动，存储主变量。 在下一次迭代中，尝试移除这些主要变量。
历史启发式（Schaeffer，1983; Schaeffer，1989）。 保持搜索树中遇到的每个合法移动的分数。 每次发现移动在搜索中是最好的，其分数通过与所调查的子树的深度成比例的量来调整。 当使用此启发式排序移动时，在具有较低得分的移动之前考虑具有较高得分的移动。
在AliBaba中，移动按以下方式排序。要考虑的第一个动作是从反驳表的移动。然后，如果在转置表中找到状态，则转置表移动是要考虑的下一个移动。这些移动之后是捕获移动（要捕获的最高值的片段，如果相等，则是捕获最低值片段）。之后跟随升迁活动（按升迁棋排序;最高价值的升迁棋优先）。剩余的移动根据其下降的历史 - 启发分数来排序。 除了上面提到的移动生成之后立即应用的移动顺序启发法之外，根移动也在迭代深化搜索过程期间排序。
4.3评价函数
用于转置表测试的评估函数很简单。它由棋类部分和状态一部分组成。棋类部分计算不同棋子之间的差异。状态部分限于平方平方值的求和。在游戏期间，对于每种类型的棋子，维持64平方的桌。每个表包含该板在板上每个方块上的状态值。这些方块表在每个新的搜索过程的开始处被标记。这些值又来源于棋子的移动性和中心控制。在每个新的搜索过程开始时填充表的技术被称为预处理。评估函数的状态部分被递增地更新：每当在搜索处理期间调查移动时，从其减去piece-fromSquare表条目的状态值，并且将pieceto-Square表条目的值添加到其中。最后，评价函数还用于僵局，三次重复以及50-移动规则以及将军。
4.4转置表
每当在搜索中调查移动时，在转置表中查找所得到的状态。 如果状态存在，并且被检查子树的深度大于或等于仍待搜索的深度，则表中的信息被认为是可靠的，并且因此用于更新窗口界限（可能引起割断）。 转置表移动总是用于命令移动（见4.2小节）。在搜索中，在将状态调查到一定深度之后，将其与最佳移动（即，引起切割的移动或具有最高得分的移动）一起存储在转置表中，其分数，搜索深度和标记，表示分数是真实值，下限还是上限。在静止搜索期间，状态不会存储在转置表中。
转置表查找的结果在树中的所有节点处使用。 如果在表中存在叶状态，则将转置表得分用于评估。 如果分数是真实值，则返回此分数。 否则，评估状态，并且如果必要，则根据由转置表中的标志指示的界限来调整评估值。 由于在静止搜索中使用评价函数，所以在静止搜索中也使用转置表。 然而，注意，由于在静态搜索期间仅检索和不存储条目，所以在该阶段期间它们的有用性受到限制。
在AliBaba中，转置表实现为每个条目具有一个或两个表状态的线性数组。 不使用溢出区。 在简单的搜索中实现转置表的更多细节在Marsland（1986）中给出。
测试集
由于各种原因，可用的测试状态集（Reinfeld，1958; Kopec和Bratko，1982; Nielsen，1991; Lang和Smith，1993）不能满足我们的目的。 相反，我们已经采用了从实际游戏中得出的一系列状态，以便测试多样化的技术。
这样做的一个优点是所选择的状态将不会偏向于战术，而是将自动地并入状态方面。 此外，这种选择还满足连续状态应当相关的要求，这在调查在移动之间清除转置表的效果时是必要的。
具体来说，我们从Euwe纪念VSB比赛1994的第2轮选择比赛Kasparov-Short的状态作为我们的测试集（见附录A）。由于显而易见的原因，省略了开始阶段。 我们只考虑从第15步起的状态。 此外，我们集中在中间游戏中使用转置表，以排除游戏结束，后者被定义为至少一个侧面具有少于18点的材料的状态。我们注意到，当前测试终止于 该游戏仍然是根据本定义的中间游戏。 我们的限制是，只有卡斯帕罗夫的状态被调查，导致18个状态作为一个测试集。
实验设计
在本节中，我们报告了七个替换方案的测试，清除移动之间的转置表的影响以及改变表的大小的影响。 我们使用在搜索期间调查的节点数作为度量，包括所有节点，即内部节点和叶节点。
6.1替换方案
每当检测到碰撞时，必须进行是否替换转置表中的现有状态的选择。 在本节中，我们研究了七种不同的替代方案，深度，New，Old，Big1，BigAll，TwoDeep，TwoBig1。 它们基于五个概念，如下编号。
1.（深度）
深层的替代方案是传统的。 它是基于对所涉及状态检查的子树的深度。 在碰撞时，具有最深子树的状态被保存在表中（Marsland，1986; Hyatt等人，1990）。 该方案背后的概念是，搜索到更大深度的子树通常包含比搜索到更浅深度的子树更多的节点。 因此，投入更多的时间来搜索更大的树。 因此，将该状态存储在转置表中可能比存储较不深入研究的状态节省更多的工作。
- （New）
当碰撞发生时，替换方案New总是替换表中的任何状态。 这个概念基于大多数转置发生在全局搜索树的小子树中的本地发现（Ebeling，1986）。
- （Old）
我们还测试了替换方案Old。 使用此方案（与方案New相反），新状态不会替换现有状态。 这个方案只是为了完整性而包括的。
-
(Big1, BigAll)
有时一个子树包含许多强迫移动。 它也可能是潜在的顺序的（在这种情况下已经发生了许多切换）。 在这种情况下，搜索树的深度不能是已经执行的搜索量的良好指示，因此可能被保存。 然后可能有吸引力的是选择具有最大子树的状态而不是具有最深子树的状态，通过节点数量而不是通过它们的深度。 缺点是节点的数量必须作为每个转置表条目的一部分被保留，从而减少了对于给定量的存储可能的条目的有效数量。
这个方案可以在两个变体中实现，例如Big1和BigAll。 前者将转置表中的表状态计算为单个节点，后者作为N个节点，其中N是为了获得所存储的表状态的信息而搜索的板状态的数量。
-
(TwoDeep,
全文共28878字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144297]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
