Глоссарий для ИС(игровых стратегий)

Глоссарий :

• Игра - соревнование двух игроков A и Б, осуществляющий поочередные ходы. Первый ход делает игрок А.
  Итог игры победа одного из игроков. Ничьих нет, игра не может быть бесконечной.
• ВС (выигрышная стратегия) - Будем говорить, что игрок имеет выигрышную стратегию (ВС),
  если он может выиграть при любых ходах противника за конечное число шагов
  Рассматриваются иогры. в которых для любой допустимой стартовой позиции ВС есть у одного из игроков
• Игрока,  у которого есть ВС для данной стартовой позиции будем называть "Победитель", а его соперника "Оппонент"
• Вершина/позиция - начальная, промежуточное или финальное состояние игры. Из начальных и промежуточных позиций
  игроки могут делать ходы. Из финальных состояний делать ходы нельзя. Достижение финальной позиции означает окончание игры.
  Для финальных вершин введем обозначения:  
  • Win (W)- выигрышная позиция. Игрок, достигший вершины "Win"Б считается победителем
  • Lose  (L) - проигрышная позиция. Игрок, попавший в вершины "Lose", считается проигравшим.
    Победителем объявляется его соперник
• Ход игрока - переход из одной позиции в другую по определенным правилам. Ход игрока можно считать ориентированным ребром в графе.
  Такт игры - ход одного из игроков. Игрок А ходит на нечётных тактах (1, 3,...), игрок Б на четных тактах (2, 4,...)
• Раскраска вершины - Если, при начале игры из данной вершины,  ВС (выигрышная стратегия) есть:
        - у игрока А,  то считается, что вершина - "выигрышшная"/"кружок"/раскрашена в "цвет игрока А"
        - у игрока Б,  то считается, что вершина - "проигрышная"/"прямоугольная"/раскрашена в "цвет игрока БА"
• Раскрасить вершину - значит определить, в цвета какого из игроков она может быть раскрашена.
• Граф игры  - двудольный, ориентированный, невзвешанный, ациклический граф, отражающий ВС для всех позиций
  (если это возможно), в котором:
  • произведена  раскраска вершин в цвета игроков;
  • все ребра соответствуют разрешенным ходам;
  • нет параллельных ребер (параллельные ребра можно объединить);
• Если в "граф игры" нельзя добавить ни одного ребра, чтобы не нарушить перечисленные условия, то он называется полным