基于博弈树的开源五子棋AI教程[6 置换表]

引子

置换表是记忆化搜索技术的应用，置换表保存了某一盘面的搜索结果。当博弈树搜索遇到相同的局面时可以调用这些信息来减少重复搜索。那么如何设计一个置换表的节点就显得比较重要，本文在经典的置换表节点增加一个显示当前玩家的字段，这一字段补足了zobrist hash单向函数的缺点，如果节点需要使用更浅深度的信息，可以通过迭代的方式来求解，丰富了置换表的信息。

定义

置换表中包换了搜索状态的散列值，剪枝信息，PV信息以及用于迭代获取浅层深度的玩家信息。

//EXACT ：表示记录中存储的分数是一个精确的估值分数。
//hashfBETA ：表示记录中存储的分数是一个下界（lower bound）。这意味着在搜索中发现了一个分数，它至少是某一分支的分数下限，可能更高。
//hashfALPHA ：表示记录中存储的分数是一个上界（upper bound）。这意味着在搜索中发现了一个分数，它至多是某一分支的分数上限，可能更低。
struct NABtransportTableNode {
    quint64 key;
    int value;
    quint8 depth;
    quint8 flags;
    MPoint bestMove;
    MPlayerType lastPlayer; //当前hash状态下，最后一个落子类型

    NABtransportTableNode() : key(InitialZobristHash), value(0), depth(InitialDepth), flags(hashfEmpty),
        bestMove(InvalidMPoint), lastPlayer(PLAYER_NONE){}
};

实现

置换表需要实现三个最主要的功能，获取，添加，清除。根据获取信息的需求不同给出三个函数getNABTranspositionTable用于获取并修改搜索中的剪枝信息，getPVNABTranspositionTable更关注获取某一指定盘面下的搜索结果，getBestMoveNABTranspositionTable更暴力，我只需要当前状下最佳着法即可。

    //置换表[用于负极大搜索，对于其他搜索方式需要修改，未做测试]
    bool getNABTranspositionTable(int &score, int depth, int &alpha, int &beta) const;
    bool getPVNABTranspositionTable(int&score, MPoint& bestMove, int depth, const quint64 &curhash) const;
    bool getBestMoveNABTranspositionTable(MPoint &bestMove) const;
    void appendNABTranspositionTable(int depth, int val, int hashf, MPoint bestMove, MPlayerType lastPlayer);
    void clearNABTranspositionTable(quint8 minCutDepth = InitialDepth);

这里只给出置换表中使用最多的获取节点剪枝信息到置换表中实现。追加表项的方法和清除置换表的方法相对简单，可以移步源代码一观。

//置换表
/*不用标记玩家或者交换上下界:因为评估是根据当前层的玩家决定的，无论是否交换手，
该层玩家始终没有变化，区别只不过是Max还是Min玩家罢了*/
bool ZobristHash::getNABTranspositionTable(int& score, int depth, int &alpha, int &beta) const
{

    if(!globalParam::utilGameSetting.IsOpenTranspositionTable) return false;

    QReadLocker locker(&globalParam::transportTableLock);
    NABtransportTableNode *hashNode = &globalParam::transportTable[m_hash & globalParam::transportTableSizeMask];
    if (hashNode->key == m_hash) {
        //因为不同棋子数目的棋盘分数没有可比性
        if(hashNode->depth < depth) return false;
        int storedScore(-INT_MAX);
        if(hashNode->depth == depth){
            storedScore = hashNode->value;
        }
        else{
            MPoint nextMove = hashNode->bestMove;
            MPlayerType nextPlayer = UtilReservePlayer(hashNode->lastPlayer);
            if(nextMove == InvalidMPoint || nextPlayer == PLAYER_NONE) return false;
            quint64 nextHash = generateHash(m_hash, nextMove, PLAYER_NONE, nextPlayer);

            for (int curDepth = 1; curDepth < depth; ++curDepth) {
                NABtransportTableNode *nextHashNode = &globalParam::transportTable[nextHash & globalParam::transportTableSizeMask];
                if (nextHashNode->key == nextHash) {
                    nextMove = nextHashNode->bestMove;
                    nextPlayer = UtilReservePlayer(nextPlayer);
                    nextHash = generateHash(nextHash, nextMove, PLAYER_NONE, nextPlayer);
                }
            }
            if(getLeafTable(globalParam::AIPlayer, storedScore, nextHash)){
                if(nextPlayer != globalParam::AIPlayer) storedScore *= -1;
            }
        }
        if(hashNode->flags == hashfExact) {//精确值
            score = storedScore;
            return true;
        }
        else if((hashNode->flags == hashfLowerBound) && score > alpha) alpha = score;//更新alpha
        else if ((hashNode->flags == hashfUperBound) && score < beta)  beta = score;//更新beta
        if(alpha >= beta){//剪枝
            score = hashNode->value;
            return true;
        }
    }
    return false;
}

这里实现区别于网上经典的实现方法，一般而言置换表中某一节点的深度越深，得到的信息越可靠。然而在五子棋中并不能一概而论，深度越深，着法越可靠，但是得分就不可靠了。深度不同，叶子棋盘的落子数必然不同，在得分没有归一化的情况下盲目使用是非常不安全的。基于这点发现，实现是通过迭代寻找指定深度，然后通过查找叶子表来求解分数，这样避免了子数不一致进行尴尬局面。
这种实现方式也可以认为是一种时间换空间策略，如果保存某一盘面的所有深度下搜索信息，置换表将成倍数递增，增加了程序的内存负担。

讨论与尾记

通过对极大极小的讨论我们可以知道一点，剪枝算法是安全可靠的，无论剪枝与否，PV路径始终是可以被搜索出来，然而置换表的引入虽加快了搜索，但搜索的不稳定性问题便会凸显出来。在对弈基本技术-置换表篇中指出

当你用置换表时，如果你允许搜索过程根据散列项来截断，那就会产生另一个问题，你的搜索会受“不稳定性”的捆扰。
　　不稳定性至少是由以下因素引起的：
　　1. 你可能在做6层的搜索，但是如果你在散列项中得到10层搜索的结果，就可能根据这个值来截断。在后来的搜索中，这个散列项被覆盖了，因此你在这个结点上得到了两个不同的值。
　　2. Zobrist键值无法记录到达结点的线路，这个结点上不是每条线路都有相同结果的。如果某条线路遇到重复局面，那么散列项的值就会跟路线有关。因为重复局面会导致和局的分值，或者至少不一样的分值。

还有一个原因已经在搜索篇章点出，评分视角的不同，评分会有差异，如果直接使用这些信息截断，极有可能将PV路径拒之门外。