Tìm kiếm có đối thủ Nghiên cứu máy tính chơi cờ đã xuất hiện rất sớm. Không lâu sau khi máy tính lập trình được ra đời vào năm 1950, Claude Shannon đã viết chương trình chơi cờ đầu tiên. các nhà nghiên cứu Trí Tuệ Nhân Tạo đã nghiên cứu việc chơi cờ, vì rằng máy tính chơi cờ là một bằng chứng rõ ràng về khả năng máy tính có thể làm được các công việc đòi hỏi trí thông minh của con người. Trong chương này chúng ta sẽ xét các vấn đề sau đây: Chơi cờ. | Chương IV Tìm kiếm có đối thủ Nghiên cứu máy tính chơi cờ đã xuất hiện rất sớm. Không lâu sau khi máy tính lập trình được ra đời vào năm 1950 Claude Shannon đã viết chương trình chơi cờ đầu tiên. các nhà nghiên cứu Trí Tuệ Nhân Tạo đã nghiên cứu việc chơi cờ vì rằng máy tính chơi cờ là một bằng chứng rõ ràng về khả năng máy tính có thể làm được các công việc đòi hỏi trí thông minh của con người. Trong chương này chúng ta sẽ xét các vấn đề sau đây Chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái. Chiến lược tìm kiếm nước đi Minimax. Phương pháp cắt cụt a-P một kỹ thuật để tăng hiệu quả của tìm kiếm Minimax. Cây trò chơi và tìm kiếm trên cây trò chơi. Trong chương này chúng ta chỉ quan tâm nghiên cứu các trò chơi có hai người tham gia chẳng hạn các loại cờ cờ vua cờ tướng cờ ca rô. . Một người chơi được gọi là Trắng đối thủ của anh ta được gọi là Đen. Mục tiêu của chúng ta là nghiên cứu chiến lược chọn nước đi cho Trắng Máy tính cầm quân Trắng . Chúng ta sẽ xét các trò chơi hai người với các đặc điểm sau. 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 đề tìm kiếm ở đây sẽ phức tạp hơn vấn đề tìm kiếm mà chúng ta đã xét trong các chương trước 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. Sau đây chúng
