Giáo trình trí tuệ nhân tạo - chapter 3

Vấn đề tìm kiếm, một cách tổng quát, có thể hiểu là tìm một đối tượng thỏa mãn một số đòi hỏi nào đó, trong một tập hợp rộng lớn các đối tượng. Chúng ta có thể kể ra rất nhiều vấn đề mà việc giải quyết nó được quy về vấn đề tìm kiếm. Các trò chơi, chẳng hạn cờ vua, cờ carô có thể xem như vấn đề tìm kiếm. Trong số rất nhiều nước đi được phép thực hiện, ta phải tìm ra các nước đi dẫn tới tình thế kết cuộc mà ta là người thắ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.