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

发布时间:2024年01月14日

引子

置换表是记忆化搜索技术的应用,置换表保存了某一盘面的搜索结果。当博弈树搜索遇到相同的局面时可以调用这些信息来减少重复搜索。那么如何设计一个置换表的节点就显得比较重要,本文在经典的置换表节点增加一个显示当前玩家的字段,这一字段补足了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路径拒之门外。

文章来源:https://blog.csdn.net/lishang6257/article/details/135579380
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。