如何处理转位表中重复绘制的问题？

Question

我在努力解决三人莫里斯问题。游戏的细节并不重要，这是一个类似于抽搐脚趾的游戏，但玩家可能会从某些位置强制取得胜利，或者通过在其他位置上反复重复游戏来迫使游戏永远重复。所以我想做一个函数，来判断一个球员是可以强迫胜利，还是通过重复来强迫平局。

我试过使用简单的否定，它工作得很好，但速度太慢，无法以无限的深度遍历游戏树。我想使用换位表，因为可能的职位数量很低(<6000)，但这正是我的问题所在。一旦我在换位表中添加(只列出了全部搜索的位置及其值，0、1或-1)，AI就会开始做出奇怪的举动，突然说这是在我被迫获胜的位置上的平局。

我认为问题来自转位表条目被保存为平面图，因为当我限制深度并且只保存强制胜利时，它似乎是有效的，但是我不知道如何解决这个问题并允许无限的深度。

下面是代码，以防我的实现出现问题：

int evaluate(ThreeMensMorris &board){
    //game is won or drawn
    if(board.isGameWon()) return -1; //current player lost
    if(board.isRepetition()) return 0; //draw by repetition

    //check if this position is already in the transposition table
    //if so, return its value
    uint32_t pos = board.getPosInt();
    for(int i = 0; i < transIdx; i++)
        if(transList[i] == pos)
            return valueList[i];

    //negamax
    //NOTE: moves are formatted as two numbers, "from" and "to",
    //where "to" is -1 to place a piece for the first time
    //so this nested for loop goes over all possible moves
    int bestValue = -100;
    for(int i = 0; i < 9; i++){
        for(int j = -1; j < 9; j++){
            if(!board.makeMove(i, j)) continue; //illegal move
            int value = -1 * evaluate(board, depth+1);
            board.unmakeMove(i, j);
            if(value > bestValue) bestValue = value;
        }
    }
    
    //we have a new position complete with a value, push it to the end of the list
    transList[transIdx] = pos;
    valueList[transIdx] = bestValue;
    transIdx++;
    
    return bestValue;
}

Answer 1

我建议你开始看国际象棋的转位表：表格。您需要给每个游戏状态一个(几乎)唯一的数字，例如通过Zobrist散列，也许这就是您在board.getPosInt()中所做的？

一个可能的错误是你没有考虑到是谁在改变它？即使一个位置在棋盘上是相同的，如果在一个位置上是玩家A回合，而在另一个位置上是B，那么情况就不一样了。在这个游戏中还有其他的事情要考虑吗？在国际象棋中，有一些东西需要考虑的可能性，以及其他特殊情况，以了解这个位置是否实际上是相同的，而不仅仅是棋子本身。

转位表非常复杂，很难调试。我希望你能让它发挥作用！