Эта статья является продолжением
статьи 49906 и
статьи 49931 в которых было показано как создавать программу построения выигрышной стратегии (ВС) по аналогии с "ручными" действиями. Продолжим данную тему и попытаемся создать "компактную" программу для решения поставленной задачи.
Новая версия программы вместо двух подпрограмм (first и second) будет иметь один стандартный блок и две программы настройки (start и next).
Результатом работы программы будет "словарь раскраски" вершин "графа игры". Принцип раскраски сохраняется.
Уточним основные понятия.
- правила игры - определяются условиями задания
- вершины графа - возможные состояния в игре. Будем подразделять на:
> стартовые - те, из которых игра может начинаться
> финальные - те, в которых игра завершается. Часть "финальных" вершин объявляется "победными для игрока попавшего в них", а часть
"проигрышными для игрок попавшего в них". Если правила игры позволяют, то будем считать, что финальных вершин всего две:
'W' -выигрышная и 'L' - проигрышная;
- словарь раскраски Dict - словарь, ключи=вершине/состоянию графа, а значение =цвету раскраски (целое число).
Начальное заполнение: Dict('W')=0; Dict('L')=-1
Построить выигрышную стратегию (ВС) - это значит раскрасить вершины графа в два цвета (чётные и нечётные) и построить двудольный граф так,
чтобы из
вершин с чётной раскраской "все возможные ходы" вели в
вершины с нечётной раскраской, а из вершин с нечётной раскраской был ход
в
вершину с чётной раскраской.
Вершины с чётной раскраской считаем "
Чётными", а
вершины с нечётной раскраской - "
НеЧётными"
Таким образом, у нас есть один "квадратик" 'W' и "кружок" 'L'. Вершины 'W' и 'L' - это стоки.
При построении раскраски будет использовать следующий принцип:
Вершина будет
Нечётной - если
существует ход в
Чётную
Вершина будет
Чётная - если
все ходы ведут в
Нечётную
Выполнение этого алгоритма позволяет построить
двудольный ориентированный граф игры