- Tham gia
- 20/4/2008
- Bài viết
- 9.433
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 = b^2. Cứ như vậy ở độ sâu d sẽ có b^d 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 16^100 hay xấp xỉ 10^120 - 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ỡ 10^10 (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).
Ví dụ một phần cây trò chơi trong hình 1.5.
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:
-------------------------------------------------------------------------------------------
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à 40^4 = 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 40^5 = 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.
VI. 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.
Viết chương trình cho thuật toán AlphaBeta
Từ phát biểu trên ta sẽ xây dựng hàm AlphaBeta bằng ngôn ngữ tựa Pascal. Hàm này sẽ có dạng khai báo như dưới, trong đó depth là độ sâu tìm kiếm, INFINITY là giá trị vô cùng, thuật toán tính toán dựa trên thế cờ hiện tại pos là các biến toàn cục:
function AlphaBeta(alpha, beta, depth): integer; begin if depth = 0 then AlphaBeta := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY; Gen; { Sinh ra mọi nước đi từ vị trí pos } while (còn lấy được một nước đi m) and (best < beta) do begin if best > alpha then alpha := best; thực hiện nước đi m; value := -AlphaBeta(-beta, -alpha, depth-1); bỏ thực hiện nước đi m; if value > best then best := value; end; AlphaBeta := best; end; end;
Lời gọi thủ tục AlphaBeta đầu tiên với độ sâu tìm kiếm 4 và thế cờ hiện tại pos có dạng như sau:
AlphaBeta(-INFINITY, +INFINITY, 4);
Cũng tương tự như thuật toán Minimax ta đã gộp hai mục 2 và 3 làm một nhờ việc đổi dấu thích hợp. So với thuật toán Minimax thì trong thuật toán AlphaBeta đã đưa thêm hai biến alpha, beta làm hai mức ngưỡng. Ta thấy cứ mỗi khi best >= beta thì thuật toán không thực hiện tiếp vòng lặp, có nghĩa là nó không chịu mở rộng tiếp những nhánh còn lại nữa. Các nhánh đó đã bị cắt bỏ - và do đó ta sẽ tiết kiệm được thời gian. Việc cắt bỏ 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 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 hoàn toàn không chống được bùng nổ tổ hợp mà chỉ làm giảm tốc độ bùng nổ. Tuy trong thực tế số nút phải xét (lượng giá) thường nhiều hơn trong điều kiện lí tưởng nhưng nó vẫn đủ để tiết kiệm khá nhiều thời gian. Trong cùng một khoảng thời gian, thuật toán AlphaBeta có thể tìm đến độ sâu gấp hai lần độ sâu tìm kiếm bằng Minimax. Hình 1.8 là đồ thị so sánh giữa hai thuật toán này.
Ví dụ: Ta sẽ xem xét thuật toán AlphaBeta hoạt động như thế nào đối với cây trò chơi như trong hình 1.9.
Cây này có độ sâu bằng 3 và hệ số phân nhánh bằng 3. Các thứ tự kết luận (các con số bên trái) được đưa ra như sau:
[1-2] Tìm kiếm đi xuống dưới theo nhánh trái cho đến lá. Ở đây giá trị tĩnh thu được là 8. Giá trị đầu tiên này do người chơi cực đại được phép chọn trong ba giá trị ở nhánh này đã đảm bảo rằng là kết quả thu được sẽ ít nhất là bằng 8. Điều lưu ý này được bước 2 ghi lại.
[3-5] Để chắc chắn không còn có điểm nào cao hơn 8, người chơi cực đại phải xét cả hai thế cờ còn lại và thu được các giá trị 7 và 2. Do đó đến đây đã kết luận chính xác điểm cao nhất có thể đạt được ở cây con là đúng bằng 8.
[6]. Leo lên một tầng cây. Đây là các nước đi của người chơi cực tiểu. Ta không hi vọng anh ta cho người chơi cực đại được nhiều điểm nên có thể tạm kết luận ở mức này là sẽ đạt được nhiều nhất là 8 điểm.
[7-8]. Để xem người chơi cực tiểu còn lựa chọn nào tốt hơn (và tồi tệ hơn cho người chơi cực đại) ta phải xem xét cả hai nước đi còn lại. Nước đi còn lại đầu tiên dẫn đến giá trị lượng giá tĩnh là 9 - một giá trị lớn hơn 8. Như vậy nhánh giữa là tồi tệ hơn cho người chơi cực tiểu. Đến đây việc cắt bỏ được thực hiện - đừng hòng người chơi cực đại với tới được điểm đó khi đã có sẵn lựa chọn thấp hơn cho anh ta (là 8). Điều này cũng dẫn đến không cần thiết phải xét hai nút còn lại - đằng nào nhánh giữa cũng đủ tồi tệ rồi và người chơi cực tiểu sẽ không chọn nó để đi.
[9-14]. Người chơi cực tiểu cần phải khảo sát tiếp lựa chọn cuối cùng. Cách làm tương tự như phần trên. Ở đây phải lượng giá cả ba nút cây và kết luận cuối cùng được đưa ra là người chơi cực đại đi giỏi lắm thì chỉ đạt được 4 điểm.
[15]. Như vậy nhờ việc khảo sát nhánh cây bên phải người chơi cực tiểu thấy rằng nếu chọn đi theo nhánh này thì người chơi cực đại chỉ được có 4 điểm thay cho 8.
[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.
VII. 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 sẽ trở lại phần này trong một chương riêng.
Tổng kết chương 1
Chương này trình bầy những kiến thức chung về trò chơi cờ, các định nghĩa và thế nào là cây trò chơi. Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường. Phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi. Đó là thuật toán Minimax và cải tiến của nó là AlphaBeta. Tuy cả hai thuật toán đều không tránh được bùng nổ tổ hợp nhưng AlphaBeta làm chậm bùng nổ tổ hợp hơn nên được dùng nhiều trong các trò chơi cờ.
----------------------------------------------------------------------------------------------
Bài đọc
SƠ LƯỢC VỀ LỊCH SỬ CÁC CHƯƠNG TRÌNH CHƠI CỜ
Vào năm 1950, Alan Turing - một nhà nghiên cứu người Anh đi tiên phong trong lĩnh vực máy tính số, đã viết chương trình chơi cờ đầu tiên. Vào lúc đó, Turing phải viết và chạy chương trình của ông bằng... bút chì và giấy. Chương trình đó, cũng như chủ nhân của nó, chơi cờ rất tồi, nhưng đạt được mục đích: cho thấy máy tính có thể chơi được cờ. Cũng vào năm đó, Claude Shannon đã vạch ra một chiến lược cho máy tính chơi cờ tốt. Nhưng vào những năm 1950 tốc độ máy tính rất chậm nên không ai dám tiên đoán liệu máy tính có thể thắng con người được không, dù trong các trò chơi đơn giản như trò Checker.
Năm 1958, một chương trình chơi cờ đã lần đầu tiên hạ được đối phương là con người. Người thua là một cô thư kí của chính đội lập trình ra nó, cô chưa bao giờ chơi cờ trước đó và được dậy chơi cờ chỉ một giờ trước cuộc đấu. Đối với ngày nay chiến công này thật nhỏ nhoi, nhưng nó cho thấy tri thức có thể được đưa vào trong một chương trình chơi cờ. Lượng tri thức này được đo chính xác bằng một giờ học chơi.
Sau chiến thắng đó, một số người trong nhóm lập trình cờ đầu tiên đã tiên đoán rằng vào những năm 60 sẽ có chương trình chơi cờ được liệt vào hàng ngũ kiện tướng thế giới. Vào những năm cuối của thập kỷ 60, Spassky đã trở thành kiện tướng cờ thế giới và các chương trình chơi cờ đã chiếm được những thứ hạng cao trong hàng ngũ những người chơi cao cấp. Nhưng nhiều người cho rằng máy tính sẽ không bao giờ có thể giải quyết được những nhiệm vụ thông minh, không thể đạt được chức Vô địch cờ thế giới.
Lời tiên đoán này được nhắc lại một lần nữa vào những năm 70, liên quan đến một cuộc đánh cược giữa David Levy, một kiện tướng quốc tế người Anh (theo phân loại của Liên đoàn cờ quốc tế các đẳng cấp cao bao gồm: Kiện tướng quốc tế, Đại kiện tướng và Vô địch thế giới) và John McCarthy, một nhà nghiên cứu trong lĩnh vực trí tuệ nhân tạo. Lời thách đấu được đưa ra vào năm 1978. Trận đấu đã được diễn ra và chương trình cờ tốt nhất thời đó, CHESS 4.7 đã bị Levy hạ trong trận đấu có năm ván tại Toronto với thành tích ba ván người thắng, một hoà và một máy thắng. Levy không chỉ chiến thắng mà còn đút túi số tiền đánh cược 1000 bảng.
Nếu như mục đích của cuộc đánh cược là làm cho những nhà nghiên cứu phải nghĩ kĩ trước khi tiên đoán đến ngày thắng lợi, thì lần đánh cược này cho thấy: mặc dù tiên đoán sai trong những năm 1958-1968 và 1968-1978, các chuyên gia chương trình cờ lại tiếp tục tiên đoán tiếp rằng máy tính sẽ đạt đến vô địch cờ thế giới trong thập kỉ tiếp theo.
Nhưng một lần nữa, vào năm 1988, Vô địch cờ thế giới vẫn là con người.
Trong năm tiếp theo, Deep Thought, một chương trình cờ mạnh nhất từ xưa đến nay đã chiến thắng một cách dễ dàng Kiện tướng Quốc tế Levy. Bộ não của Deep Thought có 250 chip và hai bộ xử lí trong một bảng mạch đơn, nó có khả năng xét 750.000 thế cờ trong một giây và tìm trước được đến 10 nước. Cũng trong năm đó, nó là máy tính đầu tiên hạ được một Đại kiện tướng (Bent Larsen). Deep Thought đã trở thành một trong một trăm người chơi cờ mạnh nhất thế giới. Nhưng trong trận đấu diễn ra vào năm 1989 giữa nhà Vô địch thế giới Garry Kasparov và Deep Thought thì nó đã bị nhà vô địch đè bẹp.
Các lời tiên đoán lại đến như các lần trước. Đã ba lần các nhà nghiên cứu tiên đoán: 'trong thập kỉ tới'. Nhưng lần này họ lại sửa lại là: 'trong 3 năm tới'...
Trong năm 1993, Deep Thought đã hạ Judit Polgar - lúc đó là Đại kiện tướng trẻ nhất trong lịch sử và là người phụ nữ chơi hay nhất thế giới, trong trận đấu 2 ván.
Trong năm 1996, Deep Blue (tên mới của Deep Thought và lúc này nó thuộc hãng IBM) là một máy tính song song có 32 bộ xử lí với 256 mạch tích hợp cỡ lớn, khả năng xét từ 2 đến 400 triệu nước đi mỗi giây) đã thắng Gary Kasparov trong ván đầu tiên của trận đấu 6 ván, nhưng lại thua trong toàn trận (với tỉ số máy thắng 1, hoà 2 và thua 3).
Cuối cùng đích mà mọi người chờ đợi đã tới, nhưng sau 9 năm từ lời tiên đoán cuối và 39 năm từ lúc có chương trình chơi cờ đầu tiên, Deep Blue đã chiến thắng nhà đương kim Vô địch thế giới Garry Kasparov vào tháng 5/1997 trong một cuộc chiến dài đầy khó khăn, với tỷ số sát nút 2 thắng, 1 thua và 3 hoà.
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 = b^2. Cứ như vậy ở độ sâu d sẽ có b^d 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 16^100 hay xấp xỉ 10^120 - 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ỡ 10^10 (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).
Ví dụ một phần cây trò chơi trong hình 1.5.
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:
-------------------------------------------------------------------------------------------
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à 40^4 = 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 40^5 = 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.
VI. 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.
Viết chương trình cho thuật toán AlphaBeta
Từ phát biểu trên ta sẽ xây dựng hàm AlphaBeta bằng ngôn ngữ tựa Pascal. Hàm này sẽ có dạng khai báo như dưới, trong đó depth là độ sâu tìm kiếm, INFINITY là giá trị vô cùng, thuật toán tính toán dựa trên thế cờ hiện tại pos là các biến toàn cục:
function AlphaBeta(alpha, beta, depth): integer; begin if depth = 0 then AlphaBeta := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY; Gen; { Sinh ra mọi nước đi từ vị trí pos } while (còn lấy được một nước đi m) and (best < beta) do begin if best > alpha then alpha := best; thực hiện nước đi m; value := -AlphaBeta(-beta, -alpha, depth-1); bỏ thực hiện nước đi m; if value > best then best := value; end; AlphaBeta := best; end; end;
Lời gọi thủ tục AlphaBeta đầu tiên với độ sâu tìm kiếm 4 và thế cờ hiện tại pos có dạng như sau:
AlphaBeta(-INFINITY, +INFINITY, 4);
Cũng tương tự như thuật toán Minimax ta đã gộp hai mục 2 và 3 làm một nhờ việc đổi dấu thích hợp. So với thuật toán Minimax thì trong thuật toán AlphaBeta đã đưa thêm hai biến alpha, beta làm hai mức ngưỡng. Ta thấy cứ mỗi khi best >= beta thì thuật toán không thực hiện tiếp vòng lặp, có nghĩa là nó không chịu mở rộng tiếp những nhánh còn lại nữa. Các nhánh đó đã bị cắt bỏ - và do đó ta sẽ tiết kiệm được thời gian. Việc cắt bỏ 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 hoàn toàn không chống được bùng nổ tổ hợp mà chỉ làm giảm tốc độ bùng nổ. Tuy trong thực tế số nút phải xét (lượng giá) thường nhiều hơn trong điều kiện lí tưởng nhưng nó vẫn đủ để tiết kiệm khá nhiều thời gian. Trong cùng một khoảng thời gian, thuật toán AlphaBeta có thể tìm đến độ sâu gấp hai lần độ sâu tìm kiếm bằng Minimax. Hình 1.8 là đồ thị so sánh giữa hai thuật toán này.
Ví dụ: Ta sẽ xem xét thuật toán AlphaBeta hoạt động như thế nào đối với cây trò chơi như trong hình 1.9.
Cây này có độ sâu bằng 3 và hệ số phân nhánh bằng 3. Các thứ tự kết luận (các con số bên trái) được đưa ra như sau:
[1-2] Tìm kiếm đi xuống dưới theo nhánh trái cho đến lá. Ở đây giá trị tĩnh thu được là 8. Giá trị đầu tiên này do người chơi cực đại được phép chọn trong ba giá trị ở nhánh này đã đảm bảo rằng là kết quả thu được sẽ ít nhất là bằng 8. Điều lưu ý này được bước 2 ghi lại.
[3-5] Để chắc chắn không còn có điểm nào cao hơn 8, người chơi cực đại phải xét cả hai thế cờ còn lại và thu được các giá trị 7 và 2. Do đó đến đây đã kết luận chính xác điểm cao nhất có thể đạt được ở cây con là đúng bằng 8.
[6]. Leo lên một tầng cây. Đây là các nước đi của người chơi cực tiểu. Ta không hi vọng anh ta cho người chơi cực đại được nhiều điểm nên có thể tạm kết luận ở mức này là sẽ đạt được nhiều nhất là 8 điểm.
[7-8]. Để xem người chơi cực tiểu còn lựa chọn nào tốt hơn (và tồi tệ hơn cho người chơi cực đại) ta phải xem xét cả hai nước đi còn lại. Nước đi còn lại đầu tiên dẫn đến giá trị lượng giá tĩnh là 9 - một giá trị lớn hơn 8. Như vậy nhánh giữa là tồi tệ hơn cho người chơi cực tiểu. Đến đây việc cắt bỏ được thực hiện - đừng hòng người chơi cực đại với tới được điểm đó khi đã có sẵn lựa chọn thấp hơn cho anh ta (là 8). Điều này cũng dẫn đến không cần thiết phải xét hai nút còn lại - đằng nào nhánh giữa cũng đủ tồi tệ rồi và người chơi cực tiểu sẽ không chọn nó để đi.
[9-14]. Người chơi cực tiểu cần phải khảo sát tiếp lựa chọn cuối cùng. Cách làm tương tự như phần trên. Ở đây phải lượng giá cả ba nút cây và kết luận cuối cùng được đưa ra là người chơi cực đại đi giỏi lắm thì chỉ đạt được 4 điểm.
[15]. Như vậy nhờ việc khảo sát nhánh cây bên phải người chơi cực tiểu thấy rằng nếu chọn đi theo nhánh này thì người chơi cực đại chỉ được có 4 điểm thay cho 8.
[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.
VII. 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 sẽ trở lại phần này trong một chương riêng.
Tổng kết chương 1
Chương này trình bầy những kiến thức chung về trò chơi cờ, các định nghĩa và thế nào là cây trò chơi. Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường. Phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi. Đó là thuật toán Minimax và cải tiến của nó là AlphaBeta. Tuy cả hai thuật toán đều không tránh được bùng nổ tổ hợp nhưng AlphaBeta làm chậm bùng nổ tổ hợp hơn nên được dùng nhiều trong các trò chơi cờ.
----------------------------------------------------------------------------------------------
Bài đọc
SƠ LƯỢC VỀ LỊCH SỬ CÁC CHƯƠNG TRÌNH CHƠI CỜ
Vào năm 1950, Alan Turing - một nhà nghiên cứu người Anh đi tiên phong trong lĩnh vực máy tính số, đã viết chương trình chơi cờ đầu tiên. Vào lúc đó, Turing phải viết và chạy chương trình của ông bằng... bút chì và giấy. Chương trình đó, cũng như chủ nhân của nó, chơi cờ rất tồi, nhưng đạt được mục đích: cho thấy máy tính có thể chơi được cờ. Cũng vào năm đó, Claude Shannon đã vạch ra một chiến lược cho máy tính chơi cờ tốt. Nhưng vào những năm 1950 tốc độ máy tính rất chậm nên không ai dám tiên đoán liệu máy tính có thể thắng con người được không, dù trong các trò chơi đơn giản như trò Checker.
Năm 1958, một chương trình chơi cờ đã lần đầu tiên hạ được đối phương là con người. Người thua là một cô thư kí của chính đội lập trình ra nó, cô chưa bao giờ chơi cờ trước đó và được dậy chơi cờ chỉ một giờ trước cuộc đấu. Đối với ngày nay chiến công này thật nhỏ nhoi, nhưng nó cho thấy tri thức có thể được đưa vào trong một chương trình chơi cờ. Lượng tri thức này được đo chính xác bằng một giờ học chơi.
Sau chiến thắng đó, một số người trong nhóm lập trình cờ đầu tiên đã tiên đoán rằng vào những năm 60 sẽ có chương trình chơi cờ được liệt vào hàng ngũ kiện tướng thế giới. Vào những năm cuối của thập kỷ 60, Spassky đã trở thành kiện tướng cờ thế giới và các chương trình chơi cờ đã chiếm được những thứ hạng cao trong hàng ngũ những người chơi cao cấp. Nhưng nhiều người cho rằng máy tính sẽ không bao giờ có thể giải quyết được những nhiệm vụ thông minh, không thể đạt được chức Vô địch cờ thế giới.
Lời tiên đoán này được nhắc lại một lần nữa vào những năm 70, liên quan đến một cuộc đánh cược giữa David Levy, một kiện tướng quốc tế người Anh (theo phân loại của Liên đoàn cờ quốc tế các đẳng cấp cao bao gồm: Kiện tướng quốc tế, Đại kiện tướng và Vô địch thế giới) và John McCarthy, một nhà nghiên cứu trong lĩnh vực trí tuệ nhân tạo. Lời thách đấu được đưa ra vào năm 1978. Trận đấu đã được diễn ra và chương trình cờ tốt nhất thời đó, CHESS 4.7 đã bị Levy hạ trong trận đấu có năm ván tại Toronto với thành tích ba ván người thắng, một hoà và một máy thắng. Levy không chỉ chiến thắng mà còn đút túi số tiền đánh cược 1000 bảng.
Nếu như mục đích của cuộc đánh cược là làm cho những nhà nghiên cứu phải nghĩ kĩ trước khi tiên đoán đến ngày thắng lợi, thì lần đánh cược này cho thấy: mặc dù tiên đoán sai trong những năm 1958-1968 và 1968-1978, các chuyên gia chương trình cờ lại tiếp tục tiên đoán tiếp rằng máy tính sẽ đạt đến vô địch cờ thế giới trong thập kỉ tiếp theo.
Nhưng một lần nữa, vào năm 1988, Vô địch cờ thế giới vẫn là con người.
Trong năm tiếp theo, Deep Thought, một chương trình cờ mạnh nhất từ xưa đến nay đã chiến thắng một cách dễ dàng Kiện tướng Quốc tế Levy. Bộ não của Deep Thought có 250 chip và hai bộ xử lí trong một bảng mạch đơn, nó có khả năng xét 750.000 thế cờ trong một giây và tìm trước được đến 10 nước. Cũng trong năm đó, nó là máy tính đầu tiên hạ được một Đại kiện tướng (Bent Larsen). Deep Thought đã trở thành một trong một trăm người chơi cờ mạnh nhất thế giới. Nhưng trong trận đấu diễn ra vào năm 1989 giữa nhà Vô địch thế giới Garry Kasparov và Deep Thought thì nó đã bị nhà vô địch đè bẹp.
Các lời tiên đoán lại đến như các lần trước. Đã ba lần các nhà nghiên cứu tiên đoán: 'trong thập kỉ tới'. Nhưng lần này họ lại sửa lại là: 'trong 3 năm tới'...
Trong năm 1993, Deep Thought đã hạ Judit Polgar - lúc đó là Đại kiện tướng trẻ nhất trong lịch sử và là người phụ nữ chơi hay nhất thế giới, trong trận đấu 2 ván.
Trong năm 1996, Deep Blue (tên mới của Deep Thought và lúc này nó thuộc hãng IBM) là một máy tính song song có 32 bộ xử lí với 256 mạch tích hợp cỡ lớn, khả năng xét từ 2 đến 400 triệu nước đi mỗi giây) đã thắng Gary Kasparov trong ván đầu tiên của trận đấu 6 ván, nhưng lại thua trong toàn trận (với tỉ số máy thắng 1, hoà 2 và thua 3).
Cuối cùng đích mà mọi người chờ đợi đã tới, nhưng sau 9 năm từ lời tiên đoán cuối và 39 năm từ lúc có chương trình chơi cờ đầu tiên, Deep Blue đã chiến thắng nhà đương kim Vô địch thế giới Garry Kasparov vào tháng 5/1997 trong một cuộc chiến dài đầy khó khăn, với tỷ số sát nút 2 thắng, 1 thua và 3 hoà.
Tác giả: Phạm Hồng Nguyên
sưu tầm, tổng hợp và dịch từ Internet
sưu tầm, tổng hợp và dịch từ Internet
