Thuật toán Nega - Scount trong cây trò chơi
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (60.74 KB, 3 trang )
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;
fAlphaBeta:=m;
end;
end;
Trong đoạn mã trên thì biến p miêu tả một đường đi (hay một chuỗi các nước đi) trên cây
trò chơi, tính từ nút gốc. Hàm Evalute là hàm lượng giá. b là số nút con tại nút p. p.i là ký
hiệu nút con thứ i (hay là nước đi thứ i có thể sinh được). MaxDepth là độ sâu tối đa mà
chúng ta cần duyệt. Chương trình được cài đặt theo phương pháp NegaMax để đơn giản
hơn.
Giải thuật Nega-Scount được phát triển dựa trên nhận xét là: Khi tìm kiếm trên một nhánh,
cửa sổ tìm kiếm (alpha, beta) càng nhỏ thì tìm càng nhanh. Nhánh đó được tìm nhanh nhất
khi cửa sổ là (-m-1, -m)(Nullwindow). Giải thuật sẽ thực hiện việc tìm kiếm bàng cách với
nút con đầu tiên (p.1), chương trình tìm kiếm băng cửa sổ đầy đủ, nhưng từ nút thứ 2 trở
đi, chương trình sẽ tìm kiếm với cửa sổ (-m-1,-m). Vì cửa sổ tìm kiếm này không chứa một
phần từ nào (nguyên) nên việc tìm kiếm chắc chắn sẽ thất bại. Giá trị nhận được vượt quá
cận trên (t>m) thì chúng ta sẽ phải thực hiện tiếp việc tìm kiếm để xác định giá trị chính
xác của nút cần tìm, nhưng với một cửa sổ tìm kiếm hẹp hơn. Thực ra giải thuật Nega-
Scount là tương tự với giải thuật PVS, nhưng nó hơn ở một nhận xét là việc tìm kiếm trên
cửa sổ (-m-1, -m) đối với những nút lá và nút sát với nút lá (d=MaxDepth-1) luôn cho kết
quả chính xác nên không cần phải tìm lại nữa. Giải thuật có thể cài đặt như sau:
functionfNegaScount(p : Position; alpha, beta, depth : Integer) : Integer;
var
i, t, m, n : Integer;
begin
ifdepth = MaxDepth then
fNegaScount:=Evaluate(p);
else
begin
m:=-Infinity;
n:=beta;
fori:=1 to b do
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ó độ
sâu nhỏ hơn 3, vì nó phải thăm mỗi nút nhiều lần. Do đó để đạt hiệu quả, ta nên sử dụng
Alpha-Beta mỗi khi phải thăm lại một nhánh nhỏ (depth=MaxDepth-3).
Giải thuật NegaScount chỉ tốt hơn Alpha-Beta khi cây tìm kiếm là khá cao với hệ số rẽ
nhánh khoảng từ 20 đến 60. Đây cũng là hệ só thường gặp trong các trò chơi. Trừ phi nếu
giải thuật được cài đặt kết hợp với bảng chuyển vị (thường là bảng băm) thì kết quả khá
hơn rất nhiều, nói chung luôn luôn tốt hơn ALpha-Beta. Vì lý do này mà hầu hết các trò
chơi cần tìm kiếm trên cây MiniMax đều sử dụng NegaScount, mà một lý do nữa là vì nó
khá giống với giải thuật Alpha-Beta nên việc chuyển đổi giữa hai giải thuật này là khá dễ
dàng.Tuy nhiên cũng phải nhấn mạnh rằng hiệu quả của bất cứ một giải thuật tìm kiếm nào
cũng phụ thuộc nhiều vào chất lượng của hàm lượng giá. Vi vậy muốn viết một chương
trình hiệu quả, cần phải có một hàm lượng giá thật tốt.
