Быки и коровыКак отгадать число за 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 способами. Не забывай, что ход без быков тоже говорит о позициях: ни одна из его цифр не стоит на своём месте. Это сразу вычёркивает часть перестановок, и до ответа часто остаётся два-три хода.
Записывай выводы
Зачёркивай цифры, которых точно нет, отмечай те, что точно есть, и прикидывай, на каком месте какая стоит: для этого есть блокнот. А потренироваться без риска для серии можно в тренировке.