игрыстатьиматематические программырусский языкразноеоб авторе

Оптимальные алгоритмы в играх быки-коровы и мастермайнд

en

Быки-коровы и мастермайнд - популярные логические игры для двоих. Проект рассматривает оптимизацию этих игр по двух критериям.

Первый критерий оптимизации

Быки и коровы. Известно, что не существует алгоритма, который может угадать любые загаданные номера не более чем за шесть ходов и существуют алгоритмы, которые могут отгадать все номера не более чем за семь ходов. Цель первого критерия найти и построить алгоритм, который минимизирует число номеров, угадываемых ровно за семь ходов. При этом все остальные номера должны угадываться не более чем за шесть ходов. Оптимальный алгоритм угадывает пятьдесят номеров за семь ходов, остальные за шесть и менее. Смотрите результаты алгоритма crushBullsCows.

Мастермайнд. Известно, что не существует алгоритма, который может угадать любые загаданные номера не более чем за четыре хода и существуют алгоритмы, которые могут отгадать все номера не более чем за пять ходов. Цель первого критерия найти и построить алгоритм, который минимизирует число номеров, угадываемых ровно за пять ходов. При этом все остальные номера должны угадываться не более чем за четыре хода. Оптимальный алгоритм угадывает 539 номеров за пять ходов, остальные за четыре и менее. Смотрите результаты алгоритма crushMastermind.

Второй критерий оптимизации

Быки и коровы. Второй критерий оптимизации состоит в том, чтобы минимизировать среднее число ходов для угадывания неизвестного номера - минимизация средней длины игры. Минимальная длина игры равна 26274/5040=5.21 хода. Смотрите результаты алгоритма avgBullsCows.

Мастермайнд. Второй критерий оптимизации состоит в том, чтобы минимизировать среднее число ходов для угадывания неизвестного номера - минимизация средней длины игры. Минимальная длина игры равна 5626/1296=4.34, если делать максимум пять ходов. Смотрите результаты алгоритма avgMastermind5. Минимальная длина игры равна 5625/1296=4.34 если число ходов произвольно (достаточно шести). Смотрите результаты оптимального алгоритма avgMastermind.

Для всех алгоритмов построены деревья на языке javascript и посчитана статистика. Можно поиграть online, используя один из оптимальных алгоритмов. Также создана статья, которая содержит описание теории, описание программирования алгоритмов, и результаты.