%BEGIN {ab-prune} ?--------------------- начало карточки

%AUTHOR: {Павел Н. Дубнер, т. (095)331-54-27}

%RESUME:
{
ab-prune.txt     -- текст про алгоритм альфа-бета сечений
kalah.c, kalah.h -- программа,  его  иллюстрирующая
kalah.doc        -- описание программы.
}

%VERSION: 1.2

%STATUS: {Freeware}


%CREATION_DATE:  5.7.92

%ISSUE: {B}

%CATALOG: {BENEFIC}

%CLUB: C

%ANALOGS: {см. сопровождающие тексты}

%OS: {MS-DOS > 3.3}

%LIMITATION: {no limitaions}

%HISTORY:  {данная версия является первой и, надеюсь, последней}

%LANGUAGE: { C }

%СОММЕNTS: {Данный набор текстов предназначен для молодых программистов,
любящих свою профессию.}


%END ?----------------------- конец формальных полей карточки




      Сейчас, когда говорят о программировании игр, имеют в виду почти
исключительно "ситуационные" (adventure) игры. Между тем, программиро-
вание логических игры (таких как шахматы, шашки, го, рэндзю...) требу-
ет особой техники, современным программистам почти неизвестной.

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

      До сих пор непревзойденное на мой взгляд изложение метода содер-
жится в статье Д.Кнута и Р.Мура (Artificial Intelligence, 1975).  Пос-
кольку достать этот номер журнала могут сейчас далеко не  все  и  пос-
кольку (увы! увы!! увы!!!) далеко не все программисты достаточно  сво-
бодно владеют английским, я предлагаю  перевод  первой  --  собственно
программистской -- части этой статьи (см. файл ab-prune.txt).

      Однако, после чтения статьи,  конечно,  остается  еще  множество
вопросов. Поскольку всегда "лучше один раз увидеть...", я привожу при-
мер игровой программы -- эти коды должны ответить на некоторые из воп-
росов. В качестве иллюстрации была выбрана очень  простая  по  дизайну
игра КАЛАХ, описание которой я впервые прочел  в  1971  г.  в  журнале
"Наука и жизнь" (вып. 12, стр. 106-114); я еще помню время, когда  на-
бор для игры в калах продавался в московском "Детском мире" на  площа-
ди Дзержинского за 2 р.

      В файле kalah.doc приводится описание игры -- по материалам упо-
мянутого журнала, и описание программы, играющей в нее; этот файл мож-
но читать независимо от текста про альфа-бета-отсечения,  поскольку  в
нем содержится все необходимое, однако, я настоятельно  рекомендую  НЕ
делать этого. Прочтите статью Кнута (ну, да! и Мура,  конечно)  --  не
пожалеете!

      С вопросами и, главное, замечаниями обращайтесь:
         Москва, (095) 331-5427, Дубнер Павел Николаевич.
