Thuật toán tìm kiếm
Pikafish không tính mọi biến đến cùng một độ sâu. Nó thử các nước có triển vọng trước, tính sâu hơn ở những biến quan trọng, và tính ít hơn hoặc dừng sớm ở các nhánh ít hứa hẹn. NNUE chấm điểm thế cờ; tìm kiếm so sánh điều gì sẽ xảy ra nếu tiếp tục đi.
Bài viết được đối chiếu với bản mã official Pikafish tại commit 1c66b9b. Tất cả các phương pháp dưới đây đều có trong bản mã này. Các ngưỡng cụ thể có thể thay đổi theo phiên bản, nên bài viết tập trung giải thích công dụng, không coi các hằng số tinh chỉnh là quy tắc cố định. Cuối bài có liên kết tới mã nguồn, Chessprogramming Wiki và các tài liệu đọc thêm.
Các bài liên quan: Hướng dẫn đọc mã nguồn, Đánh giá thế cờ và NNUE, Biểu diễn thế cờ và xử lý luật, Vận hành và giao tiếp của engine.
Nhìn tổng thể: một lượt tìm kiếm làm những gì?
Có thể hình dung tìm kiếm là lặp đi lặp lại các việc sau:
- Kiểm tra thế cờ hiện tại có rơi vào trường hợp thắng, thua, hòa, lặp lại hoặc quy định liên quan hay chưa.
- Tra bộ nhớ đệm xem đã tính thế cờ này chưa, có thể dùng lại kết quả hoặc một nước tốt hay không.
- Sinh các nước ứng viên, ưu tiên nước có triển vọng và loại nước không hợp lệ, chẳng hạn nước làm hở Tướng.
- Đi một nước, chuyển sang tính cho đối phương rồi nhận kết quả trả về; tính xong thì hoàn tác nước vừa đi.
- Dựa vào kết quả để tính sâu hơn, tìm kiếm lại hoặc dừng một số nhánh.
Đây là tổng quan một lượt tìm kiếm. Đánh giá, cắt tỉa và điều chỉnh độ sâu được thực hiện xen kẽ; các phần dưới giải thích nhiệm vụ từng phương pháp.
| Bài toán cần giải quyết | Phương pháp Pikafish sử dụng |
|---|---|
| Hai bên đều chọn nước có lợi cho mình, vậy so sánh thế nào? | Alpha-Beta theo dạng Negamax, tìm kiếm biến chính (PVS) |
| Thời gian có hạn, nên tính sâu bao nhiêu trước? | Tăng dần độ sâu, cửa sổ kỳ vọng (Aspiration Windows), quản lý thời gian |
| Xem nước nào trước, có thể dùng lại kết quả đã tính không? | Sắp xếp nước đi, heuristic lịch sử, đánh giá đổi quân tĩnh (SEE), bảng chuyển vị (TT) |
| Đã hết độ sâu nhưng chuỗi đổi quân chưa xong thì sao? | Tìm kiếm tĩnh (Quiescence Search) |
| Chỗ nào tính ít hơn, chỗ nào tính nhiều hơn? | Cắt tỉa nước rỗng, ProbCut, cắt tỉa vô vọng, LMR, IIR, mở rộng nước vượt trội và các phương pháp khác |
| Xử lý nước đi và luật cờ tướng thế nào? | Bitboard và bảng tấn công, kiểm tra tính hợp lệ, xét chiếu / đuổi quân liên tục / lặp lại và luật 60 nước |
Minimax và Negamax: đổi góc nhìn về điểm số
Trước hết, giả sử mọi điểm số đều nhìn từ phía Đỏ: điểm càng lớn càng có lợi cho Đỏ, càng nhỏ càng có lợi cho Đen. Khi Đỏ đi thì chọn giá trị lớn nhất, khi Đen đi thì chọn giá trị nhỏ nhất. Đó là Minimax (cực tiểu hóa và cực đại hóa). Một engine (động cơ cờ) không thể chỉ nhìn “mình ăn được gì”, mà còn phải tính đến đáp trả khó chịu nhất mà đối thủ có thể chọn.
Negamax gộp hai cách xử lý thành một: luôn chấm điểm từ phía bên đang đến lượt đi; đổi bên thì đổi dấu. Nếu sau khi đi một nước, đối thủ nhìn thấy điểm -80, thì với mình đó là +80. Vì vậy, cả hai bên đều chỉ cần “chọn giá trị lớn nhất”, và lời gọi đệ quy có dạng score = -search(...).
Một lớp (ply) ở đây là một nước của một bên; Đỏ và Đen mỗi bên đi một nước là hai lớp. Điểm trong ví dụ chỉ để minh họa cách so sánh, không phải giá trị cố định của một quân nào.
Alpha-Beta: không còn ảnh hưởng đến lựa chọn thì khỏi tính hết
Giả sử Đỏ đã có một phương án vẫn đạt +50 trước đáp trả tốt nhất của Đen. Khi xét phương án khác, chỉ cần thấy Đen có một đáp trả kéo điểm xuống +30, phương án này đã không thể tốt hơn phương án trước. Đen còn có thể kéo xuống +10 hay không cũng không làm Đỏ đổi lựa chọn, nên có thể bỏ qua phần tính toán còn lại.
Alpha-Beta dùng alpha và beta để biểu diễn cửa sổ điểm mà lượt tìm kiếm này quan tâm:
alpha: ngưỡng cần vượt qua; không vượt được thì không cải thiện lựa chọn hiện tại.beta: đạt ngưỡng này đã đủ để nút phía trên loại phương án tương ứng, không cần tiếp tục tìm điểm chính xác.
Cửa sổ quy định các ngưỡng điểm cần quan tâm trong lượt tìm kiếm. Kết quả không vượt alpha ban đầu là fail-low, cho cận trên; đạt hoặc vượt beta là fail-high, cho cận dưới. Kết quả trong cửa sổ là giá trị chính xác theo độ sâu và cách đánh giá đó. Fail-soft cho phép trả điểm ngoài cửa sổ, vẫn kèm loại cận tương ứng.
Nếu chỉ dùng Alpha-Beta cơ bản, trên cùng cây tìm kiếm và cùng cách đánh giá nút lá, kết quả sẽ giống Minimax đầy đủ. Cắt tỉa nước rỗng, cắt tỉa vô vọng và giảm độ sâu ở các phần sau có thêm phán đoán theo kinh nghiệm, nên không thể áp dụng chung bảo đảm này cho chúng.
Mở rộng: ví dụ Negamax / Alpha-Beta chỉ minh họa nguyên lý cơ bản
Mã giả dưới đây minh họa khung Negamax và Alpha-Beta. terminal_score() xử lý kết thúc và luật trước, gồm thua khi hết nước hợp lệ trong cờ tướng; điểm theo bên đến lượt. Ví dụ đánh giá khi hết độ sâu, còn nhánh tương ứng của Pikafish chuyển sang tìm kiếm tĩnh.
int search(int depth, int alpha, int beta) {
if (auto result = terminal_score(); result.has_value())
return *result;
if (depth <= 0)
return evaluate_side_to_move();
int best = -INF;
for (Move move : ordered_legal_moves()) {
make_move(move);
int score = -search(depth - 1, -beta, -alpha);
undo_move(move);
best = std::max(best, score);
alpha = std::max(alpha, score);
if (alpha >= beta)
break;
}
return best;
}Dấu âm không chỉ áp dụng cho điểm trả về, mà còn biến cửa sổ của nút con thành (-beta, -alpha). INF phải là một hằng số đủ lớn và an toàn; không được lấy đối của giá trị số nguyên nhỏ nhất vì có thể gây tràn số.
PVS: với các nước sau, trước tiên hỏi “có tốt hơn không?”
PVS (Principal Variation Search, tìm kiếm biến chính) dựa trên việc các nước tốt thường được xếp trước. Tại nút thuộc biến chính, nước đầu tiên được tìm kiếm với cửa sổ đầy đủ để có một ứng viên khá đáng tin cậy. Các nước sau được thử với cửa sổ rất hẹp, nhằm hỏi “nước này có vượt được nước tốt nhất hiện tại không?”. Nếu có triển vọng, engine sẽ tìm kiếm lại với cửa sổ đầy đủ khi cần.
Với điểm số nguyên, cửa sổ như (alpha, alpha + 1) thường gọi là cửa sổ bằng không (zero-window). Nó chủ yếu trả lời điểm có vượt ngưỡng hay không; không thể tìm được một điểm nguyên nằm hoàn toàn giữa hai đầu cửa sổ này.
Pikafish kết hợp PVS với LMR: ứng viên phía sau có thể được tính nông rồi tính sâu lại khi có triển vọng. Độ rộng cửa sổ quyết định mức chính xác cần hỏi; độ sâu quyết định nhìn xa bao nhiêu. Tìm kiếm cửa sổ bằng không vẫn đi nước thật; tìm kiếm nước rỗng tạm đổi lượt để thử kết quả khi nhường lượt.
Mã nguồn: Tìm kiếm đệ quy với PVS và LMR.
Một lần thử PVS với số cụ thể
Giả sử nước đầu cho +50, các nước sau được thử bằng (50, 51):
| Kết quả trả về | Thông tin có được | Bước tiếp |
|---|---|---|
| Không vượt 50 | Cận trên cho thấy chưa vượt ngưỡng. | Lấy ứng viên tiếp theo. |
| Từ 51 trở lên | Cận dưới vượt ngưỡng. | Mở rộng cửa sổ và phục hồi độ sâu khi đủ điều kiện tìm lại. |
Fail-soft trả 65 vẫn cần đọc theo ý nghĩa cận dưới; tìm lại xác định ứng viên tốt đến đâu. Xem tìm kiếm đệ quy về cách kết hợp PVS/LMR.
Tăng dần độ sâu và cửa sổ kỳ vọng: có đáp án trước, rồi cải thiện dần
Pikafish bắt đầu ở độ sâu nhỏ, rồi tăng độ sâu mục tiêu qua từng vòng. Đó là tăng dần độ sâu (Iterative Deepening). Nước tốt nhất, biến chính, điểm số và bộ nhớ đệm từ lượt tìm kiếm nông giúp vòng sau tìm đúng trọng tâm nhanh hơn. Khi hết thời gian, engine cũng đã có kết quả để dùng.
Cửa sổ kỳ vọng ở gốc đặt quanh điểm trung bình gần đây của ứng viên và xét độ dao động điểm. Kết quả ra xa cửa sổ sẽ làm mở rộng phía tương ứng rồi tìm lại, tiết kiệm công ở ứng viên ổn định và tính thêm khi có thay đổi bất ngờ.
depth 20 là độ sâu mục tiêu của vòng lặp. Giảm độ sâu, mở rộng và tìm kiếm tĩnh khiến các nhánh đạt độ sâu thực tế khác nhau. Biến chính (PV) thể hiện đường đi hiện được kỳ vọng từ hai bên, có thể thay đổi khi tính tiếp.
Mã nguồn: Vòng lặp tăng độ sâu và điều chỉnh cửa sổ.
Sinh nước đi: liệt kê ứng viên rồi kiểm tra có đi được không
Sinh nước đi, kiểm tra tính hợp lệ và sắp xếp giải quyết ba việc riêng: có những ứng viên nào, nước nào đi được và tính nước nào trước.
Bộ sinh nước đi có thể liệt kê nước bắt quân (CAPTURES), nước không bắt quân (QUIETS), nước thoát chiếu (EVASIONS) hoặc toàn bộ nước giả hợp lệ (PSEUDO_LEGAL). “Giả hợp lệ” nghĩa là đáp ứng cách di chuyển cơ bản, nhưng vẫn có thể làm hở Tướng sau khi đi. Tìm kiếm chính gọi pos.legal() để kiểm tra sau khi lấy một ứng viên. Khi cần lấy ngay danh sách hợp lệ đầy đủ, chế độ sinh LEGAL cũng thực hiện bước lọc này.
Quiet thường được gọi là “nước tĩnh”, nhưng ở đây chỉ có nghĩa là nước không bắt quân, vẫn có thể chiếu Tướng.
Những tình huống cờ tướng cần xử lý riêng
- Pháo: khi không bắt quân thì đi thẳng qua đường trống; khi bắt quân phải có đúng một quân làm ngòi. Khi bị Pháo chiếu, chuyển quân mình đang làm ngòi đi cũng có thể giải chiếu.
- Mã và Tượng: phải xét cản chân Mã, cản mắt Tượng và việc Tượng không được qua sông. Nước đi ngang của Tốt sau khi qua sông, cùng giới hạn trong cung của Tướng và Sĩ, cũng được quy định bởi các quy tắc tấn công tương ứng.
- An toàn của Tướng: sau khi đi, Tướng mình không được bị tấn công, kể cả trường hợp hai Tướng đối mặt.
- Nhiều quân cùng chiếu: không thể bê nguyên quy tắc cờ vua “bị chiếu đôi thì chỉ được đi Vua”. Khi có nhiều quân chiếu, mã hiện tại sinh toàn bộ nước giả hợp lệ rồi lọc ra các đáp trả hợp lệ.
Với giả định rằng ứng viên đã đáp ứng cách di chuyển cơ bản, legal() chủ yếu kiểm tra Tướng có an toàn sau khi đi không; các phán định phụ thuộc vào lịch sử như chiếu liên tục hay đuổi quân liên tục do phần xử lý luật phía sau đảm nhiệm.
Mã nguồn: Phân loại nước đi và sinh nước thoát chiếu, Kiểm tra an toàn của Tướng.
Bitboard và bảng tấn công: xử lý một nhóm điểm cùng lúc
Bitboard biểu diễn một tập hợp điểm trên bàn cờ bằng các bit, chẳng hạn “vị trí mọi quân Đỏ” hoặc “những điểm con Mã này có thể tấn công”. Các phép toán bit như giao và hợp xử lý được cả nhóm điểm cùng lúc. Pikafish dùng bitboard 128 bit để chứa 90 điểm của bàn cờ tướng, đồng thời vẫn giữ một mảng để tra quân theo từng điểm.
Phạm vi tấn công của Xe, Pháo, Mã, Tượng và các quân khác được tra qua bảng lập sẵn. Nhánh biên dịch thông thường dùng phép nhân magic và dịch bit để tính chỉ số; nhánh bật USE_PEXT dùng các lệnh PEXT / PDEP. Nhánh nào được dùng phụ thuộc vào bản biên dịch; không thể từ đó kết luận một loại lệnh luôn nhanh hơn trên mọi CPU.
Khi đi vào một nhánh tìm kiếm, engine thực hiện nước đi; khi quay lại thì hoàn tác. Với trạng thái thế cờ và khóa hash, engine chỉ cập nhật những phần thay đổi sau mỗi nước đi, tránh phải quét lại toàn bàn sau mỗi nước.
Mã nguồn: Kiểu dữ liệu bitboard, Bảng tấn công và chỉ số, Thực hiện và hoàn tác nước đi.
Sắp xếp nước đi và heuristic lịch sử: thử nước có triển vọng trước
Sắp xếp tốt giúp sớm tìm được nước mạnh, để Alpha-Beta dừng các nhánh khác nhanh hơn. Trong tìm kiếm chính thông thường, thứ tự lấy nước đi đại thể là:
- Nước ứng viên lưu trong bảng chuyển vị (TT move).
- Những nước bắt quân được SEE và các đánh giá nhanh khác xếp vào nhóm tốt.
- Những nước không bắt quân có điểm lịch sử tốt.
- Những nước bắt quân bị xếp vào nhóm kém.
- Những nước không bắt quân bị xếp vào nhóm kém.
MovePicker sinh, chấm và lấy ứng viên theo giai đoạn, với quy trình riêng cho giải chiếu, tìm kiếm tĩnh và ProbCut. “Tốt” và “kém” chỉ mức ưu tiên; nước bắt quân xếp kém vẫn có thể được tìm. Nước không bắt quân có điểm lịch sử cao có thể đứng trước nước bắt quân kém. Thứ tự chủ yếu dùng nước TT, lịch sử bắt quân và các lịch sử không bắt quân.
Heuristic lịch sử (History Heuristic) ghi hiệu quả nước đi trong tìm kiếm. Nước thường tạo cắt nhánh hữu ích hoặc kết quả tốt được tăng ưu tiên; liên tục kém thì giảm ưu tiên. Các thống kê được giữ trong bảng lịch sử của engine.
Mã sử dụng đồng thời lịch sử chính, lịch sử bắt quân, lịch sử chuỗi nước đi (xét cả các nước trước đó), lịch sử cấu trúc Tốt và lịch sử ở gần nút gốc. Điểm của nước bắt quân kết hợp giá trị quân bị bắt với lịch sử bắt quân. Điểm của nước không bắt quân còn xét việc chiếu, tránh khỏi hoặc đi vào vùng tấn công của quân có giá trị thấp hơn và các thông tin khác.
Mã nguồn: Các giai đoạn và cách chấm điểm của MovePicker, Định nghĩa các bảng lịch sử.
SEE: ước lượng nhanh đổi quân có thiệt không
SEE (Static Exchange Evaluation, đánh giá đổi quân tĩnh) ước lượng nhanh liệu một chuỗi đổi quân trên cùng điểm đến có đạt ngưỡng lợi ích hay không: mình ăn sang, đối thủ ăn lại, mình còn ăn tiếp được không, tính sơ bộ lời hay lỗ? see_ge() của Pikafish trả lời câu hỏi “có đạt ít nhất ngưỡng đã cho không?”.
SEE hỗ trợ sắp thứ tự bắt quân, cắt tỉa và lọc nước không bắt quân dễ mất quân. Nó tập trung vào lợi ích đổi quân tại điểm đến. Đe dọa ở nơi khác và phối hợp sau thí quân cần tìm kiếm tiếp.
Mã nguồn: Đánh giá đổi quân tĩnh.
Bảng chuyển vị: tận dụng lại thế cờ đã tính
Các thứ tự nước đi khác nhau có thể dẫn tới cùng một thế cờ. Bảng chuyển vị (Transposition Table, TT) dùng khóa hash để tra kết quả tìm kiếm trước đó, lưu nước ứng viên, độ sâu, điểm số, loại cận của điểm, đánh giá tĩnh và các thông tin khác.
Cận được lưu gắn với độ sâu, đánh giá và chiến lược tìm kiếm chọn lọc đã tạo ra nó; muốn dùng lại cần kiểm tra các điều kiện ấy.
| Loại bản ghi | Ý nghĩa |
|---|---|
EXACT | Giá trị trả về chính xác trong điều kiện của lượt tìm kiếm đó |
LOWER | Cận dưới: biết rằng ít nhất tốt đến mức này, thường gặp khi fail-high |
UPPER | Cận trên: biết rằng không vượt quá giá trị này, thường gặp khi fail-low |
Chỉ khi độ sâu, loại nút, loại cận và các điều kiện khác phù hợp, engine mới có thể dùng ngay điểm đã lưu và dừng tìm kiếm. Nếu chưa đủ điều kiện, nước đi trong bộ nhớ đệm vẫn có thể được thử trước. EXACT cũng không có nghĩa đã chứng minh bằng toán học kết quả thắng thua cuối cùng của ván cờ.
Giá trị thế cờ tướng còn chịu ảnh hưởng của lịch sử nước đi và luật 60 nước. Mã hiện tại có kiểm tra luật tương ứng và một số biện pháp bảo vệ khi dùng bộ nhớ đệm; không thể đơn giản cho rằng “quân đứng giống nhau thì bất kể lịch sử thế nào cũng dùng chung kết quả vô điều kiện”.
Mã nguồn: Cấu trúc dữ liệu TT, Đọc TT và cắt nhánh trong tìm kiếm chính. Xem Giải thích về Hash để biết cách đặt dung lượng bộ nhớ.
Tìm kiếm tĩnh: đừng dừng khi mới tính được nửa chuỗi đổi quân
Giả sử tìm kiếm vừa đạt độ sâu mục tiêu ngay sau nước “mình ăn được một quân đối phương”. Nếu chấm điểm ngay mà chưa thấy đối thủ có thể ăn lại ở nước tiếp theo, engine sẽ tưởng mình lời quân. Tìm kiếm tĩnh (Quiescence Search, qsearch) tiếp tục xét một số biến chiến thuật sau khi hết độ sâu thông thường, giảm kiểu đánh giá sai do “dừng giữa chừng” này.
Pikafish hiện tại thường tiếp tục tìm kiếm các nước bắt quân; khi bị chiếu thì chuyển sang các ứng viên thoát chiếu, không thể chỉ sinh nước bắt quân.
- Khi không bị chiếu, có thể lấy đánh giá tĩnh hiện tại làm mốc stand pat, rồi xét các nước bắt quân đáng tìm kiếm xem có cải thiện được mốc đó không. Stand pat là mốc gần đúng trong tìm kiếm; khi chơi thật vẫn phải đi một nước hợp lệ.
- Khi bị chiếu, không được dùng stand pat mà phải xét nước thoát chiếu; nếu không có đáp trả hợp lệ thì thua.
- Bản thân qsearch cũng dùng bảng chuyển vị, cắt tỉa vô vọng, SEE và các cách sàng lọc khác, không vét cạn mọi nước bắt quân hay mọi nước chiếu.
- Trong cờ tướng, không còn nước hợp lệ thì thua, ngay cả khi không bị chiếu. Mã hiện tại cũng kiểm tra trường hợp bí này; không thể áp dụng quy tắc hòa khi không còn nước hợp lệ nhưng không bị chiếu (stalemate) của cờ vua.
“Tìm kiếm tĩnh” vẫn thực hiện nước đi và đệ quy; “đánh giá tĩnh” mới là chấm điểm thế cờ hiện tại. Cần phân biệt hai việc này.
Mã nguồn: qsearch.
Cắt tỉa: dành sức tính cho nhánh có khả năng ảnh hưởng kết quả hơn
Các phương pháp tìm kiếm có chọn lọc dưới đây đều có trong Pikafish hiện tại. Chúng kết hợp đánh giá tĩnh, độ sâu, lịch sử và cửa sổ điểm để quyết định chỗ nào có thể tính ít hơn. Chúng dựa trên giả định theo kinh nghiệm và có thể đánh giá sai; điều kiện áp dụng, biên an toàn và tìm kiếm lại giúp kiểm soát rủi ro. Bảng chỉ giải thích công dụng, không có nghĩa “chỉ cần đúng một câu mô tả là luôn áp dụng”.
| Phương pháp | Giải thích dễ hiểu |
|---|---|
| Razoring | Khi điểm tĩnh đã thấp hơn alpha rất nhiều và thỏa các điều kiện khác, chuyển sang tìm kiếm tĩnh để kiểm tra chiến thuật trước mắt, thay vì tiếp tục tìm kiếm sâu như dự định. |
| Cắt tỉa vô vọng ngược (Reverse Futility) | Khi điểm tĩnh trừ đi biên an toàn vẫn đủ cao, một số nút có thể trả kết quả sớm để bỏ qua phần tìm kiếm tiếp theo. |
| Cắt tỉa nước rỗng (Null-move Pruning) | Giả định nội bộ rằng mình nhường một lượt; nếu tìm kiếm nông vẫn cho kết quả đủ tốt, có thể không cần tính lần lượt hết các nước thật. Xem phần dưới. |
| ProbCut | Với các nước bắt quân có triển vọng, tìm kiếm tĩnh trước rồi tìm kiếm nông hơn khi cần. Nếu vượt ngưỡng cao hơn beta, có thể dừng sớm cây con hiện tại. |
| Small ProbCut | Dùng cận dưới trong TT nếu nó đủ sâu và vượt rõ rệt một ngưỡng bổ sung để trả kết quả sớm, không lặp lại toàn bộ quy trình thử nước bắt quân. |
| Cắt tỉa theo số nước (Move-count Pruning / LMP) | Khi đã thử đủ nhiều ứng viên và thỏa điều kiện, bỏ qua các nước không bắt quân phía sau; ngưỡng số lượng thay đổi theo tình huống. |
| Cắt tỉa ứng viên vô vọng (Futility) | Kết hợp điểm tĩnh, giá trị quân có thể bắt, lịch sử và độ sâu dự kiến để bỏ qua ứng viên có vẻ khó đuổi kịp alpha. |
| Cắt tỉa theo lịch sử (History Pruning) | Không tiếp tục tìm kiếm một số nước không bắt quân nếu điểm lịch sử chuỗi nước đi / cấu trúc Tốt quá kém. |
| Cắt tỉa bằng SEE | Bỏ qua một số ứng viên khi ước lượng đổi quân nhanh cho thấy thiệt hại quá lớn; ngưỡng thay đổi theo độ sâu và các yếu tố khác. |
Các phán đoán này bị giới hạn bởi loại nút, tình trạng bị chiếu, điểm sát cục, lực lượng quân và lịch sử cùng các điều kiện khác; không nên hiểu rằng mỗi phương pháp đều áp dụng cho mọi thế cờ.
Ngoài ra, cắt tỉa theo khoảng cách sát cục (Mate-distance Pruning) dùng số lớp từ nút gốc tới hiện tại để thu hẹp các cận điểm sát cục có thể có, loại bỏ phần tìm kiếm không thể cải thiện khoảng cách dẫn tới sát cục. Đây là suy luận từ cận điểm, cần phân biệt với các phán đoán theo kinh nghiệm ở trên.
Mã nguồn: Cắt tỉa ở cấp nút, Sàng lọc từng nước, Cắt tỉa theo khoảng cách sát cục.
Vì sao nước rỗng hữu ích, và có thể sai ở đâu?
Cắt tỉa nước rỗng thử giả định rằng nếu nhường đối thủ đi trước mà thế vẫn đủ tốt thì có lẽ cũng có một nước thật phù hợp. Mã tạm đổi lượt và tìm ở độ sâu thấp hơn. Nhường lượt này chỉ dùng nội bộ tìm kiếm.
Thế xấu đi vì bắt buộc tới lượt mình đi gọi là zugzwang, làm sai giả định trên. Mã giới hạn nước rỗng bằng điều kiện như không bị chiếu và còn Xe, Mã hoặc Pháo; ở độ sâu lớn có thể xác minh từ thế ban đầu. Mức giảm tùy điều kiện, còn xác minh giúp giảm nguy cơ cắt sai.
Giảm độ sâu và mở rộng: nhánh quan trọng đáng được tính sâu hơn
Cắt tỉa là bỏ một phần tìm kiếm; giảm độ sâu là tính ít lớp hơn trước; mở rộng là tính thêm. Pikafish điều chỉnh độ sâu theo diễn biến tìm kiếm.
| Phương pháp | Vai trò trong mã hiện tại |
|---|---|
| LMR (Late Move Reductions, giảm độ sâu các nước xét sau) | Tìm kiếm nông trước với các nước xếp sau, ít triển vọng hơn; nếu kết quả vượt alpha, tùy kết quả mà tính sâu lại. Mức giảm xét lịch sử, loại nút và các yếu tố khác, đồng thời cũng có thể áp dụng cho nước bắt quân. |
| IIR (Internal Iterative Reductions, giảm độ sâu lặp nội bộ) | Giảm độ sâu tại nút hiện tại khi thiếu ứng viên TT và thỏa các điều kiện khác. IID dùng một lượt tìm nông trước để tìm ứng viên, với quy trình khác. |
| Mở rộng nước vượt trội (Singular Extension) | Tạm loại một ứng viên TT đáp ứng điều kiện rồi tìm kiếm nông các nước còn lại; nếu chúng đều kém rõ rệt thì dành thêm độ sâu cho ứng viên này. |
| Multi-cut và mở rộng âm | Trong bước kiểm tra loại ứng viên nói trên, nếu các nước còn lại vẫn đủ tốt thì có thể cắt nhánh ngay; trong một số điều kiện khác, giảm độ sâu dành cho ứng viên TT. |
Mở rộng nước vượt trội đo khoảng cách giữa ứng viên TT và các lựa chọn khác trong một lượt tìm hạn chế. Một ứng viên nổi bật có thể được tăng độ sâu dù vẫn có nhiều nước hợp lệ. Các điều chỉnh khác còn xét loại nút, lịch sử và kết quả tìm kiếm.
Mã nguồn: IIR, Mở rộng nước vượt trội và xử lý liên quan, LMR và tìm kiếm lại.
NNUE và hiệu chỉnh đánh giá: điểm số cũng định hướng tìm kiếm
Tìm kiếm thường cần ước lượng thế cờ mà không đi tiếp. Pikafish gọi đánh giá NNUE, rồi kết hợp thông tin hiệu chỉnh trong tìm kiếm để sử dụng điểm này. Nó vừa giúp chấm điểm nút lá, vừa ảnh hưởng tới một số phép cắt tỉa và cách phân bổ độ sâu.
Lịch sử hiệu chỉnh đánh giá (Correction History) ghi sai lệch giữa điểm tĩnh và kết quả tìm kiếm sau đó. Thống kê theo Tốt, các quân khác và nước trước dùng để điều chỉnh điểm liên quan. Chúng nằm trong bảng lịch sử tìm kiếm; trọng số NNUE đến từ tệp mạng đã tải.
Vì thế, cần phân biệt ba việc: NNUE ước lượng thế cờ, các bảng lịch sử hỗ trợ sắp xếp hoặc hiệu chỉnh, còn tìm kiếm so sánh các biến tiếp theo. Chúng phối hợp để quyết định engine dành thời gian vào đâu.
Mã nguồn: Tính và cập nhật hiệu chỉnh đánh giá, Điểm gọi đánh giá trong tìm kiếm.
Luật cờ tướng: cùng bàn cờ chưa chắc là cùng bài toán
Tìm kiếm không chỉ kiểm tra chiếu và hết nước hợp lệ, mà còn phải xử lý chiếu liên tục, đuổi quân liên tục, thế cờ lặp lại, luật 60 nước và các tình huống liên quan. Cùng thế cờ xuất hiện lại không có nghĩa chắc chắn hòa.
rule_judge() dùng lọc nhanh để xét có cần đọc lịch sử, rồi lần theo chuỗi trạng thái kiểm tra chiếu và đuổi. Phán định đã xác lập có thể trả ngay; một số lần lặp trong tìm kiếm cho cận điểm rồi tiếp tục với cửa sổ hẹp hơn.
Cần kiểm tra riêng tính hợp lệ nước đi, phán định theo lịch sử và điều kiện dùng lại bộ nhớ đệm. Xem Biểu diễn thế cờ và xử lý luật về sinh nước, nhìn lại chu kỳ và giao định danh quân bị đuổi.
Mã nguồn: Xử lý lặp lại và luật. Xem thêm bối cảnh về luật trong Những tranh luận về luật cờ tướng.
Đa luồng, MultiPV và thời gian: phân chia lượt tính này thế nào?
Đa luồng tiến hành các lượt tìm riêng, dùng chung bảng chuyển vị; một phần lịch sử chia sẻ theo nút NUMA. Các luồng có tính trùng nhưng cũng tận dụng thông tin nhau để lại. Hiệu quả tùy thế cờ, phần cứng và điều kiện tìm kiếm.
MultiPV giữ biến chính cho nhiều ứng viên ở gốc và cần thêm lượt tìm ở gốc. Nó hỗ trợ so sánh lựa chọn; càng nhiều ứng viên càng chia nhỏ ngân sách tính cho một đường.
Quản lý thời gian trước hết tính ngân sách từ thời gian còn lại, thời gian cộng thêm, số nước còn phải đi, Move Overhead và các yếu tố khác. Sau đó engine điều chỉnh dựa trên việc điểm số giảm, nước tốt nhất có ổn định không và những thông tin liên quan. Giới hạn thời gian cố định, số nút và các giới hạn khác cũng ảnh hưởng đến lúc dừng. Tăng dần độ sâu giúp engine cải thiện đáp án đã có trong các giới hạn này.
Mã nguồn: Khởi động luồng và chọn kết quả, Ngân sách thời gian, Điều chỉnh thời gian trong tìm kiếm. Các thiết lập liên quan nằm ở Tùy chọn UCI.
Mã nguồn và tài liệu đọc thêm
Nên bắt đầu đọc mã Pikafish ở đâu?
Toàn bộ liên kết dưới đây được cố định tại commit dùng để đối chiếu bài viết, tránh việc mã thay đổi sau này khiến số dòng không còn khớp:
search.cpp: tăng dần độ sâu, PVS, các kiểu cắt tỉa, giảm độ sâu, mở rộng và tìm kiếm tĩnh.movepick.cppvàhistory.h: các giai đoạn lấy nước, điểm sắp xếp và thống kê lịch sử.movegen.cppvàattacks.h: sinh nước đi và phạm vi tấn công.position.cpp: tính hợp lệ, thực hiện và hoàn tác nước đi, SEE và luật cờ tướng.tt.h,thread.cpp,timeman.cpp: bộ nhớ đệm, luồng và phân bổ thời gian.
Tìm hiểu thêm về thuật toán
Chessprogramming Wiki phù hợp để tra thuật ngữ và ý tưởng chung; nhiều ví dụ ở đó dành cho cờ vua. Khi đọc, cần phân biệt phương pháp tìm kiếm chung với luật của từng trò chơi. Muốn biết Pikafish thực sự dùng phương pháp nào, hãy đối chiếu mã nguồn được dẫn trong bài này.
- Nền tảng và cửa sổ: Alpha-Beta, PVS, Tăng dần độ sâu, Cửa sổ kỳ vọng.
- Sắp xếp và tái sử dụng: Sắp xếp nước đi, Heuristic lịch sử, Bảng chuyển vị, SEE.
- Phân bổ công việc tìm kiếm: Tìm kiếm tĩnh, Cắt tỉa nước rỗng, LMR, Mở rộng nước vượt trội.
- Các cơ chế hỗ trợ: Sinh nước đi, Lịch sử hiệu chỉnh đánh giá.
- Bài báo gốc: The History Heuristic and Alpha-Beta Search Enhancements in Practice của Jonathan Schaeffer; Verified Null-Move Pruning của David-Tabibi và Netanyahu. Các bài báo giúp hiểu ý tưởng thiết kế; số liệu thí nghiệm trước đây và cách triển khai cụ thể trong đó không đồng nhất với Pikafish hiện tại.
