Search algorithm

[calcitem]

Main logic:

#include "endgame.h"
#include "evaluate.h"
#include "mcts.h"
#include "option.h"
#include "thread.h"

using Eval::evaluate;
using std::string;

Value MTDF(Position *pos, Sanmill::Stack<Position> &ss, Value firstguess,
           Depth depth, Depth originDepth, Move &bestMove);

Value qsearch(Position *pos, Sanmill::Stack<Position> &ss, Depth depth,
              Depth originDepth, Value alpha, Value beta, Move &bestMove);

bool is_timeout(TimePoint startTime);

/// Search::init() is called at startup
void Search::init() noexcept { }

/// Search::clear() resets search state to its initial value
void Search::clear()
{
    Threads.main()->wait_for_search_finished();

#ifdef TRANSPOSITION_TABLE_ENABLE
    TT.clear();
#endif
    Threads.clear();
}

/// Thread::search() is the main iterative deepening loop. It calls search()
/// repeatedly with increasing depth until the allocated thinking time has been
/// consumed, the user stops the search, or the maximum search depth is reached.

int Thread::search()
{
    Sanmill::Stack<Position> ss;

    Value value = VALUE_ZERO;
    const Depth d = get_depth();

    if (gameOptions.getAiIsLazy()) {
        const int np = bestvalue / VALUE_EACH_PIECE;
        if (np > 1) {
            if (d < 4) {
                originDepth = 1;
                sync_cout << "Lazy Mode: depth = " << originDepth << sync_endl;
            } else {
                originDepth = 4;
                sync_cout << "Lazy Mode: depth = " << originDepth << sync_endl;
            }
        } else {
            originDepth = d;
        }
    } else {
        originDepth = d;
    }

    const time_t time0 = time(nullptr);
    srand(static_cast<unsigned int>(time0));

    if (rootPos->get_phase() == Phase::moving) {
        if (posKeyHistory.size() >= rule.nMoveRule) {
            return 50;
        }

        if (rule.endgameNMoveRule < rule.nMoveRule &&
            rootPos->is_three_endgame() &&
            posKeyHistory.size() >= rule.endgameNMoveRule) {
            return 10;
        }

        if (rule.threefoldRepetitionRule && rootPos->has_game_cycle()) {
            return 3;
        }

        assert(posKeyHistory.size() < 256);
    }

    if (rootPos->get_phase() == Phase::placing) {
        posKeyHistory.clear();
        rootPos->st.rule50 = 0;
    } else if (rootPos->get_phase() == Phase::moving) {
        rootPos->st.rule50 = static_cast<unsigned>(posKeyHistory.size());
    }

    MoveList<LEGAL>::shuffle();

    Value alpha = VALUE_NONE;
    Value beta = VALUE_NONE;

    if (gameOptions.getAlgorithm() != 2 /* !MTD(f) */) {
        alpha = -VALUE_INFINITE;
        beta = VALUE_INFINITE;
    }

    if (gameOptions.getMoveTime() > 0 || gameOptions.getIDSEnabled()) {
        debugPrintf("IDS: ");

        constexpr Depth depthBegin = 2;
        Value lastValue = VALUE_ZERO;

        const TimePoint startTime = now();

        for (Depth i = depthBegin; i < originDepth; i += 1) {
            TranspositionTable::clear();

            if (gameOptions.getAlgorithm() == 2 /* MTD(f) */) {
                // debugPrintf("Algorithm: MTD(f).\n");
                value = MTDF(rootPos, ss, value, i, i, bestMove);
            } else if (gameOptions.getAlgorithm() == 3 /* MCTS */) {
                value = monte_carlo_tree_search(rootPos, bestMove);
            } else {
                value = qsearch(rootPos, ss, i, i, alpha, beta, bestMove);
            }

            debugPrintf("%d(%d) ", value, value - lastValue);

            lastValue = value;

            if (is_timeout(startTime)) {
                debugPrintf("originDepth = %d, depth = %d\n", originDepth, i);
                goto out;
            }
        }
    }

    TranspositionTable::clear();

    if (gameOptions.getAlgorithm() != 2 /* !MTD(f) */
        && gameOptions.getIDSEnabled()) {
        alpha = -VALUE_INFINITE;
        beta = VALUE_INFINITE;
    }

    if (gameOptions.getAlgorithm() == 2 /* MTD(f) */) {
        value = MTDF(rootPos, ss, value, originDepth, originDepth, bestMove);
    } else if (gameOptions.getAlgorithm() == 3 /* MCTS */) {
        value = monte_carlo_tree_search(rootPos, bestMove);
    } else {
        value = qsearch(rootPos, ss, d, originDepth, alpha, beta, bestMove);
    }

out:

    lastvalue = bestvalue;
    bestvalue = value;

    return 0;
}

vector<Key> posKeyHistory;

Value qsearch(Position *pos, Sanmill::Stack<Position> &ss, Depth depth,
              Depth originDepth, Value alpha, Value beta, Move &bestMove)
{
    Value value;
    Value bestValue = -VALUE_INFINITE;

    Depth epsilon;

    if (pos->rule50_count() > rule.nMoveRule ||
        (rule.endgameNMoveRule < rule.nMoveRule && pos->is_three_endgame() &&
         pos->rule50_count() >= rule.endgameNMoveRule)) {
        alpha = VALUE_DRAW;
        if (alpha >= beta) {
            return alpha;
        }
    }

    // Transposition table lookup

    const Key posKey = pos->key();

    // check transposition-table

    const Value oldAlpha = alpha; // To flag BOUND_EXACT when eval above alpha
                                  // and no available moves

    Bound type = BOUND_NONE;

    const Value probeVal = TranspositionTable::probe(posKey, depth, alpha, beta,
                                                     type);

    if (probeVal != VALUE_UNKNOWN) {

        bestValue = probeVal;

        return bestValue;
    }

    // process leaves

    // Check for aborted search
    // TODO(calcitem): and immediate draw
    if (unlikely(pos->phase == Phase::gameOver) || // TODO(calcitem): Deal with
                                                   // hash
        depth <= 0 || Threads.stop.load(std::memory_order_relaxed)) {
        bestValue = Eval::evaluate(*pos);

        // For win quickly
        if (bestValue > 0) {
            bestValue += depth;
        } else {
            bestValue -= depth;
        }

        return bestValue;
    }

    // if this isn't the root of the search tree (where we have
    // to pick a move and can't simply return VALUE_DRAW) then check to
    // see if the position is a repeat. if so, we can assume that
    // this line is a draw and return VALUE_DRAW.
    if (rule.threefoldRepetitionRule && depth != originDepth &&
        pos->has_repeated(ss)) {
        return VALUE_DRAW;
    }

    // Initialize a MovePicker object for the current position, and prepare
    // to search the moves.
    MovePicker mp(*pos);
    const Move nextMove = mp.next_move();
    const int moveCount = mp.move_count();

    if (moveCount == 1 && depth == originDepth) {
        bestMove = nextMove;
        bestValue = VALUE_UNIQUE;
        return bestValue;
    }

    for (int i = 0; i < moveCount; i++) {
        TranspositionTable::prefetch(pos->key_after(mp.moves[i].move));
    }

    // Loop through the moves until no moves remain or a beta cutoff occurs
    for (int i = 0; i < moveCount; i++) {
        ss.push(*pos);
        const Color before = pos->sideToMove;
        const Move move = mp.moves[i].move;

        // Make and search the move
        pos->do_move(move);
        const Color after = pos->sideToMove;

        if (gameOptions.getDepthExtension() == true && moveCount == 1) {
            epsilon = 1;
        } else {
            epsilon = 0;
        }

        // epsilon += pos->piece_to_remove_count(pos->sideToMove);

        if (gameOptions.getAlgorithm() == 1 /* PVS */) {
            // debugPrintf("Algorithm: PVS.\n");

            if (i == 0) {
                if (after != before) {
                    value = -qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                     -beta, -alpha, bestMove);
                } else {
                    value = qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                    alpha, beta, bestMove);
                }
            } else {
                if (after != before) {
                    value = -qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                     -alpha - VALUE_PVS_WINDOW, -alpha,
                                     bestMove);

                    if (value > alpha && value < beta) {
                        value = -qsearch(pos, ss, depth - 1 + epsilon,
                                         originDepth, -beta, -alpha, bestMove);
                    }
                } else {
                    value = qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                    alpha, alpha + VALUE_PVS_WINDOW, bestMove);

                    if (value > alpha && value < beta) {
                        value = qsearch(pos, ss, depth - 1 + epsilon,
                                        originDepth, alpha, beta, bestMove);
                    }
                }
            }
        } else {
            if (after != before) {
                value = -qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                 -beta, -alpha, bestMove);
            } else {
                value = qsearch(pos, ss, depth - 1 + epsilon, originDepth,
                                alpha, beta, bestMove);
            }
        }

        pos->undo_move(ss);

        // Check for a new best move
        // Finished searching the move. If a stop occurred, the return value of
        // the search cannot be trusted, and we return immediately without
        // updating best move and TT.
        if (Threads.stop.load(std::memory_order_relaxed))
            return VALUE_ZERO;

        if (value >= bestValue) {
            bestValue = value;

            if (value > alpha) {
                if (depth == originDepth) {
                    bestMove = move;
                }

                if (value < beta) {
                    // Update alpha! Always alpha < beta
                    alpha = value;
                } else {
                    assert(value >= beta); // Fail high
                    break;                 // Fail high
                }
            }
        }
    }

    TranspositionTable::save(
        bestValue, depth,
        TranspositionTable::boundType(bestValue, oldAlpha, beta), posKey);

    return bestValue;
}

Value MTDF(Position *pos, Sanmill::Stack<Position> &ss, Value firstguess,
           Depth depth, Depth originDepth, Move &bestMove)
{
    Value g = firstguess;
    Value lowerbound = -VALUE_INFINITE;
    Value upperbound = VALUE_INFINITE;
    Value beta;

    while (lowerbound < upperbound) {
        if (g == lowerbound) {
            beta = g + VALUE_MTDF_WINDOW;
        } else {
            beta = g;
        }

        g = qsearch(pos, ss, depth, originDepth, beta - VALUE_MTDF_WINDOW, beta,
                    bestMove);

        if (g < beta) {
            upperbound = g; // fail low
        } else {
            lowerbound = g; // fail high
        }
    }

    return g;
}

bool is_timeout(TimePoint startTime)
{
    const auto limit = gameOptions.getMoveTime() * 1000;
    const TimePoint elapsed = now() - startTime;

    if (elapsed > limit) {
        return true;
    }

    return false;
}

[calcitem]

这里是一个关于置换表（Transposition Table, TT）的实现，用于棋类或其他回合制游戏中的搜索优化。置换表通常用于存储之前搜索的节点信息，以避免重复计算。您的实现中涉及了不同类型的边界（BOUND_EXACT, BOUND_UPPER, BOUND_LOWER），这些是alpha-beta剪枝的常用策略。下面是一些关于您代码实现中可能的逻辑问题和优化点：

1. 数据类型和值的正确性

• 您的TTEntry结构体中的value8定义为int8_t。这个数据类型仅支持-128到127的范围，这是否足以表示您的棋局评分？如果评分可能超出这个范围，您可能需要更大的数据类型。
• 类似地，depth8字段也是int8_t，这同样只支持非常有限的深度。确保这对您的搜索深度是足够的。

2. probe函数的逻辑

• 在probe函数中，您检查项的age是否与当前的transpositionTableAge匹配。如果不匹配，您直接返回VALUE_UNKNOWN。这里的逻辑是否正确取决于您如何处理age字段。如果您希望使用这个字段来检测条目是否过时（例如，来自之前的搜索迭代），那么这种实现是合适的。
• 您在判断边界类型时，对于BOUND_UPPER和BOUND_LOWER的处理逻辑应该反转。即：

  case BOUND_UPPER:
      if (tte.value() <= alpha) {
          return alpha;
      }
      break;
  case BOUND_LOWER:
      if (tte.value() >= beta) {
          return beta;
      }
      break;

  在这里，对于BOUND_UPPER应该是if (tte.value() >= beta)，而对于BOUND_LOWER应该是if (tte.value() <= alpha)，因为UPPER意味着实际值不大于alpha，LOWER意味着实际值不小于beta。

3. save函数的逻辑

• 在save函数中，如果在置换表中找到了相同的键且age相同，您仅当新条目的深度不大于旧条目时才更新。这通常是正确的，但是您还需要考虑当新值是更好的边界类型时也应该更新。

4. 清理机制

• 您使用了一个年龄计数器来确定何时清理整个表。这种方法可以工作，但也可能导致性能损失，因为可能过早地丢弃了有用的信息。通常，更好的方法是使用更复杂的置换策略，如淘汰最不常用或最浅的条目。

5. 性能考虑

• TT.move在probe函数中总是被设置，即使找到的值是VALUE_UNKNOWN。这可能导致不必要的移动设置。
• 如果性能问题依然存在，建议检查HashMap的实现，特别是其冲突解决机制和哈希函数的效率。

代码逻辑主要问题在于边界值的处理，可能导致alpha-beta剪枝不正确，从而影响搜索性能。建议对这些逻辑进行调整和测试。

---

代码存在一些可能影响性能和逻辑正确性的点。重点分析可能影响 alpha-beta 算法性能的地方：

1. 深度优先逻辑:

   • 代码中在TranspositionTable::probe函数里使用了深度比较。如果传入的depth参数大于置换表中条目的深度，这将导致函数返回VALUE_UNKNOWN。这意味着如果当前搜索的深度比存储在置换表中的深度更深，这个值将不会被用于剪枝，可能导致性能下降。这是正确的行为，但对性能有重要影响，尤其是在深度很大的搜索中。

2. 置换表的清理机制:

   • TranspositionTable::clear方法中的逻辑只有在transpositionTableAge达到uint8_t的最大值时才会真正清空置换表。这种机制可能导致置换表中包含大量无用的、过时的数据，从而影响查找性能。

3. Alpha-Beta 剪枝逻辑:

   • 在probe函数中，如果条目的值小于或等于alpha（BOUND_UPPER情况），或者大于或等于beta（BOUND_LOWER情况），它应该返回相应的值以直接进行剪枝。但是，如果value的比较结果不符合期望，你应该检查是否正确处理了所有情况。特别是，如果没有合适的返回，最后应该保证逻辑的完整性。

4. 值类型转换和范围检查:

   • 在你的TTEntry类中，value8和depth8字段是以8位存储的，你需要确保在使用这些字段之前它们没有溢出或者意外地被截断。此外，对这些字段的转换应当仔细处理以确保数据的正确性。

5. 并发和线程安全:

   • 根据你的代码，看起来HashMap可能会在多线程环境下访问（尽管你的代码中没有明确显示这一点）。如果是这样的话，你需要确保HashMap的实现是线程安全的，或者在访问时加以适当的同步措施。

6. 调试和性能监控:

   • 为了更好地理解性能问题，建议添加更多的调试语句来监控关键函数的调用频率、执行时间以及内存使用情况。这可以帮助你确定性能瓶颈是否真的与置换表的实现有关。

结合上述分析，如果你的 alpha-beta 算法性能较低，确实可能与置换表的实现有关。建议对可能影响性能的这些方面进行调优和测试，看看是否能通过调整这些逻辑来提升性能。

---

1. 在 TranspositionTable::probe 函数中，如果 depth > tte.depth()，直接跳转到 out 标签。这样做可能会错过一些有用的置换表项。更好的做法是继续执行，因为即使深度较浅，置换表项仍然可能包含有价值的信息，例如更好的边界值或最佳移动。

2. 在 TranspositionTable::save 函数中，检查了新项的深度是否大于现有项。这个逻辑没问题，但你可以考虑在替换置换表项时，优先替换年龄较老的项。这样可以更好地利用置换表空间。

3. 你使用了 TRANSPOSITION_TABLE_FAKE_CLEAN 宏来实现置换表的伪清理。这是一种节省时间的好方法，因为它避免了完全清空置换表。然而，这也意味着随着时间的推移，置换表的利用率可能会降低，因为一些过时的项目仍然存在。你可以考虑在搜索结束时或其他适当的时机进行完全清理。

4. 在 TranspositionTable::clear 函数中，你使用了 debugPrintf 函数。确保在生产代码中移除或禁用调试语句，以避免不必要的开销。

5. 你的实现没有利用 TranspositionTable::boundType 函数。考虑在 TranspositionTable::save 中使用它来确定边界类型，以提高代码的一致性和可读性。

总的来说，置换表实现看起来是合理的。Alpha-beta 算法的性能问题可能与其他因素有关，如搜索深度、启发式函数的质量、移动排序等。

另外，确保你的 HashMap 实现是高效的，因为置换表的性能在很大程度上取决于底层哈希表的质量。如果可能的话，考虑使用现有的、经过良好测试的哈希表实现。

希望这些建议对你有所帮助！如果你有任何其他问题，欢迎随时问我。

---

[calcitem]

1. 数据范围和表示

• 您的实现中TTEntry使用的int8_t来存储值（value8），这可能限制了评分的范围（-128到127）。这个范围可能不足以准确表示某些棋局的评分，尤其是在较深的搜索或者有多重材料差异的情况下。Stockfish使用int16_t来存储值，这提供了更大的范围（-32768到32767）。
• 同样，depth8字段的数据类型为int8_t，这意味着深度的存储也受到了限制。虽然这通常足够（深度通常不会超过100），但在复杂算法或深度增强策略中可能成为限制。

2. 老化机制的处理

• 您的代码中的老化机制（通过age8）看起来只在TRANSPOSITION_TABLE_FAKE_CLEAN启用时才活跃。这种方法可能会导致过时的数据被重复使用，从而影响搜索的质量。相比之下，Stockfish使用一个周期性更新的generation机制，这允许它更有效地区分当前搜索与之前搜索的数据。

3. 置换表的实现细节

• Stockfish使用固定大小的集群（Cluster），这有助于保证数据的缓存效率，同时实现了一个更复杂的替换策略来决定哪个条目应该被新的搜索数据覆盖。
• 您的实现似乎没有显式的替换策略，它只是在必要时更新或插入新条目。这可能导致置换表中保留了较多低价值的条目。

4. 缺少功能和可能的错误

• 在您的probe函数中使用goto可能导致代码难以跟踪和维护。这里推荐使用更清晰的流程控制结构。
• 代码中的TT_MOVE_ENABLE宏如果未定义，可能会导致tte.ttMove在未初始化的情况下被访问。

建议

• 考虑扩展value8和depth8的类型到至少int16_t，以便提供更大的范围和精确度。
• 实现一个更完善的老化和替换策略，参考Stockfish的做法，以提高置换表的效率和效果。
• 移除goto语句，采用更现代的流程控制方法来增强代码的可读性和可维护性。
• 如果TT_MOVE_ENABLE宏未定义，确保对应的功能不会尝试访问未初始化的变量。

[calcitem]

tt.h和tt.cpp文件中，实现了一个棋局的置换表（Transposition Table），这通常用于增加棋类游戏中搜索算法的效率，如alpha-beta剪枝。但是，检查您的代码后，发现可能存在几个潜在的问题和不足，这些问题可能导致性能不佳：

1. 数据类型选择：

   • 您在TTEntry中使用int8_t和uint8_t存储值和深度。这在处理更大范围或更细粒度的值和深度时可能不够用。比如，评分（value）的范围可能超过了int8_t的最大值127。

2. 缓存利用率：

   • 您的TTEntry结构可能没有优化以适应现代CPU的缓存行大小。不适当的结构大小可能导致缓存未命中率高，从而降低性能。

3. 冲突处理：

   • 您的实现中似乎没有明显处理哈希冲突的策略。当多个棋局位置映射到同一个哈希键时，可能会发生覆盖，这在棋类游戏中相对常见。

4. 置换表的清理机制：

   • 您使用了一个TRANSPOSITION_TABLE_FAKE_CLEAN的定义来决定是否使用年龄标记（age marker）。这个标记有助于在不完全清空表的情况下进行有效的更新，但是这种方式可能没有完全利用到置换表的历史优势，尤其是在较长的游戏或多次搜索中。

与Stockfish的实现相比，Stockfish在TTEntry中包括了更多的元素（如key, pv node, eval value等），这些都是为了提高置换表的准确性和效率。它还使用了复杂的替换策略和多线程安全的清理机制，以及高度优化的内存布局以适应现代硬件的特点。

建议改进：

• 扩展数据类型：考虑使用更大的数据类型（如int16_t或uint16_t）来存储更大范围的值。
• 结构大小优化：调整TTEntry的大小，使其适合现代处理器的缓存行大小（通常为64字节）。
• 改善冲突管理：实施更复杂的冲突解决策略，如使用链表或开放寻址法。
• 改善清理和更新机制：可能需要实现更复杂的清理机制，如周期性地重置部分旧数据而不是完全清空，或使用更精细的年龄和历史管理。

这些改进可能有助于提升您的alpha-beta剪枝算法的性能，通过减少无效的查找和提高置换表的命中率。

[calcitem]

在你的棋类游戏置换表（transposition table）的实现中，确实存在一些可能需要修正的问题。在比较你的实现和 Stockfish 的实现后，以下是一些关键点和建议的改进措施：

1. 使用标准类型定义

你的代码中使用了 int8_t 和 uint8_t，但未包括相应的头文件 <cstdint>。这可能会导致在某些编译器或环境中编译失败。应该在 tt.h 中包含 <cstdint>。

2. 封装和访问控制

Stockfish 的实现中使用了封装和更细致的访问控制来保护数据结构的完整性，例如使用 private 成员变量和更多的 friend 类声明。你的代码中应该考虑实现类似的封装措施来增强代码的健壮性和维护性。

3. 键的处理

Stockfish 在 TTEntry 中明确存储了键（key）的部分（16位），这有助于解决哈希冲突。你的实现似乎没有存储键，而是直接依赖 HashMap 的功能。考虑是否需要在 TTEntry 中存储键的一部分来改善性能和碰撞管理。

4. 年龄和生成管理

Stockfish 通过细致管理条目的生成和年龄，使用了复杂的逻辑来确定何时覆盖旧条目。这包括使用位运算来处理包装和生成的增量。你的实现中也使用了 age8，但处理方式相对简单。考虑引入更复杂的生成管理，以优化置换表的效率和有效性。

5. 多线程安全和性能

Stockfish 在处理置换表时采用了多线程安全措施，比如在 clear() 方法中使用多线程来清除表项。这种方法可以显著提高大型置换表处理的效率。如果你的环境支持多线程，应该考虑引入类似的策略。

6. 节点类型和深度计算

Stockfish 使用 pv node 位来标记主要变量节点，这有助于搜索算法优化。同时，深度处理也更为复杂，包括了相对深度和绝对深度的转换。你的实现中可能需要增加这种类型的支持，以便更好地利用置换表信息。

7. 函数实现和策略

Stockfish 的 probe 和 save 方法包含了复杂的逻辑，旨在最优化利用置换表。例如，在 save 方法中，有条件的覆盖逻辑以防止不必要的写操作。你的代码中的相应函数应该也采用这种策略，确保条目的正确更新。

建议你参照 Stockfish 的实现对你的代码进行重构和优化，特别是在内存管理、性能优化和多线程利用等方面。

[calcitem]

游戏置换表实现和Stockfish的实现之间有几点关键区别，我们可以一一检查并提出可能的改进。

1. 置换表结构体 TTEntry

• 字段使用: 您的实现使用了简化的字段，例如 value8、depth8、genBound8。Stockfish 使用更多的字段（例如 move16、value16、eval16 等），这使得它能够存储更多关于棋局的信息，例如确切的移动、评估值等。
• 字段大小: 您使用的是 int8_t 和 uint8_t 类型，这对于简单的值和深度是足够的，但限制了存储的范围和精度。如果您的棋类游戏评分的范围超出了-128到127，或者需要更深的搜索深度，则需要使用更大的数据类型。

2. 键冲突处理

• 键的存储: 在 Stockfish 的实现中，每个 TTEntry 包括一个 key16 字段，这有助于处理哈希冲突。您的实现似乎没有存储键本身，这可能导致无法区分不同棋局位置的冲突。
• 键的比较：Stockfish 在替换策略中使用键值进行比较，确保正确的位置信息被更新。您的实现需要添加相似的机制来确保键的一致性。

3. 年龄和清理

• 清理机制: Stockfish 使用 generation8 机制，通过周期性增加值并处理溢出来管理和清理置换表。您的实现中也有 age8，但其清理逻辑可能不够健壮，考虑采用类似 Stockfish 的方法。

4. 置换表的大小和内存管理

• 内存分配: Stockfish 使用大页面和对齐内存来优化置换表的性能。您的实现中使用的是 HashMap，这简化了代码但可能在性能上有所牺牲。如果性能是关键考虑因素，可能需要实现类似的内存管理策略。

5. 多线程支持

• 多线程清理: Stockfish 在清理置换表时使用多线程，这可以大大加速处理过程。如果您的应用场景中包含多线程环境，考虑添加对多线程的支持。

代码示例修改建议

您的代码实现中，您可能需要添加键的存储和比较逻辑，并改进您的 age8 使用策略，以便更可靠地管理置换表的有效性。这里是一个可能的示例改进：

// 在TTEntry中添加key字段和使用它的逻辑
struct TTEntry {
    TTEntry() { }

    Value value() const noexcept { return static_cast<Value>(value8); }
    Depth depth() const noexcept { return static_cast<Depth>(depth8) + DEPTH_OFFSET; }
    Bound bound() const noexcept { return static_cast<Bound>(genBound8); }
    Key key() const noexcept { return key8; }  // 假设使用uint8_t足以存储键的一部分

#ifdef TT_MOVE_ENABLE
    Move tt_move() const noexcept { return (Move)(ttMove); }
#endif

private:
    friend class TranspositionTable;
    uint8_t key8 {0};  // 添加一个键字段
    int8_t value8 {0};
    int8_t depth8 {0};
    uint8_t genBound8 {0};
#ifdef TRANSPOSITION_TABLE_FAKE_CLEAN
    uint8_t age8 {0};
#endif
#ifdef TT_MOVE_ENABLE
    Move ttMove {MOVE_NONE};
#endif
};

这只是开始。

[calcitem]

以下是关于置换表（TT）如何使用的关键点，包括ttMove、PV以及相关方面：

1. 置换表（TT）是一个哈希表，它存储了在搜索过程中遇到的位置信息。它允许通过缓存先前搜索过的位置的结果来避免重复工作。

2. 在search函数中，代码使用TT.probe(posKey, ss->ttHit)来探测置换表。它试图找到与当前位置的哈希键（posKey）对应的条目。如果找到了条目（ss->ttHit为真），则从该条目中检索到的移动将存储在ttMove中。

3. ttMove是在先前对同一位置的搜索中找到的最佳移动。在移动排序中，它被赋予更高的优先级，因为它在当前搜索中也更可能是一个好棋。

4. 代码会检查是否有一个可用的ttMove，以及它的值（分数）是否足够好以达到截断（ttValue）。如果ttMove是安静的（非捕获）并且导致beta截断，则会更新其移动排序分数，以鼓励在未来更早地进行搜索。

5. 主要变化（PV）是搜索认为的最佳移动序列。当找到更好的移动时，代码会更新PV（update_pv函数）。它将子节点的PV附加到当前节点的PV。

6. ss->ttPv标志表示当前节点是否是一个PV节点（即，从这个位置出发的最佳移动是否指向PV）。它用于决定是否更新PV并执行完整的PV搜索。

7. 搜索完成后，最佳移动、分数、深度和其他信息将使用tte->save()存回置换表中。这允许在未来的搜索中重用这些信息。

8. value_to_tt和value_from_tt函数用于在存储在置换表中的分数值和搜索中使用的实际分数值之间进行转换。这是为了根据当前的ply调整配对分数。

9. 当没有可用的思考移动时，extract_ponder_from_tt函数用于从置换表中检索思考移动。在退出搜索时，它会调用此函数为GUI提供一个思考移动，以便在对手的时间内进行思考。

置换表是国际象棋引擎中的关键优化。它存储先前计算的结果，允许基于先前的搜索进行移动排序，并促进主要变化的构建和更新。通过置换表高效地处理ttMove、PV和相关数据，以提高搜索效率和质量。