Минимальное представление дерева поиска

Я добавил числа для узлов и выделил «максимальные» строки. Невыделенные строки являются «минимальными» строками (т. е. игрок хочет минимизировать результат). Очевидно, что L — это самое низкое значение, а W — самое высокое значение. Обычно мы присваиваем 1 победе, -1 проигрышу и 0 ничье. Игрок Y хочет, чтобы это число было как можно меньше (он выигрывает, если игрок X получает L). Игрок X хочет сделать число как можно большим (он хочет W).

Если игра доходит до узла 4, вы знаете, что игрок X выиграет, несмотря ни на что. Поэтому 4 обозначается W (или 1). Если игра доходит до узла 5, вы знаете, что он проигрывает, поэтому он отмечен буквой L. То же самое происходит и с узлом 6 (который получает W).

Чтобы назначить узел 2, мы отмечаем, что 2 находится в «минимальной» строке (это ход игрока Y). 4, 5, 6 имеют W, L, W соответственно. Игрок Y может свести к минимуму это, выбрав узел 5, и поэтому выиграет. Следовательно, Игрок X знает, что если Игрок Y умен, Игрок X проиграет, если выберет А.

Мы можем сделать то же самое с другой стороны, чтобы показать, что если Игрок X выберет B, то у него будет ничья. Следовательно, игрок X должен выбрать B.

Когда код написан для минимакса, он выполняет обход дерева после заказа< /a> и присваивает значения узлам, просматривая потомков.