-
Notifications
You must be signed in to change notification settings - Fork 0
Home
這是一個基於Qt開發的五子棋程式，借鑑了一些西洋棋程式的演算法，以容易理解的方式撰寫，程式碼分為以下6部分：Algorithm, Core, Evaluation, Game, Search, Windows。
為了可讀性而放棄了Bitboard，運用Multiple Pattern Matching計算單行分數，選擇經典的Aho–Corasick Algorithm，這裡直接使用開源實現。
此實現簡單易用，值得注意的是由於trie有成員變數是unique_ptr，因此沒有Default Copy Constructor跟Default Copy Assignment Operator。
共用的enum，例如：棋型分數、棋子顏色、勝負狀態。棋型分數如下，只要保證高分棋型遠大於低分棋型且足夠多的低分棋型能夠媲美高分棋型就可以。
enum Score {
One = 20,
Two = 120,
Three = 720,
Four = 720,
OpenFours = 4320,
Five = 50000,
Max = 10000000,
Min = -Max
};負責估計局面及著法的分數，透過字串匹配演算法實現。局面分數為橫15行；豎15行；對角線21行；反對角線21行的總和，每一行分數則為AC自動機匹配到的棋型分數總和，棋型分數表如下，'0'代表空位，'1'代表我方棋子。每下一子就更新一次局面分數，只要更新該子對應的那4行就可以了，有些位置對角線或反對角線是沒有分數的，因為不能形成五子，計算分數是沒有意義的，另外如果悔棋只需要根據歷史紀錄復原分數即可。
const QHash<std::string, Score> shapeScoreTable = {
{"00100", One},
{"01010", Two}, {"001100", Two},
{"01110", Three}, {"010110", Three}, {"011010", Three},
{"11110", Four}, {"01111", Four}, {"10111", Four}, {"11011", Four}, {"11101", Four},
{"011110", OpenFours},
{"11111", Five}
};著法分數由上、下、左、右、左上、左下、右上、右下八個方向的棋型總和而來，每個方向延伸4個位置，即橫、豎、對角線、反對角線每一個方向各9(4+1+4)個位置，同樣通過AC自動機匹配這9個位置所對應的棋型，著法分數還分為對於黑方與對於白方的分數，兩個分數之和表示該著法對雙方的價值。
在搜尋過程中會頻繁計算棋型分數且容易計算到同樣的棋型，為了減少重複計算而引入了QCache，必須設定一個足夠大的快取，棋型總數為
QCache<std::string, int> shapeScore = QCache<std::string, int>(1 << 23);生成著法並透過Evaluator更新著法的分數，便於後續著法排序。在著法生成器中有一個重要參數r，用於限制範圍，一般來說r至少要是2以上，也就是考慮落子位置附近2圈，在落子後將落子位置附近r圈的點都加入著法生成器，同時更新落子位置八個方向的4個延伸位置的分數，每個著法存有黑方與白方橫、豎、對角線、反對角線四行的分數，最後將落子位置由著法生成器中移除，悔棋同樣根據歷史紀錄復原。
void MovesGenerator::move(const QPoint &point)
{
const int r = moves.empty() ? 1 : 3;
history.push(moves);
// 加入落子位置附近r圈的點
for (int i = -r; i <= r; ++i) {
for (int j = -r; j <= r; ++j) {
if (const auto neighborhood = point + QPoint(i, j); Search::Engine::isLegal(neighborhood)
&& (*board)[neighborhood.x()][neighborhood.y()] == Empty) {
if (!moves.contains(neighborhood)) {
moves.insert(neighborhood, {{0, 0, 0, 0}, {0, 0, 0, 0}});
}
}
}
}
constexpr std::array<int, 2> d = {-1, 1};
constexpr std::array<int, 4> dx = {1, 0, 1, 1};
constexpr std::array<int, 4> dy = {0, 1, 1, -1};
// 更新八個方向的四個延伸位置的點的分數
for (size_t i = 0; i < 2; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 1; k <= 4; ++k) {
if (const auto neighborhood = point + QPoint(d[i] * dx[j] * k, d[i] * dy[j] * k);
Search::Engine::isLegal(neighborhood) && (*board)[neighborhood.x()][neighborhood.y()] == Empty) {
if (moves.contains(neighborhood)) {
const auto [blackScore, whiteScore] = evaluator->evaluatePoint(neighborhood, j);
moves[neighborhood].first[j] = blackScore;
moves[neighborhood].second[j] = whiteScore;
}
}
}
}
}
// 移除落子位置
moves.remove(point);
}包含最重要的搜尋演算法以及搜尋所需的同形表，涉及到除了Windows之外的所有程式。
同形表需要將局面hash，並儲存該局面的分數，當搜尋到相同局面時直接回傳紀錄的分數。同形表與PVS和Forward Pruning的交互作用下會導致搜尋的不穩定性，然而它能夠大幅提升搜尋速度，因此這樣的Trade-off是值得的。Hash方法採用Zobrist hashing，產生一個亂數代表開始局面，並對黑、白兩方的所有建立亂數表，用於表示黑子、白子落子位置。
TranspositionTable::TranspositionTable(const size_t &size)
: hashTable(QVarLengthArray<std::array<HashEntry, 8>>(size))
, mask(size - 1)
, checkSum(0) // 開始局面
, age(0)
{
std::random_device device;
std::default_random_engine engine(device());
std::uniform_int_distribution<unsigned long long> distribution;
// 建立雜湊表
for (size_t i = 0; i <= mask; ++i) {
hashTable[i].fill(HashEntry{0, HashEntry::Exact, {-1, -1}, 0, 0, MISS});
}
// 建立亂數表
for (size_t i = 0; i < 15; ++i) {
for (size_t j = 0; j < 15; ++j) {
blackRandomTable[i][j] = distribution(engine);
whiteRandomTable[i][j] = distribution(engine);
}
}
}同形表替換策略採用Aging技術，優先替換相同局面的Entry，再替換過老的Entry。
void TranspositionTable::insert(const unsigned long long &hashKey, const HashEntry::Type &type,
const QPoint &move,
const int &depth, const int &score)
{
const auto index = hashKey & mask;
auto &entries = hashTable[index];
auto *replacement = &entries.front();
for (auto &entry : entries) {
// 相同局面的Entry
if (entry.lock == hashKey) {
replacement = &entry;
break;
}
// 過老的Entry
if (entry.depth - (age - entry.age) < replacement->depth - (age - replacement->age)) {
replacement = &entry;
}
}
if (type != HashEntry::Exact && depth + 2 < replacement->depth) {
return;
}
replacement->lock = hashKey;
replacement->type = type;
replacement->move = move == QPoint(-1, -1) ? replacement->move : move;
replacement->depth = depth;
replacement->score = score;
replacement->age = age;
}探測同形表時，需要entry深度大於等於搜尋深度才能使用，這是因為較淺的搜尋分數不可信，即使深度不足仍然可以提供著法，通過這樣的啟發能夠更快的搜尋到PV-Path，另外當探測到相同局面時，更新該entry的age，這是基於Temporal locality。
int TranspositionTable::probe(const unsigned long long &hashKey, const int &alpha, const int &beta,
const int &depth, QPoint &move)
{
const auto index = hashKey & mask;
auto &entries = hashTable[index];
for (auto &[entryLock, entryType, entryMove, entryAge, entryDepth, entryScore] : entries) {
if (entryLock == hashKey) {
// 提供著法
move = entryMove;
// 更新entry的age
entryAge = age;
// entry深度需大於搜尋深度
if (entryDepth >= depth) {
switch (entryType) {
case HashEntry::Exact:
return entryScore;
case HashEntry::LowerBound:
if (entryScore >= beta) {
return entryScore;
}
break;
case HashEntry::UpperBound:
if (entryScore <= alpha) {
return entryScore;
}
break;
}
}
}
}
return MISS;
}一種基於Alpha-Beta Pruning的搜尋演算法，其假設第一個著法為PV-Node，因此該演算法需要Move ordering，這裡按照著法生成器給出的著法分數排序，該演算法對第二個之後的著法進行 Null Window Search (Zero Window Search) 驗證是否為PV-Node，當該著法是PV-Node時，重新進行完整的搜尋，在經過Move ordering後，一般來說PV-node不會是很後面的著法，只有在勢均力敵的情況下才有可能發生，基於棋型的Evaluation在雙方皆沒有優勢棋型時就是這樣的情形，然而類似圍棋的外勢，或許某一方已經占據極大優勢，這種處境就會導致搜尋演算法錯誤判斷局勢且搜尋效率較低，但設計出一個Evaluation能夠正確地評估這種情況是非常困難的，因此有些引擎會採用NNUE作為Evaluation。
int pvs(alpha, beta, depth) {
if (depth <= 0) {
return evaluate(); // 這裡可以是Quiescence Search，一般來說會進行VCF搜尋，但會花費更多時間
}
moves = generate();
first move = moves.front();
doMove(first move);
// 完整的搜尋
score = -pvs(-beta, -alpha, depth - 1);
undoMove();
if (score > alpha) {
alpha = score;
}
for (move : Remaining moves) {
doMove(move);
// NWS (ZWS)
score = -pvs(-alpha - 1, -alpha, depth - 1);
undoMove(move);
// 確認是否為PV-Node
if (score > alpha && score < beta) {
doMove(move);
// 重新進行完整的搜尋
score = -pvs(-beta, -alpha, depth - 1);
undoMove();
}
if (score >= beta) {
return score; // Fail-Soft Beta-Cutoff.
}
if (score > alpha) {
alpha = score;
}
}
return score;
}那麼為什麼 NWS (ZWS) 能加速搜尋呢？這是因為在Negamax+Alpha-Beta Pruning中的
如果能夠預先知道分數是否也能夠直接使用NWS呢？答案是不行的，Branch and Bound的bound必須建立在有已知解的前提下，因此就算已知無禁手規則下黑方必勝，使用勝利分數進行NWS只會讓所有路線都產生
不像Alpha-Beta Pruning是安全的，Forward Pruning是有風險的，幸運的是有一些方法可以使風險降低，大多數的Forward Pruning是利用前面提到的
非常有效的一種Forward Pruning，讓對手多走一步，並進行較淺的搜尋，如果搜尋到的分數仍然大於
Null Move Pruning不能在以下兩種局面使用
- 我方正被將軍，套用在五子棋就是我方目前沒有直接勝利的著法且對方已有連四棋型。
- 迫移局面(Zugzwang)，五子棋不會有這種局面，因為五子棋走棋肯定是比不走棋好的。
這個方法似乎很完美，然而進行更淺的搜尋會更容易受Horizon effect影響，因此搜尋過程中必須適當地延伸搜尋深度。
// R: Null Move Pruning Depth Reduction, 一般是2或3，也有Adaptive Null Move Pruning這樣的做法。
if (nodeType == CutNode && !inCheck && nullOk) {
doNullMove(); // 交換落子方
score = -pvs(-beta, -beta + 1, depth - R - 1); // 實作中需傳遞nodeType
undoNullMove(); // 復原
if (score >= beta) {
return beta;
}
}對當前節點的前M個著法進行較淺的搜尋，如果有C個的著法的搜尋分數大於
/*
MC_C: Multi-Cut number of cutoffs.
MC_M: Multi-Cut number of moves.
MC_R: Multi-Cut depth reduction.
*/
if (nodeType == CutNode && depth > MC_R && moves.size() >= MC_M) {
c = 0;
for (m = 0; m < MC_M; ++m) {
doMove(moves[m]);
score = -pvs(-beta, -alpha, depth - MC_R - 1); // 實作中需傳遞nodeType
undoMove();
if (score >= beta) {
if (++c >= MC_C) {
return beta;
}
}
}
}前面提到的Forward Pruning都是在Cut-Node使用，這個方法對PVS做出一些修改，使得Forward Pruning也可以在All-Node使用。詳細可參閱原始論文。
對於對手已經有連四棋型且我方沒有直接勝利的著法時，需要延伸這個路線的搜尋，這是必要的，否則搜尋引擎的棋力會相當弱，原因是前面提到的Horizon effect。這個延伸方法並不能保證最終局面是quiescence，因為我方還有可能VCT或VCF，對方還有可能VCT，前者最糟就是錯過本來能贏的機會，這還能接受，然而後者就是最不希望出現的情況，想要解決後者必須進行VCT搜尋，但VCT搜尋相當耗時。
主介面與遊戲介面的實現，主要負責渲染畫面。使用非同步方式進行搜尋避免主執行緒blocking。
future = QtConcurrent::run([ &, this]() {
const auto stone = static_cast<const Stone>(-playerStone);
engine.move(engine.bestMove(stone), stone);
last = engine.lastMove();
});移動游標重新渲染提示框時，不使用update()或reprint()，這兩個函數會重新渲染整個畫面，重複且快速地移動游標將造成非常高的CPU占用率，正確用法如下。
repaint(int x, int y, int w, int h);
update(int x, int y, int w, int h);