Một số thuật toán áp dụng trong các trò chơi trí tuệ - Tìm hiểu về trí tuệ nhân tạo (Phần 1)

Như chúng ta đã biết việc nghiên cứu trí tuệ nhân tạo (Artificial Intelligence – AI)  có thể đi theo nhiều lĩnh vực khác nhau như:

Ø Lập luận, suy diễn tự động.

Ø Biểu diễn tri thức.

Ø Lập kế hoạch.

Ø Học máy: một lĩnh vực nghiên cứu của AI đang được phát triển mạnh mẽ và có nhiều ứng dụng trong các lĩnh vực khác nhau như khai phá dữ liệu, khám phá tri thức,…

Ø Xử lý ngôn ngữ tự nhiên: một nhánh của AI, tập trung vào các ứng dụng trên ngôn ngữ của con người. Các ứng dụng trong nhận dạng tiếng nói, nhận dạng chữ viết, dịch tự động, tìm kiếm thông tin,…

Ø Hệ chuyên gia: cung cấp các hệ thống có khả năng suy luận để đưa ra những kết luận. Các hệ chuyên gia có khả năng xử lý lượng thông tin lớn và cung cấp các kết luận dựa trên những thông tin đó. Có rất nhiều hệ chuyên gia nổi tiếng như các hệ chuyên gia y học MYCIN, đoán nhận cấu trúc phân tử từ công thức hóa học DENDRAL, …

Ø Robotics: nghiên cứu, chế tạo robot có trí thông minh, khả năng giao tiếp ứng xử như con người.

Ø Trò chơi trí tuệ: nghiên cứu, áp dụng các giải thuật thiết kế trò chơi có khả năng tinh toán, áp dụng nước đi như con người.

Trong loạt bài về trí tuệ nhân tạo này, mình và các bạn sẽ cùng đi tìm hiểu từng lĩnh vực ứng dụng của AI ở trên, và bài viết hôm nay chúng ta sẽ bắt đầu với một số thuật toán được ứng dụng trong các trò chơi trí tuệ.

1. Giải thuật Heuristic

1.1 Khái niệm Heuristic

“Heuristic là phương pháp tiếp cận bằng cảm tính, mang tính kinh nghiệm, dùng trong phương pháp "thử và sai" để giải quyết tương đối các bài toán khó.”

+Heuristic là một khả năng ước lượng dẫn đến lời giải

+Heuristic là những tri thức được rút tỉa từ những kinh nghiệm, “trực giác” của con người

+Heuristic có thể là những tri thức “đúng” hoặc “sai”

+Heuristic là những “tri thức siêu cấp” được dùng để đánh giá tri thức khác, đánh giá kết quả của quá trình suy diễn hoặc kiểm chứng các tri thức mới và “thường đúng”

1.2  Đặc tính và nguyên lý

Thuật giải Heuristic là một sử mở rộng khái niệm của thuật toán. Nó thể hiện cách giải bài toán với những đặc tính sau:

+Tìm được lời giải tốt

+Thời gian giải bài toán chấp nhận được

+Khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người

Có nhiều phương pháp để xây dựng một thuật giải Heuristic, người ta thường dựa vào một số nguyên lý cơ bản sau:

+Nguyên lý vét cạn thông minh: là dựa vào cách tìm đặc biệt để tìm lời giải.

+Nguyên lý tham lam (greedy): lấy tiêu chuẩn tối ưu của bài toán (toàn cục) làm tiêu chuẩn của từng bước giải (cục bộ) để tìm lời giải.

+Nguyên lý thứ tự: thực hiện hành động dựa trên một thứ tự hợp lý để tìm lời giải

Dưới đây ta sẽ xem một ví dụ của thuật giải Heuristic theo nguyên lý tham lam để xem cách mà thuật giải hoạt động:

VD: Hãy tìm hành trình cho một người giao hàng đi qua n điểm khác nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn đường đi là ngắn nhất. Giả sử rằng có con đường nối trực tiếp từa giữa hai điểm bất kỳ.

Đồ thị bài toán như sau:

                 

                          

Ta có thể sử dụng một thuật giải Heuristic với nguyên lý tham để tìm một lời giải tương đối tối. Ý tưởng như sau:

+Từ điểm khởi đầu, liệt kê tất cả quãng đường tới n điểm còn lại rồi chọn đi theo con đường ngắn nhất.

+Khi đã đến một điểm, chọn đến điểm kế tiếp theo nguyên tắc ở trên. Tức là liệt kê tất cả con đường và điểm ta đang đứng đến những điểm chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình cho đến lúc không còn điểm nào để đi.

Cách chọn đường đi thể hiện trong hình dưới đây:

 

Chúng ta thấy hành trình tìm được sẽ có tổng là 14

Tuy nhiên đó là một đường đi tương đối tốt mà thuật giải Heuristic đã tìm thấy cho chúng ta chứ chưa phải là đường đi tối ưu nhất. Quãng đường tối ưu có tổng chiều là bằng 10 (1>2>5>4>3>1).

1.3   Hàm đánh giá Heuristic

Hàm đánh giá Heuristic là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào giá trị hiện tại của bài toán tại mỗi bước giải, giúp chọn được cách hành động tương đối hợp lý trong từng bước của giải thuật

Thông thường trong một bài toán tìm kiếm có thông tin, người ta gọi là tìm kiếm thông tin Heuristic hay là Hàm đánh giá Heuristic.

2.   Các phương pháp tìm kiếm Heuristic

Trước khi tìm hiểu tổng quan về các phương pháp tìm kiếm, ta sẽ xem xét cấu trúc chung của một trò chơi, hay một bài toán có dạng như thế nào. Thông thường thì chúng có dạng “tìm đường đi trong đồ thị” hay cách nói khác là “xuất phát từ một đỉnh của đồ thị, tìm đường đi hiệu quả nhất đén một đỉnh nảo đó”.

2.1    Tìm kiếm theo chiều sâu

Là kỹ thuật tìm lời giải theo các cung của không gian bài toán theo chiều dọc, xử lý theo trật tự xác định.

Bắt đầu từ môt nút rồi tiếp tục đến khi hoặc gặp ngõ cụt, hoặc đến đích. Nếu không đi tiếp được, tức là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác. Quay lại một mức ở đây là quay lại mức trước đó của trạng thái hiện hành (trạng thái biến đổi thành trạng thái hiện hành). Nếu cứ quay lui đến trạng thái khởi đầu mà vẫn thất bại thì ta kết luận là không có lời giải.

2.2    Tìm kiếm theo chiều rộng

Là kỹ thuật tìm kiếm lời giải trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.

Nếu như tìm kiếm theo chiều sâu chỉ tìm kiếm lưu ý đến mở rộng trạng thái được chọn mà không mở rộng các trạng thái khác thì ngược lại với nó, tìm kiếm theo chiều rộng mang hình ảnh của vết dầu loang. Bắt đầu tìm kiếm lời giải từ mức đầu tiên (mức đỉnh của đồ thị), nếu mức này không có lời giải, nó chuyển xuống mức sau để tiếp tục tìm kiếm cho đến khi định vị được lời giải (nếu có).

     

            Một số so sánh giữa hai phương pháp tìm kiếm:

	Chiều sâu	Chiều rộng
Tính hiệu quả	Hiệu quả khi lời giải nằm sâu trong cây tìm kiếm và có một phương án chọn hướng đi chính xác. Hiệu quả của chiến lược phụ thuộc vào phương án chọn hướng đi. Phương án càng kém hiệu quả thì hiệu quả của chiến lược càng giảm. Thuận lợi khi muốn tìm chỉ một lời giải.	Hiệu quả khi lời giải nằm gần gốc của cây tìm kiếm. Hiệu quả của chiến lược phụ thuộc vào độ sâu của lời giải. Lời giải càng xa gốc thì hiệu quả của chiến lược càng giảm. Thuận lợi khi muốn tìm nhiều lời giải.
Lượng bộ nhớ sử dụng để lưu trữ các trạng thái	Chỉ lưu lại các trạng thái chưa xét đến.	Phải lưu toàn bộ các trạng thái.
Trường hợp xấu nhất	Vét cạn toàn bộ	Vét cạn toàn bộ.
Trường hợp tốt nhất	Phương án chọn hướng đi tuyệt đối chính xác. Lời giải được xác định một cách trực tiếp.	Vét cạn toàn bộ.

Tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng đều là các phương pháp tìm kiếm có hệ thống và chắc chắn tìm ra lời giải. Tuy nhiên hai phương pháp này đều là tìm kiếm vét cạn, với bài toán không gian lớn thì không thể dùng hai chiến lược tìm kiếm này. Hơn nữa, hai chiến lược này đều có tính chất “mù quáng” vì chúng không chú ý đến những thông tin (tri thức) ở trạng thái hiện thời và thông tin về đích cần đạt tới cùng mối quan hệ giữa chúng. Các tri thức này vô cùng quan trọng và rất có ý nghĩa để chúng ta thiết kế các thuật giải hiệu quả hơn, chẳng hạn như thuật giải tìm kiếm leo đồi (hill-climbing) và tìm kiếm tốt nhất đầu tiên (best-first-search).

2.3    Tìm kiếm leo đồi (Hill-Climbing)

Tìm kiếm leo đồi là phương pháp tìm kiếm theo kiểu tìm sâu và sử dụng những thông tin phản hồi về các trạng thái để xác định hướng đi tiếp nào là tốt. Hay nói cách khác, leo đồi là tìm sâu kết hợp với việc sử dụng hàm đánh giá Heuristic để biết trạng thái nào tốt hơn. Phương pháp leo đồi chú trọng vào việc tìm xem hướng đi nào dễ dẫn tới trạng thái đích nhất. Thông thường leo đồi hoạt động bằng việc chọn một trạng thái tốt hơn trạng thái đang khảo sát để phát triển việc tìm kiếm. Tuy nhiên, khác với tìm kiếm sâu, leo đồi không lưu tất cả các trạng thái con mà chỉ lưu đúng một trạng thái được chọn nếu có.

Nếu như chỉ chọn một trạng thái tốt hơn, ta sử dụng leo đồi đơn giản; còn chọn trạng thái tốt nhất, ta sử dụng leo đồi dốc đứng.

Tư tưởng thuật giải leo đồi đơn giản:

1. Xét trạng thái ban đầu:

   -Nếu là đích thì thoát và thông báo đã tìm được lời giải

   -Ngược lại, đặt trạng thái hiện hành là trạng thái ban đầu

2. Lặp đến khi: gặp được đích hoặc không còn trạng thái tiếp theo nào hợp lệ của trạng thái hiện hành:

   -Đặt một trạng thái mới là trạng thái tiếp theo hợp lệ của trạng thái hiện hành

   -Đánh giá trạng thái mới này:

               +Nếu là đích => dừng

               +Nếu không là đích, nhưng tốt hơn trạng tái hiện hành => cập nhật nó thành trạng thái hiện hành

               +Nếu không tốt hơn thì tiếp tục lặp

Tư tưởng thuật giải leo đồi dốc đứng

1. Xét trạng thái ban đầu:

   -Nếu là đích thì thoát và thông báo đã tìm được lời giải

   -Ngược lại, đặt trạng thái hiện hành là trạng thái ban đầu

2. Lặp đến khi: gặp được đích hoặc không còn tồn tại một trạng thái tiếp theo nào tốt hơn trạng thái hiện hành

   -Đặt ra một tập các trạng thái kế tiếp có thể có của trạng thái hiện hành và tốt hơn nó

   -Xác định một trạng thái là trạng thái tốt nhất trong tập các trạng thái kế tiếp

   -Đặt trạng thái hiện hành là trạng thái tốt nhất đó

Tuy tư tưởng là như thế, song cả hai phương pháp leo đồi đơn giản và leo đồi dốc đứng đều có khả năng thất bại trong việc tìm lời giải của bài toán mặc dù lời giải đó thực sự hiện hữu. Cả hai giải thuật đều có thể kết thúc khi đạt được một trạng thái mà không còn trạng thái nào tốt hơn nữa có thể phát sinh nhưng trạng thái này không phải là trạng thái đích. Điều này sẽ xảy ra nếu chương trình đạt đến một điểm cực đại địa phương hay một đoạn đơn điệu ngang.

Điểm cực đại địa phương (a local maximum) : là một trạng thái tốt hơn tất cả lân cận của nó nhưng không tốt hơn một số trạng thái khác ở xa hơn. Nghĩa là tại một điểm cực đại địa phương, mọi trạng thái trong một lân cận của trạng thái hiện tại đều xấu hơn trạng thái hiện tại.

Đoạn đơn điệu ngang (a plateau) : là một vùng bằng phẳng của không gian tìm kiếm, trong đó, toàn bộ các trạng thái lân cận đều có cùng giá trị.

Nói một cách ngắn gọn, leo đồi dốc đứng sẽ tốn nhiều thời gian hơn cho một bước nhưng lại đi ít bước hơn; còn leo đồi đơn giản tốn ít thời gian hơn cho một bước đi nhưng lại phải đi nhiều bước hơn. Đây chính là yếu tố được và mất giữa hai thuật giải nên ta phải cân nhắc kỹ lưỡng khi lựa chọn thuật giải.

2.4 Tìm kiếm tốt nhất đầu tiên (Best-first-search)

Kỹ thuật BFS kết hợp ưu điểm không phải quan tâm đến sự mở rộng tất cả các nhánh của tìm sâu và không bị sa vào các đường dẫn bế tắc (các nhánh cụt) của tìm rộng.

Kỹ thuật BFS sử dụng hàm đánh giá Heuristic. Dựa vào mức độ của bài toán tại các nút, hàm đánh giá sẽ gán con số, trọng số cho mỗi nút. Con số này được xem xét trong lúc tìm kiếm, nút mang trọng số lớn nhất sẽ được chọn trong quá trình tìm kiếm.

Tại mỗi bước của BFS, giải thuật sẽ chọn trạng thái mà nó cho rằng là có ưu thế nhất trong số các trạng thái đã sinh ra được đến thời điểm đó.

Khác với giải thuật leo đồi có cải tiến ở chỗ: có lưu tất cả những trạng thái đã phát sinh đến thời điểm chọn trạng thái để xét tiếp.

Ta xem một ví dụ: Khởi đầu, chỉ có một nút (trạng thái) A nên nó sẽ được mở rộng tạo ra 3 nút mới B,C và D. Các con số dưới nút là giá trị cho biết độ tốt của nút. Con số càng nhỏ, nút càng tốt. Do D là nút có khả năng nhất nên nó sẽ được mở rộng tiếp sau nút A và sinh ra 2 nút kế tiếp là E và F. Đến đây, ta lại thấy nút B có vẻ có khả năng nhất (trong các nút B,C,E,F) nên ta sẽ chọn mở rộng nút B và tạo ra 2 nút G và H. Nhưng lại một lần nữa, hai nút G, H này được đánh giá ít khả năng hơn E, vì thế sự chú ý lại trở về E. E được mở rộng và các nút được sinh ra từ E là I và J. Ở bước kế tiếp, J sẽ được mở rộng vì nó có khả năng nhất. Quá trình này tiếp tục cho đến khi tìm thấy một lời giải.

Từ ví dụ trên, ta đưa ra tư tưởng cho giải thuật BFS, BFS sử dụng hai danh sách:

· OPEN: tập chứa các trạng thái đã được sinh ra nhưng chưa được xét đến (vì ta đã chọn một trạng thái khác). Thực ra, OPEN là một loại hàng đợi ưu tiên (priority queue) mà trong đó, phần tử có độ ưu tiên cao nhất là phần tử tốt nhất.

· CLOSED: tập chứa các trạng thái đã được xét đến. Chúng ta cần lưu trữ những trạng thái này trong bộ nhớ để đề phòng trường hợp khi một trạng thái mới được tạo ra lại trùng với một trạng thái mà ta đã xét đến trước đó.

Thuật giải BFS

1.      Đặt OPEN chứa trạng thái khởi đầu

2.      Lặp cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện:

-         Chọn trạng thái tốt nhất trong OPEN và xóa nó khỏi OPEN (Đưa vào CLOSED)

-         Nếu nó là trạng thái kết thức thì thoát, ngược lại:

-         Phát sinh các trạng thái con của nó, với mỗi trạng thái con:

+ Xét xem nó có tốt nhất trong số các trạng thái con

+ Thêm nó vào OPEN, thực hiện việc lặp lại như trên.

Có thể thấy BFS khá đơn giản. Tuy vậy, trên thực tế, cũng như tìm kiếm chiều sâu và chiều rộng, hiếm khi ta dùng BFS một cách trực tiếp.

3.   Các giải thuật tìm kiếm lời giải cho trò chơi

3.1 Cây trò chơi và tìm kiếm trên cây trò chơi

Thông thường các trò chơi trí tuệ thường là trò chơi đối kháng giữa hai đấu thủ, mỗi một đấu thủ sẽ sở hữu cho mình một loại quân, thường là quân đen và quân trắng. Hai người chơi thay phiên nhau đưa ra các nước đi tuân theo các luật đi nào đó, các luật này là như nhau cho cả hai người. Điển hình là cờ vua, trong cờ vua hai người chơi có thể áp dụng các luật đi con tốt, con xe,... để đưa ra nước đi. Luật đi con tốt Trắng xe Trắng,... cũng như luật đi con tốt Đen, xe Đen,... Một đặc điểm nữa là hai người chơi đều được biết thông tin đầy đủ về các tình thế trong trò chơi (không như trong chơi bài, người chơi không thể biết các người chơi khác còn những con bài gì). Vấn đề chơi cờ có thể xem như vấn đề tìm kiếm nước đi, tại mỗi lần đến lượt mình, người chơi phải tìm trong số rất nhiều nước đi hợp lệ (tuân theo đúng luật đi), một nước đi tốt nhất sao cho qua một dãy nước đi đã thực hiện, anh ta giành phần thắng. Tuy nhiên vấn đề tim kiếm ở đây sẽ phức tạp hơn vấn đề tìm kiếm mà chúng ta đã tìm hiểu trong các phần trên, bởi vì ở đây có đối thủ, người chơi không biết được đối thủ của mình sẽ đi nước nào trong tương lai.

Việc chơi cờ, hay còn nói là tìm kiếm đối kháng có thể xem như vấn đề tìm kiếm trong không gian trạng thái mà mà mỗi trạng thái là một tình thế (hay một nước đi). Để thuận tiện cho việc chọn nước đi, người ta biểu diễn không gian trạng thái như một cây trò chơi.

Cây trò chơi được hiểu là cây ngữ nghĩa, trong đó các nút thể hiện cấu hình trò chơi, các nhánh thể hiện các bước chuyển. Có thể xem hai nhánh xuất phát từ một tút là hai quyết định của hai đấu thủ.

Gọi p là mức của cây thì độ sâu của cây là d = p-1. Giả sử trong chơi cờ, nước đi được xem như gồm một lựa chọn của một bên và nước đi phản ứng của bên kia. Tuy vậy trên cây trò chơi, người ta cũng có thể coi mỗi lựa chọn hay bước chuyển như một nước đi.

3.2 Giải thuật Mini-max

Giả sử có bộ phân tích tình huống cho phép chuyển các nhận định về các tình huống về con số định lượng đơn giản. Giả sử mức dương chỉ sự thuận lợi cho một đối thủ(đấu thủ max), và âm chỉ sự thuận lợi cho đối thủ kia(đấu thủ min). Trị tuyệt đối chứng tỏ mức độ thuận lợi

Quá trình tính ra con số phản ánh chất lượng trò chơi gọi là đánh giá tĩnh, hàm tính toán gọi là bộ đánh giá tĩnh, con số là tỉ số đánh giá tĩnh(điểm đánh giá tĩnh).

Cây trò chơi được dùng cho việc thể hiện trò chơi giữa hai đấu thủ này.

Đấu thủ max tìm các bước chuyển đưa đến đánh giá là số dương lớn và giả sử rằng đấu thủ min sẽ cố giữa trò chơi hướng về tình huống có đánh giá tĩnh âm nhiều.

Trên cây trò chơi, trước tiên đấu thủ max đi, xuất phát từ mức thứ nhất, họ phải tính sao để đến mức sau của cây, ứng với lượt đi của đấu thủ min trò chơi tạo điều kiện tốt cho họ.

Tư tưởng Giải thuật 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.

3.3 Giải thuật cắt tỉa Alpha-Beta

Được định nghĩa rằng một điều chắc là tồi thì đừng tốn thời gian để thấy nó tồi như thế nào.

Giải thuật cắt tỉa Alpha-Beta là một cải tiến của giải thuật 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át sinh và lượng giá, do đó có thể tăng độ sâu của cây tìm kiếm.

Giải thuật Alpha-beta dùng hai tham số là alpha và beta để theo dõi các khả năng.

-         Alpha liên quan với các nút MAX và có khuynh hướng không bao giờ giảm

-         Beta liên quan với các nút MIN và có khuyenh hướng không bao giờ tăng.

Tư tưởng giải thuật Alpha - Beta

·        Nếu mức đang xét là đỉnh (gốc cây), đặt giá trị của alpha là -∞ và beta là +∞

·        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 lại kết quả.

·        Nếu như mức đang xét là của người chơi cực tiểu

o   Thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục Alpha-Beta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta.

§  Áp dụng thủ tục AlphaBeta với giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả.

§  So sánh giá trị ghi nhớ với giá trị beta, nếu giá trị đó nhỏ hơn thì đặt beta bằng giá trị mới này.

o   Ghi nhớ lại beta

·        Nếu như mức đang xét là của người chơi cực đại

o   Thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục AlphaBeta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta.

§  Áp dụng thủ tục AlphaBeta với  giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả.

§  So sánh giá trị ghi nhớ với giá trị alpha, nếu giá trị đó lớn hơn thì đặt alpha bằng giá trị mới này.

o   Ghi nhớ lại alpha.   

4.   Kết luận

Các phương pháp tìm kiếm Heuristic và các phương pháp tìm kiếm lời giải cho trò chơi thường được thể hiện bằng đồ thị biểu diễn trạng thái (hay nói cách khác là biểu diễn trên cây ngữ nghĩa). Các phương pháp ở trên có thể được phân thành ba nhóm phương pháp tìm kiếm.

-  Tìm kiếm không có thông tin: bao gồm tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng.

-  Tìm kiếm có thông tin: bao gồm tìm kiếm leo đồi (Hill-Climbing) và tìm kiếm tốt nhất đầu tiên (BFS).

-  Tìm kiếm đối kháng: giải thuật tìm kiếm Minimax, giải thuật cắt tỉa Alpha-Beta.

Các kỹ thuật tìm kiếm không có thông tin trong một số trường hợp rất kém hiệu quả và thậm chí không áp dụng được. Vì thế mà người ta không thường xuyên áp dụng chúng mà hay phải cải tạo, cải tiến chúng để áp dụng. Việc tìm kiếm sẽ trở nên dễ dàng hơn đôi chút khi mà việc tìm kiếm là có thông tin. Các phương pháp tìm kiếm có thông tin hiệu quả hơn tìm kiếm không có thông tin. Tuy nhiên, trong một số trường hợp lại có thể không tìm được ra lời giải cho dù lời giải có hiện hữu. Trong nhiều trường hợp người ta sẽ phải cân nhắc lựa chọn các kỹ thuật tìm kiếm sao cho phù hợp với yêu cầu bài toán đề ra.

Còn đối với tìm kiếm đối kháng, điển hình là trò chơi đối kháng giữa hai đấu thủ, như các trò chơi cờ tướng, cờ vua, cờ vây..., có thể là người với người hoặc người với máy. Thông tin cho việc tìm kiếm là hiện hữu ngay trên bàn cờ. Mỗi thế cờ là một nước đi của một đấu thủ. Hai người chơi sẽ luân phiên nhau thực hiện nước đi với mục đích sao cho lợi thế nghiêng về mình là nhiều hơn. Đối với tìm kiếm đối kháng. Người ta hay sử dụng thuật giải Minimax, thông thường Minimax được xây dựng tìm kiếm ở một mức nhất định (hay độ sâu cho trước) và có thể sử dụng cải tiến của nó là giải thuật cắt tỉa Alpha-Beta. Tất nhiên được gọi là cải tiến thì Alpha-Beta phải có cái lợi thế so với Minimax, ở chỗ nó tìm kiếm nhanh hơn, với độ sâu nhiều hơn.

Tuy nhiên độ dài của bài viết có giới hạn, nên mình xin phép trình bày đến đây. Bài viết tiếp theo trong loạt bài viết Tìm hiểu về trí tuệ nhân tạo, mình sẽ đưa các bạn tìm hiểu chi tiết hơn về giải thuật MiniMax được ứng dụng trong trò chơi cờ tướng ra sao, và cùng xem mình có thể thắng được trí tuệ nhân tạo do chính mình viết ra không nhé!