Lộ trình chuyên sâu về Minimax và Tìm kiếm đối kháng (Adversarial Search), bắt đầu từ mô hình hóa trò chơi, cây trạng thái, đệ quy, Minimax, Negamax và Alpha–Beta Pruning; sau đó mở rộng đến các kỹ thuật được sử dụng trong game engine hiện đại như Move Ordering, Iterative Deepening, Transposition Table, Zobrist Hashing, Quiescence Search, PVS, Aspiration Window, Null Move Pruning và LMR. Xuyên suốt lộ trình, học viên từng bước vận dụng kiến thức để xây dựng một Chess Engine hoàn chỉnh.

Đăng nhập để tham gia lộ trình luyện tập

MINIMAX – ADVERSARIAL SEARCH – CHESS ENGINE

1. Giới thiệu

Lộ trình này nghiên cứu Minimax và Tìm kiếm đối kháng (Adversarial Search) từ nền tảng đến nâng cao.

Mục tiêu không phải chỉ là học thuộc một hàm minimax() hay alphaBeta(), mà là hiểu toàn bộ quá trình:

$$\boxed{ \text{Mô hình hóa} \rightarrow \text{Sinh trạng thái} \rightarrow \text{Tìm kiếm} \rightarrow \text{Đánh giá} \rightarrow \text{Cắt tỉa} \rightarrow \text{Tối ưu} }$$

Học viên sẽ đi từ những trò chơi nhỏ có thể vẽ toàn bộ cây trạng thái đến những trò chơi có không gian tìm kiếm rất lớn.

Ở cuối lộ trình, toàn bộ kiến thức được tổng hợp trong đồ án:

\boxed{\text{Xây dựng Chess Engine}}

Cờ vua đóng vai trò là đồ án xuyên suốt, nhưng lộ trình không chỉ dạy riêng cờ vua. Các khái niệm được nghiên cứu trên nhiều loại trò chơi để học viên hiểu bản chất của thuật toán và có khả năng áp dụng sang những bài toán khác.

2. Mục tiêu của lộ trình

Sau khi hoàn thành lộ trình, học viên cần có khả năng:

mô hình hóa chính xác một trò chơi đối kháng;
xác định đầy đủ trạng thái của trò chơi;
xác định người chơi hiện tại;
sinh các hành động hợp lệ;
xây dựng hàm chuyển trạng thái;
xác định trạng thái kết thúc;
xây dựng hàm Utility;
xây dựng cây trò chơi;
phân biệt Game Tree và Game Graph;
trace cây tìm kiếm bằng tay;
cài đặt Minimax;
cài đặt Negamax;
cài đặt Alpha–Beta Pruning;
hiểu chính xác điều kiện cắt nhánh;
phân tích độ phức tạp tìm kiếm;
cải thiện Move Ordering;
sử dụng Iterative Deepening;
xây dựng Principal Variation;
xây dựng Transposition Table;
hiểu và cài đặt Zobrist Hashing;
xây dựng Evaluation Function;
hiểu Horizon Effect;
cài đặt Quiescence Search;
nghiên cứu Principal Variation Search;
sử dụng Aspiration Window;
hiểu Null Move Pruning;
hiểu Late Move Reduction;
nghiên cứu Futility Pruning;
nghiên cứu Razoring;
nghiên cứu Extensions;
tiếp cận các kỹ thuật search nâng cao;
tổ chức kiến trúc một game engine;
xây dựng Chess Engine có khả năng chơi thực tế.

3. Mô hình toán học của trò chơi

Một trò chơi đối kháng có thể được mô hình hóa bởi:

$$G= \left( S, s_0, P, A, T, \operatorname{Terminal}, U \right)$$

trong đó:

$S$ là tập hợp tất cả các trạng thái;
$s_0$ là trạng thái ban đầu;
$P(s)$ xác định người chơi có lượt tại trạng thái $s$ ;
$A(s)$ là tập hợp các hành động hợp lệ tại trạng thái $s$ ;
$T(s,a)$ là trạng thái nhận được sau khi thực hiện hành động $a$ tại trạng thái $s$ ;
$\operatorname{Terminal}(s)$ xác định trạng thái $s$ có phải trạng thái kết thúc hay không;
$U(s)$ là giá trị của trạng thái kết thúc.

Có thể hình dung:

s \xrightarrow{a} T(s,a).

Trong đó:

$s$ là trạng thái hiện tại;
$a$ là hành động được chọn;
$T(s,a)$ là trạng thái tiếp theo.

4. Utility – Giá trị của trạng thái kết thúc

Với trò chơi hai người có ba kết quả:

thắng;
hòa;
thua;

ta có thể quy ước:

$$U(s)= \begin{cases} +1, & \text{nếu MAX thắng},\\ 0, & \text{nếu hòa},\\ -1, & \text{nếu MAX thua}. \end{cases}$$

Trong một engine thực tế, giá trị có thể lớn hơn.

Ví dụ:

$$U(s)= \begin{cases} +M, & \text{nếu bên đang tối ưu chắc chắn thắng},\\ 0, & \text{nếu hòa},\\ -M, & \text{nếu bên đang tối ưu chắc chắn thua}, \end{cases}$$

với $M$ là một số rất lớn.

5. Từ trò chơi đến bài toán tìm kiếm

Quá trình tư duy cơ bản là:

$$\boxed{ \text{Luật chơi} \rightarrow \text{State} \rightarrow \text{Action} \rightarrow \text{Transition} \rightarrow \text{Game Tree} \rightarrow \text{Search} }$$

Một trò chơi sau khi được mô hình hóa đúng sẽ trở thành một bài toán tìm kiếm trên không gian trạng thái.

PHẦN I. NỀN TẢNG MÔ HÌNH HÓA

6. State – Trạng thái

Trạng thái $s$ phải chứa đủ mọi thông tin ảnh hưởng đến tương lai của trò chơi.

Một biểu diễn tổng quát có thể là:

$$s= ( \text{board}, \text{sideToMove}, \text{historyInformation}, \text{additionalState} ).$$

Không được nhầm:

$$\text{State} = \text{hình ảnh hiện tại của bàn chơi}.$$

Trong nhiều trò chơi, hình dạng bàn chơi chưa đủ để xác định trạng thái.

Một trạng thái đúng phải cho phép xác định:

A(s),

T(s,a),

\operatorname{Terminal}(s),

và:

U(s).

7. Điều kiện để State được mô hình hóa đúng

Nếu hai lịch sử khác nhau:

H_1\neq H_2

dẫn đến hai vị trí trông giống nhau nhưng:

A(H_1)\neq A(H_2),

thì hai lịch sử đó không được xem là cùng một trạng thái.

Nói cách khác:

$$\boxed{ \text{Nếu thông tin làm thay đổi nước đi hợp lệ thì nó phải thuộc State.} }$$

Đây là nguyên tắc cực kỳ quan trọng khi xây dựng:

Game Graph;
Memoization;
Transposition Table;
Zobrist Hashing.

8. Năm bước kiểm chứng mô hình trò chơi

Bước 1. Liệt kê toàn bộ biến trạng thái

Liệt kê mọi thông tin có thể làm thay đổi:

A(s),

T(s,a),

\operatorname{Terminal}(s),

hoặc:

U(s).

Nếu một biến có khả năng ảnh hưởng đến ít nhất một trong bốn thành phần trên, biến đó có thể cần xuất hiện trong State.

Bước 2. Chọn góc nhìn Utility

Phải xác định rõ giá trị được tính theo góc nhìn nào.

Ví dụ:

Root-player perspective

U(s)>0

nghĩa là tốt cho người chơi ở nút gốc.

Side-to-move perspective

U(s)>0

nghĩa là tốt cho người đang có lượt.

Không được thay đổi góc nhìn giữa chừng.

Bước 3. Kiểm tra tính đầy đủ

Với mọi trạng thái reachable nhưng chưa kết thúc:

\neg\operatorname{Terminal}(s),

phải có:

A(s)\neq\varnothing.

Đồng thời, với mọi:

a\in A(s),

trạng thái:

T(s,a)

phải là trạng thái hợp lệ.

Bước 4. Kiểm tra cơ chế đổi lượt

Sau mỗi transition phải xác định chính xác:

P(T(s,a)).

Không được mặc định mọi trò chơi luôn đổi lượt theo mẫu:

A\rightarrow B\rightarrow A\rightarrow B.

Một số trò chơi có:

lượt bổ sung;
mất lượt;
chance node;
nhiều hơn hai người chơi.

Bước 5. Kiểm tra History Collision

Sinh một tập nhỏ các lịch sử khác nhau:

H_1,H_2,\ldots,H_k.

Nếu:

$$\operatorname{Encode}(H_i) = \operatorname{Encode}(H_j)$$

nhưng tương lai của chúng khác nhau, tức là:

A(H_i)\neq A(H_j),

hoặc Utility tương lai khác nhau, thì State đang thiếu thông tin.

PHẦN II. CÂY TRÒ CHƠI VÀ ĐỆ QUY

9. Game Tree – Cây trò chơi

Từ trạng thái ban đầu $s_0$ , mỗi hành động hợp lệ sinh ra một trạng thái con.

Ví dụ:

                         s0
                    /     |     \
                  s1      s2      s3
                 /  \    /  \    /  \
               s4   s5  s6  s7  s8  s9

Trong đó:

mỗi nút là một trạng thái;
mỗi cạnh là một hành động;
nút gốc là trạng thái ban đầu;
nút lá có thể là trạng thái kết thúc hoặc trạng thái tại giới hạn tìm kiếm.

10. Độ sâu của cây

Nếu trạng thái $s$ nằm cách nút gốc $k$ nước đi, ta gọi:

\operatorname{depth}(s)=k.

Ví dụ:

Depth 0:                 s0

Depth 1:          s1     s2     s3

Depth 2:        s4 s5   s6 s7   s8 s9

11. Branching Factor

Giả sử mỗi trạng thái có trung bình $b$ hành động hợp lệ.

Ta gọi $b$ là:

Branching Factor – hệ số phân nhánh.

Số trạng thái tại độ sâu $d$ xấp xỉ:

b^d.

Tổng số trạng thái từ độ sâu $0$ đến $d$ :

1+b+b^2+\cdots+b^d.

Theo công thức cấp số nhân:

1+b+b^2+\cdots+b^d = \frac{b^{d+1}-1}{b-1}.

Do đó:

T(d)=O(b^d).

12. Đệ quy trong cây trò chơi

Một hàm tìm kiếm tổng quát có cấu trúc:

search(state):
    if state là trạng thái kết thúc:
        return giá trị

    best = ...

    for action in legalActions(state):
        nextState = transition(state, action)

        value = search(nextState)

        cập nhật best

    return best

Đây chính là cấu trúc nền tảng của:

Minimax;
Negamax;
Alpha–Beta;
PVS;
Quiescence Search.

PHẦN III. MINIMAX

13. Ý tưởng Minimax

Xét trò chơi hai người:

MAX muốn giá trị càng lớn càng tốt;
MIN muốn giá trị càng nhỏ càng tốt.

Ta giả sử:

\boxed{\text{Cả hai người chơi đều chơi tối ưu.}}

14. Công thức Minimax

Nếu $s$ là trạng thái kết thúc:

V(s)=U(s).

Nếu đến lượt MAX:

V(s) = \max_{a\in A(s)} V(T(s,a)).

Nếu đến lượt MIN:

V(s) = \min_{a\in A(s)} V(T(s,a)).

Do đó:

$$V(s)= \begin{cases} U(s), & \text{nếu } \operatorname{Terminal}(s), \\[6pt] \displaystyle \max_{a\in A(s)}V(T(s,a)), & \text{nếu } P(s)=\operatorname{MAX}, \\[10pt] \displaystyle \min_{a\in A(s)}V(T(s,a)), & \text{nếu } P(s)=\operatorname{MIN}. \end{cases}$$

15. Ví dụ Minimax

Xét cây:

                         MAX
                      /       \
                     A         B
                   /   \     /   \
                  3     5   2     9
                    MIN       MIN

Tại $A$ :

V(A)=\min(3,5)=3.

Tại $B$ :

V(B)=\min(2,9)=2.

Tại nút gốc:

V(\text{root}) = \max(3,2) = 3.

Do đó MAX chọn nhánh $A$ .

16. Tư duy ngược từ lá

Minimax không quyết định trực tiếp từ nút gốc.

Thuật toán:

đi xuống các trạng thái sâu hơn;
tìm giá trị các nút lá;
truyền giá trị ngược lên;
MIN lấy nhỏ nhất;
MAX lấy lớn nhất.

Ta có:

$$\text{Leaves} \rightarrow \text{MIN/MAX} \rightarrow \text{Parent} \rightarrow \cdots \rightarrow \text{Root}.$$

Đây gọi là quá trình:

Backpropagation of Minimax values.

17. Độ phức tạp của Minimax

Với:

branching factor là $b$ ;
độ sâu tìm kiếm là $d$ ;

Minimax có độ phức tạp thời gian:

O(b^d).

Nếu sử dụng DFS đệ quy và không lưu toàn bộ cây, bộ nhớ thường vào khoảng:

O(d)

cho call stack, chưa tính dữ liệu trạng thái.

PHẦN IV. NEGAMAX

18. Từ Minimax sang Negamax

Với trò chơi hai người zero-sum:

V_{\text{A}}(s) = - V_{\text{B}}(s).

Điều này cho phép gộp MAX và MIN thành một công thức duy nhất.

19. Công thức Negamax

Ta có:

$$V(s) = \max_{a\in A(s)} \left( -V(T(s,a)) \right).$$

Dạng đầy đủ:

$$V(s)= \begin{cases} U(s), & \text{nếu } \operatorname{Terminal}(s), \\[6pt] \displaystyle \max_{a\in A(s)} \left( -V(T(s,a)) \right), & \text{ngược lại}. \end{cases}$$

20. Ý nghĩa dấu âm trong Negamax

Giả sử từ trạng thái hiện tại ta đi tới trạng thái $s'$ .

Giá trị:

V(s')

được tính theo góc nhìn của đối thủ.

Vì trò chơi zero-sum:

$$\text{giá trị của ta} = -\text{giá trị của đối thủ}.$$

Do đó:

score=-V(s').

Đây chính là nguồn gốc của dấu âm trong Negamax.

PHẦN V. ALPHA–BETA PRUNING

21. Vấn đề của Minimax

Minimax phải duyệt số trạng thái tăng theo:

O(b^d).

Khi $b$ hoặc $d$ lớn, số node tăng cực nhanh.

Do đó cần loại bỏ những nhánh chắc chắn không thể ảnh hưởng đến quyết định cuối cùng.

Đó là mục tiêu của:

Alpha–Beta Pruning.

22. Ý nghĩa của Alpha

$\alpha$ là giá trị tốt nhất mà MAX đã đảm bảo được trên đường tìm kiếm hiện tại.

Có thể hiểu:

\alpha = \text{lower bound của MAX}.

23. Ý nghĩa của Beta

$\beta$ là giá trị tốt nhất mà MIN đã đảm bảo được.

Có thể hiểu:

\beta = \text{upper bound của MAX}.

24. Điều kiện cắt Alpha–Beta

Khi:

\alpha\ge\beta,

nhánh còn lại không cần được tìm kiếm tiếp.

Ta thực hiện:

\boxed{\text{Cutoff}}

25. Tính đúng của Alpha–Beta

Alpha–Beta không thay đổi đáp án Minimax.

Ta có:

$$V_{\operatorname{AlphaBeta}}(s) = V_{\operatorname{Minimax}}(s).$$

Alpha–Beta chỉ giảm số trạng thái phải duyệt.

26. Alpha–Beta trong Negamax

Một dạng phổ biến:

negamax(state, depth, alpha, beta):

    if depth == 0 hoặc state kết thúc:
        return evaluate(state)

    best = -INF

    for move in legalMoves(state):

        make(move)

        score = -negamax(
            nextState,
            depth - 1,
            -beta,
            -alpha
        )

        unmake(move)

        best = max(best, score)

        alpha = max(alpha, score)

        if alpha >= beta:
            break

    return best

Việc đổi:

[\alpha,\beta]

thành:

[-\beta,-\alpha]

xuất phát từ phép đổi góc nhìn của Negamax.

PHẦN VI. MOVE ORDERING

27. Tại sao thứ tự nước đi quan trọng?

Alpha–Beta càng tìm thấy nước đi tốt sớm thì càng dễ cắt các nhánh còn lại.

Nếu Move Ordering rất tốt, độ phức tạp lý tưởng có thể tiến gần:

O(b^{d/2}).

Trong khi Minimax thông thường là:

O(b^d).

28. Ví dụ ảnh hưởng của Move Ordering

Nếu:

b=36,

thì Minimax có số node gần:

36^d.

Trong trường hợp Alpha–Beta có thứ tự gần lý tưởng:

36^{d/2} = 6^d.

Sự khác biệt này cực kỳ lớn khi $d$ tăng.

29. Các kỹ thuật Move Ordering

Lộ trình lần lượt nghiên cứu:

Transposition Table Move;
Principal Variation Move;
Winning Capture;
MVV-LVA;
SEE;
Killer Move;
History Heuristic;
Countermove;
Continuation History.

Một thứ tự tham khảo:

1. TT Move
2. PV Move
3. Good Captures
4. Killer Moves
5. Quiet Moves theo History
6. Bad Captures

PHẦN VII. ITERATIVE DEEPENING

30. Ý tưởng

Thay vì tìm trực tiếp depth $d$ , ta tìm:

1,2,3,\ldots,d.

Ví dụ:

Depth 1
Depth 2
Depth 3
Depth 4
Depth 5
...

31. Công thức chi phí

Tổng số node xấp xỉ:

b+b^2+b^3+\cdots+b^d.

Mặc dù phải tìm lại nhiều lần, tổng độ phức tạp vẫn cùng bậc:

O(b^d).

Tầng sâu nhất chiếm phần lớn số node.

32. Lợi ích của Iterative Deepening

Iterative Deepening cung cấp:

best move tạm thời;
Principal Variation;
Move Ordering tốt hơn;
dữ liệu cho Transposition Table;
khả năng quản lý thời gian;
khả năng dừng search an toàn.

PHẦN VIII. PRINCIPAL VARIATION

33. Principal Variation là gì?

Principal Variation, viết tắt là PV, là chuỗi nước đi tốt nhất mà engine dự đoán khi cả hai bên chơi tối ưu.

Ta ký hiệu:

PV= (m_1,m_2,\ldots,m_k).

Trong đó:

$m_1$ là best move tại root;
$m_2$ là best response của đối thủ;
$m_3$ là nước đáp lại tốt nhất;
và tiếp tục như vậy.

PHẦN IX. TRANSPOSITION TABLE

34. Từ Game Tree đến Game Graph

Cùng một trạng thái có thể đạt được bởi nhiều thứ tự nước đi khác nhau.

Ví dụ:

s_0 \rightarrow s_1 \rightarrow s_3,

nhưng đồng thời:

s_0 \rightarrow s_2 \rightarrow s_3.

Nếu search lại từ $s_3$ mỗi lần, engine sẽ lặp lại rất nhiều phép tính.

35. Transposition Table

Ta lưu kết quả đã tìm kiếm:

TT[key] = ( depth, score, bound, bestMove ).

Một entry thường chứa:

hash key;
depth;
score;
bound type;
best move;
generation hoặc age.

36. Exact Bound

Nếu search biết chính xác:

V(s)=score,

ta lưu:

\operatorname{BOUND\_EXACT}.

37. Lower Bound

Nếu chỉ biết:

V(s)\ge score,

ta có:

\operatorname{LOWER\_BOUND}.

Điều này thường xuất hiện khi xảy ra beta cutoff.

38. Upper Bound

Nếu biết:

V(s)\le score,

ta có:

\operatorname{UPPER\_BOUND}.

PHẦN X. ZOBRIST HASHING

39. Mục tiêu

Transposition Table cần một khóa đại diện cho trạng thái.

Khóa phải:

tính nhanh;
cập nhật nhanh;
phân bố tốt;
có xác suất collision thấp.

Một kỹ thuật chuẩn là:

Zobrist Hashing.

40. Công thức Zobrist Hash

Với mỗi cặp:

(\text{piece},\text{square}),

ta sinh một số nguyên ngẫu nhiên 64-bit.

Hash của trạng thái:

H = R_1 \oplus R_2 \oplus \cdots \oplus R_k.

Trong đó:

\oplus

là phép XOR.

41. Cập nhật Incremental Hash

Giả sử một quân di chuyển từ ô $a$ sang ô $b$ .

Ta có thể cập nhật:

H' = H \oplus Z[piece][a] \oplus Z[piece][b].

Nhờ đó việc cập nhật hash có thể thực hiện trong:

O(1).

Không cần hash lại toàn bộ bàn cờ.

PHẦN XI. EVALUATION FUNCTION

42. Tại sao cần Evaluation?

Với trò chơi nhỏ, có thể tìm đến trạng thái kết thúc.

Nhưng với trò chơi lớn, ta chỉ tìm đến một độ sâu giới hạn.

Khi đó cần ước lượng:

V(s) \approx \operatorname{Eval}(s).

43. Mô hình Evaluation tuyến tính

Một mô hình cơ bản:

$$\operatorname{Eval}(s) = \sum_{i=1}^{k} w_i f_i(s).$$

Hay:

$$\operatorname{Eval}(s) = w_1f_1(s) +w_2f_2(s) +\cdots +w_kf_k(s).$$

Trong đó:

$f_i(s)$ là đặc trưng;
$w_i$ là trọng số.

44. Evaluation trong cờ vua

Ví dụ:

$$\operatorname{Eval}(s) = \operatorname{Material}(s) + \operatorname{Position}(s) + \operatorname{Mobility}(s) + \operatorname{KingSafety}(s) + \operatorname{PawnStructure}(s).$$

Các đặc trưng có thể bao gồm:

Material;
Piece-Square Table;
Mobility;
Center Control;
Space;
Pawn Structure;
Passed Pawn;
Isolated Pawn;
Doubled Pawn;
Backward Pawn;
King Safety;
Bishop Pair;
Rook on Open File;
Rook on Seventh Rank;
Piece Activity;
Endgame King Activity.

PHẦN XII. HORIZON EFFECT

45. Hiệu ứng đường chân trời

Giả sử engine chỉ search tới depth $d$ .

Một biến cố quan trọng xảy ra ở:

d+1.

Engine không nhìn thấy biến cố đó.

Ta gọi đây là:

Horizon Effect.

Ví dụ:

Depth d:
Engine thấy mình đang hơn một quân.

Depth d + 1:
Đối thủ có thể ăn lại quân.

Depth d + 2:
Vị trí thực tế trở nên bất lợi.

Nếu search dừng tại $d$ , Evaluation có thể đánh giá sai.

PHẦN XIII. QUIESCENCE SEARCH

46. Ý tưởng

Không nên gọi Evaluation tại một trạng thái đang có biến động chiến thuật mạnh.

Ta thực hiện:

$$\text{Normal Search} \rightarrow \text{Depth }0 \rightarrow \text{Quiescence Search}.$$

47. Các nước đi trong Quiescence Search

Quiescence Search thường chỉ xét những nước đi chiến thuật:

captures;
promotions;
đôi khi checks;
các forcing moves quan trọng.

Mục tiêu là đạt tới trạng thái tương đối yên tĩnh:

s_q.

Sau đó mới tính:

\operatorname{Eval}(s_q).

48. Stand Pat

Trong Quiescence Search, engine thường bắt đầu bằng:

standPat=\operatorname{Eval}(s).

Sau đó mới thử các nước đi chiến thuật.

Nếu:

standPat\ge\beta,

có thể xảy ra cutoff ngay.

PHẦN XIV. PRINCIPAL VARIATION SEARCH

49. Ý tưởng PVS

Nếu Move Ordering tốt, nước đi đầu tiên có khả năng cao là nước tốt nhất.

Do đó:

nước đầu tiên được search với cửa sổ đầy đủ;
các nước sau được thử bằng cửa sổ rất hẹp.

Nước đầu tiên:

[\alpha,\beta].

Các nước tiếp theo:

[\alpha,\alpha+1].

Trong Negamax tương ứng thường xuất hiện zero-window dạng:

[-\alpha-1,-\alpha].

Nếu thử nghiệm cho thấy nước đi có khả năng cải thiện Alpha, ta search lại bằng full window.

PHẦN XV. ASPIRATION WINDOW

50. Ý tưởng

Sau khi search depth $d-1$ , ta đã có score:

S_{d-1}.

Score tại depth $d$ thường không quá xa giá trị này.

Thay vì sử dụng:

[-\infty,+\infty],

ta thử:

[ S_{d-1}-\delta, S_{d-1}+\delta ].

51. Fail-Low và Fail-High

Nếu:

score\le\alpha,

ta có:

Fail-Low.

Nếu:

score\ge\beta,

ta có:

Fail-High.

Khi đó engine mở rộng cửa sổ và search lại.

PHẦN XVI. NULL MOVE PRUNING

52. Ý tưởng Null Move

Giả sử người chơi hiện tại tạm thời bỏ lượt.

Ta xét một Null Move:

s \rightarrow s_{\operatorname{null}}.

Nếu ngay cả khi bỏ lượt mà vị trí vẫn đủ tốt để đạt:

score\ge\beta,

thì nhiều nước đi thật cũng không cần được tìm đầy đủ.

53. Reduced Null Move Search

Null Move thường được tìm ở độ sâu giảm:

d' = d-1-R,

với:

R>0.

Điều này giúp giảm đáng kể số node.

54. Hạn chế của Null Move

Null Move phải được sử dụng cẩn thận trong:

zugzwang;
một số endgame;
vị trí rất ít quân;
những trạng thái mà quyền được đi thực tế lại là bất lợi.

PHẦN XVII. LATE MOVE REDUCTION

55. Ý tưởng LMR

Nếu Move Ordering tốt, các nước đi được xét rất muộn thường ít có khả năng là best move.

Thay vì search:

d-1,

ta thử:

d-1-R.

Nếu kết quả đáng chú ý, ta search lại với full depth.

56. Reduced Search và Re-search

Ta có mô hình:

$$\text{Late Move} \rightarrow \text{Reduced Search}.$$

Nếu:

score>\alpha,

thì có thể thực hiện:

\text{Full-depth Re-search}.

PHẦN XVIII. FUTILITY PRUNING

57. Ý tưởng

Tại các node gần lá, giả sử:

\operatorname{Eval}(s)+Margin<\alpha.

Nếu một quiet move rất khó có thể cải thiện đủ giá trị để vượt Alpha, một số nhánh có thể được bỏ qua.

Đây là:

Futility Pruning.

PHẦN XIX. RAZORING

58. Ý tưởng Razoring

Nếu tại độ sâu nhỏ:

\operatorname{Eval}(s)+Margin<\alpha,

engine có thể thử một tìm kiếm rẻ hơn, thường liên quan đến Quiescence Search, trước khi thực hiện full search.

Mục tiêu là loại bỏ sớm những node rất khó cải thiện Alpha.

PHẦN XX. EXTENSIONS

59. Search Extension

Không phải mọi nhánh đều cần giảm depth giống nhau.

Thông thường:

d_{\text{child}}=d-1.

Nhưng tại một vị trí đặc biệt:

d_{\text{child}} = d-1+E,

với $E$ là extension.

60. Các dạng Extension

Có thể nghiên cứu:

Check Extension;
Recapture Extension;
Passed Pawn Extension;
Singular Extension.

Extension phải được kiểm soát để tránh làm cây tìm kiếm tăng quá lớn.

PHẦN XXI. SINGULAR EXTENSION

61. Ý tưởng

Giả sử một nước đi $m^\*$ có score vượt trội đáng kể so với tất cả lựa chọn khác.

Ta muốn kiểm tra:

m^\* \gg m_i \qquad \forall m_i\neq m^\*.

Nếu nước đi thực sự mang tính singular, engine có thể search nước đó sâu hơn.

Kỹ thuật này thường liên hệ chặt chẽ với:

TT Move;
Transposition Table bounds;
reduced verification search;
search depth.

PHẦN XXII. CÁC KỸ THUẬT SEARCH NÂNG CAO

62. Những kỹ thuật tiếp tục nghiên cứu

Sau nền tảng Alpha–Beta, lộ trình tiếp tục với:

NegaScout;
Principal Variation Search;
Zero-Window Search;
Aspiration Search;
Null Move Pruning;
Late Move Reduction;
Futility Pruning;
Razoring;
Singular Extension;
ProbCut;
Multi-Cut;
MTD(f);
SSS*;
MultiPV;
Parallel Search;
Tablebase;
NNUE;
Monte Carlo Tree Search;
AlphaZero-style Search.

Điều quan trọng không phải học thuộc tên kỹ thuật.

Với mỗi kỹ thuật phải trả lời được:

$$\boxed{ \text{Kỹ thuật này đang cố giảm phần nào của cây tìm kiếm?} }$$

và:

$$\boxed{ \text{Điều kiện nào cho phép tối ưu mà vẫn giữ độ chính xác đủ tốt?} }$$

PHẦN XXIII. BÀI TẬP XUYÊN SUỐT

63. Trò chơi nhỏ trước, trò chơi lớn sau

Lộ trình không bắt đầu trực tiếp bằng Chess Engine.

Học viên trước hết làm việc với những trò chơi đủ nhỏ để:

tự vẽ toàn bộ cây;
trace từng bước;
kiểm tra kết quả bằng tay;
so sánh thuật toán với brute force.

64. Các nhóm trò chơi

Các bài tập có thể bao gồm:

trò chơi lấy đá;
Nim;
Subtraction Game;
Tic-Tac-Toe;
Connect Four;
Othello;
Checkers;
trò chơi trên đồ thị;
trò chơi trạng thái hữu hạn;
game có trạng thái lặp;
game có transposition;
game có imperfect information;
game có chance node.

65. Quy trình giải mỗi bài

Mỗi trò chơi được phân tích theo chu trình:

$$\boxed{ \text{Luật chơi} \rightarrow \text{State} \rightarrow \text{Actions} \rightarrow \text{Transition} \rightarrow \text{Terminal} \rightarrow \text{Utility} }$$

Sau đó:

$$\boxed{ \text{Brute Force} \rightarrow \text{Minimax} \rightarrow \text{Negamax} \rightarrow \text{Alpha-Beta} \rightarrow \text{Optimization} }$$

PHẦN XXIV. ĐỒ ÁN XUYÊN SUỐT – CHESS ENGINE

66. Mục tiêu đồ án

Cờ vua là bài toán tổng hợp để kết nối tất cả nội dung đã học:

$$\text{Game Modeling} + \text{Move Generation} + \text{Search} + \text{Evaluation} + \text{Optimization}.$$

Engine không được viết toàn bộ trong một chương.

Nó được xây dựng từng bước trong suốt lộ trình.

67. Kiến trúc tổng quát

Chess Engine
│
├── Position
│
├── Board Representation
│
├── Move
│
├── Move Generation
│
├── Legal Move Checking
│
├── Make Move
│
├── Unmake Move
│
├── Zobrist Hashing
│
├── Evaluation
│
├── Search
│   ├── Minimax
│   ├── Negamax
│   ├── Alpha-Beta
│   ├── PVS
│   └── Quiescence Search
│
├── Move Ordering
│   ├── TT Move
│   ├── Captures
│   ├── Killer Moves
│   └── History Heuristic
│
├── Transposition Table
│
├── Iterative Deepening
│
├── Time Management
│
├── Opening Support
│
├── Endgame Tablebase
│
└── UCI Interface

68. Position

Module Position phải biểu diễn đầy đủ trạng thái cờ vua.

Một trạng thái có thể được xem là:

s= ( B, STM, C, EP, H, F ),

trong đó:

$B$ là cấu hình bàn cờ;
$STM$ là bên đang đi;
$C$ là Castling Rights;
$EP$ là En Passant State;
$H$ là thông tin cần thiết liên quan lịch sử;
$F$ là các bộ đếm hoặc trạng thái bổ sung cần thiết.

69. Move Generation

Từ trạng thái $s$ , engine sinh:

A(s).

Move Generator cần xử lý:

Pawn Move;
Pawn Capture;
Promotion;
En Passant;
Knight Move;
Bishop Move;
Rook Move;
Queen Move;
King Move;
Castling.

70. Pseudo-Legal Move và Legal Move

Không phải mọi nước đi đúng theo quy tắc di chuyển quân đều hợp lệ.

Ta phân biệt:

A_{\text{pseudo}}(s)

và:

A_{\text{legal}}(s).

Trong đó:

$$A_{\text{legal}}(s) \subseteq A_{\text{pseudo}}(s).$$

Một nước đi không hợp lệ nếu sau khi thực hiện, vua của bên đi vẫn bị chiếu.

71. Make Move / Unmake Move

Search thực hiện rất nhiều chuỗi:

make(move)
search(child)
unmake(move)

Do đó:

makeMove() phải nhanh;
unmakeMove() phải chính xác;
toàn bộ State phải được khôi phục hoàn toàn.

Ta yêu cầu:

$$\operatorname{Unmake} ( \operatorname{Make}(s,m) ) = s.$$

Đây là một invariant quan trọng của engine.

72. Evaluation của Chess Engine

Phiên bản cơ bản có thể dùng:

Eval = Material + PST.

Sau đó mở rộng:

$$Eval = Material + PST + Mobility + PawnStructure + KingSafety + Space + Activity.$$

73. Search Pipeline

Pipeline tổng quát:

$$\boxed{ \text{Position} \rightarrow \text{Generate Moves} \rightarrow \text{Order Moves} \rightarrow \text{Search} \rightarrow \text{Evaluate} \rightarrow \text{Best Move} }$$

74. Search nâng cao trong Chess Engine

Sau khi engine cơ bản hoạt động, lần lượt bổ sung:

Minimax
    ↓
Negamax
    ↓
Alpha-Beta
    ↓
Move Ordering
    ↓
Iterative Deepening
    ↓
Transposition Table
    ↓
Quiescence Search
    ↓
PVS
    ↓
Aspiration Window
    ↓
Null Move
    ↓
LMR
    ↓
Futility / Razoring
    ↓
Extensions

Mỗi bước phải được kiểm chứng trước khi chuyển sang bước tiếp theo.

PHẦN XXV. KIỂM THỬ ENGINE

75. Perft

Trước khi đánh giá sức mạnh search, Move Generator phải được kiểm tra chính xác.

Ta định nghĩa:

\operatorname{Perft}(s,d)

là số vị trí lá đạt được khi duyệt toàn bộ các nước đi hợp lệ đến độ sâu $d$ .

Công thức:

\operatorname{Perft}(s,0)=1.

Với $d>0$ :

$$\operatorname{Perft}(s,d) = \sum_{a\in A(s)} \operatorname{Perft}(T(s,a),d-1).$$

Nếu Perft sai thì không nên tiếp tục tối ưu Search.

76. Invariant Testing

Một số invariant quan trọng:

$$\operatorname{Unmake} ( \operatorname{Make}(s,m) ) = s.$$

Hash cũng phải thỏa:

$$H_{\text{incremental}}(s) = H_{\text{recomputed}}(s).$$

Sau Make/Unmake, mọi thành phần của Position phải trở về đúng trạng thái ban đầu.

PHẦN XXVI. TIME MANAGEMENT

77. Quản lý thời gian

Một engine thực tế không thể search vô hạn.

Giả sử còn:

T_{\text{remaining}}

thời gian.

Engine phải quyết định:

T_{\text{move}}

cho nước hiện tại.

Có thể xem:

$$T_{\text{move}} = f( T_{\text{remaining}}, \text{increment}, \text{game phase}, \text{position complexity} ).$$

Iterative Deepening giúp engine luôn có một best move khả dụng khi thời gian hết.

PHẦN XXVII. UCI

78. Universal Chess Interface

Để engine giao tiếp với GUI cờ vua, có thể xây dựng giao thức:

UCI – Universal Chess Interface.

Các lệnh quan trọng bao gồm:

uci
isready
position
go
stop
quit

Engine nhận:

position ...

sau đó thực hiện:

go ...

và trả về:

bestmove ...

PHẦN XXVIII. PHƯƠNG PHÁP HỌC

79. Quy trình học chuẩn

Mỗi thuật toán phải được học theo chuỗi:

$$\boxed{ \text{Bài toán} \rightarrow \text{Mô hình} \rightarrow \text{Ví dụ nhỏ} \rightarrow \text{Cây trạng thái} \rightarrow \text{Trace} \rightarrow \text{Công thức} \rightarrow \text{Code} \rightarrow \text{Kiểm chứng} \rightarrow \text{Tối ưu} }$$

Không chuyển thẳng từ định nghĩa sang code.

80. Trace thuật toán

Với mỗi thuật toán, học viên phải có khả năng trace:

trạng thái hiện tại;
depth;
player;
action đang thử;
score trả về;
best score;
alpha;
beta;
cutoff;
trạng thái của Transposition Table nếu có.

Ví dụ:

Node: S
Depth: 4
Alpha: -3
Beta: 5

Try move A
    score = 1

Alpha = max(-3, 1) = 1

Try move B
    score = 6

Alpha = max(1, 6) = 6

Vì:
alpha >= beta
6 >= 5

=> Beta Cutoff

81. Không học thuộc code

Mục tiêu không phải:

nhớ code Minimax

mà phải hiểu:

\boxed{ \text{Vì sao mỗi dòng code tồn tại?} }

Học viên phải tự trả lời được:

State là gì?
Ai đang có lượt?
Action hợp lệ là gì?
Transition hoạt động như thế nào?
Terminal được xác định ra sao?
Utility đang tính theo góc nhìn của ai?
Tại sao phải đổi dấu?
Tại sao Alpha được cập nhật?
Tại sao có thể cutoff?
Tại sao Move Ordering ảnh hưởng tốc độ?
Tại sao TT entry cần depth?
Tại sao Quiescence Search cần thiết?
Tại sao reduced search có thể được sử dụng?
Khi nào phải re-search?

PHẦN XXIX. LỘ TRÌNH TƯ DUY

82. Cấp độ 1 – Hiểu trạng thái

Học viên phải hiểu:

$$\text{State} \rightarrow \text{Actions} \rightarrow \text{Next States}.$$

83. Cấp độ 2 – Hiểu cây trò chơi

Hiểu:

$$\text{Current State} \rightarrow \text{Children} \rightarrow \text{Recursive Search}.$$

84. Cấp độ 3 – Hiểu Minimax

Hiểu:

MAX \rightarrow \max

và:

MIN \rightarrow \min.

85. Cấp độ 4 – Hiểu Negamax

Hiểu tính đối xứng:

V_{\text{me}} = - V_{\text{opponent}}.

86. Cấp độ 5 – Hiểu Alpha–Beta

Hiểu cửa sổ:

[\alpha,\beta]

và điều kiện:

\alpha\ge\beta.

87. Cấp độ 6 – Hiểu Move Ordering

Hiểu rằng:

$$\text{Better Ordering} \Rightarrow \text{Earlier Cutoffs} \Rightarrow \text{Fewer Nodes}.$$

88. Cấp độ 7 – Hiểu Search Engine

Hiểu toàn bộ pipeline:

$$\boxed{ \text{Position} \rightarrow \text{MoveGen} \rightarrow \text{Move Ordering} \rightarrow \text{Search} \rightarrow \text{Evaluation} \rightarrow \text{TT} \rightarrow \text{Best Move} }$$

PHẦN XXX. KẾT QUẢ SAU LỘ TRÌNH

89. Kiến thức đạt được

Sau khi hoàn thành lộ trình, học viên cần nắm chắc:

Game State;
Game Tree;
Game Graph;
Recursive Search;
Minimax;
Negamax;
Alpha–Beta;
Move Ordering;
Iterative Deepening;
Principal Variation;
Transposition Table;
Zobrist Hashing;
Evaluation;
Horizon Effect;
Quiescence Search;
PVS;
Aspiration Window;
Null Move Pruning;
LMR;
Futility Pruning;
Razoring;
Extensions;
Singular Extension;
các hướng Search nâng cao.

90. Kỹ năng đạt được

Học viên phải có khả năng:

tự mô hình hóa trò chơi;
tự xây dựng cây trạng thái;
tự trace thuật toán;
tự cài đặt Minimax;
chuyển Minimax sang Negamax;
cài đặt Alpha–Beta;
phát hiện và giải thích cutoff;
phân tích số node;
tối ưu thứ tự nước đi;
xây dựng TT;
xây dựng hash trạng thái;
xây dựng Evaluation Function;
thiết kế Search Engine theo module;
kiểm thử bằng Perft;
xây dựng Chess Engine có khả năng chơi thực tế.

91. Mục tiêu cuối cùng

Mục tiêu cuối cùng không phải là:

Học thuộc Minimax.

Mà là hình thành được tư duy:

$$\boxed{ \text{Mô hình hóa chính xác} \rightarrow \text{Tìm kiếm chính xác} \rightarrow \text{Đánh giá hợp lý} \rightarrow \text{Tối ưu có kiểm chứng} }$$

Từ một trò chơi nhỏ, học viên phải có khả năng tự đặt ra các câu hỏi:

\text{State là gì?}

\text{Action là gì?}

\text{Transition là gì?}

\text{Terminal là gì?}

\text{Utility là gì?}

\text{Search cần đi sâu đến đâu?}

\text{Nhánh nào thực sự cần duyệt?}

\text{Thông tin nào có thể tái sử dụng?}

$$\text{Làm thế nào để tìm sâu hơn trong cùng một khoảng thời gian?}$$

Đó chính là tư duy cốt lõi của Adversarial Search.

92. Đích đến của lộ trình

Toàn bộ lộ trình hội tụ về chu trình:

$$\boxed{ \text{Game} \rightarrow \text{Model} \rightarrow \text{Search} \rightarrow \text{Evaluate} \rightarrow \text{Optimize} \rightarrow \text{Engine} }$$

Và đồ án cuối cùng:

\boxed{ \text{CHESS ENGINE} }

không chỉ là một chương trình chơi cờ, mà là sản phẩm tổng hợp của:

thuật toán;
cấu trúc dữ liệu;
đệ quy;
tìm kiếm;
tối ưu;
heuristic;
mô hình hóa;
kiểm thử;
kỹ thuật phần mềm.

Mục tiêu cuối cùng của lộ trình là giúp học viên hiểu sâu bản chất của Minimax và Search, đủ khả năng đi từ một luật chơi đơn giản đến việc tự thiết kế, cài đặt, kiểm chứng và tối ưu một game engine hoàn chỉnh.

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
MN0001 Dòng thời gian hợp lệ (Valid Timeline)	9	2	1
MN0002 Chọn engine từ log kiểm thử (Engine Log Selection)	2	2	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
MN0100 Trò chơi lấy sỏi tổng quát (Generalized Take-Away Game)	1	1	1
MN0101 Thắng, thua hay hòa trên đồ thị (Graph Game)	1	1	1

Người tham gia: 1
Tạo bởi: Phước Hưng