(*~\Глагол\Отделы\Игры\КрНолики\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(**)                            ОТДЕЛ Игра;
(*============================================================================*)
(* НАЗНАЧЕНИЕ: алгоритм игры "Крестики-нолики"                                *)
(* ПРАВИЛА:                                                                   *)
(*   Игра идет на квадратном поле 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); 
    позиция:=опозиция 
  КОН 
КОН Ход;

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

КОН Игра. 
