Thuật toán Nega - Scount trong cây trò chơi
Cao Thanh Tùng
Giải thuật tìm kiếm trong cây trò chơi là khá quan trọng. Nếu giải thuật tốt có thể giúp cho
chương trình tính toán được đến độ sâu lớn hơn, dẫn tới chất luợng của mỗi nước đi được
nâng lên (tất nhiên điều này còn phụ thuộc nhiều vào việc viết hàm lượng giá cho mỗi
nước đi). Giải thuật Nega-Scount (của giáo sư Alexander Reinefeld thuộc trường đại học
Hamburg) là giải thuật được dùng phổ biến hiện nay. Nó phát triển trên cơ sở của một
thuật toán nổi tiếng từ những năm 50 là Alpha-Beta. Nó giúp giảm bớt số nút phải thăm
trong cây trò chơi, có thể từ 20 dến 30% nếu được dùng kết hợp với bảng chuyển
vị(Transposition Table). Để minh họa cho sức mạnh của giải thuật Nega-Scount, chúng ta
sẽ xem xét qua về giải thuật Alpha-Beta. Đây là đoạn mã miêu tả giải thuật này:
function
fAlphaBeta (p : Position; alpha, beta, depth : Integer): Integer;
var
i, t, m : Integer;
begin
ifdepth = MaxDepth then
fAlphaBeta:=Evaluate(p)
else
begin
m:=-Infinity;
fori:=1 to b do
begin
t:=-fAlphaBetăp.i, -beta, -max(alpha, m), depth+1);
ift>m then m:=t;
ift≥beta then
begin
fAlphaBeta:=m;
Exit;
end;
end;

begin
t:=-fNegaScount(p.i,-n, -max(alpha, m), depth+1);
ift>m then
if(n=beta) or (depth >= MaxDepth-2) then
m:=t
else
m:=-fNegaScount(p.i,-beta, -t, depth+1);
ifm>=beta then
begin
fNegaScount:=m;
Exit;
end;
n:=Max(alpha,m)+1;
end;
fNegaScount:=m;
end;
end;
Khit>m, NegaScount buộc phải thăm lại nhánh đó với một cửa sổ rộng hơn trước (nhưng
vẫn hẹp hơn cửa số (-beta, -alpha)), và chỉ có hai trường hợp không phải tìm kiếm lại là khi
cửa sổ tìm kiếm đã đầy đủ (n= beta, hay la i=1) hay nút đang xét là nút là hoặc ngay sát nút
lá (depth ≥MaxDepth-1). Nếu không việc tìm kiếm sẽ được thực hiện trên cửa số (-beta,
-t).
Khi thực hiện lại việc tìm kiếm, NegaScount phải thăm nhánh vừa tìm, từ trái sang phải
một lần nữa, nên việc lưu lại thông tin của lần tìm kiếm vừa thực hiện là cần thiết. Ví dụ ta
có thể lưu lại đường đi tới nhánh lá bên trái cúng (là đường vừa đi qua), để lần sau tìm lại,
ta sẽ đi dọc theo đường đó rồi thực hiện tìm kiềm tiếp bắt đầu từ nút lá tiếp theo (không
phải tìm từ đầu). Kinh nghiệm cho thấy làm như vậy có thể giảm được khoảng 8% số nút
lá cần phải thăm khi tìm trong một cây trò chới có độ sâu tối đa là 7 và hệ số rẽ nhánh là 30
(tức là trung bình môi nút có 30 nút con).
Giải thuật NegaScount sẽ làm việc kém hiệu quả hơn Alpha-Beta nếu tìm trên cây có độ