SỬ DỤNG HEURISTIC TRONG CÁC TRÒ CHƠI

Thủ tục minimax

Xét các trò chơi hai đối thủ đối kháng, chẳng hạn trò chơi nim. Để chơi nim, một số token (vật biểu hiện như đồng xu, lá bài, mảnh gỗ, ...) được đặt trên bàn giữa hai đối thủ. Ở mỗi nước đi, người chơi phải chia đống token thành hai đống nhỏ có số lượng khác nhau. Ứng với một số token vừa phải, không gian trạng thái này có thể triển khai đến cùng. Hình sau biểu diễn không gian trạng thái của trò chơi có 7 token.

Hình 4.6 – Không gian trạng thái của trò chơi nim

Khi chơi các trò chơi có thể triển khai hết không gian trạng thái, khó khăn chủ yếu là phải tính toán phản ứng của đối thủ. Một cách xử lý đơn giản nhất là giả sử đối thủ của bạn cũng sử dụng kiến thức về không gian trạng thái giống như bạn và áp dụng kiến thức đó kiên định để thắng cuộc. Mặc dù giả thiết này có những hạn chế của nó nhưng nó cũng cho chúng ta một cơ sở hợp lý để dự đoán hành vi của đối thủ. Minimax sẽ tìm kiếm không gian của trò chơi này theo giả thiết đó.

Hai đối thủ trong một trò chơi được gọi là MIN và MAX. MAX đại diện cho đối thủ quyết giành thắng lợi hay cố gắng tối đa hóa ưu thế của mình. Ngược lại MIN là đối thủ cố gắng tối thiểu hóa điểm số của MAX. Ta giả thiết MIN cũng dùng cùng những thông tin như MAX.

Khi áp dụng thủ tục Minimax, chúng ta đánh dấu luân phiên từng mức trong không gian tìm kiếm phù hợp với đối thủ có nước đi ở mức đó. Trong ví dụ trên, MIN được quyền đi trước, từng nút lá được gán giá trị 1 hay 0 tùy theo kết quả đó là thắng cuộc đối với MAX hay MIN. Minimax sẽ truyền các giá trị này lên cao dần trên đồ thị qua các nút cha mẹ kế tiếp nhau theo luật sau:

- Nếu trạng thái cha mẹ là nút MAX, gán cho nó giá trị tối đa của các con cháu của nó.

- Nếu trạng thái cha mẹ là nút MIN, gán cho nó giá trị tối thiểu của các con cháu của nó.

Giá trị được gán cho từng trạng thái bằng cách đó sẽ chỉ rõ giá trị của trạng thái tốt nhất mà đối thủ này có thể hy vọng đạt được. Các giá trị này sẽ được dùng để lựa chọn các nước đi có thể có. Kết quả của việc áp dụng Minimax vào đồ thị không gian trạng thái đối với trò chơi Nim được thể hiện như hình trên. Vì tất cả các nước đi đầu tiên có thể xảy ra cho MIN sẽ dẫn đến các nút có giá trị 1 nên đối thủ MAX luôn có thể bắt trò chơi giành thắng lợi cho mình bất kể nước đi đẩu tiên của MIN là như thế nào (đường đi thắng lợi của MAX được cho theo mũi tên đậm).

Áp dụng minimax đến độ sâu lớp cố định

Khi áp dụng Minimax cho các trò chơi phức tạp, hiếm khi có khả năng mở rộng đồ thị không gian trạng thái đến các nút lá. Thay vào đó không gian trạng thái này chỉ có thể được triển khai đến một số mức xác định phụ thuộc tiềm năng về thời gian và bộ nhớ chẳng hạn. Chiến lược này được gọi là tính trước n nước đi (n –move lookahead). Vì giá trị các nút trong đồ thị con này không phải là trạng thái kết thúc của trò chơi nên chúng không phản ánh giá trị thắng cuộc hay thua cuộc. Chúng chỉ có thể được gán một giá trị phù hợp với một hàm đánh giá heuristic nào đó. Giá trị được truyền ngược về nút gốc không cung cấp thông tin thắng cuộc hay thua cuộc mà chỉ là giá trị heuristic của trạng thái tốt nhất có thể tiếp cận sau n nước đi kể từ nút xuất phát. Việc tính trước này sẽ làm tăng hiệu quả của heuristic vì nó được áp dụng vào một phạm vi lớn hơn trong không gian trạng thái. Minimax sẽ hợp nhất tất cả các giá trị của các nút con cháu của một trạng thái thành một giá trị duy nhất cho trạng thái đó.

Trong các đồ thị trò chơi được tìm kiếm bằng mức hay lớp, MAX và MIN luân phiên nhau chọn các nước đi. Mỗi nước đi của một đối thủ sẽ xác định một lớp mới trên đồ thị. Các chương trình trò chơi nói chung đều dự tính trước một độ sâu lớp cố định (thường được xác định bằng các giới hạn về không gian hoặc thời gian của máy tính). Các trạng thái trên mức đó được đánh giá theo các heuristic và các giá trị này sẽ được truyền ngược lên bằng thủ tục Minimax, sau đó thuật toán tìm kiếm sẽ dùng các giá trị vừa nhận được để chọn lựa một nước trong số các nước đi kế tiếp. Bằng cách tối đa hóa cho các cha mẹ MAX và tối thiểu hóa cho các cha mẹ MIN, những giá trị này đi lùi theo đồ thị đến con của trạng thái hiện hành. Sau đó trạng thái hiện hành dùng chúng để tiến hành lựa chọn trong các con của nó. Hình sau trình bày quá trình Minimax trên một không gian trạng thái giả thuyết tính trước bốn lớp.

Hình 4.7 – Minimax đối với một không gian trạng thái giả định

Hình 4.8 giới thiệu một ứng dụng của Minimax độ sâu lớp cố định vào trò chơi Tic-tac-toe.

Hình 4.8 – Minimax hai lớp được áp dụng vào nước đi mở đầu trò chơi Tic-tac-toe

Ở đây sử dụng một heuristic hơi phức tạp hơn, nó cố đo mức độ tranh chấp trong trò chơi. Heuristic chọn một trạng thái cần đo, tính tất cả các đường thắng mở ra cho MAX, rồi trừ đi tổng số các đường thắng mở ra cho MIN. Giải thuật tìm kiếm sẽ cố gắng tối đa hóa sự chênh lệch (hiệu số) đó. Nếu có một trạng thái bắt buộc thắng cuộc cho MAX, nó sẽ được đánh giá là +∞, còn với trạng thái bắt buộc thắng cuộc cho MIN thì được đánh giá là -∞. Hình 4.8 trình bày heuristic này được áp dụng cho hai mức bắt đầu không gian trạng thái.

Câu hỏi :

Khi một máy tính sử dụng giải thuật minimax để chơi cờ, máy tính chơi tốt

hơn khi thời gian cho phép để tính toán cho nước cờ kế tiếp là lâu hơn.

Hãy giải thích một cách ngắn gọn điều này.

Thủ tục cắt tỉa alpha – beta (alpha-beta prunning)

Minimax yêu cầu phải có sự phân tích qua hai bước đối với không gian tìm kiếm: Bước đầu truyền xuống đến độ sâu của lớp áp dụng heuristic và bước sau để truyền ngược các giá trị trên cây. Minimax lần theo tất cả các nhánh trong không gian bao gồm cả những nhánh mà một thuật toán thông minh hơn có thể bỏ qua hay tỉa bớt. Các nhà nghiên cứu trong lĩnh vực chơi game đã xây dựng một kỹ thuật tìm kiếm gọi là cắt tỉa alpha –beta nhằm nâng cao hiệu quả tìm kiếm trong các bài toán trò chơi hai đối thủ.

Ý tưởng của tìm kiếm alpha – beta rất đơn giản: Thay vì nếu như tìm kiếm toàn bộ không gian đến một độ sâu lớp cố định, tìm kiếm alpha – beta thực hiện theo kiểu tìm kiếm sâu. Có hai giá trị, gọi là alpha và beta được tạo ra trong quá trình tìm kiếm. Giá trị alpha liên quan với các nút MAX và có khuynh hướng không bao giờ giảm. Ngược lại giá trị beta liên quan đến các nút MIN và có khuynh hướng không bao giờ tăng. Giả sử có giá trị alpha của một nút MAX là 6, MAX không cần phải xem xét giá trị truyền ngược nào nhỏ hơn hoặc bằng 6 có liên quan với một nút MIN nào đó bên dưới. Alpha là giá trị thấp nhất mà MAX có thể nhận được sau khi cho rằng MIN cũng sẽ nhận giá trị tốt nhất của nó. Tương tự nếu MIN có giá trị beta là 6 nó cũng không cần xem xét các nút nằm dưới nó có giá trị lớn hơn hoặc bằng 6.

Để bắt đầu thuật toán tìm kiếm alpha – beta, ta đi xuống hết độ sâu lớp theo kiểu tìm kiếm sâu, đồng thời áp dụng đánh giá heuristic cho một trạng thái và tất cả các trạng thái anh em của nó. Giả thuyết tất cả đều là nút MIN. Giá trị tối đa của các nút MIN này sẽ được truyền ngược lên cho nút cha mẹ (là một nút MAX). Sau đó giá trị này được gán cho ông bà của các nút MIN như là một giá trị beta kết thúc tốt nhất. Tiếp theo thuật toán này sẽ đi xuống các nút cháu khác và kết thúc việc tìm kiếm đối với nút cha mẹ của chúng nếu gặp bất kỳ một giá trị nào lớn hơn hoặc bằng giá trị beta này. Quá trình này gọi là cắt tỉa beta (β cut). Cách làm tương tự cũng được thực hiện cho việc cắt tỉa alpha (α cut) đối với các nút cháu của một nút MAX.

Hai luật cắt tỉa dựa trên các giá trị alpha và beta là:

• Quá trình tìm kiếm có thể kết thúc bên dưới một nút MIN nào có giá trị beta nhỏ hơn hoặc bằng giá trị alpha của một nút cha MAX bất kỳ của nó.
• Quá trình tìm kiếm có thể kết thúc bên dưới một nút MAX nào có giá trị alpha lớn hơn hoặc bằng giá trị beta của một nút cha MIN bất kỳ của nó.

Việc cắt tỉa alpha – beta như vậy thể hiện quan hệ giữa các nút ở lớp n và các nút ở lớp n+2 và do quan hệ đó toàn bộ các cây con bắt nguồn ở lớp n+1 đều có thể loại khỏi việc xem xét. Chú ý rằng giá trị truyền ngược thu được hoàn toàn giống như kết quả Minimax, đồng thời tiết kiệm được các bước tìm kiếm một cách đáng kể.

A có β = 3 (Trị nút A sẽ không lớn hơn 3)B bị cắt tỉa β, vì 5 > 3C có α = 3 (Trị nút C sẽ không nhỏ hơn 3)D bị cắt tỉa α, vì 0 < 3E bị cắt tỉa α, vì 2 < 3Trị nút C là 3

Hình 4.9 – Thực hiện giải thuật cắt tỉa alpha – beta

TỔNG KẾT CHƯƠNG IV:

Các heuristic tìm kiếm đã được giới thiệu thông qua các trò chơi đơn giản như trò đố 8 ô, Tic-tac-toe, … và cũng đã được phát triển đến các không gian bài toán phức tạp hơn. Chương này cũng đã trình bày việc áp dụng heuristic cho các trò chơi đối kháng có hai người chơi, dùng cách rút gọn tối thiểu trên độ sâu lớp và cắt tỉa alpha - beta để thực hiện việc tính trước các nước đi và dự đoán hành vi của đối thủ. Việc áp dụng các heuristic này đã làm cho không gian bài toán trở nên ngắn gọn hơn, thời gian tìm kiếm một lời giải có thể chấp nhận được là tối thiểu và quá trình tìm kiếm vì thế cũng trở nên đơn giản hơn khá nhiều. Phần chương V tiếp theo, chúng ta sẽ xem xét các kỹ thuật cao câp hơn cho việc cài đặt các thuật toán.

Bài tập chương IV

Xét bài toán trò đố 8 ô như sau:

Dùng các hàm lượng giá heuristic sau, hãy triển khai không gian trạng thái của bài toán theo giải thuật leo núi đến mức 5:

• h1 = số lượng các vị trí sai khác so với trạng thái goal.
• h2 = tổng số độ dời ngắn nhất của các ô về vị trí đúng (khoảng cách Manhattan)

Trong cây tìm kiếm dưới đây, mỗi nút có 2 giá trị đi kèm: giá trị bên trái của nút (in nghiêng) thể hiện giá trị heuristic của nút, và giá trị bên phải nút thể hiện thứ tự nút được duyệt qua. Với mỗi chiến lược tìm kiếm dưới đây, hãy viết danh sách thứ tự các nút được duyệt, so sánh và cho biết ta đã dùng giải thuật tìm kiếm nào trên cây :

• Tìm kiếm rộng BFS
• Tìm kiếm sâu DFS
• Tìm kiếm tốt nhất đầu tiên
• Tìm kiếm leo núi

Thực hiện giải thuật Minimax trên cây sau đây:

Sẽ có gì khác biệt nếu như ta dùng giải thuật cắt tỉa alpha – beta để định trị nút gốc cho cây?

Hãy áp dụng giải thuật cắt tỉa alpha-beta cho các cây sau đây. Cho biết các nhánh được cắt là alpha-cut hay beta-cut và giá trị nút gốc sau khi định trị: