Бики та коровиЯк відгадати число за 5–7 ходів
У грі «Бики та корови» везіння вирішує менше, ніж здається. Добрий хід не обов’язково вгадує цифри, зате сильно скорочує список чисел, які ще можуть бути відповіддю. Нижче дані нашого бота: він зіграв усі 5040 можливих чисел.
Скільки ходів потрібно боту
У середньому боту потрібно 5,27 ходу. За п’ять ходів або швидше він відгадує 61% чисел, за шість 98%, і жодного разу не витрачає більше ніж 7 ходів.
| Ходів | Чисел | Частка |
|---|---|---|
| 1 | 1 | менше 0,1% |
| 2 | 4 | менше 0,1% |
| 3 | 59 | 1,2% |
| 4 | 574 | 11,4% |
| 5 | 2430 | 48,2% |
| 6 | 1885 | 37,4% |
| 7 | 87 | 1,7% |
Для порівняння: повний комп’ютерний перебір усіх стратегій показує, що в середньому грати краще ніж за 5,21 ходу неможливо. Бот відстає від ідеалу менш ніж на десяту частку ходу, і при цьому його логіку можна пояснити одним реченням.
Головна ідея: ділити варіанти порівну
Кожна відповідь розбиває решту чисел на групи. Якщо майже всі варіанти дають однакову відповідь, хід майже нічого не повідомляє. Якщо ж групи приблизно рівні, хоч яка відповідь прийде, варіантів залишиться мало. Бот на кожному ході перебирає всі 5040 чисел і обирає те, після якого в середньому залишиться найменше кандидатів. За тією ж логікою розбір після гри позначає найкращі ходи.
Перший хід
Поки нічого не відомо, усі перші ходи однаково добрі: будь-яке число перетворюється на 0123 простою заміною цифр. Після першого ходу в середньому залишається близько 931 варіанта. Ось як розподіляються відповіді на 0123:
| Відповідь | Чисел |
|---|---|
| 0 биків, 1 корова | 1440 |
| 0 биків, 2 корови | 1260 |
| 1 бик, 1 корова | 720 |
| 1 бик, 0 корів | 480 |
| 0 биків, 0 корів | 360 |
| 0 биків, 3 корови | 264 |
| 1 бик, 2 корови | 216 |
| 2 бики, 0 корів | 180 |
| 2 бики, 1 корова | 72 |
| 3 бики, 0 корів | 24 |
| 0 биків, 4 корови | 9 |
| 1 бик, 3 корови | 8 |
| 2 бики, 2 корови | 6 |
| 4 бики, 0 корів | 1 |
Найчастіше приходить одна або дві корови. Відповідь «0 биків, 0 корів» насправді вдала: вона одразу прибирає чотири цифри, і залишається 360 чисел.
Другий і третій хід
- Бери нові цифри. Другий хід на кшталт 4567 зазвичай корисніший за перестановку тих самих 0123: так дізнаєшся, скільки загаданих цифр ховається в іншій четвірці, а отже, і в парі 8 і 9, що залишилася.
- Змішуй старе й нове. Коли відомо, що серед 0123 є дві цифри із загаданого числа, хід із двох старих і двох нових цифр допомагає зрозуміти, які саме.
- Не бійся ходів, які не можуть бути відповіддю. Іноді число, яке точно не підходить під попередні відповіді, ділить варіанти краще за будь-яке підхоже. Бот так і робить.
Позиції важливіші за цифри
Коли набір цифр зрозумілий, залишається з’ясувати порядок: чотири цифри можна розставити 24 способами. Не забувай, що хід без биків теж дещо каже про позиції: жодна з його цифр не стоїть на своєму місці. Це одразу викреслює частину перестановок, і до відповіді часто залишається два-три ходи.
Записуй висновки
Закреслюй цифри, яких точно немає, позначай ті, що точно є, і прикидай, яка на якому місці стоїть: для цього є блокнот. А потренуватися без ризику для серії можна на тренуванні.