TRÒ CHƠI ĐỐI KHÁNG VÀ CÁC PHƯƠNG PHÁP TÌM KIẾM

[baotrung]

I. Dạng trò chơi
Trong phần này, ta sẽ xem cách một chương trình máy tính có thể chơi
được các trò chơi đấu trí như các trò chơi cờ Vua, cờ Tướng, cờ vây, cờ
caro (go-moku), go, checker... như thế nào. Các trò này còn gọi là các
trò chơi đối kháng, diễn ra giữa hai đấu thủ. Nói chung, các trò chơi
đó đều có thể chuyển về một dạng bài toán tìm kiếm đặc biệt: tìm đường
đi đến các điểm cao nhất giữa hai đấu thủ. Đặc điểm của các trò chơi
trên như sau:
• Có hai đấu thủ, mỗi người chỉ đi một nước khi tới lượt.
• Các đấu thủ đều biết mọi thông tin về tình trạng trận đấu.
• Trận đấu không kéo dài vô tận, phải diễn ra hòa, hoặc một bên thắng và bên kia thua.
Thông thường ta hay gọi các trò chơi này là các loại cờ. Đôi khi ta gọi
đây là các trò chơi Minimax (dựa trên tên của thuật toán tìm kiếm cơ
bản áp dụng cho chúng). Hình 1.1 là ví dụ về một số trò chơi nói trên.
Các trò chơi như chơi bài, dò mìn, xúc sắc... không thuộc lớp trò chơi
này.

II. Cây trò chơi
Các trạng thái bàn cờ khác nhau (hay còn gọi là một thế cờ, tình huống
cờ) trong quá trình chơi có thể biểu diễn thành một cây tìm kiếm (được
gọi là cây trò chơi - hình 1.2) và ta sẽ tiến hành tìm kiếm trên cây để
tìm được nước đi tốt nhất. Cây trò chơi có các nút của cây là các tình
huống khác nhau của bàn cờ, các nhánh nối giữa các nút sẽ cho biết từ
một tình huống bàn cờ chuyển sang tình huống khác thông qua chỉ một
nước đi đơn nào đó. Dĩ nhiên, các nước đi này diễn ra theo cặp do hai
đấu thủ lần lượt tiến hành. Độ sâu của cây trò chơi ply là số tầng của
cây (chính là độ sâu d của cây). Thuật ngữ “nước đi” trong sách được
thống nhất chỉ bao gồm một lần đi của một đấu thủ hoặc một lần đi phản
ứng lại của đối thủ bên kia. Chú ý nó khác với thói quen dùng trong
thực tế một nước đi bao gồm lần đi của ta và một lần đi của đối thủ.
Nói cách khác, nước đi ở đây thực chất chỉ là "nửa nước" theo cách hiểu
của làng cờ.


III. Vét cạn
Dùng một thuật toán vét cạn để tìm kiếm trên cây trò chơi dường như là
một ý tưởng đơn giản. Ta chỉ cần chọn nhánh cây sẽ dẫn tới nước thắng
để đi quân là đảm bảo thắng lợi. Nếu đúng vậy, các loại cờ sẽ trở thành
các trò chơi buồn tẻ, sẽ chẳng còn đâu những bí quyết huyền ảo thần kì
và bàn cờ sẽ chẳng khác gì bàn... tính. Rất tiếc (hoặc rất may) rằng,
cách làm này lại không thể thực hiện nổi do cái gọi là bùng nổ tổ hợp.
Ví dụ, nếu từ một thế cờ, trung bình có khả năng đi được 16 nước đi
khác nhau (ta gọi đó là hệ số nhánh con tại mỗi nút là b = 16). Như
vậy, sau một tầng ta sẽ có 16 nút con, mỗi nút này lại có thể có 16 con
nữa. Tổng số nút con ở độ sâu thứ hai là 16x16 = b2. Cứ như vậy ở độ
sâu d sẽ có bd nút.
Nếu giả sử độ sâu của cây là 100 (hệ số nhánh 16 và độ sâu 100 đều là
những con số còn nhỏ hơn con số thường gặp trong trò chơi cờ), thì số
nhánh phải duyệt lên đến 16100 hay xấp xỉ 10120 - một con số lớn khủng
khiếp. Để hình dung số đó lớn thế nào, ta giả sử tất cả các nguyên tử
trong vũ trụ đều trở thành máy tính để tính nước đi với tốc độ một giây
tính được cỡ 1010 (10 tỷ) nước đi, và nếu chúng hoạt động cật lực từ
thời vụ nổ lớn đến nay (theo một số lý thuyết, thì thế giới này hình
thành sau một vụ nổ gọi là vụ nổ lớn bigbang, trước đây cỡ 15 tỷ năm)
thì đến bây giờ mới có thể đi được nước đi đầu tiên.

Vì số các khả năng tăng quá nhanh, chỉ có một số ít những vấn đề đơn
giản là thích hợp với kiểu tìm kiếm vét hết mọi khả năng này (kiểu tìm
kiếm vét cạn đòi hỏi phải kiểm tra tất cả các đỉnh). Do đó, các phương
pháp tìm kiếm khác đã ra đời và phát triển. Ngược lại, nếu có một
phương pháp luôn luôn chính xác nhằm đánh giá một thế cờ này là tốt hay
kém so với thế kia, thì trò chơi trở thành đơn giản bằng cách chọn nước
đi dẫn tới thế cờ tốt nhất. Do đó sẽ không cần phải tìm kiếm gì nữa.
Rất tiếc, các thủ tục như vậy không hề có. Ta cần có chiến lược tìm
kiếm trong trò chơi.



IV. Chiến lược tìm kiếm trong trò chơi
Một chiến lược thường được cả người lẫn máy dùng là phân tích thế cờ
chỉ sau một số nước đi nào đó của cả hai bên. Sau khi "nhìn xa" xem bàn
cờ có những khả năng biến đổi như thế nào sau một số nước, ta sẽ đánh
giá độ xấu tốt của các thế cờ nhận được. Tiếp theo, ta sẽ chọn nước đi
sẽ dẫn tới một thế cờ tốt nhất trong số đó có cân nhắc đến cách đi của
cả hai bên. Với máy, thế cờ này được đánh giá là tốt hơn thế cờ kia nhờ
so sánh điểm của thế đó do bộ lượng giá trả lại. Chúng ta chỉ có khả
năng xét trước một số hữu hạn các nước (ví dụ đại kiện tướng chơi cờ
vua có thể xét trước 8-10 nước đi, người thường chỉ 2-4 nước đi). Rõ
ràng là nếu xét càng sâu thì chơi càng giỏi. Nhưng không thể thực hiện
điều này với độ sâu quá lớn được do số nút ở độ sâu đó có thể trở nên
lớn khủng khiếp và không đủ thời gian để phân tích. Nếu dừng ở một độ
sâu hợp lý thì bộ phân tích có thể hoàn thành việc tính toán trong một
thời gian hạn định.

V. Thủ tục Minimax[1]
Giả sử chúng ta có một bộ phân tích thế cờ có thể áp dụng tất cả các
luật, các phương pháp đánh cờ khác nhau vào từng thế cờ và chuyển đổi
chúng thành một con số đại diện (cho điểm thế cờ). Mặt khác, ta giả sử
con số đó là dương khi áp dụng cho thế cờ của một đấu thủ (được gọi là
người chơi cực đại - maximizer), và là âm khi áp dụng cho đấu thủ bên
kia (được gọi là người chơi cực tiểu - minimizer). Quá trình tính toán
cho điểm thế cờ được gọi là lượng giá tĩnh (static evaluation). Hàm
thực hiện việc tính toán được gọi là một bộ lượng giá tĩnh, và giá trị
nhận được gọi là điểm lượng giá tĩnh. Cả hai đấu thủ đều cố gắng đi như
thế nào đó để đạt được điểm tuyệt đối lớn nhất. Người chơi cực đại sẽ
tìm những nước đi dẫn đến điểm của mình trở nên lớn hơn (hay cao nhất
có thể được) hay điểm của đối thủ bớt âm hơn (nhỏ hơn về giá trị tuyệt
đối). Còn đấu thủ của anh ta, người chơi cực tiểu, lại ra sức phản
kháng lại, để dẫn tới điểm âm của anh ta âm hơn hay điểm dương của đối
thủ nhỏ đi (hình 1.4).
Người chơi cực đại hi vọng chọn nước đi bên phải để đạt được điểm 8.
Thế nhưng nếu đi như vậy thì khi đến lượt đi của người chơi cực tiểu,
anh ta sẽ cố gắng không cho người chơi cực đại đạt được điểm này bằng
cách chọn nước đi nhánh bên trái và như vậy, người chơi cực đại chỉ
được có 1 điểm thay vì 8. Ngược lại, nếu người chơi cực đại chọn nước
đi bên trái, thì trong tình huống xấu nhất anh ta vẫn còn được 2 điểm,
lớn hơn là chọn nước đi bên phải. Nói chung, người chơi cực đại sẽ phải
tìm cách nhận ra các nước đi của đối phương tiếp theo làm cho điểm giảm
xuống. Và tương tự như vậy, người chơi cực tiểu phải nhận biết được
nước đi của người chơi cực đại cố gắng làm tăng điểm lên. Thủ tục tìm
nước đi tốt nhất trên cây trò chơi như trên được gọi là thủ tục Minimax
do điểm ở mỗi nút có thể là điểm cực đại hoặc có thể là điểm cực tiểu
và có thuật toán như sau:

[baotrung]

Thuật toán Minimax • Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm), tính giá trị tĩnh của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả • Nếu như mức đang xét là của người chơi cực tiểu, áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất • Nếu như mức đang xét là của người chơi cực đại, áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả lớn nhất. Viết chương trình cho thuật toán Minimax Bây giờ, ta thử dựa vào phát biểu trên để viết chương trình cho thuật toán này bằng ngôn ngữ tựa Pascal. Đây là một hàm có tên là Minimax và sẽ là loại đệ qui. Trước hết, để hàm này biết đã đạt đến giới hạn tìm kiếm chưa, ta cần cung cấp cho nó một tham số về độ sâu tìm kiếm depth (để biết phải tìm đến đâu), đồng thời ta cũng phải cho biết thế cờ hiện tại pos để nó từ đó nó biết cách tính tiếp. Giá trị trả về của hàm chính là điểm của thế cờ (bàn cờ) pos. Vậy hàm sẽ có khai báo dạng: function Minimax (pos, depth): integer; Mỗi khi Minimax được gọi, nó sẽ càng gần đến giới hạn tìm kiếm, do đó ta sẽ gọi hàm này với độ sâu bằng độ sâu cũ trừ đi một. Đạt đến độ sâu giới hạn chính là khi depth = 0. Khi đạt độ sâu này ta sẽ gọi hàm lượng giá Eval để đánh giá chất lượng của thế cờ pos hiện tại (thực hiện điều một của thuật toán). Như vậy bước đầu hàm này có dạng sau: function Minimax (pos, depth): integer; begin if depth = 0 then { Đã đạt đến giới hạn } Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin ... Minimax (pos, depth - 1); { Gọi đệ qui với độ sâu giản dần} ... end; end; Ở trên, Minimax được gọi với độ sâu giảm đi một. Đó là độ sâu của các thế cờ là con. Các thế cờ con pos'' đó là các thế cờ được tạo ra từ pos bằng cách đi một nước đi hợp lệ m nào đó. Do đó ta phải có các lệnh thực hiện đi quân để đến các thế cờ mới. Để biết từ thế cờ pos có thể đi được những nước nào, ta dùng một thủ tục Gen có tham số là thế cờ cha pos. Thủ tục này sẽ cất các thế cờ con pos'' đó vào bộ nhớ (dạng danh sách). Việc tiếp theo là ta lấy từng thế cờ đó ra và áp dụng tiếp thủ tục Minimax cho nó để tính điểm value của nó. Vậy hàm Minimax bây giờ có dạng: function Minimax (pos, depth): integer; begin if depth = 0 then Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin pos := Tính thế cờ mới nhờ đi m; value := Minimax (pos, depth-1); { Tính điểm của pos } ... end; ... end; end; Theo phát biểu của thuật toán, ta thấy các điều 2 và 3 chỉ khác nhau ở cách chọn kết quả tốt nhất best phụ thuộc vào người chơi đang là người chơi cực đại hay cực tiểu. Cuối cùng thuật toán sẽ trả về điểm tốt nhất đạt được. Vậy hàm này được phát triển tiếp thành: function Minimax (pos, depth): integer; begin if depth = 0 then Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin pos := Tính thế cờ mới nhờ đi m; value := Minimax (pos, depth-1); { Tính điểm của pos } { Chọn điểm tốt nhất tuỳ thuộc theo người chơi } if người chơi là người cực đại then begin if best < value then best := value; end else begin if best > value then best := value; end end; Minimax := best; { Trả về giá trị tốt nhất } end; end; Thông thường để cho tiện (và cũng rất gần sự thực) ta coi cả hai người chơi (hai bên) có cùng cách đánh giá về một thế cờ. Có điều thế cờ này là tốt với một người thì phải được đánh giá là tồi với người kia và ngược lại. Trong máy tính cách thể hiện tốt nhất là ta cho điểm một thế cờ có thêm dấu âm dương: dấu âm dành cho người chơi cực đại và dấu âm cho người chơi cực tiểu. Với người chơi cực đại sẽ mong muốn điểm này càng dương càng tốt, còn người chơi cực tiểu lại mong muốn điểm này càng âm càng tốt. Do đó để dễ xử lí ta sẽ tuỳ theo mức người chơi mà đổi dấu giá trị đánh giá thế cờ pos. Chú ý rằng, thay đổi độ sâu là chuyển sang đối phương nên phải đổi dấu. Chương trình thực hiện đổi dấu như sau: value := -Minimax (pos, depth-1); { Tính điểm của pos } Cũng do dùng cùng hàm lượng giá nên khi đến lượt người chơi cực đại và cực tiểu có cùng cái nhìn như nhau về một thế cờ. Điều này dẫn đến có thể dùng cùng cách chọn nước đi tốt nhất cho họ (gộp được điều 2 và 3 lại với nhau được). Giá trị best cần được khởi đầu rất nhỏ để đảm bảo không vượt mọi giá trị value, tốt nhất là giá trị -vô cùng: function Minimax (pos, depth): integer; begin if depth = 0 then Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin best := -INFINITY; Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin pos := Tính thế cờ mới nhờ đi m; value := -Minimax (pos, depth - 1); if value > best then best := value; end; Minimax := best; end; end; Thông thường, bàn cờ được biểu diễn bằng các biến toàn cục. Do đó thay cho truyền tham số là một bàn cờ mới pos vào thủ thục Minimax thì người ta biến đổi luôn biến toàn cục này nhờ thực hiện nước đi "thử" (nước đi dẫn đến bàn cờ mới pos). Sau khi Minimax thực hiện việc tính toán dựa vào bàn cờ lưu ở biến toàn cục thì thuật toán sẽ dùng một số thủ tục để loại bỏ nước đi này. Như vậy Minimax bỏ các tham số pos như sau: function Minimax (depth): integer; begin if depth = 0 then Minimax := Eval { Tính thế cờ pos trong biến toàn cục } else begin best := -INFINITY; Gen; { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin thực hiện nước đi m; value := -Minimax (depth - 1); bỏ thực hiện nước đi m; if value > best then best := value; end; Minimax := best; end; end; Thuật toán Minimax với việc đảo dấu mỗi khi thay đổi độ sâu như trên đôi khi được gọi là thuật toán Negamax. Đánh giá thuật toán Minimax Nếu hệ số nhánh trung bình của cây là b và ta thực hiện tìm kiếm đến độ sâu d thì số nút phải lượng giá ở đáy cây như ta đã biết là bd. Đây chính là số đo độ phức tạp của thuật toán. Nếu b = 40, d = 4 (các con số thường gặp trong trò chơi cờ) thì số nút phải lượng giá là 404 = 2560000 (trên 2 triệu rưỡi nút). Còn với b = 40, d = 5 thì số nút phải lượng giá sẽ tăng 40 lần nữa thành 405 = 102400000 (trên 102 triệu nút). Lưu ý: toàn bộ ý tưởng của thuật toán này là dựa trên việc chuyển đổi mỗi thế cờ thành một con số để đánh giá. Rất tiếc là các con số này thường không tốt và không đủ để đánh giá hết mọi điều. Mặt khác, thuật toán này có thể rất tốn kém (chạy chậm) do việc sinh các nước đi và lượng giá rất tốn thời gian tính toán, do vậy độ sâu của cây trò chơi cũng bị hạn chế nhiều. Ta cần có thêm những cải tiến để cải thiện tình hình.