国际象棋--可以用三角形的桌子来收集光伏移动，最后是大副吗？

Question

我试图弄清楚一个传统的国际象棋引擎(没有AI)是如何工作的，现在我试图收集pv (主变化)移动使用三角表。所以我使用了一个NxN表和一个非常简单的实现

private Integer alphaBeta(final int depth, int alpha, int beta) {
    ...
    pvLength[ply] = ply;
    ...
    while (move != null) {
        ...
        if (value > alpha) {  // (1)
            dPvTable[ply][ply] = move;
            nextPly = ply + 1;
            for (int p = nextPly; p < pvLength[nextPly]; ++p) {
                pvTable[ply][p] = pvTable[nextPly][p];
            }
            pvLength[ply] = pvLength[nextPly];
            ...
        }
        ...
    }
    ...
}

我正在比较提取的pv和从转位表中产生的pv。

如果pv不以死刑犯结束，它就能很好地工作。如果它以一个检查点结尾，则三角表只返回第一个(正确)移动。

我尝试过许多改变，但都没有成功。唯一有效的方法(以牺牲搜索速度为代价)是将条件(1)更改为

if (value >= alpha) {

但是很明显，这不是一个可以接受的改变，因为这样搜索就会一直探索树直到最后一步，并且不会在第一次找到的时候结束。

我只想知道，是否有人有同样的问题:这种行为是由于我的实现缺陷吗？或者这个方法只是不能返回所有的PV移动时有校验？

Answer 1

经进一步核实后，我将回答我的问题。

前提:在我的引擎中，使用alpha (-30000)来评估检查官。我使用的是迭代深化，所以(我猜)我不需要通过加法来确定检查点的“距离”，就像通常用来选择“最近的”一样。

因此，我认为使用此方法不可能在搜索期间或在搜索结束时读取pv行，此时pv以一个检查点结束:只有当( == > alpha)进行更新时，pv行才会被更新，并且在下一次迭代时，该条件不再满足，因为值为alpha。为了注册pv行，我尝试修改条件(value > alpha)，但是这样整个搜索就被扭曲了。

然而，你总是得到正确的最佳移动。

另一方面，当校验者不是alpha，而是alpha + ply时，此方法将返回pv行的所有移动。但这延长了搜索的速度，减缓了搜索速度。

即使使用Chess编程Wiki中描述的“堆栈上的pv -List”方法，我也注意到了相同的行为，因为pv行是在相同的条件下更新的。

这是一个例子，我希望它足够清楚。

The real pv line got from TT is:
    [h2-h3      , Kg4-f4     , Rd6-f6     , Nh5xf6(R)  , g2-g3      ]

In the search, we have:

            4 ->    move=g2-g3    value= 30000    alpha=306    beta=30000
            4 // g2-g3 is a pv move (gives checkmate at ply=4), and is
            4 // registered in pvTable because value > alpha
            4 old pv=[]
            4 new pv=[g2-g3      , b4xc3(P)   ]

         3 ->    move=Nh5xf6    value=-30000    alpha=-30000    beta=-306
         3 // Nh5xf6 is a pv move, but is not registered in pvTable because
         3 // value == alpha

      2 ->    move=Rd6-f6    value= 30000    alpha=306    beta=30000
      2 // Rd6-f6 is a pv move and is registered, but in a line that is not
      2 // linked to Nh5xf6
      2 old pv=[Ng5-f7     , g6-g5      , Bh6xg5(P)  , Kf4-e4     ]
      2 new pv=[Rd6-f6     , Bb6xd8(R)  , g2-g3      , b4xc3(P)   ]

   1 ->    move=Kg4-f4    value=-30000    alpha=-30000    beta=30000
   1 // Kg4-f4 is a pv move, but is not registered in pvTable because
   1 // value == alpha

0 ->    move=h2-h3    value=30000    alpha=-30000    beta=30000
0 // so the pv remains incorrect
0 old pv=[h2-h3      , Kg4-f4     , Ng5-f7     , Kf4-e4     , Rd6xg6(P)  ]
0 new pv=[h2-h3      , Kg4-f4     , Ng5-f7     , Kf4-e4     , Rd6xg6(P)  ]