В игровых программах также используется поиск в пространстве состояний, но стратегия поиска более избирательна, чем в случае прямого применения алгоритма generate-and-test. Кроме того, нужно принимать во внимание и то, что в игре, как правило, принимают участие две противоборствующие стороны. Были разработаны довольно неплохие программы для игры в шашки, нарды и шахматы. Созданные программы игры в шахматы нельзя отнести к классу систем, основанных на знаниях, а скорее к классу программ, обладающих способностью избирательно анализировать пространство состояний, что значительно повышает скорость и эффективность анализа. Методы и алгоритмы этого класса в данной книге рассматриваться не будут.
Другая задача, которая занимала умы исследователей в области искусственного интеллекта в середине 50-х годов, — доказательство теорем. Смысл задачи доказательства состоит в том, чтобы показать, как некоторое утверждение, которое требуется доказать (теорема), логически следует из декларированного множества других утверждений или аксиом (которые полагаются истинными или являются такими априори).
2.1. Комбинаторный взрыв
Исследованием вычислительной обозримости (или необозримости) проблем занимается теория сложности. Для начала нам потребуется только знать, что существуют классы проблем, решение которых требует ресурсов, экспоненциально возрастающих при линейном увеличении размерности задачи.