(******************************************************************************)
(**)                    ОТДЕЛ Игра;                    (**)
(******************************************************************************)
(* НАЗНАЧЕНИЕ: алгоритм игры "Крестики-нолики"                    *)
(* ПРАВИЛА:                    *)
(*   Игра идет на квадратном поле 3х3 клетки. Игроки по очереди ставят        *)
(*   в клетках - один крестики (+), второй нолики (о). Выигрывает тот,        *)
(*   кто первым замкнул линию (вертикальную, горизонтальную или диагональную).*)
(******************************************************************************)

ВИД   
   Позиция=ЦЕПЬ[10];  

ПЕР                 (*         номера клеток в позиции: |0 1 2| *)   
   позиция-:Позиция; (* текущая игровая позиция          |3 4 5| *)  
   опозиция:Позиция; (* текущий лучший ход машины        |6 7 8| *)

(******************************************************************************)
ЗАДАЧА ЕстьЛинияИз(зн:ЗНАК):КЛЮЧ;  
(* Цель:  поиск замкнутой линии в текущей позиции
  * До:    <зн> - вид искомых значков ('+' или 'о')
  * Ответ: ВКЛ, если в <позиция> есть линия из 3-х <зн> *)
УКАЗ  
   ЕСЛИ (позиция[0] = зн) И (позиция[1] = зн) И (позиция[2] = зн) ИЛИ  
        (позиция[3] = зн) И (позиция[4] = зн) И (позиция[5] = зн) ИЛИ  
        (позиция[6] = зн) И (позиция[7] = зн) И (позиция[8] = зн) ИЛИ  
        (позиция[0] = зн) И (позиция[3] = зн) И (позиция[6] = зн) ИЛИ  
        (позиция[1] = зн) И (позиция[4] = зн) И (позиция[7] = зн) ИЛИ  
        (позиция[2] = зн) И (позиция[5] = зн) И (позиция[8] = зн) ИЛИ  
        (позиция[0] = зн) И (позиция[4] = зн) И (позиция[8] = зн) ИЛИ  
        (позиция[6] = зн) И (позиция[4] = зн) И (позиция[2] = зн) ТО
     ВОЗВРАТ ВКЛ
   ИНАЧЕ
     ВОЗВРАТ ОТКЛ
   КОН
КОН ЕстьЛинияИз;  

(******************************************************************************)
ЗАДАЧА Окончена-():КЛЮЧ;  
(* Цель:  определить конец игры
  * Ответ: ВКЛ, если достигнут конец игры *)
ПЕР  
   n:ЦЕЛ;  
УКАЗ  
   ЕСЛИ ЕстьЛинияИз("+") ИЛИ ЕстьЛинияИз("о") ТО
     ВОЗВРАТ ВКЛ  
   КОН;  
   (* если еще можно ходить, то это не конец *)
   ОТ n:=0 ДО 8 ВЫП  
     ЕСЛИ позиция[n] = " " ТО
       ВОЗВРАТ ОТКЛ  
     КОН  
   КОН;  
   (* ничья *)
   ВОЗВРАТ ВКЛ  
КОН Окончена;  
    
(******************************************************************************)
ЗАДАЧА Оценить(свои:ЗНАК; alpha,beta,глубина:ЦЕЛ):ЦЕЛ;  
(* Цель:  просчет наилучшего хода методом Alpha-beta отсечения
  * До:    <свои>    - свои значки
  *        <alpha>   - нижняя оценка
  *        <beta>    - верхняя оценка
  *        <глубина> - глубина поиска
  * Ответ: оценка <позиция> с точки зрения <свои> *)
ПЕР  
   чужие:ЗНАК;  
   оценка:ЦЕЛ;  
   естьХод:КЛЮЧ;
   n:ЦЕЛ;  
УКАЗ  
   ЕСЛИ свои = "о" ТО чужие:="+" ИНАЧЕ чужие:="о" КОН;  
   ЕСЛИ ЕстьЛинияИз(чужие) ТО   
     (* это наш проигрыш *)  
     ВОЗВРАТ -1
   КОН;  
   (* пока не нашли ни одной свободной клетки *)
   естьХод:=ОТКЛ;
   (* переберем все клетки позиции *)  
   ОТ n:=0 ДО 8 ВЫП  
     ЕСЛИ позиция[n] = " " ТО   
       естьХод:=ВКЛ;
       (* сделаем ход *)  
       позиция[n]:=свои;  
       (* и оценим его *)  
       оценка:=-Оценить(чужие,-beta,-alpha,глубина+1);  
       ЕСЛИ оценка > alpha ТО  
         alpha:=оценка;  
         ЕСЛИ глубина = 0 ТО  
           опозиция:=позиция
         КОН  
       КОН;  
       (* восстановим позицию *)  
       позиция[n]:=" ";  
       (* отсечение *)
       ЕСЛИ alpha >= beta ТО  
         ВОЗВРАТ alpha
       КОН  
     КОН  
   КОН;  
   ЕСЛИ естьХод ТО
     ВОЗВРАТ alpha
   ИНАЧЕ
     (* ничья *)  
     ВОЗВРАТ 0
   КОН
КОН Оценить;  
    
(******************************************************************************)
ЗАДАЧА Ход-(n:ЦЕЛ);
(* Цель:  полуход "+" и ответный полуход "о"
  * До:    <n>       - куда ходят "+"
  * После: <позиция> - новая позиция  *)
ПЕР
   оценка:ЦЕЛ;
УКАЗ
   позиция[n]:="+";  
   ЕСЛИ НЕ Окончена() ТО   
     оценка:=Оценить("о",-2,2,0);  
     позиция:=опозиция  
   КОН  
КОН Ход;

(******************************************************************************)
ЗАДАЧА НачатьЗаново-;
(* Цель:  подготовиться к новой игре *)
УКАЗ
   позиция:="         "
КОН НачатьЗаново;

КОН Игра.