Алгоритм Куна

Пример 1:

Решение от преподавателя:

Цифры в вершинах дерева игры соответствуют номеру игрока, который эту вершину контролирует; буквы в вершинах обозначают исходы игры; висячиквершины выделены жирным. Чтобы найти выигрыши игроки и путь игры, рассматриваем вершины, преемниками которых являются только висячие вершы. По матрице выигрышей определяем, какой именно ход совершает игрок (на рисунке обозначаем выбор игрока жирной стрелкой). После этого отсекаем висячие вершины и повторяем алгоритм. Таким образом в конечном итоге определяется путь игры и выигрыши игроков в конце. В данной игре путь обозначен на рисунке жирными линиями, исходом игры будет исход b = (5, 8, 17, -3).

Пример 2:

Решение от преподавателя:

Цифры в вершинах дерева игры соответствуют номеру игрока, который эту вершину контролирует; буквы в вершинах обозначают исходы игры; висячиквершины выделены жирным. Чтобы найти выигрыши игроки и путь игры, рассматриваем вершины, преемниками которых являются только висячие вершы. По матрице выигрышей определяем, какой именно ход совершает игрок (на рисунке обозначаем выбор игрока жирной стрелкой). После этого отсекаем висячие вершины и повторяем алгоритм. Таким образом в конечном итоге определяется путь игры и выигрыши игроков в конце. В данной игре путь обозначен на рисунке жирными линиями, исходом игры будет исход с = (9, 4, 6).