Маджонг-solitaire алгоритм решения, который нуждается в ускорении

Question

Я разрабатываю маджонг-solitaire solver и до сих пор, я делаю довольно хорошо. Тем не менее, не так быстро, как хотелось бы, поэтому я прошу дополнительной оптимизации техники, о которых вы, ребята, знаете.

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

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

• Если доступно четыре бесплатных плитки, немедленно удалите их.
• Если есть три плитки, которые можно подобрать, и по крайней мере один из них - свободная плитка, удалите незакрепленные.
• Если есть три плитки, которые можно подобрать, и только одна свободная плитка (две потери), удалите свободный и один случайный свободный.
• Если есть три свободные плитки, удалите два из них (не важно, какие из них).
• Поскольку в четыре раза больше одной и той же плитки, если два из них оставлены, удалите их, так как они остались единственными.

Мой алгоритм ищет решение в нескольких потоках рекурсивно. Как только ветка закончена (в положение, где больше нет движений), и это не привело к решению, оно помещает позицию в вектор, содержащий плохие. Теперь, всякий раз, когда запускается новая ветка, она будет перебираться через плохие позиции, чтобы проверить, была ли эта конкретная позиция уже проверена.
Этот процесс продолжается до тех пор, пока не будет найдено решение или не будут проверены все возможные позиции.

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

Итак, я прошу вас еще раз, если у вас есть хорошие идеи, как реализовать больше правил для безопасного удаления фрагментов или любого другого ускорения в отношении алгоритма.

С наилучшими пожеланиями, nhaa123

Answer 1

Я не совсем понимаю, как работает ваш решатель. Когда у вас есть выбор ходов, как вы решаете, какую возможность исследовать в первую очередь?

Если вы выбираете произвольный вариант, это не достаточно хорошо - это просто грубый поиск, в основном. Возможно, вам сначала понадобится изучить «лучшие отрасли». Чтобы определить, какие ветви «лучше», вам нужна эвристическая функция, которая оценивает позицию. Затем вы можете использовать один из популярных алгоритмов эвристического поиска. Проверьте это:

• A * Поиск
• поиск луча

(Google является вашим другом)

Answer 2

Вместо вектора, содержащего "плохие" позиции, использовать набор, который имеет постоянное время поиска вместо линейного.

Answer 3

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

Также упоминается raindog-2. Закажите свои поисковые пути. У вас есть правила, поэтому дайте указания в соответствии с этими правилами. Пойдите для максимальной свободной плитки, а затем для максимальной свободной плитки. Итак, попробуйте каждый шаг, который вы можете сделать в ситуации, закажите их и продолжите с наиболее оптимальной ситуацией.

Answer 4

Несколько лет назад я написал программу, которая решает пасьянсы Solitaire Mahjongg, подглядывая. Я использовал его для изучения миллиона черепах (занял день или что-то наполовину на компьютере: у него было два ядра), и оказалось, что около 2,96% из них не могут быть решены.

http://www.math.ru.nl/~debondt/mjsolver.html

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