Дональд Кнут вдохновитель алгоритмов

Question

Я работаю над игрой вдохновителя, которая реализует алгоритм Дональда Кнута. Первые пять шагов ясны. Мне нужно создать набор перестановок для каждого возможного ответа, использовать 1122 в качестве первого предположения, сравнить каждый возможный ответ из набора с 1122 и затем удалить любой из возможных ответов, который не дает такой же обратной связи, как текущее предположение. Теперь проблема заключается в определении следующего предположения и в том, как я должен реализовать шаг 6. Алгоритм показан ниже.

Алгоритм пяти предположений, предложенный Доналом Кнута для решения задачи. Game Mastermind.

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

Алгоритм работает как следующим образом:

1. Создайте набор S из 1296 возможных кодов (1111, 1112 ... 6665, 6666).

2. Начните с первоначального предположения 1122 (Кнут приводит примеры, показывающие, что другие первые угадывания, такие как 1123, 1234, не дают результата при пяти попытках для каждого кода).

3. Сыграйте отгадку, чтобы получить ответ в виде цветных и белых колышков .

4. Если ответ состоит из четырех цветных колышков, игра выиграна, алгоритм завершается.

5. В противном случае удалите из S любой код, который бы не давать такой же ответ, если текущее предположение было кодом.
   
   Например, если ваше текущее предположение - 1122, и вы получаете ответ BW;
   Если бы код был 1111, вы бы получили два черных колышка (BB) с предположением 1122, что не то же самое, что один черный колышек и один белый колышек (BW). Итак, удалите 1111 из списка возможных решений.
   
   F (1122,1112) = BBB ≠ BW → Удалить 1112 из S
   
   F (1122,1113) = BB ≠ BW → Удалить 1113 из S
   
   F (1122,1114) = BB ≠ BW → Удалить 1114 из S
   
   F (1122,1314) = BW = BW → Сохранить 1314 в S
   
   

6. Примените технику минимакса, чтобы найти следующее предположение:
   Для каждого возможного предположения, то есть любого неиспользуемого кода 1296, а не только кодов в S, вычислите, сколько возможности в S будут исключены для каждого возможного результата цветного / белого колышка. Оценка предположения - это минимальное количество возможностей, которые оно могло бы исключить из S.
   
   Одно значение от l oop до S для каждого неиспользованного кода из 1296 обеспечит «количество совпадений» для каждого из возможных цветные / белые колышки; Создайте набор предположений с наименьшим максимальным счетом (отсюда и minmax).
   Из набора предположений с минимальным (максимальным) счетом выберите одно в качестве следующего предположения, по возможности выбирая член S.
   
   Кнут следует соглашению о выборе предположения с наименьшим числовым значением, например, 2345 ниже, чем 3456. Кнут также приводит пример, показывающий, что в некоторых случаях ни один член S не будет среди предположений с наибольшим количеством очков, и, следовательно, предположение не может выиграть следующий ход, но будет необходим для обеспечения выигрыша из пяти.
   
   

7. Повторите с шага 3
   
   Ссылка на страницу Википедии

Answer 1

Возьмите набор непроверенных кодов и назовите его T.

Выполните итерацию по T, рассматривая каждый код как предположение, g.

Для каждого g выполните итерацию по T снова рассматривая каждый код как возможный истинный скрытый код, c.

Вычислите оценку черно-белой привязки, полученную путем угадывания g, если реальный код равен c. Назовите это s.

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

Если вы рассмотрели все возможные коды (для что g) считать, что оценка, которая выпадает чаще всего. Вы могли бы назвать это наименее информативным возможным результатом угадывания g. Это оценка g; чем оно ниже, тем лучше.

При итерации по g следите за предположением с наименьшим баллом. Это предположение.