alpha-beta thuật toán cắt nhánh để viết chương trình chơi cờ

[baotrung]

Thuật giải Alpha-Beta




Xét một trò chơi trong đó hai người thay phiên nhau đi nước của mình
như cờ vua, cờ tướng, carô,... Trò chơi có một trạng thái bắt đầu và
mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới.
Trò chơi sẽ kết thúc theo một quy định nào đó, theo đó thì cuộc chơi sẽ
dẫn đến một trạng thái phản ánh có một người thắng cuộc hoặc một trạng
thái mà cả hai đấu thủ không thể phát triển được nước đi của mình, ta
gọi nó là trạng thái hòa cờ. Ta tìm cách phân tích xem từ một trạng
thái nào đó sẽ dẫn đến đấu thủ nào sẽ thắng với điều kiện cả hai đấu
thủ đều có trình độ như nhau.

Một trò chơi như vậy có thể được biểu diễn bởi một cây, gọi là cây trò
chơi. Mỗi một nút của cây biểu diễn cho một trạng thái. Nút gốc biểu
diễn cho trạng thái bắt đầu của cuộc chơi. Mỗi nút lá biểu diễn cho một
trạng thái kết thúc của trò chơi (trạng thái thắng thua hoặc hòa). Nếu
trạng thái x được biểu diễn bởi nút n thì các con của n biểu diễn cho
tất cả các trạng thái kết quả của các nước đi có thể xuất phát từ trạng
thái x.

Ví dụ 3-5: Xét trò chơi carô có 9 ô. Hai người thay phiên nhau đi X
hoặc O. Người nào đi được 3 ô thẳng hàng (ngang, dọc, xiên) thì thắng
cuộc. Nếu đã hết ô đi mà chưa phân thắng bại thì hai đấu thủ hòa nhau.
Một phần của trò chơi này được biểu diễn bởi cây sau:




Trong cây trò chơi trên, các nút lá được tô nền và viền khung đôi để dễ
phân biệt với các nút khác. Ta có thể gán cho mỗi nút lá một giá trị để
phản ánh trạng thái thắng thua hay hòa của các đấu thủ. Chẳng hạn ta
gán cho nút lá các giá trị như sau:

· 1 nếu tại đó người đi X đã thắng,

· -1 nếu tại đó người đi X đã thua và

· 0 nếu hai đấu thủ đã hòa nhau.

Như vậy từ một trạng thái bất kỳ, đến lượt mình, người đi X sẽ chọn cho
mình một nước đi sao cho dẫn đến trạng thái có giá trị lớn nhất (trong
trường hợp này là 1). Ta nói X chọn nước đi MAX, nút mà từ đó X chọn
nước đi của mình được gọi là nút MAX. Người đi O đến lượt mình sẽ chọn
một nước đi sao cho dẫn đến trạng thái có giá trị nhỏ nhất (trong
trường hợp này là -1, khi đó X sẽ thua và do đó O sẽ thắng). Ta nói O
chọn nước đi MIN, nút mà từ đó O chọn nước đi của mình được gọi là nút
MIN. Do hai đấu thủ luân phiên nhau đi nước của mình nên các mức trên
cây trò chơi cũng luânphiên nhau là MAX và MIN. Cây trò chơi vì thế còn
có tên là cây MIN-MAX. Ta có thể đưa ra một quy tắc định trị cho các
nút trên cây để phản ánh tình trạng thắng thua hay hòa và khả năng
thắng cuộc của hai đấu thủ.

Nếu một nút là nút lá thì trị của nó là giá trị đã được gán cho nút đó.
Ngược lại, nếu nút là nút MAX thì trị của nó bằng giá trị lớn nhất của
tất cả các trị của các con của nó. Nếu nút là nút MIN thì trị của nó là
giá trị nhỏ nhất của tất cả các trị của các con của nó.

Quy tắc định trị này cũng gần giống với quy tắc định trị cho cây biểu
thức số học, điểm khác biệt ở đây là các toán tử là các hàm lấy max
hoặc min và mỗi nút có thể có nhiều con. Do vậy ta có thể dùng kỹ thuật
quay lui để định trị cho các nút của cây trò chơi.

Để cài đặt ta có một số giả thiết sau:

· Ta có một hàm Payoff nhận vào một nút lá và cho ta giá trị của nút lá đó.

· Các hằng ∞ và -∞ tương ứng là các trị Payoff lớn nhất và nhỏ nhất.

· Khai báo kiểu ModeType = (MIN, MAX) để xác định định trị cho nút là MIN hay MAX.

· Một kiểu NodeType được khai báo một cách thích hợp để biểu diễn cho một nút trên cây phản ánh một trạng thái của cuộc chơi.

· Ta có một hàm is_leaf để xác định xem một nút có phải là nút lá hay không?

· Hàm max và min tương ứng lấy giá trị lớn nhất và giá trị nhỏ nhất của hai giá trị.

Giải thuật vét cạn định trị cây trò chơi
Hàm Search nhận vào một nút n và kiểu mode của nút đó (MIN hay MAX) trả về giá trị của nút.

Nếu nút n là nút lá thì trả về giá trị đã được gán cho nút lá. Ngược
lại ta cho n một giá trị tạm value là -∞ hoặc ∞ tùy thuộc n là nút MAX
hay MIN và xét con của n. Sau khi một con của n có giá trị V thì đặt
lại value = max(value,V) nếu n là nút MAX và value = min(value,V) nếu n
là nút MIN. Khi tất cả các con của n đã được xét thì giá trị tạm value
của n trở thành giá trị của nó.

Code:


 function Search(n : NodeType; mode: ModeType): real;
var C : NodeType ; { C là một nút con của nút n}
Value : real;
{Lúc đầu ta cho value một giá trị tạm, sau khi đã xét hết tất cả các con của nút n
thì value là giá trị của nút n }
begin
    if is_leaf(n) then return ( Payoff(n) )
    else begin
          {Khởi tạo giá trị tạm cho n }
          if mode = MAX then value := -∞ else value := ∞;

          {Xét tất cả các con của n, mỗi lần xác định được giá trị của một nút con,
          ta phải đặt lại giá trị tạm value. Khi đã xét hết tất cả các con thì value
          là giá trị của n}

          for với mỗi con C của n do
              if mode = MAX then
                    Value := max(Value, Search(C, MIN) )
              else Value := min(Value, Search(C, MAX) );
          return (value);
    end;
end;



Kỹ thuật cắt tỉa Alpha-Beta (Alpha-Beta Pruning)

Trong giải thuật vét cạn ở trên, ta thấy để định trị cho một nút nào
đó, ta phải định trị cho tất cả các nút con cháu của nó, và muốn định
trị cho nút gốc ta phải định trị cho tất cả các nút trên cây. Số lượng
các nút trên cây trò chơi tuy hữu hạn nhưng không phải là ít. Chẳng hạn
trong cây trò chơi ca rô nói trên, nếu ta có bàn cờ bao gồm n ô thì có
thể có tới n! nút trên cây (trong trường hợp trên là 9!). Đối với các
loại cờ khác như cờ vua chẳng hạn, thì số lượng các nút còn lớn hơn
nhiều. Ta gọi là một sự bùng nổ tổ hợp các nút.

Chúng ta cố gắng tìm một cách sao cho khi định trị một nút thì không
nhất thiết phải định trị cho tất cả các nút con cháu của nó. Trước hết
ta có nhận xét như sau:

Nếu P là một nút MAX và ta đang xét một nút con Q của nó (dĩ nhiên Q là
nút MIN). Giả sử Vp là một giá trị tạm của P, Vq là một giá trị tạm của
Q và nếu ta có Vp ≥ Vq thì ta không cần xét các con chưa xét của Q nữa.
Vì nếu có xét thì giá trị của Q cũng sẽ nhỏ hơn hoặc bằng Vq và do đó
không ảnh hưởng gì đến Vp. Tương tự nếu P là nút MIN (tất nhiên Q là
nút MAX) và Vp ≤ Vq thì ta cũng không cần xét đến các con chưa xét của
Q nữa. Việc không xét tiếp các con chưa được xét của nút Q gọi là việc
cắt tỉa Alpha-Beta các con của nút Q.

Trên cơ sở nhận xét đó, ta nêu ra quy tắc định trị cho một nút không phải là nút lá trên cây như sau:

1. Khởi đầu nút MAX có giá trị tạm là -∞ và nút MIN có giá trị tạm là ∞.

2. Nếu tất cả các nút con của một nút đã được xét hoặc bị cắt tỉa thì giá trị tạm của nút đó trở thành giá trị của nó.

3. Nếu một nút MAX n có giá trị tạm là V1 và một nút con của nó có giá
trị là V2 thì đặt giá trị tạm mới của n là max (V1,V2). Nếu n là nút
MIN thì đặt giá trị tạm mới của n là min (V1,V2).

4. Vận dụng quy tắc cắt tỉa Alpha-Beta nói trên để hạn chế số lượng nút phải xét.

Code:


 function cat_tia(Q: NodeType; mode: ModeType; Vp: real): real;
var C : NodeType ; { C là một nút con của nút Q}
    Vq : real;
{Vq là giá trị tạm của Q, sau khi tất cả các con của nút Q đã xét hoặc bị cắt tỉa thì Vq là giá trị của nút Q}
begin
    if is_leaf(Q) then return ( Payoff(Q) )
    else begin
          { Khởi tạo giá trị tạm cho Q }
          if mode = MAX then Vq := -∞ else Vq := ∞;
          {Xét các con của Q, mỗi lần xác định được giá trị của một nút con của Q, ta phải đặt lại giá trị tạm Vq và so sánh với Vp để có thể cắt tỉa hay không}
              Xét C là con trái nhất của Q;
              while C là con của Q DO
                    if mode = MAX then begin
                        Vq:= max(Vq, Cat_tia(C, MIN, Vq));
                        if Vp ≤ Vq then return(Vq);
          end
              else begin Vq := min(Vq, Cat_tia(C, MAX, Vq));
                    if Vp ≥ Vq then return(Vq);
                    end;
              return (Vq);
    end;
end;


Ví dụ 3-6: Vận dụng quy tắc trên để định trị cho nút A trong cây trò chơi trong ví dụ 3-5.

A là nút MAX, lúc đầu nó có giá trị tạm là -∞, xét B là con của A, B là
nút lá nên giá trị của nó là giá trị đã được gán 1, giá trị tạm của A
bây giờ là max (-∞,1) = 1. Xét con C của A, C là nút MIN, giá trị tạm
lúc đầu của C là ∞. Xét con E của C, E là nút MAX, giá trị tạm của E là
-∞. Xét con I của E, I là nút lá nên giá trị của nó là 0. Quay lui lại
E, giá trị tạm của E bây giờ là max (-∞,0) = 0. Vì E chỉ có một con là
I đã xét nên giá trị tạm 0 trở thành giá trị của E. Quay lui lại C, giá
trị tạm mới của C là min (∞,0) = 0. A là nút MAX có giá trị tạm là 1, C
là con của A, có giá trị tạm là 0, 1>0 nên ta không cần xét con F
của C nữa. Nút C có hai con là E và F, trong đó E đã được xét, F đã bị
cắt, vậy giá trị tạm 0 của C trở thành giá trị của nó. Sau khi có giá
trị của C, ta phải đặt lại giá trị tạm của A, nhưng giá trị tạm này
không thay đổi vì max (1,0) = 1. Tiếp tục xét nút D, D là nút MIN nên
giá trị tạm là ∞, xét nút con G của D, G là nút MAX nên giá trị tạm của
nó là -∞, xét nút con J của G. Vì J là nút lá nên có giá trị 0. Quay
lui lại G, giá trị tạm của G bây giờ là max (-∞,0) = 0 và giá trị tạm
này trở thành giá trị của G vì G chỉ có một con J đã xét. Quay lui về
D, giá trị tạm của D bây giờ là min (∞,0) = 0. Giá trị tạm này của D
nhỏ hơn giá trị tạm của nút A MAX là cha của nó nên ta cắt tỉa con H
chưa được xét của D và lúc này D có giá trị là 0. Quay lui về A, giá
trị tạm của nó vẫn không thay đổi, nhưng lúc này cả 3 con của A đều đã
được xét nên giá trị tạm 1 trở thành giá trị của A. Kết quả được minh
họa trong hình sau: