Вам следует заглянуть в поиск по дереву Монте-Карло, он звучит так, как будто отлично вписывается в вашу проблему.
Вместо того, чтобы использовать эвристику, он запускает полную игру, используя случайных игроков в каждой ветви, прежде чем развернуть дерево. Хорошая вещь в этом заключается в том, что вы на самом деле строите дерево вероятностей, и вам не нужно расширять дерево до конца или с помощью эвристики, такой как MinMax.
MCTS также является лучшим в настоящее время методом в GO игры, и в настоящее время лучше всего играет в игры с неизвестными правилами. Для дополнительного эффекта вы можете использовать агентов конечного автомата вместо случайных игроков, чтобы сделать вероятность более точной. Кроме того, вы можете уменьшить коэффициент ветвления с помощью решателя, который пропускает определенные ветви, используя эвристику, полученную из машинного обучения. (Но это то, что вы бы сделали последним, чтобы увеличить скорость техники)
Если вы можете использовать MinMax, вы можете делать MCTS без особых проблем :) А MCTS может играть в гораздо более сложные игры, чем MinMax, из-за его значительно уменьшенной сложности по сравнению. (Хорошо, если вы намерены постоянно расширять правила игры)
Посмотрите здесь, если вам интересно:
http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf
И да, вы должны делать это на каждом ходу для каждого игрока. Таким образом, и MinMax, и MCTS будут работать медленно; все методы дерева игр медленные
С MinMax вы можете сохранить часть своего дерева; переместитесь в ветку, которая является вашим новым состоянием, и удалите ее родителя и поддеревья, которые связаны с ним Затем разверните еще одну глубину в оставшемся поддереве. Но это предположение; У меня никогда не было времени, чтобы сделать это раньше :) (однако вы будете сохранять ошибки в своих расчетах вероятности)
Хорошая вещь об этих методах в том, что когда вы их создали, они работают. Техника машинного обучения работает намного быстрее, но требует нескольких часов, если не дней обучения перед использованием;)