3) Алгоритмы перебора, занимаются рассмотрением разных вариантов решения задачи. Если у решения есть некая структура (например, как в шахматах, стороны делают по очереди ходы в соответствии с правилами игры), то можно перебирать не все варианты, и, иногда очень и очень
существенно, сократить время решения залдачи.
Альфа-Бета процедура --- это имя одного из простейших таких методов сокращения перебора.
4) Ув. СанитарЖеня привел некоторые действительно фундаментальные задачи организации программ. Однако мне кажется, что эти вещи в нашей стране разрабатывались несколько иными группами людей (А.П. Ершов, С.С.Лавров, М.Р. Шура-Бура и др.)(за исключением, возможно, задач хранения дебютного справочника).
5) На самом деле было несколько групп занимавшихся шахматнымми
программами. По крайней мере, были две группы: Ботвинника,
и Адельсон-Вельский, Арлазаров и Донской (Кажется ВНИИСИ). Последняя группа работала позже, и написала программу Каисса, ставшую году этак в 1974 чемпионом мира.(Это о рекламной части).
Насколько мне известно, алгоритмы, аналогичные шахматным использовались (и возможно используются) в неких весьма топичных программах моделирования БД на оперативном и стратегическом уровне. Однако, напрямую они оказались не слишком пригодными, и они были подвергнуты доработке и адаптации, детали которых покрыты для меня мраком :)