В статье Кнут описывает, как была выбрана стратегия:
Таблица 1 была найдена путем выбора на каждом этапе тестового шаблона, который минимизирует максимальное количество оставшихся возможностей, над всеми возможными ответами создателя кода.Если этот минимум может быть достигнут с помощью «действительного» паттерна (паттерна, который делает возможным «четыре черных удара»), следует использовать действительный.В соответствии с этим условием был выбран первый такой тестовый шаблон в числовом порядке.К счастью, эта процедура гарантирует победу за пять ходов.
Так что это в некоторой степени жадная стратегия (попытка добиться наибольшего прогресса на каждом шаге, а не в целом), и, кроме того, естьспециальная стратегия разрыва связей.Это означает, что он не должен быть оптимальным по ожидаемому значению, и действительно Кнут говорит именно то, что:
Стратегия в Таблице 1 не является оптимальной с точки зрения «ожидаемого количества ходов», но этонаверное очень близкоОдна строка, которую можно улучшить [...]
Так что уже во время публикации статьи Кнут знал, что она не оптимальна, и даже имел явный пример.
Когда этот документ был переиздан в его сборнике Избранные статьи о развлечениях и играх (2010), он добавляет 5-страничное дополнение к 6-страничному документу.В этом добавлении он начинает с упоминания рандомизации в самом первом абзаце и обсуждает вопрос минимизации ожидаемого числа ходов.Анализируя его как сумму всех ходов, сделанных по всем 1296 возможным кодовым словам, он упоминает несколько статей:
Его оригинальный алгоритм дал 5801 (среднее значение 5801/1296 ≈ 4.47608), инезначительное улучшение дает 5800 (≈ 4,4753).
Роберт У. Ирвинг, «На пути к оптимальной стратегии Mastermind», журнал Recreational Matmatics 11 (1978), 81-87 [во время пребывания в«максимум 5» достигает 5664 ⇒ ≈4,37]
E.Нойвирт, «Некоторые стратегии для Mastermind», Zeitschrift fur Research Research 26 (1982), B257-B278 [достигает 5658 ⇒ ≈4.3657]
Кэндзи Кояма и Тони В. Лай, «Anоптимальная стратегия Mastermind », журнал Recreational Matmatics 25 (1993), 251-256 [achieves 5626 ⇒ ≈4.34104938]
Последнее из них является наилучшим из возможных, как было найдено сисчерпывающий поиск в глубину.(Обратите внимание, что все эти документы могут работать немного лучше в ожидаемом количестве ходов, если вы позволяете им иногда делать 6 ходов ... Я дал числа с ограничением «не более 5», потому что это то, о чем здесь задается вопрос.)
Вы можете сделать это более общим (более сложным), предполагая, что создатель кода является состязательным и не выбирает равномерно случайным образом среди 1296 возможных кодовых слов, но в зависимости от того, какое распределение будет затруднять работу нарушителя кода.Наконец, он упоминает о большой работе, проделанной Томом Нестором, которая окончательно решает многие из таких вопросов.
Вы можете повеселиться, пытаясь проследить или воспроизвести эти результаты (например, написать исчерпывающую программу поиска).Наслаждайтесь!