KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN KHOA HỌC MÁY TÍNH
B O C O Á Á ĐỒ ÁN TRÍ TUỆ NHÂN TẠO
Đề bài : Minh họa thuật toán Anpha – Beta bằng chương trình chơi cờ tướng
I. Giới thiệu
Trò chơi Cờ Tướng là một minh hoạ rất tốt cho bài toán tìm kiếm trên cây trò chơi và áp
dụng thuật toán AlphaBeta trên cây này như thế nào. Đây là một trò chơi thú vị và tương
đối phổ biến ở Việt nam, châu Á cũng như trên toàn thế giới. Nó tạo cảm giác dường như
máy tính có thể suy nghĩ và đọ sức với con người . Cờ Tướng là loại cờ có độ phức tạp và
rất nhiều mặt tương đương với cờ Vua.
Trong phần này, chúng tôi sẽ giới thiệu những kiến thức cơ bản nhất về một chương trình
chơi cờ phải như thế nào. Các chương trình cũng hết sức đơn giản
Hinh 2.1
II. Viết chương trình chơi cờ
1. Biểu diễn bàn cờ và quân cờ
Bàn cờ trong trò chơi cờ Tướng là một bảng chữ nhật bao gồm 9 đường dọc và 10 đường
ngang. Các quân cờ chia làm hai bên đứng tại các giao điểm của các đường. Bàn cờ và vị
trí khởi đầu các quân cờ như hình 2.1. Cách đơn giản nhất để biểu diễn một bàn cờ trong
máy tính là ta dùng một mảng hai chiều, kích thước 9 x 10:
BYTE piece[10,9];
Mảng trên hoạt động tốt nhưng có cái bất tiện là ta phải dùng tới hai chỉ số để truy cập
vào mảng (ví dụ vị trí quân Pháo góc trên bên trái (cột 2, dòng 3) là piece[3, 2]). Một cải
tiến nhỏ là ta dùng mảng một chiều như sau:
BYTE piece[90];
Truy nhập đến vị trí quân Pháo góc trên bên trái lúc này là piece[20].
Các ô của mảng sẽ chứa những giá trị khác nhau cho biết đó là quân cờ gì. Mỗi quân cờ
sẽ được gán một mã số khác nhau như bảng dưới đây. Các chỗ trống (không có quân cờ)
sẽ được điền kí hiệu trống (EMPTY):
Quân cờ Kí hiệu Giá trị
Tốt (Chốt) PAWN 0
Sĩ BISHOP 1

Trắng LIGHT 1
Trống EMPTY 7
Ta lại có thông tin về bên được khai báo khởi đầu tương tự:
BYTE color[BOARD_SIZE]= {
0, 0, 0, 0, 0, 0, 0, 0, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 0, 7, 7, 7, 7, 7, 0, 7,
0, 7, 0, 7, 0, 7, 0, 7, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7,
1, 7, 1, 7, 1, 7, 1, 7, 1,
7, 1, 7, 7, 7, 7, 7, 1, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7,
1, 1, 1, 1, 1, 1, 1, 1, 1}
Để biết bên nào tới lượt đi, ta dùng một biến toàn cục m_side chứa một trong hai giá trị
LIGHT và DARK. Một biến toàn cục khác m_xside sẽ có sẵn giá trị ngược với side để
tiện tính toán (ví dụ nếu m_side = LIGHT thì m_xside = DARK). Khi tới phiên đối
phương đi, ta cần đảo ngược giá trị trong cả side và xside bằng các lệnh như sau (chú ý là
LIGHT+DARK = 3):
m_side := m_xside; m_xside := 3 - m_xside;
Ngoài ra, ta còn khai báo biến computerside cũng chỉ có một trong hai giá trị LIGHT và
DARK nhằm cho biết bên nào là máy.
2. Sinh nước đi
Một trong những việc quan trọng nhất để máy tính có thể chơi được cờ là phải chỉ cho nó
biết mọi nước đi có thể đi được từ một thế cờ. Máy sẽ tính toán để chọn nước đi có lợi
nhất cho nó. Các yêu cầu chính đối với một thủ tục sinh nước đi là:
• Chính xác (rất quan trọng). Một nước đi sai sẽ làm hỏng mọi tính toán. Đồng thời
chương trình có thể bị trọng tài xử thua luôn. Do số lượng nước đi sinh ra lớn,
luật đi quân nhiều và phức tạp nên việc kiểm tra tính đúng đắn tương đối khó.
• Đầy đủ (rất quan trọng). Sinh được mọi nước đi có thể có từ một thế cờ.

i := x - 1; { Nước sang trái đầu tiên }
while ((i-1) div 9) = ((x-1) div 9) do
begin
if (ô thứ i là trống) or (ô thứ i có quân đối phương) then
gen_push(vị trí của Xe, vị trí ô đang xét);
if ô thứ i không trống then
break; { Kết thúc quá trình sinh nước đi sang trái }
i := i - 1; { Xét tiếp vị trí bên trái }
end;
Việc sinh những nước đi theo chiều khác cũng tương tự (ví dụ để sinh nước đi theo chiều
đứng ta chỉ cần cộng hoặc trừ một bội số của 9) nhưng điều kiện kiểm tra sẽ khác nhau.
Như vậy, chương trình sinh nước đi Gen có dạng như sau:
for Xét lần lượt từng quân cờ bên hiện tại do
case quâncờ of
Xe: begin
while Xét lần lượt tất cả các ô từ bên phải Xe cho đến lề trái bàn cờ do
begin
if (ô đang xét là ô trống) or (ô đang xét chứa quân đối phương) then
gen_push(vị trí của Xe, vị trí ô đang xét)
if ô đang xét không trống then break;
end;
while Xét lần lượt tất cả các ô từ bên trái Xe cho đến lề phải bàn cờ do

while Xét lần lượt tất cả các ô từ bên trên Xe cho đến lề trên bàn cờ do

while Xét lần lượt tất cả các ô từ bên dưới Xe cho đến lề dưới bàn cờ do

end; { Xong quân Xe }
Pháo:


trị 13 là kích thước một dòng của mảng này). Để sinh các nước đi chéo ta phải cộng trừ
với một hằng số khác. Ta nên lưu các hằng số này vào mảng offset có 2 chiều. Một chiều
dựa vào loại quân cờ nên chỉ số được đánh từ 1 đến 7. Chiều còn lại là số hướng đi tối đa
của một quân cờ. Quân cờ có nhiều hướng nhất là quân Mã có tới 8 hướng nên chiều này
được khai báo chỉ số từ 1 đến 8. Các quân cờ có số hướng ít hơn sẽ được điền 0 vào phần
thừa. Chú ý là nước đi quân Tốt của hai bên khác nhau hướng tiến. Để tiết kiệm ta chỉ lưu
nước tiến của Tốt đen, còn nước tiến của Tốt trắng chỉ đơn giản lấy ngược dấu.
Kiểm tra vị trí được phép đến
Việc chuyển toạ độ từ bàn cờ thường sang bàn cờ mở rộng chỉ giúp ta loại bỏ được các
nước vượt quá biên. Ta còn phải kiểm tra một số giới hạn khác. Ví dụ như Tướng và Sĩ
không thể đi ra ngoài cung, Tượng chỉ được phép ở 7 điểm cố định phía bên mình, Tốt
chỉ được phép tung hoành trên đất đối phương, còn phía bên mình cũng bị giới hạn ngặt
nghèo một số ô Để thực hiện những phép kiểm tra này, ta dùng một mảng là legalmove
ứng với từng ô trên bàn cờ sẽ cung cấp các thông tin này. Để kiểm tra một quân cờ có
được phép ở đó không, ta dùng một mặt nạ bít Maskpiece mà tuỳ theo từng quân sẽ có
giá trị khác nhau. Nếu ở ô cần kiểm tra có bit trùng với mặt nạ này được đặt là 1 thì quân
cờ đó được phép đến ô đấy.

Ví dụ, ô số 3 có giá trị legalmove[3] = 5 (chuyển thành số nhị phân là 00000101) cho biết
các quân cờ được phép đi đến đó là Tượng, Xe, Pháo, Mã.
Ngoài ra, ta còn phải kiểm tra nước bị cản (đối với Tượng và Mã) và xử lí cách ăn quân
của quân Pháo như một trường hợp đặc biệt. Như vậy, tổng thể sinh các nước đi cho một
quân cờ có dạng như sau:
p := piece[i]; { Sinh nước đi cho quân cờ p ở vị trí i }
for j := 1 to 8 do begin { Số hướng đi tối đa }
if offset[p,j] = 0 then break;
x:=mailbox90[i]; { Chuyển sang bàn cờ mở rộng}
if p in [ROOK, CANNON] then n := 9 else n := 1;
for t:=1 to n do { Số nước có thể đi theo một hướng}
begin

thể là đánh giá của ta về xác suất chiến thắng, nhưng đối với đa số chương trình
thì con số đó không có gì đặc biệt, nó chỉ là con số mà mục đích chính là so sánh
được với nhau.
2. Chúng ta nên đo chất lượng của một thế cờ tương tự như phép đo của đối phương
(do đó, nếu ta coi là đạt được một thế tốt thì đối phương của ta phải thấy đó là thế
xấu đối với họ và ngược lại). Điều này tuy không thật đúng lắm, nhưng nó giúp
cho thuật toán tìm kiếm của ta làm việc tốt và trong thực tế cũng khá gần với sự
thật.
Trong chương này chúng ta chỉ cài đặt phương pháp đơn giản nhưng cơ bản nhất: lượng
giá dựa trên cơ sở giá trị của từng quân cờ. Cách tính này sẽ lấy tổng giá trị các quân cờ
hiện có của bên mình trừ đi tổng giá trị các quân cờ hiện có của đối phương. Do đó, một
thế cờ này hơn thế cờ kia ở chỗ nó còn nhiều quân bên mình hơn, nhiều quân giá trị cao
hơn cũng như có bắt được nhiều quân và quân giá trị cao của đối phương hơn không.
Cách làm này đã bỏ qua mất những nghệ thuật, chiến lược chơi cờ (mà đó là những điểm
để đánh giá một người là giỏi cờ hay không). Các quân cờ được triển khai không theo
một chiến lược chung nào hết (vô định). Nó còn tạo cảm giác như cờ "vồ", nghĩa là chỉ
nhằm nhằm sơ hở của đối phương là "ăn" ngay mà không cần biết đến hậu quả (điều này
không hẳn đúng, lí do sẽ trình bầy dưới). Tuy nhiên phương pháp tính điểm này có những
ưu điểm sau:
• Là cách tính điểm cơ bản nhất, đóng vai trò chủ đạo trong điểm của một thế cờ.
Nó là cơ sở của đa số hàm đánh giá. Ta cũng có thể nhận thấy trong phần lớn thời
gian diễn ra trận đấu, hai bên đều tìm cách tiêu diệt quân của nhau. Các phương
án, chiến lược thường chỉ được tính như những điểm cộng thêm vào và đóng góp
một tỷ lệ nhỏ trong tổng số điểm của một thế cờ. Việc chỉ nhằm "vồ" quân của đối
phương nhưng sau khi suy nghĩ sâu nhiều nước cũng đã trở thành "cao cờ" rồi
đấy. Nói cho cùng, mục đích chính của chúng ta cũng là "vồ" bằng được quân có
giá trị cao nhất - Tướng đối phương.
• Là cách tính đơn giản nhất và nhanh nhất. Do tính nhanh, ta có thể tăng thêm độ
sâu tìm kiếm. Việc tăng thêm độ sâu lại giúp máy có cái nhìn xa hơn, "cao cờ"
hơn và nhiều khi khắc phục được nhược điểm của cách tính đơn giản.

{
if (m_color[i]==DARK) s += pointtable[m_piece[i]][DARK][i];
else if (m_color[i]==LIGHT) s -= pointtable[m_piece[i]][LIGHT][i];
}
if (m_side==LIGHT) s = -s;
return s + Bonous();
}
Tham khảo kiến thức cờ Tướng
GIÁ TRỊ CỦA CÁC QUÂN CỜ
Khái niệm giá trị của các quân cờ không phải là mới đối với những người chơi cờ từ các
thế kỷ trước. Từ lâu, làng cờ đã có câu nhận định sức mạnh của các quân chủ lực là "Xe
10, Pháo 7, Mã 3" hoặc đánh giá Xe là quân chủ lực mạnh nhất bằng câu "Nhất Xa sát
vạn" hay đánh giá một Tốt qua hà, sức mạnh bằng nửa con Xe (nhất Tốt độ hà, bán Xa
chi lực). Thế nhưng sự đánh giá nhận định này về sức mạnh của các quân không chính
xác và cũng không đầy đủ. Do đó khái niệm giá trị của các quân cần được xác định rõ và
hoàn chỉnh hơn. Thông thường, theo thời gian một ván cờ được chia thành ba giai đoạn:
khai cuộc, trung cuộc và tàn cuộc. Trong ba giai đoạn này thì trung cuộc chiếm nhiều
thời gian nhất và có ý nghĩa đến thắng thua nhiều nhất. Do đó các định giá quân cờ
thường là cho giai đoạn này.
Chúng ta đã biết mỗi loại quân cờ hay mỗi binh chủng có đặc điểm, tính năng và tác
dụng khác nhau nên sức mạnh của chúng cũng khác nhau, giá trị của chúng cũng không
giống nhau. Ngay bản thân mỗi quân cờ cũng không phải lúc nào sức mạnh cũng giữ
nguyên như cũ. Khi đứng ở vị trí tốt nó phát huy tính năng tác dụng tối đa khác hẳn với
khi nó đứng ở vị trí xấu, không thể phát huy tính năng tác dụng được, hay chỉ phát huy ở
mức rất hạn chế. Vậy điều trước tiên chúng ta phải thấy mỗi quân cờ có hai giá trị: giá
trị vốn có và giá trị biến động. Giá trị vốn có thường được gọi là giá trị cơ bản (giá trị
tĩnh), còn giá trị biến động được gọi là giá trị tương đối.
Các nhà nghiên cứu lí luận về cờ đã trao đổi thống nhất với nhau bảng giá trị cơ bản của
các quân như sau:
Nếu lấy Tốt chưa qua sông làm chuẩn để xác định giá trị thì nó là quân kém năng lực

vô cùng to lớn, không một quân nào so sánh được. Tất cả các quân đều có thể đổi, có thể
hi sinh nhưng riêng quân Tướng không thể đánh đổi mà cũng không thể hi sinh, vì mất
Tướng là thua cờ. Do đó cũng không nên định giá trị cơ bản của Tướng vì định cũng
chẳng có ý nghĩa gì.
(Sưu tầm)

4. Xử lí một nước đi "thử"
Trong quá trình tính toán tìm nước đi tốt nhất cho mình, máy thường phải đi "thử" một
nước rồi lại tính tiếp. Sau đó nó sẽ phục hồi lại nước đi này. Do quá trình thử - phục hồi
diễn ra rất nhanh và không hiện ra màn hình nên máy có thể thử hàng chục triệu lần mỗi
khi đến lượt. Việc đi thử được thực hiện nhờ gọi hàm Makemove. Việc khôi phục nước
đi này nhờ gọi thủ tục UnMakemove. Như vậy, chương trình thường xuyên thực hiện các
câu lệnh dạng như sau:
while tất cả các nước đi có thể có từ một thế cờ do begin
Makemove(một_nước_đi); { Đi thử một nước }
best := Tính điểm của nước đi thử đó;
UnMakemove; { phục hồi nước đi này}
Lưu nước đi có điểm cao nhất;
end;
Để tính được điểm của nước đi vừa thực hiện, nhiều khi máy lại phải thử đi tiếp một số
nước nữa. Cứ như vậy các hàm Makemove và UnMakemove có thể được gọi lồng nhau
rất sâu.
Khi đi thử, hàm Makemove phải lưu lại các thông tin cần thiết cho việc khôi phục lại sau
này. Cách đơn giản nhất - lưu lại cả bàn cờ, không dùng được do các thông tin phải lưu
quá nhiều. Thực chất, ta chỉ cần lưu các thông tin bao gồm: điểm xuất phát của quân cờ,
điểm đến và loại quân cờ mà nó bắt được (nếu có). Để lưu các thông tin này, hàm sử
dụng một mảng hist_dat các bản ghi chứa thông tin đó và con trỏ hdp được tổ chức như
một ngăn xếp, nghĩa là nước đi sau cùng sẽ được phục hồi trước nhất.
Khi máy đi "thử" cho một bên một nước, thì nước sau sẽ đến lượt đối phương. Do đó
hàm này cũng phải thay đổi giá trị các biến toàn cục về bên đi và đối thủ side và xside

5. Tìm kiếm AlphaBeta
Thủ tục AlphaBeta
Thủ tục AlphaBeta là một cải tiến thuật toán Minimax nhằm tỉa bớt nhánh của cây trò
chơi, làm giảm số lượng nút phải sinh và lượng giá, do đó có thể tăng độ sâu của cây tìm
kiếm. Giả sử hình 1.6 là một thế cờ mà hai nút đầu tiên đã được lượng giá. Nếu thực hiện
thủ tục Minimax đối với các nút đó sẽ cho thấy người chơi cực đại đã được đảm bảo nếu
đi nước bên trái sẽ được ít nhất là 2 điểm dù là các lượng giá của các nút khác cho kết
quả như thế nào đi nữa.
Bây giờ, ta lại giả sử nút tiếp theo được lượng giá và cho kết quả là 1. Nếu đi vào nhánh
này thì đối phương sẽ đảm bảo làm điểm của người chơi cực đại không thể vượt quá
được giá trị 1 dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Do đó
đến đây, nước đi tốt nhất là chọn nước đi bên trái với đảm bảo là ít nhất đạt được 2 điểm.
Và do đó, hoàn toàn không cần thiết phải lượng giá nút còn lại.

Nguyên tắc Alpha-Beta
Nếu biết điều đó thật sự tồi thì đừng mất thời gian tìm hiểu nó sẽ tồi tệ đến đâu

Ý tưởng này được gọi là nguyên tắc Alpha-Beta do nó dùng trong thủ tục AlphaBeta (ta
sẽ xét dưới đây). Hai tham số của thủ tục này (theo các đặt tên truyền thống) được gọi là
alpha và beta và dùng để theo dõi các triển vọng - chúng cho biết các giá trị nằm ngoài
khoảng [alpha, beta] là các điểm "thật sự tồi" và không cần phải xem xét nữa. Khoảng
[alpha, beta] còn được gọi là cửa sổ alpha, beta. Trong ngữ cảnh của các trò chơi, nguyên
tắc Alpha-Beta nói rằng, mỗi khi xem xét một nút bất kì, nên kiểm tra các thông tin đã
biết về các nút cha, ông của nó. Rất có thể do có đủ thông tin từ cha, ông nên không cần
phải làm bất cứ việc gì nữa cho nút này. Cũng vậy, nguyên tắc này cũng giúp chỉnh sửa
hoặc xác định chính xác giá trị tại nút cha, ông nó. Như trên nói, một cách để tiện theo
dõi quá trình tính toán là dùng các tham số alpha và beta để ghi lại các thông tin theo dõi
cần thiết. Thủ tục AlphaBeta được bắt đầu tại nút gốc với giá trị của alpha là -vôcùng và
beta là +vôcùng. Thủ tục sẽ tự gọi đệ quy chính nó với khoảng cách giữa các giá trị alpha
và beta ngày càng hẹp hơn.

này hoàn toàn an toàn với những lí do ta đã xét ở trên. Ta thấy rằng mỗi lần hàm này
được gọi thì chỉ có tham số beta được dùng để so sánh cắt bỏ, còn tham số alpha không
được dùng. Tuy nhiên khi áp dụng cùng thuật toán cho cây con thì ta đã hoán vị hai giá
trị alpha, beta cho nhau (và đảo cả dấu), do đó alpha sẽ có tác dụng trong độ sâu sau, rồi
độ sâu sau nữa lại đến lượt beta Nói cách khác, một giá trị chỉ luôn ảnh hưởng đến
người chơi cực đại, còn giá trị kia lại luôn ảnh hưởng đến người chơi cực tiểu. Chúng là
các ngưỡng của họ (ngưỡng giữa các nước đi được chấp nhận và không chấp nhận).
Những nước đi cần quan tâm phải nằm lọt giữa hai giá trị này. Dần dần khoảng cách giữa
hai giá trị alpha - beta càng ngày càng thu hẹp và dẫn đến các nhánh cây có giá trị nằm
ngoài khoảng này nhanh chóng bị cắt bỏ (hình 1.7).
Đánh giá thuật toán AlphaBeta
Trong điều kiện lí tưởng, thuật toán AlphaBeta chỉ phải xét số nút theo công thức:
= với d chẵn
= với d lẻ
Với b = 40 và d = 4 ta có số nút phải xét là 2x40^2 - 1 = 3199. Như vậy trong điều kiện lí
tưởng thì số nút phải xét nhờ AlphaBeta (chỉ khoảng 3 nghìn nút) ít hơn thuật toán
Minimax (hơn 2,5 triệu nút) là 2560000 / 3199 khoảng 800 lần. Còn với b = 40 và d = 5
ta có số nút phải xét là 40^3 + 40^(5/2) - 1 = 64000+10119-1 = 74118. Số nút phải xét
nhờ AlphaBeta ít hơn thuật toán Minimax (hơn 102 triệu nút) là 102400000/74118 =
1382 lần.
Dưới đây là bảng so sánh số nút phải xét giữa hai thuật toán Minimax và AlphaBeta.
Ta có thể nhận xét như sau:
- Số lần tăng số nút khi tăng độ sâu của Minimax luôn là hệ số phân nhánh b, trong
trường hợp này là 40. Số lần tăng của AlphaBeta ít hơn nhiều: chỉ cỡ 1.7 lần khi tăng từ d
lẻ sang d chẵn và 23.2 lần khi từ d chẵn sang lẻ - trung bình chỉ tăng khoảng hơn 6 lần
khi tăng d
- Số nút của AlphaBeta tăng chậm hơn rất nhiều lần so với Minimax. Tỉ số nút phải xét
giữa hai thuật toán này càng cao khi d càng lớn.
Công thức tính số nút cho thấy số nút phải xét khi dùng AlphaBeta ít hơn nhiều so với
Minimax nhưng vẫn là hàm số mũ và vẫn dẫn tới bùng nổ tổ hợp. Thuật toán AlphaBeta

[16]. Bây giờ ta có thể kết luận ở mức trên cùng. Mức này là của người chơi cực đại. Anh
ta thấy rằng nếu chọn đi theo nhánh trái thì được 4 điểm. Như vậy anh ta đã chắc chắn
điểm của mình sẽ ít nhất là 4 rồi. Để xem liệu có thể đạt được điểm cao hơn nữa hay
không cần phải xem xét hai nhánh còn lại.
[17-30]. Tương tự như phần trên, ta kết luận nhánh giữa sẽ mang lại cho người chơi cực
đại 5 điểm. 31. Cũng tương tự như kết luận 16, ở đây ta kết luận khả quan hơn là người
chơi cực đại đã cầm chắc 5 điểm và có thể còn cao hơn.
[32-38] Ta kết luận được rất nhanh là cây con bên phải chỉ cho "thu hoạch" nhiều nhất là
3 điểm - một điểm số quá kém do đó thuật toán không buồn xem xét các trường hợp còn
lại nữa. Do đó đã tiết kiệm được 6 nút không cần phải lượng giá và cũng không phải sinh
nước đi cho hai trường hợp.
[39]. Kết luận cuối cùng là điểm cao nhất mà người chơi cực đại có thể thu được là 5
điểm nhờ chọn đi theo nhánh giữa.
Hướng cải thiện việc tỉa nhánh của thuật toán AlphaBeta
Thuật toán AlphaBeta nói chung giúp chúng ta tiết kiệm nhiều thời gian so với Minimax
mà vẫn đảm bảo kết quả tìm kiếm chính xác. Tuy nhiên lượng tiết kiệm này không ổn
định - phụ thuộc vào số nút mà nó cắt bỏ. Trong trường hợp xấu nhất thuật toán không
cắt được một nhánh nào và phải xét số nút đúng bằng Minimax. Ta cần đẩy mạnh việc cắt
bỏ nhờ đẩy nhanh sự thu hẹp của cửa sổ tìm kiếm alpha - beta. Cửa sổ này được thu hẹp
một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này
thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như
vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này
càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu (các công thức về số nút phải
lượng giá trong điều kiện lí tưởng ở trên tính được với trật tự là tốt nhất).
Ta đã thấy chương trình mẫu của thủ tục AlphaBeta. Hàm AlphaBeta của ta về cơ bản là
giống như vậy, chỉ bỏ đi các tham số pos (thế cờ hiện tại - ở đây là giá trị của hai mảng
piece và color) ở một số hàm do đã biến đổi trực tiếp vào các mảng toàn cục piece và
color (nhờ các hàm Makemove và UnMakemove mà ta đã đề cập đến ở trên) nên chúng
chính là thế cờ đang xét.
function AlphaBeta(alpha, beta: integer; depth: byte): integer;

căn cứ vào giá trị chân lí này để ngừng chơi.
7. Hiện thông tin
muốn biết thêm một vài số liệu như: thời gian mỗi lần máy nghĩ, hệ số phân nhánh của
cây trò chơi, số thế cờ nó phải tính giá trị, khả năng xét thế cờ trung bình của máy là bao
nhiêu cũng như nhiều số liệu khác. Việc quan sát các số liệu này còn giúp ta biết các cải
tiến, sửa đổi về sau có thực sự hoạt động tốt không.
Cách lấy số liệu rất đơn giản, ta khai báo thêm một số biến toàn cục, thêm một số lệnh và
cuối cùng in chúng ra màn hình ở chỗ thích hợp. Một số thông tin rất khó lấy chính xác,
ta sẽ tạm bằng lòng với những số liệu gần đúng vậy.
Để biết mỗi lần nghĩ, máy đã lượng giá bao nhiêu thế cờ - một thông tin vô cùng quan
trọng, ta khai báo một biến toàn cục m_evalcount và mỗi khi hàm Eval() được gọi ta lại
tăng giá trị của nó thêm một.
Để có được hệ số phân nhánh chính xác ta phải thống kê qua một số dữ liệu lớn. Chú ý
rằng, số nhánh con được sinh ra mỗi lần gọi hàm Gen được đo bằng hiệu
m_gen_end[m_ply] – m_gen_begin[m_ply]. Do đó hệ số phân nhánh được đo bằng cách
lấy tổng các nhánh con này rồi chia cho số lần gọi hàm Gen (đo bằng biến m_gencount).
Càng chơi lâu, các dữ liệu đo được càng lớn, kết quả sẽ càng chính xác.
// biến dùng để đo hệ số phân nhánh
long m_brandtotal;
long m_gencount;
// biến dùng để đo số nút lượng giá
long m_evalcount;
BOOL Gen()
{

m_brandtotal = m_brandtotal + m_gen_end[m_ply] - m_gen_begin[m_ply];
m_gencount += 1;
}
short Eval()
{