Giáo trình Trí tuệ nhân tạo - Phạm Thọ Hoàng (Phần 1)

hàm h tăng lên 1). Lúc này danh sách sắp xếp có 2 nút lá tương ứng với hai trạng thái có 
hàm h=7 và h=9. Trong 2 nút lá này, giải thuật sẽ chọn nút có giá trị hàm h nhỏ hơn 
(h=7) để mở rộng cây. Tiếp tục mở rộng cây theo hướng nút lá có giá trị h nhỏ nhất 
(trong trường hợp có nhiều nút lá cùng có giá trị nhỏ nhất thì chọn nút lá nào xuất hiện 
trước) thì ta được một phần của cây như trong hình vẽ trên. 
2. Các biến thể của giải thuật best first search 
Ý tưởng của giải thuật tìm kiếm tốt nhất đầu tiên (best first search) là mở rộng cây tìm 
kiếm theo hướng ưu tiên các nút lá có triển vọng chứa trạng thái đích (dựa trên hàm đánh 
giá h). Giải thuật best-first-search có các biến thể sau: 
- Khi hàm h(n) là chi phí của dãy phép chuyển từ trạng thái đầu đến trạng thái n thì giải 
thuật best-first-search có tên gọi khác là giải thuật tìm kiếm đều (uniform search). Trong 
trường hợp này, cây tìm kiếm sẽ mở rộng đều về tất cả các hướng theo vết dầu loang từ 
trạng thái đầu. Khi hàm chi phí của dãy phép chuyển là số các đỉnh trung gian thì giải 
thuật uniform search trở thành giải thuật tìm kiếm theo chiều rộng. Giải thuật uniform 
search sẽ cho lời giải với chi phí nhỏ nhất, tuy nhiên cây tìm kiếm sinh ra trong giải thuật 
này thường có kích thước rất lớn. 
- Khi h(n) là ước lượng chi phí/khoảng cách từ n đến đích (ví dụ như khoảng cách 
Manhatan trong bài toán 8 số ở trên) thì giải thuật best-first-search được gọi là giải thuật 
tham ăn (greedy search). Giải thuật tham ăn sẽ chọn nút lá n “gần” đến đích nhất trong 
số các nút lá của cây tìm kiếm để mở rộng cây, và nó không quan tâm đến chi phí từ 
trạng thái đầu đến n. Do vậy giải thuật có xu hướng cho ra kết quả trong thời gian nhanh 
nhất, nhưng không phải lúc nào cũng là lời giải ngắn nhất. 
- Khi h(n) = f(n) + g(n), trong đó f(n) là hàm chi phí/khoảng cách từ trạng thái đầu đến n 
và g(n) là hàm ước lượng chi phí/khoảng cách từ n đến trạng thái đích, và nếu g(n) là ước 
lượng dưới của hàm chi phí/khoảng cách thực sự từ n đến trạng thái đích thì giải thuật 
best-first-search được gọi là giải thuật A*. Giải thuật A* là giải thuật trung hòa giữa hai 
giải thuật uniform và giải thuật greedy ở trên. A* cho lời giải có chi phí nhỏ nhất (bạn 
đọc có thể tìm hiểu chứng minh điều này ở các tài liệu khác) và cây tìm kiếm có kích 
thước vừa phải. 
 Ví dụ, đối với bài toán tìm đường đi từ thành phố Arad đến thành phố Bucharest đã mô tả 
trong 1.b, nếu chúng ta sử dụng khoảng cách Ơclit (khoảng cách theo đường chim bay) từ 
mỗi thành phố đến đích (xem hình vẽ trên) thì các giải thuật uniform, greedy và A* sẽ 
cho các cây tìm kiếm như sau: 
Một phần cây tìm kiếm của giải thuật Uniform search 
 Cây tìm kiếm của giải thuật Greedy search 
Cây tìm kiếm của giải thuật A* 
3. Các giải thuật khác 
* Tìm kiếm leo đồi: 
Ý tưởng: Tìm kiếm theo chiều sâu kết hợp với hàm đánh giá. Mở rộng trạng thái hiện tại 
và đánh giá các trạng thái con của nó bằng hàm đánh giá heuristic. Tại mỗi bước, nút lá 
“tốt nhất” sẽ được chọn để đi tiếp. 
Procedure Hill-Climbing_search; 
Begin 
 1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu; 
 2. Loop do 
 2.1 If S rỗng then {thông báo thất bại; stop}; 
 2.2 Lấy trạng thái u ở đầu ngăn xếp S; 
 2.3 If u là trạng thái kết thúc then 
 {thông báo thành công; stop}; 
 2.4 For mỗi trạng thái v kề u do đặt v vào danh sách L; 
2.5 Sắp xếp L theo thứ tự tăng dần của hàm đánh giá sao cho trạng 
thái tốt nhất ở đầu danh sách L; 
 2.6 Chuyển danh sách Lvào ngăn xếp S; 
End; 
Ví dụ : Với ví dụ đồ thị không gian trạng thái như hình 2.2 thì cây tìm kiếm leo đồi 
tương ứng như hình 2.4 : 
 Hạn chế của thuật toán : 
- Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ: 
+ Lời giải tìm được không tối ưu 
+ Không tìm được lời giải mặc dù có tồn tại lời giải 
- Giải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái đã 
duyệt. 
* Tìm kiếm Beam 
Để hạn chế không gian tìm kiếm, người ta đưa ra phương pháp tìm kiếm Beam. Đây 
là phương pháp tìm kiếm theo chiều rộng nhưng có hạn chế số đỉnh phát triển ở mỗi 
mức. Trong tìm kiếm theo chiều rộng, tại mỗi mức ta phát triển tất cả các đỉnh, còn 
tìm kiếm Beam thì chọn k đỉnh tốt nhất để phát triển. Các đỉnh này được xác định bởi 
hàm đánh giá. Ví dụ, với đồ thì không gian trạng thái như hình 2.2 và lấy k=2 thì cây 
tìm kiếm Beam như hình 2.5. Các đỉnh được chọn ở mỗi mức là các đỉnh được tô màu 
đỏ: 
E
A 20
D6
7
I 8
5
C 15 
Cây tìm kiếm leo đồi 
F10
GB0
 * Tìm kiếm nhánh cận 
Ý tưởng : thuật toán tìm kiếm leo đồi kết hợp với hàm đánh giá f(u). Tại mỗi bước, 
khi phát triển trạng thái u, chọn trạng thái con v tốt nhất (f(v) nhỏ nhất) của u để phát 
triển ở bước sau. Quá trình tiếp tục như vậy cho đến khi gặp trạng thái w là đích, hoặc 
w không có đỉnh kề, hoặc w có f(w) lớn hơn độ dài đường đi tối ưu tạm thời (đường đi 
đầy đủ ngắn nhất trong số những đường đi đầy đủ đã tìm được). Trong các trường hợp 
này, chúng ta không phát triển đỉnh w nữa, tức là cắt bỏ những nhánh xuất phát từ w, 
và quay lên cha của w để tiếp tục đi xuống trạng thái tốt nhất trong số những trạng 
thái còn lại chưa được phát triển. 
Procedure Branch-and-Bound; 
Begin 
 1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu; 
 Gán giá trị ban đầu cho cost; /*cost là giá trị đường đi tối ưu tạm thời*/ 
 2. Loop do 
 2.1 If S rỗng then {thông báo thất bại; stop}; 
 2.2 Lấy trạng thái u ở đầu ngăn xếp S; 
H 
G 
K 
E 
A 20 
D 6 
7 
I 
8 
12 
5
3 
B 
0 
C 
15 
Cây tìm kiếm Beam
F 
10 
B 0 G 5 
 2.3 If u là trạng thái kết thúc then 
 if g(u)<=cost then {cost ←g(u); quay lại 2.1}; 
 2.4 if f(u)>cost then quay lại 2.1; 
 2.5 For mỗi trạng thái v kề u do 
 {g(v) ←g(u)+k(u,v); 
 f(v) ←g(v) +h(v); 
 đặt v vào danh sách L1}; 
 2.6 Sắp xếp L theo thứ tự tăng dần của hàm f; 
2.7 Chuyển danh sách Lvào ngăn xếp S; 
End; 
Ví dụ : Với đồ thị không gian trạng thái như hình 2.7, đỉnh xuất phát A và đỉnh đích 
B. Áp dụng thuật toán nhánh – cận, ta xây dựng được cây tìm kiếm như hình 2.9 và 
giá trị của hàm f tại các đỉnh được tính như bảng 2.2: 
Đỉnh phát 
triển (u) 
Đỉnh con 
(v) 
g(v) f(v) Đỉnh 
chọn 
C 9 9+15=24 
D 7 7+6=13 D 
E 13 13+8=21 
A 
F 20 20+7=27 
H 7+8=15 15+10=25 D 
E 7+4=11 11+8=19 E 
K 11+4=15 15+2=17 K E 
I 11+3=14 14+4=18 I 
K B 15+6=21 21+0=21 
B cost := 21 
K 14+9=23 23+2=25 I 
B 14+5=19 19+0=19 B 
B cost := 19 
A
14 
C24 
F
27 
B
I
K
K
ED13 
21 
E 19 
25 19 21 
H25 
B
18 
Cây tìm kiếm nhánh-cận 
17 
Tính giá trị hàm f cho thuật toán 
nhánh-cận 
Nhận xét : Thuật toán nhánh-cận cũng là thuật toán đầy đủ và tối ưu nếu h(u) là hàm 
đánh giá thấp và có độ dài các cung không nhỏ hơn một số dương δ nào đó 
 Chương 4 – Các giải thuật tìm kiếm lời giải cho trò chơi 
Chương trình chơi cờ đầu tiên được viết bởi Claude Shannon vào năm 1950 đã là một 
minh chứng cho khả năng máy tính có thể làm được những việc đòi hỏi trí thông minh 
của con người. Từ đó người ta nghiên cứu các chiến lược chơi cho máy tình với các trò 
chơi có đối thủ (có hai người tham gia). Việc giải quyết bài toán này có thể đưa về bài 
toán tìm kiếm trong không gian trạng thái, tức là tìm một chiến lược chọn các nước đi 
hợp lệ cho máy tính. Tuy nhiên, vấn đề tìm kiếm ở đây phức tạp hơn so với vấn đề tìm 
kiếm trong chương trước, vì người chơi không biết trước đối thủ sẽ chọn nước đi nào tiếp 
theo. Chương này sẽ trình bày một số chiến lược tìm kiếm phổ biến như Minimax, 
phương pháp cắt cụt α-β. 
1. Cây trò chơi đầy đủ 
Các trò chơi có đối thủ có các đặc điểm: hai người thay phiên nhau đưa ra các nước đi 
tuân theo các luật của trò chơi (các nước đi hợp lệ), các luật này là như nhau đối với cả 
hai người chơi, chẳng hạn các trò chơi cờ: cờ vua, cờ tướng, cờ ca rô (tic-tăc-toe), . Ví 
dụ, trong chơi cờ vua, một người điều khiển quân Trắng và một người điều khiển quân 
Đen. Người chơi có thể lựa chọn các nước đi theo các luật với các quân tốt, xe, mã, 
Luật đi quân tốt Trắng, xe Trắng, mã Trắng, giống luật đi quân tốt Đen, xe Đen, mã 
Đen,Hơn nữa, cả hai người chơi đều biết đầy đủ các thông tin về tình thế cuộc chơi. 
Thực hiện trò chơi là người chơi tìm kiếm nước đi tốt nhất trong số rất nhiều nước đi hợp 
lệ, tại mỗi lượt chơi của mình, sao cho sau một dãy nước đi đã thực hiện người chơi phải 
thắng cuộc. 
Vấn đề chơi cờ có thể được biểu diễn trong không gian trạng thái, ở đó, mỗi trạng thái là 
một tình thế của cuộc chơi (sự sắp xếp các quân cờ trên bàn cờ): 
- Trạng thái xuất phát là sự sắp xếp các quân cờ của hai bên khi bắt đầu cuộc chơi 
(chưa ai đưa ra nước đi) 
- Các toán tử biến đổi trạng thái là các nước đi hợp lệ 
- Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng, thường được xác định bởi 
một số điều kiện dừng (chẳng hạn, quân Trắng thắng hoặc quân Đen thắng hoặc hai 
bên hòa nhau) 
- Hàm kết cuộc: mang giá trị tương ứng với mỗi trạng thái kết thúc. Chẳng hạn, trong 
cờ vua, hàm kết cuộc có giá trị là 1 tại các trạng thái mà Trắng thắng, -1 tại các trạng 
thái mà Trắng thua và 0 tại các trạng thái hai bên hòa nhau. Trong các trò chơi tính 
điểm khác thì hàm kết cuộc có thể nhận các giá trị nguyên trong đoạn [-m, m], với m 
là một số nguyên dương nào đó. 
Như vậy, trong các trò chơi có đối thủ, người chơi (điều khiển quân Trắng – gọi tắt là 
Trắng) luôn tìm một dãy các nước đi xen kẽ với các nước đi của đối thủ (điều khiển quân 
Đen – gọi tắt là Đen) để tạo thành một đường đi từ trạng thái ban đầu đến trạng thái kết 
thúc là thắng cho Trắng. 
Không gian tìm kiếm đối với các trò chơi này có thể được biểu diễn bởi cây trò chơi như 
sau: gốc của cây ứng với trạng thái xuất phát, các đỉnh trên cây tương ứng với các trạng 
thái của bàn cờ, các cung (u, v) nếu có biến đổi từ trạng thái u đến trạng thái v. Các đỉnh 
trên cây được gán nhãn là đỉnh Trắng (Đen) ứng với trạng thái mà quân Trắng (Đen) đưa 
ra nước đi. Nếu một đỉnh u được gán nhãn là Trắng (Đen) thì các đỉnh con v của nó là tất 
cả các trạng thái nhận được từ u do Trắng (Đen) thực hiện một nước đi hợp lệ nào đó. Do 
đó, các đỉnh trên cùng một mức của cây đều có nhãn là Trắng hoặc đều có nhãn là Đen, 
các lá của cây ứng với trạng thái kết thúc. 
Ví dụ: trò chơi Dodgem: 
Có hai quân Trắng và hai quân Đen được xếp vào bàn cờ 
3x3. Ban đầu các quân cờ được xếp như hình bên. Quân 
Đen có thể đi đến ô trống bên phải, ở trên hoặc ở dưới. 
Quân Trắng có thể đi đến ô trống bên trên, bên trái hoặc 
bên phải. Quân Đen nếu ở cột ngoài cùng bên phải có thể 
đi ra khỏi bàn cờ, quân Trắng nếu ở hàng trên cùng có thể 
đi ra khỏi bàn cờ. Ai đưa được cả hai quân của mình ra 
khỏi bàn cờ hoặc tạo ra tình thế mà đối phương không đi 
được là thắng cuộc. 
Trò chơi Dodgem
2. Giải thuật Minimax 
Quá trình chơi cờ là quá trình mà Trắng và Đen thay phiên nhau đưa ra các nước đi hợp 
lệ cho đến khi dẫn đến trạng thái kết thúc cuộc chơi. Quá trình này biểu diễn bởi đường 
đi từ nút gốc tới nút lá trên cây trò chơi. Giả sử tại một đỉnh u nào đó trên đường đi, nếu u 
là đỉnh Trắng (Đen) thì cần chọn một nước đi nào đó đến một trong các đỉnh con Đen 
(Trắng) v của u. Tại đỉnh Đen (Trắng) v sẽ chọn đi tiếp đến một đỉnh con Trắng (Đen) w 
của v. Quá trình này tiếp tục cho đến khi đạt đến một đỉnh lá của cây. 
Chiến lược tìm nước đi của Trắng hay Đen là luôn tìm những nước đi dẫn tới trạng thái 
tốt nhất cho mình và tồi nhất cho đối thủ. Giả sử Trắng cần tìm nước đi tại đỉnh u, nước 
đi tối ưu cho Trắng là nước đi dẫn tới đỉnh con v sao cho v là tốt nhất trong số các đỉnh 
con của u. Đến lượt Đen chọn nước đi từ v, Đen cũng chọn nước đi tốt nhất cho mình. Để 
chọn nước đi tối ưu cho Trắng tại đỉnh u, cần xác định giá trị các đỉnh của cây trò chơi 
gốc u. Giá trị của các đỉnh lá ứng với giá trị của hàm kết cuộc. Đỉnh có giá trị càng lớn 
càng tốt cho Trắng, đỉnh có giá trị càng nhỏ càng tốt cho Đen. Để xác định giá trị các 
đỉnh của cây trò chơi gốc u, ta đi từ mức thấp nhất (các đỉnh lá) lên gốc u. Giả sử cần xác 
định giá trị của đỉnh v mà các đỉnh con của nó đã xác định. Khi đó, nếu v là đỉnh Trắng 
Đen
Trắng
Đen
Cây trò chơi Dodgem với Đen đi trước
thì giá trị của nó là giá trị lớn nhất trong các đỉnh con, nếu v là đỉnh Đen thì giá trị của nó 
là giá trị nhỏ nhất trong các đỉnh con. 
Sau đây là thủ tục chọn nước đi cho Trắng tại đỉnh u Minimax(u, v), trong đó v là đỉnh 
con được chọn của u: 
Procedure Minimax(u, v); 
begin 
 val ←-∝; 
 for mỗi w là đỉnh con của u do 
 if val(u) <= MinVal(w) then 
 {val ← MinVal(w); v ← w} 
end; 
--------------------------------------------------- 
Function MinVal(u); {hàm xác định giá trị cho các đỉnh Đen} 
begin 
 if u là đỉnh kết thúc then MinVal(u) ← f(u) 
 else MinVal(u) ← min{MaxVal(v) | v là đỉnh con của u} 
end; 
--------------------------------------------------- 
Function MaxVal(u); { hàm xác định giá trị cho các đỉnh Trắng} 
begin 
 if u là đỉnh kết thúc then MaxVal(u) ← f(u) 
 else MaxVal(u) ← max{MinVal(v) | v là đỉnh con của u} 
end; 
Trong các thủ tục và hàm trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết thúc u. 
Thuật toán Minimax là thuật toán tìm kiếm theo chiều sâu. Về lý thuyết, chiến lược 
Minimax cho phép tìm nước đi tối ưu cho Trắng. Tuy nhiên trong thực tế, ta không có đủ 
thời gian để tính toán nước đi tối ưu này. Bởi vì thuật toán tính toán trên toàn bộ cây trò 
chơi (xem xét tất cả các đỉnh của cây theo kiểu vét cạn). Trong các trò chơi hay thì kích 
thước của cây trò chơi là cực lớn. Chẳng hạn, trong cờ vua, chỉ tính đến độ sâu 40 thì cây 
trò chơi đã có đến 10120 đỉnh. Nếu cây có độ cao m và tại mỗi đỉnh có b nước đi thì độ 
phức tạp về thời gian của thuật toán Minimax là O(bm). 
Trong thực tế, các trò chơi đều có giới hạn về thời gian. Do đó, để có thể tìm nhanh nước 
đi tốt (không phải tối ưu) thay vì sử dụng hàm kết cuộc và xét tất cả các đỉnh của cây trò 
chơi, ta sử dụng hàm đánh giá và chỉ xem xét một bộ phận của cây trò chơi. 
3. Giải thuật Minimax với độ sâu hạn chế 
a) Hàm đánh giá 
Hàm đánh giá eval cho mỗi đỉnh u là đánh giá “mức độ lợi thế” của trạng thái u. Giá trị 
của eval(u) là số dương càng lớn thì trạng thái u càng có lợi cho Trắng, giá trị của eval(u) 
là số dương càng nhỏ thì trạng thái u càng có lợi cho Đen, eval(u)=0 thì trạng thái u 
không có lợi cho đối thủ nào, eval(u)=+∝ thì u là trạng thái thắng cuộc cho Trắng, 
eval(u)=-∝ thì u là trạng thái thắng cuộc cho Đen. 
Hàm đánh giá đóng vai trò rất quan trọng trong các trò chơi, nếu hàm đánh giá tốt sẽ định 
hướng chính xác việc lựa chọn các nước đi tốt. Việc thiết kế hàm đánh giá phụ thuộc vào 
nhiều yếu tố: các quân cờ còn lại của hai bên, sự bố trí các quân cờ này, Để đưa ra hàm 
đánh giá chính xác đòi hỏi nhiều thời gian tính toán, tuy nhiên, trong thực tế người chơi 
bị giới hạn thời gian đưa ra nước đi. Vì vậy, việc đưa ra hàm đánh giá phụ thuộc vào kinh 
nghiệm của người chơi. Sau đây là một số ví dụ về cách xây dựng hàm đánh giá: 
Ví dụ 1: Hàm đánh giá cho cờ vua. Mỗi loại quân được gán một giá trị số phù hợp với 
“sức mạnh” của nó. Chẳng hạn, quân tốt Trắng (Đen) được gán giá trị 1 (-1), mã hoặc 
tượng Trắng (Đen) được gán giá trị 3 (-3), xe Trắng (Đen) được gán giá trị 5 (-5) và hậu 
Trắng (Đen) được gán giá trị 9 (-9). Hàm đánh giá của một trạng thái được tính bằng cách 
lấy tổng giá trị của tất cả các quân cờ trong trạng thái đó. Hàm đánh giá này được gọi là 
hàm tuyến tính có trọng số, vì có thể biểu diễn dưới dạng: 
 s1w1 + s2w2 +  + snwn 
Trong đó, wi là giá trị của quân cờ loại i, si là số quân loại đó. 
Đây là cách đánh giá đơn giản, vì nó không tính đến sự bố trí của các quân cờ, các mối 
tương quan giữa chúng. 
Ví dụ 2: Hàm đánh giá trạng thái trong trò chơi Dodgem. Mỗi quân Trắng được gán giá 
trị tương ứng với các vị trí trên bàn cờ như trong hình bên trái. Mỗi quân Đen được gán 
giá trị ở các vị trí tương ứng nhu hình bên phải: 
30 35 40 -10 -25 -40 
 15 20 25 -5 -20 -35 
0 5 10 0 -15 -30 
Ngoài ra, nếu quân Trắng cản trực tiếp một quân Đen, nó được thêm 40 điểm, nếu cản 
gián tiếp được thêm 30 điểm (xem hình dưới). Tương tự, nếu quân Đen cản trực tiếp quân 
Trắng nó được thêm -40 điểm, cản gián tiếp được thêm -30 điểm. 
Áp dụng cách tính hàm đánh giá nêu trên, ta tính được giá trị của các trạng thái ở các 
hình dưới như sau: 
Trắng cản gián tiếp Đen 
 được thêm 30 điểm 
Trắng cản trực tiếp Đen 
được thêm 40 điểm 
b) Thuật toán 
Để hạn chế không gian tìm kiếm, khi xác định nước đi cho Trắng tại u, ta chỉ xem xét cây 
gốc u tại độ cao h nào đó. Áp dụng thủ tục Minimax cho cây trò chơi gốc u, độ cao h và 
sử dụng hàm đánh giá để xác định giá trị cho các lá của cây. 
Procedure Minimax(u, v, h); 
begin 
 val ←-∝; 
 for mỗi w là đỉnh con của u do 
 if val(u) <= MinVal(w, h-1) then 
 {val ← MinVal(w, h-1); v ← w} 
end; 
--------------------------------------------------- 
Function MinVal(u, h); {hàm xác định giá trị cho các đỉnh Đen} 
begin 
 if u là đỉnh kết thúc or h = 0 then MinVal(u, h) ← eval(u) 
 else MinVal(u, h) ← min{MaxVal(v, h-1) | v là đỉnh con của u} 
end; 
--------------------------------------------------- 
Function MaxVal(u, h); { hàm xác định giá trị cho các đỉnh Trắng} 
begin 
 if u là đỉnh kết thúc or h =0 then MaxVal(u, h) ← eval(u) 
 else MaxVal(u, h) ← max{MinVal(v, h-1) | v là đỉnh con của u} 
end; 
Giá trị hàm đánh giá:75= 
(-10+0+5+10)+(40+30) 
Giá trị hàm đánh giá:-5=
(-25+0+20+10)+(-40+30)
4. Giải thuật Minimax với cắt tỉa alpha-beta 
Trong chiến lược Minimax với độ sâu hạn chế thì số đỉnh của cây trò chơi phải xét vẫn 
còn rất lớn với h>=3. Khi đánh giá đỉnh u tới độ sâu h, thuật toán Minimax đòi hỏi phải 
đánh giá tất cả các đỉnh của cây gốc u với độ sâu h. Tuy nhiên, phương pháp cắt cụt 
alpha-beta cho phép cắt bỏ những nhánh không cần thiết cho việc đánh giá đỉnh u. 
Phương pháp này làm giảm bớt số đỉnh phải xét mà không ảnh hưởng đến kết quả đánh 
giá đỉnh u. 
Ý tưởng: Giả sử tại thời điểm hiện tại đang ở đỉnh Trắng a, đỉnh a có anh em là v đã được 
đánh giá. Giả sử cha của đỉnh a là b, b có anh em là u đã được đánh giá, và cha của b là c 
như hình sau: 
Khi đó ta có giá trị đỉnh Trắng c ít nhất là giá trị của u, giá trị của đỉnh Đen b nhiều nhất 
là giá trị của v. Do đó, nếu eval(u) > eval(v) ta không cần đi xuống để đánh giá đỉnh a 
nữa mà vẫn không ảnh hưởng đến đánh giá đỉnh c. Hay nói cách khác, ta có thể cắt bỏ 
cây con gốc a. 
Lập luận tương tự cho trường hợp a là đỉnh Đen, trường hợp này nếu eval(u)<eval(v) ta 
cũng cắt bỏ cây con gốc a. 
Để cài đặt kỹ thuật này, đối với các đỉnh nằm trên đường đi từ gốc tới đỉnh hiện thời, ta 
sử dụng tham số α để ghi lại giá trị lớn nhất trong các giá trị của các đỉnh con đã đánh giá 
c 
v a
bu 
max
max
min
Cắt bỏ cây con gốc a nếu eval(u)>eval(v)
của một đỉnh Trắng, tham số β để ghi lại giá trị nhỏ nhất trong các giá trị của các đỉnh 
con đã đánh giá của một đỉnh Đen. 
Thuật toán: 
Procedure Alpha_beta(u, v); 
begin 
 α←-∝; β←-∝; 
 for mỗi w là đỉnh con của u do 
 if α <= MinVal(w, α, β) then 
 {α ← MinVal(w, α, β); v ← w} 
end; 
--------------------------------------------------- 
Function MinVal(u, α, β); {hàm xác định giá trị cho các đỉnh Đen} 
begin 
 if u là đỉnh kết thúc or u là lá của cây hạn chế then 
 MinVal(u, α, β) ← eval(u) 
 else for mỗi đỉnh v là con của u do 
 {β ← min{β, MaxVal(v, α, β)} ; 
 If α >= β then exit}; 
 /*cắt bỏ các cây con từ các đỉnh v còn lại */ 
 MinVal(u, α, β) ← β; 
end; 
--------------------------------------------------- 
Function MaxVal(u, α, β); { hàm xác định giá trị cho các đỉnh Trắng} 
begin 
 if u là đỉnh kết thúc or là lá của cây hạn chế then 
MaxVal(u, α, β) ← eval(u) 
 Else for mỗi đỉnh v là con của u do 
α ← max{α, MinVal(v, α, β)} ; 
If α >= β then exit}; 
 /*cắt bỏ các cây con từ các đỉnh v còn lại */ 
 MaxVal(u, α, β) ← α 
 end;