logo标签列表

置换表导致国际象棋引擎失败

c++chess
3
前言：我知道这个问题可能对于Stack Overflow来说有点太宽泛了。尽管如此，我已经尽力添加了尽可能多的信息。
我正在使用C++从头开始编写一个国际象棋引擎，它大部分已经完成（除了它有一个弱的评估函数）。然而奇怪的是，当置换表启用时，引擎每次都会输掉比赛，犯下非常明显的低级错误（失去一位皇后，或者有时是一位皇后和另一件棋子）。当禁用置换表探测时，引擎轻松地击败了Nero和TSCP。
我使用了一个非常简单的置换表实现，采用始终替换方案，取自Bruce Morland的网站here。
这里是探测实现：
bool probe_table(TranspositionTable& t_table, unsigned int ply,
uint64 hash_key, unsigned int depth, unsigned int& pv_move, int& score,
int alpha, int beta)
{
    unsigned int index = hash_key % t_table.num_entries;

    assert(index < t_table.num_entries);

    if(t_table.t_entry[index].hash_key == hash_key)
    {
        pv_move = t_table.t_entry[index].move;

        if(t_table.t_entry[index].depth >= depth)
        {
            score = t_table.t_entry[index].score;

            if(score > IS_MATE) score -= ply;
            else if(score < -IS_MATE) score += ply;

            switch(t_table.t_entry[index].flag)
            {
                case TFALPHA:
                {
                    if(score <= alpha)
                    {
                        score = alpha;
                        return 1;
                    }
                }
                case TFBETA:
                {
                    if(score >= beta)
                    {
                        score = beta;
                        return 1;
                    }
                }
                case TFEXACT:
                {
                    return 1;
                }
                default: assert(false); // At least one flag must be set.
            }
        }
    }

    return 0;
}

在alpha-beta搜索中，表格被探测（根据截断等情况，条目也被正确地存储）：
if(probe_table(board.t_table, board.ply, board.hash_key, depth, pv_move,
    score, alpha, beta))
{
    return score;
}

编辑：为了完整起见，以下是在搜索中存储代码的重要部分摘录：

if(score > alpha) // Alpha cutoff.
{
    if(score >= beta) // Beta cutoff.
    {
        ...

        store_entry(board.t_table, board.ply, board.hash_key, best_move,
                    beta, depth, TFBETA);

        return beta;
    }

    alpha = score;

    ...
    }
}

...

assert(alpha >= old_alpha);

if(alpha != old_alpha)
{
    store_entry(board.t_table, board.ply, board.hash_key, best_move,
        best_score, depth, TFEXACT);
}
else
{
    store_entry(board.t_table, board.ply, board.hash_key, best_move,
        alpha, depth, TFALPHA);
}

我已经考虑和探索了引擎的每个其他部分的故障，但没有出现任何故障。完全禁用探测（但仍然使用表来存储PV线），效果非常好。
我还考虑了我天真实现思考的影响。为了思考，每当有一个思考移动可用时，我只需向UCI打印出bestmove xxxx ponder xxxx。如果启用了思考，GUI会让引擎思考（这只是一个常规搜索，但稍后将通过置换表使用）。
为了测试，我完全禁用了思考，但没有显示任何改进。在一段时间内获得胜利后，引擎只是放弃了它的皇后。我认为这要么是由于表中的某些错误条目，要么是由于我无法理解的其他稳定性问题导致的。
这就是我需要遇到过这种情况的人指点我一个大致方向的地方。
编辑：正如grek40所要求的那样，这里有一个刚刚发生的例子（引擎是白色，轮到白方移动）。

Position

引擎再次由于愚蠢的移动而输掉了比赛。请注意，引擎达到这样糟糕的位置可能是因为置换表本身。
在比赛中填充置换表的情况下分析这个位置：
info score cp -425 depth 1 nodes 1 time 0 pv e1d1
info score cp -425 depth 2 nodes 2 time 0 pv e1d1
info score cp -425 depth 3 nodes 3 time 0 pv e1d1
info score cp -425 depth 4 nodes 4 time 0 pv e1d1
info score cp -425 depth 5 nodes 5 time 0 pv e1d1
info score cp -425 depth 6 nodes 6 time 0 pv e1d1
info score cp -425 depth 7 nodes 7 time 0 pv e1d1
info score cp -425 depth 8 nodes 8 time 0 pv e1d1
info score cp -425 depth 9 nodes 9 time 0 pv e1d1
info score cp -425 depth 10 nodes 10 time 0 pv e1d1
info score cp -440 depth 11 nodes 10285162 time 3673 pv f5f8 e7f8 b2b3 b7b5 e1c1 d6d5 a3a4
info score cp -440 depth 12 nodes 29407669 time 10845 pv f5f8 e7f8 e1f1 f8e7 f1f5 d6d5
bestmove f5f8 ponder e7f8

再次分析不使用置换表（实际上，使用了表，但已清除）：

info score cp -415 depth 1 nodes 82 time 0 pv f5f8
info score cp -415 depth 2 nodes 200 time 0 pv f5f8 e7f8
info score cp -405 depth 3 nodes 900 time 0 pv f5f8 e7f8 b2b3
info score cp -425 depth 4 nodes 2936 time 1 pv f5f8 e7f8 b2b3 f8e7
info score cp -415 depth 5 nodes 10988 time 4 pv f5f8 e7f8 b2b3 b7b5 e1d1
info score cp -425 depth 6 nodes 65686 time 25 pv f5f8 e7f8 e1f1 d7e7 f1d1 b7b5
info score cp -420 depth 7 nodes 194124 time 76 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f7
info score cp -425 depth 8 nodes 357753 time 141 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f5 d7c7
info score cp -425 depth 9 nodes 779686 time 292 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
info score cp -425 depth 10 nodes 1484178 time 560 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
info score cp -435 depth 11 nodes 29481132 time 11117 pv f5f8 d6d5 e1e5
info score cp -435 depth 12 nodes 106448053 time 41083 pv f5f8 e7f8
bestmove f5f8 ponder e7f8

值得注意的是，在深度为10时，得分从置换表搜索中准确无误。编辑：此位置在比赛后进行了分析。在比赛中，引擎没有足够的时间完成更高深度的搜索，导致它下出了荒谬的e1d1。为什么会发生这种情况呢？引擎从深度1开始就找到了更好的着法，但从置换表中却找到了不同的着法。我还想知道为什么在置换表搜索中没有PV线。我最好的猜测是来自Bruce Morland网站上的搜索不稳定性引用：Zobrist键不考虑到达节点的路径。不是每条路径都相同。可能某个哈希元素中的分数是基于一条路径的，如果在树的其他点遇到重复，则该路径会包含重复。重复可能会导致平局分数，或至少是不同的分数。编辑：我尝试禁用当没有TFEXACT值时存储到表格中。也就是说，我停止了存储和检索TFALPHA / TFBETA值，并且它的效果非常好。有人知道原因吗？
你能否用确定性的移动序列重现你的问题？ - grek40
你需要调试你的代码。找出导致由于置换表检查而产生错误移动的确切代码路径。添加转储表的函数。为表格添加单元测试。当您似乎确定发生了置换时，请打印一些内容。 - M.M
@Fernando 我有同样的问题，我添加了TT后我的引擎变得弱了，正在寻找解决方案。 - tttony
1
你可以查看我的Github获取我的TT代码：https://github.com/fernandotenorio/Tunguska - Fernando
@Fernando 谢谢你的 Git。我会看一下 :) 两年前我没有解决这个问题。 - Shreyas
显示剩余16条评论
1个回答
0

我注意到您在检查深度标准之前就已经设置了（通过引用传递的）pv_move。这意味着probe_table可能会更改pv_move并仍然返回0（未命中）（而不是设置score）。这看起来很糟糕？

如果哈希表项存在，则它是PV线，其第一个元素是PV移动，无论深度如何。 PV移动作为移动得分更高，并由Alpha-Beta首先搜索。如果发现该移动不好，它只会正常移动。但是，如果条目存在且满足深度标准，则使用标志设置相关分数，然后probe_table()返回。然后，Alpha-Beta看到满足深度标准并返回位置的分数而不进行搜索。太长不看：这是设计上的。 - Shreyas
好的，谢谢。感谢您包含Morland链接和您的代码。将您的代码与网站代码进行比较，看起来Morland从未在移动循环内部记录TFALPHA哈希，只有在之后使用最大alpha时才会记录。您似乎正在存储每当alpha==oldalpha时，内部。不知道这是否也会有所不同... - Jeff Y
虽然你可能是对的，但我会尝试使用Morland的确切代码。 - Shreyas
其实，没关系。如果 score >= beta，那么在使用 TFBETA 进行哈希后，它会立即返回 beta。 - Shreyas
如果(depth == 0) return quiescence(alpha, beta, board, search_info);。与Morland不同，我没有将这个值哈希化，也不知道为什么。我应该这样做。谢谢你指出这一点。你说得对，我可能会错过一些东西，我会修复它。但这并不能解释为什么引擎会输 :(（或者可以吗？） - Shreyas
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接