Блог

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

Моя единственная проблема в том, и это то, что мешает мне опубликовать мой проект
, заключается в том, что я не знаю, как оценивать мои доски по уровням сложности. Я искал ВЕЗДЕ,
размещал сообщения на форумах и т.д. Я не хочу писать алгоритмы сам, не в этом суть этого проекта,
и, кроме того, они слишком сложны для меня, поскольку я не математик.

Единственное, к чему я был близок, это этот веб-сайт, который оценивает с помощью JS
но проблема в том, что код написан таким паршивым недокументированным, очень разовым образом,
поэтому его нельзя позаимствовать…

Я перейду к сути —
Может кто-нибудь, пожалуйста, указать мне место, которое предлагает исходный код для оценки судоку?

Спасибо

Обновление 22.6.11:
Это моя игра в судоку, и я внедрил свою собственную систему оценивания, которая опирается
на базовые методы решения человеческой логики, так что ознакомьтесь с ней.

Я сам рассматривал эту проблему, и лучшее, что я могу сделать, это определить, насколько сложна головоломка для решения, фактически решив ее и проанализировав игровое дерево.

Изначально: реализуйте свой решатель, используя «человеческие правила», а не алгоритмы, которые вряд ли будут использоваться игроками-людьми. (Интересная проблема сама по себе.) Оцените каждое логическое правило в вашем решателе в соответствии с его сложностью для использования людьми. Используйте значения в сотнях или больше, чтобы у вас была свобода корректировать оценки относительно друг друга.

Решите головоломку. В каждой позиции:

• Перечислите все новые ячейки, которые могут быть логически выведены в текущей игровой позиции.
• Оценка за каждый вывод (полное решение одной ячейки) — это оценка самого простого правила, которого достаточно для выполнения этого вывода.
• РЕДАКТИРОВАТЬ: Если для выполнения одного вывода необходимо применить более одного правила вместе или одно правило несколько раз, отслеживайте это как одно «составное» применение правила. Чтобы получить результат по составному правилу, возможно, используйте минимальное количество приложений отдельных правил для решения ячейки, умноженное на сумму баллов по каждому из них. (Для таких выводов требуется значительно больше умственных усилий.) Вычисление этого минимального количества приложений может потребовать больших затрат процессора в зависимости от вашего набора правил. Любое приложение с правилом, которое полностью решает одну или несколько ячеек, следует откатить, прежде чем продолжить изучение позиции.
• Исключите все вычеты с оценкой выше минимальной среди всех вычетов. (Логика здесь в том, что игрок не будет воспринимать более сложные задания, поскольку он воспринял более простое и воспользовался им; а также это обещает сократить количество вычислений в процессе принятия решения.)
• Минимальный балл на текущей позиции, деленный на количество «самых простых» выводов (если их много, найти один проще), представляет собой сложность этой позиции. Итак, если правило A является самым простым применимым правилом с оценкой 20 и может быть применено в 4 ячейках, позиция имеет оценку 5.
• Выберите наугад один из «самых простых» выводов по ходу игры и переходите к следующей игровой позиции. Я предлагаю сохранять только полностью решенные ячейки для следующей позиции, не передавая никакого другого состояния. Конечно, это расточительно для процессора, повторяя уже выполненные вычисления, но цель состоит в том, чтобы имитировать человеческую игру.

Общая сложность головоломки равна сумме баллов позиций на вашем пути по игровому дереву.

РЕДАКТИРОВАТЬ: Альтернативная оценка позиции: Вместо полного исключения вычетов с использованием более сложных правил, рассчитайте общую сложность каждого правила (или составного приложения) и выберите минимальную. (Логика здесь в том, что если правило A имеет 50 баллов, а правило B — 400 баллов, и правило A может быть применено в одной ячейке, но правило B может быть применено в десяти, то оценка позиции равна 40, потому что игрок с большей вероятностью определит один из десяти более сложных вариантов, чем один более легкий. Но для этого вам потребуется вычислить все возможности.)

РЕДАКТИРОВАТЬ: Альтернатива, предложенная Briguy37: включить все вычеты в оценку позиции. Оценивайте каждую позицию так, 1 / (1/d1 1/d2 ...) где d1 , d2 и т.д. Указаны индивидуальные выводы. (Это в основном вычисляет «сопротивление выполнению любого вывода» в позиции с учетом индивидуальных «сопротивлений вычету» d1 , d2 и т.д. Но для этого вам потребуется вычислить все возможности.)

Надеюсь, эта стратегия подсчета очков даст показатель для головоломок, который увеличивается по мере увеличения вашей субъективной оценки сложности. Если это не так, то корректировка оценок ваших правил (или ваш выбор эвристики из приведенных выше вариантов) может привести к желаемой корреляции. Как только вы достигнете постоянной корреляции между оценкой и субъективным опытом, вы должны быть в состоянии судить, какими должны быть числовые пороги «легко», «сложно» и т.д. И тогда все готово!

Дональд Кнут изучил проблему и разработал алгоритм Dancing Links для решения судоку, а затем оценил их сложность.

Погуглите, есть несколько реализаций движка Dancing Links.

Возможно, вы могли бы оценить общую «ограниченность» головоломки? Учтите, что новая головоломка (только с подсказками) может содержать определенное количество ячеек, которые можно определить, просто исключив значения, которые она не может содержать. Мы могли бы сказать, что эти ячейки «ограничены» меньшим числом возможных значений, чем обычная ячейка, и чем более сильно ограничены существующие ячейки, тем большего прогресса можно добиться в головоломке без угадывания. (Здесь мы рассматриваем требование «угадывания» как то, что делает головоломку сложной.)

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

Конечно, я на самом деле не играю в судоку (мне просто нравится писать игры и решатели для этого), поэтому я понятия не имею, является ли это допустимым показателем, просто размышляю вслух =)

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

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

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

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

Майк

Я делал это в прошлом.

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

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

При подсчете баллов за содоку каждой методике присваивается определенное значение балла, которое вы суммируете за каждое поле, которое вам нужно заполнить. В то время как ‘single empty cell’ может получить 0, ‘XY Chain’ может получить 100. Вы сводите в таблицу все необходимые методы (и частоту) и получаете окончательное взвешивание. Существует множество мест, в которых перечислены ожидаемые значения для этих весов, но все они довольно эмпирические. Вы пытаетесь смоделировать человеческую логику, поэтому не стесняйтесь придумывать свои собственные веса или улучшать систему (если вы действительно используете только цепочки XY, головоломка, вероятно, проще, чем если бы для нее требовались более продвинутые механизмы).

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

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

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

1. Случайным образом генерируйте фиксированное количество начальных макетов головоломки, скажем, 100.
2. Изначально предложите раздел случайной сложности, который позволяет пользователю разыгрывать случайные головоломки из доступных макетов.
3. Сохраняйте среднее случайное время решения для каждого пользователя. Я бы, вероятно, составил таблицу лидеров top 10 / top X, чтобы это вызвало интерес к игре в случайные головоломки.
4. Сохраняйте средний множитель времени решения для каждого решения головоломки (если пользователь обычно решает головоломку за 5 минут и решает ее за 20 минут, 4 должно быть включено в средний множитель времени решения головоломки)
5. После того, как головоломка будет сыграна достаточное количество раз, чтобы получить базовую сложность для головоломки, скажем, 5 раз, добавьте эту головоломку в свой список оцененных головоломок и добавьте другую случайно сгенерированную головоломку к имеющимся макетам головоломок.
   Примечание: Вам следует сохранить первую головоломку в вашем списке случайных головоломок, чтобы вы могли получать по ней все лучшую статистику.
6. Как только у вас будет достаточное количество головоломок с базовым рейтингом, скажем, 50, разрешите пользователям получить доступ к части вашего приложения с рейтингом сложности. Сложность каждой головоломки будет равна среднему множителю времени для этой головоломки.
   Примечание: Когда пользователи решают играть в головоломки с номинальной сложностью, это не должно влиять на среднее время случайного решения или средний множитель времени решения, если только вы не хотите перейти к вычислению средневзвешенных значений (в противном случае, если пользователь играет в много более сложных головоломок, его среднее время и временные множители будут искажены).

Используя описанный выше метод, решение будет оценено от 0 (уже решено / нет времени решать) до 1 (пользователи, вероятно, решат эту головоломку за свое среднее время) до 2 (пользователям, вероятно, потребуется в два раза больше времени, чтобы решить эту головоломку, чем их среднее время) до бесконечности (пользователям потребуется вечность, чтобы найти решение этой головоломки).