Решение LinkedIn Queens с помощью Haskell ( imiron.io )
связанный:
– с SMT (11 дней назад, 47 комментариев) https://news.ycombinator.com/item?id=44259476
– с APL (10 дней назад, 1 комментарий) https://news.ycombinator.com/item?id=44273489 и (8 дней назад, 20 комментариев) https://news.ycombinator.com/item?id=44275900
– с MiniZinc (1 день назад, 0 комментариев) https://news.ycombinator.com/item?id=44353731
– с SAT (27 дней назад, 1 комментарий) https://news.ycombinator.com/item?id=44115866
Напоминает мне эту классику: https://aphyr.com/posts/342-typing-the-technical-interview
Кто-нибудь знает какие-либо алгоритмы для генерации этих игровых полей?
Что позволит создавать сложные доски?
Обычно нужна подпрограмма, которая может сказать вам 1) имеет ли проблема решение, и 2) является ли решение уникальным (обычное требование для таких головоломок). Используя такую модель в качестве подпрограммы, можно выполнить эвристический поиск для постепенного создания головоломок. Если выбранная вами технология решателя может обрабатывать количественные проблемы, ее можно использовать для объединения этих двух проблем в одну, но это гораздо сложнее.
Если базовый решатель, который у вас есть, — это система, которая может работать в различных конфигурациях с различными уровнями рассуждений и предположений, а также отчет о необходимом количестве поиска, если таковой имеется, это может быть очень полезным для измерения сложности. В Sudoku as a Constraint problem ( https://citeseerx.ist.psu.edu/document?doi=4f069d85116ab6b4c… ) Хельмут Симонис протестировал множество головоломок судоку 9×9 против различных уровней распространения и предварительной обработки в качестве способа измерения сложности головоломок судоку, классифицируя их по уровню рассуждений, необходимого для решения без поиска. Модель MiniZinc для LinkedIn Queens ( https://news.ycombinator.com/item?id=44353731 ) можно использовать с различными решателями и уровнями распространения в качестве такой подпрограммы.
Теперь, для создания головоломок на уровне производства, например, как это делает King для Candy Crush, проблемы и требования еще сложнее. Я слышал презентацию, где они говорили об обучении нейронных сетей играть как люди-тестеры, то есть не оптимальная игра, а самая человеческая игра, чтобы проверить уровень сложности головоломок.
Это сложная проблема по ряду причин 🙂
1) Не так уж сложно создать задачу хотя бы с одним решением (просто сначала положите ферзей, а затем вытяните ящики), но не существует хорошего способа создания уровней с уникальными решениями.
2) Как только вы этого достигнете, будет трудно предсказать, насколько сложным будет уровень, и тогда будет трудно сделать уровни проще/сложнее.
Я как раз сейчас изучаю эту тему (ну, я делаю все виды головоломок на основе сетки, но это пример). Алгоритм пытается делать «хорошие» уровни, но есть большая вероятность, что в итоге получится что-то бесполезное, что нам придется выбросить, а затем попробовать снова.
Легко создавать уровни, которые являются тривиальными, и столь же легко создавать уровни, которые находятся далеко за пределами человеческих возможностей, но попадание в зону «сложных, но решаемых для человека» — вот где возникает большая часть трудностей.
Мне, наверное, стоит попробовать написать человекочитаемую версию того, как я это делаю. Это включает в себя кучу кода Rust, так что я могу затронуть целую кучу модных тем!
Source: news.ycombinator.com