Комп’ютерний алгоритм гри бики й корови (третя частина) в розділі математичні ігри

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

У третьому стовпці зазначено кількість чисел, які можуть дати відповідну відповідь на першому ходу. Найприємніший відповідь, звичайно, 4б, відразу закінчують гру. Як ми бачимо, найбільша різноманітність можливих чисел залишається при відповіді 1к- 1440.

Зрозуміло, результат гри, тобто кількість ходів, за яке відгадувати задумане число, в якійсь мірі залежить від випадку. Але багато що визначається і мистецтвом грають. Тут виникає питання: що розуміти під майстерністю гри в «бики й корови»? Адже навіть початківець гравець вже першим ходом може випадково відгадати задумане число, але це ще не говорить про його умінні.

Припустимо, гравці А і Б зіграли матч з трьох партій.

Гравець А у всіх трьох партіях відгадав число партнера з 5 ходів. Гравець В двох партіях відгадав число за 4 ходи, а в одній за 9. Хто грає краще? Гравець Б виграв матч з рахунком 2: 1, але ж загальне число ходів у нього більше. Якщо, скажімо, в шахах важлива сама перемога незалежно від тривалості партії, то в «биків і корів» саме швидкість відгадування, кількість витрачених ходів власне і складають результат гри.

Розглянемо два найбільш цікавих підходу до оцінки сили гри в «бики й корови». Позначимо через l i число ходів, за яке даний гравець відгадує число з номером i (i пробігає значення від 1 до 5040).

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

де lср - середнє число ходів, за яке гравець відгадує число, а lмакс - число ходів, яке гарантуватиме йому розкриття шифру.

У грі людей завжди легко розібратися, хто сильніший. Інша справа, коли мова йде про ЕОМ. Для довільної стратегії гри, сформульованої у вигляді деякого алгоритму, можна обчислити числа lср і lмакс і, отже, в залежності від критерію визначити, яка програма для ЕОМ сильніше.

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