logo

Математические игры - компьютерный алгоритм игры Быки и Коровы (часть третья)


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

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

Загадывая число в «быках и коровах», его первую цифру можно выбрать десятью способами, вторую — девятью (одна цифра занята), третью — восемью, наконец, четвертую — семью, всего имеем 10X9X8X7 = 5040 различных чисел. В мастермайнде на любом месте может стоять колышек любого цвета (из шести возможных), то есть всего 6^4= 1296 вариантов.

Итак, в «быках и коровах» имеется 5040 различных чисел, которые можно загадывать и которыми можно ходить. А сколько существует различных ответов? Все они указаны во втором столбце таблицы (рис. 2), их 14 (очевидно, ответ 3б 1к невозможен). Горизонтальной чертой в таблице разделены случаи, в которых обнаружены все четыре цифры, три цифры, две, одна и ни одной.

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

Разумеется, результат игры, то есть количество ходов, за которое отгадывается задуманное число, в какой-то степени зависит от случая. Но многое определяется и искусством играющих. Здесь возникает вопрос: что понимать под мастерством игры в «быки и коровы»? Ведь даже начинающий игрок уже первым ходом может случайно отгадать задуманное число, но это еще не говорит о его умении.

Предположим, игроки А и Б сыграли матч из трех партий.

Игрок А во всех трех партиях отгадал число партнера из 5 ходов. Игрок В двух партиях отгадал число за 4 хода, а в одной за 9. Кто играет лучше? Игрок Б выиграл матч со счетом 2:1, но ведь общее число ходов у него больше. Если, скажем, в шахматах важна сама победа независимо от продолжительности партии, то в «быках и коровах» именно скорость отгадывания, количество затраченных ходов собственно и составляют результат игры.

Рассмотрим два наиболее интересных подхода к оценке силы игры в «быки и коровы». Обозначим через li число ходов, за которое данный игрок отгадывает число с номером i (i пробегает значения от 1 до 5040).

Введем две характеристики его силы игры в «быки и коровы»:

Быки и Коровы - фомулы

Быки и Коровы - табл. 2Табл. 1

где lср - среднее число ходов, за которое игрок отгадывает число, а lмакс — число ходов, гарантирующее ему раскрытие шифра.

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

В игре людей всегда легко разобраться, кто сильнее. Другое дело, когда речь идет об ЭВМ. Для произвольной стратегии игры, сформулированной в виде некоторого алгоритма, можно вычислить числа lср и lмакс и, значит, в зависимости от критерия определить, какая программа для ЭВМ сильнее.

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

Если говорить об lср, то здесь полной ясности цока нет. Найдены стратегии, которые для мастермайнда дают значение lср чуть меньше 4, а для «быков и коров» — чуть больше 5, но вопрос об оптимальных алгоритмах остается открытым.

Что же касается числа lмакс, представляющего больший интерес, то проблема полностью решена. Для мастермайнда построен наилучший алгоритм игры, при котором любое число шифровальщика разгадывается не позднее пятого хода, и доказано, что для любого другого алгоритма (стратегии) найдется хотя бы одно число, на разгадку которого уйдет не меньше пяти ходов.
Таким образом, lмакс = 5.

Конечно, нас не должен удивлять тот факт, что для «быков и коров» числа lср и lмакс больше, чем для мастермайнда, - ведь в первом случае возможных вариантов шифра почти в 4 раза больше. Впрочем, известен усложненный вариант игры супермастермайнд, в котором вместо четырех отверстий используются пять и вместо шести цветов кодовых колышков — восемь.