Я строю игровое дерево для поиска карточной игры, похожей на бридж.Итак, я начал с создания решателя с двойным манекеном для моста.Я пытаюсь оптимизировать текущий алгоритм поиска по дереву игр, который основан на поиске по дереву альфа-бета-сокращения, улучшенному с помощью MTD-f https://en.wikipedia.org/wiki/MTD-f.(Весь мой текущий код написан на Java)
Я читал статью М. Гинзберга о «поиске разделов».Его можно найти во многих местах в Интернете, например, https://www.aaai.org/Papers/AAAI/1996/AAAI96-034.pdf. По словам Гинзберга, он набрал на порядок порядок производительности.
После того, как он несколько раз прочитал статью, я думаю, что большеили менее понять это, по крайней мере, идея довольно проста, но решить это не так.
- Я не уверен, что полностью понимаю, как можно избежать сложности пересечения в алгоритме с помощью поиска в нулевом окне, хотя нетрудно понять, что он преобразует сложную проблему вдвоичная проблема 0 или 1.
- Гинзберг продолжает отмечать в своем примере моста
"хотя детали функций аппроксимации и структуры данных зависят от правил моста и обсуждения ихреализация выходит за рамки этой статьи "
Я полностью не вижу, какой тип структур данных может быть использован для реализации этого, например, первая строка алгоритма:
if there is an entry (S,[x,y],z) with p elemOf S return (z,S)
Где
- «запись» относится к записи в той или иной форме «таблицы транспонирования»
- p - позиция (как обычно она есть вдерево игры)
- S - это набор позиций!
- [x, y] - возможный интервал исхода, аналогичный альфе и бете
This
- каким-то образомприравнивает таблицу транспонирования, где ключи - это наборы позиций?!
- как определить elemOf?...
Аналогично для системы разделов, обозначаемой в документе (P, R, C).Как можно построить «аппроксимирующие функции» для них?
Кажется, я не могу найти реализации этой идеи, структуры данных для ее поддержки ... Кто-нибудь пробовал?Действительно ли это стоит всех усилий?
PS Единственное упоминание о чем-то подобном, как я обнаружил, было магистерской диссертацией С.Купфершмида: http://gki.informatik.uni -freiburg.de / theses / diploma_de.html (полностью на немецком языке, но он определяет только отношение эквивалентности между картами, которое учитывает особенности Skat. Для чего-то вроде bridge это похоже на «эквивалентность ранга», т.е. если у вас 6 и 4 одинаковой мастии 5 из этой масти были сыграны, тогда 6 и 4 эквивалентны для исхода игры)