Как рекурсивно заполнить дерево с 4 детьми ниже каждого узла в Java

Question

Я построил свой собственный древовидный класс данных в Java, который должен использоваться в минимаксном алгоритме. Каждый узел в дереве будет содержать объект Board (что-то еще, что я создал), представляющий уникальное состояние игры, а ребра (представляющие направление движения целых чисел - игра Tron) в дереве будут представлять перемещение, сделанное пользователем для достижения состояние края приводит к. Я хочу сделать функцию, которая берет в Дереве и рекурсивно заполняет ее до глубины «DEPTH» (поддерживается как константа в другом месте, а не параметр) с измененными состояниями игры, учитывая каждый из четырех возможных целых чисел, сделанных каждым игроком в каждый уровень. Я просто не совсем уверен, как лучше это сделать ...

Кроме того, поскольку он используется для минимакса, древовидная структура должна выглядеть следующим образом:

• Корень, представляющий ток, без изменений состояние игры
• детей 1-го уровня, представляющие измененные игровые состояния дали 4 возможных ходов пользователя
• детей 2-го уровня, представляющих измененные игровые состояниям дало 4 возможных ходов противника
• 3-го состояния игры уровня 4 ходов пользователя, учитывая движения противника, й так далее ... простирающийся на ПОДРОБНОЕ число уровней

Вот основные методы, которые я должен работать с:

• конструктор для дерева, принимая совет и направление Integer, ведущее к на доске
• метод productChildren(), который берет дерево и логический «userMove» и добавляет 4 новых совета к внутреннему списку дочерних элементов Tree, которые представляют измененные состояния игры, данные каждому из 4 возможных ходов пользователя или оппонента. Параметр «userMove» указывает, должен ли Совет выпускаться как ребенок, должен быть результат 4-х ходов пользователя или 4 хода противника.
• метод Дерева называется getDepth(), которые возвращают глубину этого узла в пределах большого дерева, состоящее из его родителей и детей (если он есть) -> возвращает 0, если это корень

может кто-нибудь возможно, предоставит мне немного псевдокода (используя методы, которые я предоставил, если только не нужны другие методы), так как я бы заполнил Дерево в этом альтернативном, минимаксном способе?

Answer 1

У меня есть пара комментариев по вашей структуре данных, прежде чем переходить к реализации логики.

Нет необходимости хранить полную копию платы в каждом узле дерева. Учитывая, что он используется для минимакса, единственное, что вам нужно знать в каждой точке, - это шаги, чтобы добраться туда и значение этой позиции. Вам нужно будет знать состояние доски в листах, чтобы вычислить значение, но даже тогда нет необходимости хранить его копию после завершения вычисления.

Чтобы пойти еще дальше, минимакс даже не требует сохранения постоянной копии дерева. Если это делается с помощью рекурсии, максимальное или минимальное значение на каждом узле может храниться в локальных переменных и возвращаться - нет необходимости хранить постоянную копию в дереве.

В статье wikipedia на minimax есть некоторый псевдокод, который может помочь вам начать работу.