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.
