Поиск – это метод решения проблемы, в котором систематически просматривается пространство состояний задачи. Примеры состояний задачи: различные размещения фигур на доске в шахматах или же промежуточные шаги логического обоснования. Затем в этом пространстве альтернативных решений производится перебор в поисках окончательного ответа. Ученые утверждают, что эта техника лежит в основе человеческого способа решения различных задач. Отметим, что поиск является одной из фундаментальных проблем, занимающих разработчиков искусственного интеллекта.

Многие ранние исследования в области поиска в пространстве состояний совершались на основе таких распространенных настольных игр, как шашки, шахматы и пятнашки. Вдобавок к свойственному им интеллектуальному характеру такие игры имеют некоторые свойства, делающие их идеальным объектом для экспериментов. Большинство игр ведутся с использованием четко определенного набора правил: это позволяет легко строить пространство поиска и избавляет исследователя от неясности и путаницы, присущих менее структурированным проблемам. Позиции фигур легко представимы в компьютерной программе, они не требуют создания сложных формализмов, необходимых для передачи семантических тонкостей более сложных предметных областей. Тестирование игровых программ не порождает никаких финансовых или этических проблем. Поиск в пространстве состояний – принцип, лежащий в основе большинства исследований в области ведения игр.

Игры могут порождать необычайно большие пространства состояний. Для поиска в них требуются мощные методики, определяющие, какие альтернативы следует рассматривать. Такие методики называются эвристиками и составляют значительную область исследований искусственного интеллекта. Эвристика – стратегия полезная, но потенциально способная упустить правильное решение. Примером эвристики может быть рекомендация проверять, включен ли прибор в розетку, прежде чем делать предположения о его поломке, или выполнять рокировку в шахматной игре, чтобы попытаться уберечь короля от шаха. Большая часть того, что мы называем разумностью, по-видимому, опирается на эвристики, которые люди используют в решении задач.

Поскольку у большинства из нас есть опыт в этих простых играх, можно попробовать разработать свои эвристики и испытать их эффективность. Для этого не нужны консультации экспертов в каких-то темных для непосвященных областях, вроде медицины или математики. Поэтому игры являются хорошей основой для изучения эвристического поиска. Программы ведения игр, несмотря на их простоту, ставят перед исследователями новые вопросы, включая вариант, при котором ходы противника невозможно детерминировано предугадать. Наличие противника усложняет структуру программы, добавляя в нее элемент непредсказуемости и потребность уделять внимание психологическим и тактическим факторам игровой стратегии.