转置表会导致搜索不稳定 [英] Can a transposition table cause search instability

问题描述

我在写一个象棋引擎，最近添加了一个转置表。

当运行几个测试时，我发现虽然搜索仍然返回相同的最佳移动，移动的价值（对于最大化玩家来说有多好） 。

这是转置表的正常行为吗？我记得读一个转置表可能会导致搜索不稳定。这是什么意思？

解决方案

是的，转置表会引入搜索不稳定性。

幸运的是，这种情况很少发生，转座表的优点远远超过了复杂程度。

1。转置表的功能是什么？

在您的程序中添加转置表（TT）之后，您应注意两个主要区别：

1. 改善移动顺序：从TT移动通常是最好的移动


2. 提前截止：

<$>
在国际象棋中，您可以停止并使用存储在TT条目中的值 ，改进的移动顺序是最重要的因素。只有在游戏中，转换的可能性增加，你会看到更多的早期截止。




那么，搜索不稳定是什么意思？这意味着，当您搜索一个给定距离的位置，然后重复相同的搜索（相同的位置，相同的距离），您将得到相同的结果。





2。简单最小化/ alpha beta搜索algorthm





让我们先忽略搜索扩展，从一个简单的minimax或alpha-beta搜索开始。





请注意，搜索将具有可重复搜索的属性，并且将不会看到搜索不稳定性。即使您通过从转置表中移动来改善移动顺序，对于每个搜索仍然会得到相同的结果。但是，在添加TT之后，来自更深层搜索的额外临界值通常会破坏该属性并引入不稳定性。





例如，考虑一个包含深层战术的位置： / p>





• 低距离搜索可能看不到，但搜索距离较远。


• 之后，结果存储在TT中，用低距离重新搜索也将看到战术。


• 更糟糕的是，当TT条目被覆盖时，改进的知识再次变得很多。






因此，使用额外的知识强制提前截止是导致不稳定的因素。 （但实际上，它是值得的，因为它是一个理论问题。）





3。搜索扩展程序





应用于简单的alpha beta搜索时，改进的移动顺序本身不会导致搜索不稳定。在实现许多扩展的现实世界搜索算法中，情况更复杂。其中一些扩展对移动顺序也很敏感。





一个突出的例子叫做延迟移动减少（LMR）。它使用事实，移动顺序的质量通常如此高，使得仅仅前几个移动必须被彻底搜索，而其他移动很可能是坏的移动，并且将仅以较小的距离搜索。





LMR只是移动顺序使搜索较不可重复的一个例子。但同样，优势占主导地位。





4。搜索不稳定性是多少？





没有明确的答案。在实践中，你不能完全消除不稳定性，但如果不稳定性失去控制，你的搜索将变得效率低下。





当然，错误也可能是不稳定背后的原因。所以，这是你的搜索中的错误吗？好吧，我不知道。可能。 ： - ）




I'm writing a chess engine and recently added a transposition table.

When running a few tests, I found that although the search still returned the same best move, the value of the move (how good it is for the maximizing player) fluctuated.

Is this normal behavior for a transposition table? I remember reading that a transposition table can cause search instability. Is this what that means? So is this a normal occurrence or a serious bug in my code?

解决方案

Yes, transposition tables introduce search instability.

Fortunately, it occurs rarely enough that the advantages of transposition tables outweigh that complication by far.

1. What is the function of a transposition table?

After adding transposition tables (TT) to your program, you should notice two main differences:

1. Improve move ordering: The move from TT is generally the best possible move
2. Early cutoffs: When you reach a position again, which has been already searched with a greater distance, you can stop and use the value stored in the TT entry

In chess, the improved move ordering is the most important factor. Only in endgames, the likelihood of transposition increased, and you will see more early cutoffs.

So, what does search instability mean? It means that when you search one position with a given distance and later repeat the same search (same position, same distance), you will get the identical result.

2. Simple minimax/alpha beta search algorthm

Let us first ignore search extension and start with a simple minimax or alpha-beta search.

Note that you search will have the property that searches are repeatable, and will see no search instabilities. Even if you improve your move ordering with a move from a transposition table, you will still get the same result for every search. However, after adding TT, the extra cutoffs from a deeper search will in general break that property and introduce instabilities.

For instance, consider a position containing a deep tactic:

• A search with a low distance may not see it, but a search with a greater distance will.
• After that result is stored in the TT, a re-search with the low distance will see the tactic, too. It now behaves differently compared to the original search.
• Even worse, when the TT entry is overwritten, the improved knowledge gets lots again.

So, using extra knowledge to force early cutoffs is a factor that leads to instability. (But in practice, it is worth it, as it is more a theoretical problem.)

3. Search extensions

When applied to a simple alpha beta search, the improved move ordering itself does not lead to search instabilities. The situation is more complicated in real-world search algorithms which implement many extensions. Some of these extensions are sensitive to the move ordering, too.

One prominent example is called Late Move Reduction (LMR). It uses the fact, that the quality of move ordering is generally so high that only the first few moves have to be searched thoroughly, while the other moves are most likely bad ones and will only be searched with a reduced distance.

LMR is only one example where move ordering makes search less repeatable. But again, the advantages predominate.

4. How much search instability is normal?

There is no clear answer. In practice, you cannot eliminate instabilities completely but if the instability gets out of control, your search will become inefficient.

Of course, bugs can be the reason behind instabilities, too. So, is it a bug in your search? Well, I don't know. Could be. :-)

这篇关于转置表会导致搜索不稳定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！