Игра быки и коровы алгоритм решения

Правила игры изложены в отдельной статье, а здесь мы займёмся изучением вопроса оптимального алгоритма поиска числа противника в игре быки и коровы. И так, есть общие принципы как следует задавать вопросы:

  • Вопрос должен быть таким, чтобы ответ был максимально информативен.
  • Категорически избегаем повторений. Нет нужды спрашивать то, что мы уже знаем.
  • Немного везения как никогда будет кстати.

Сколько комбинаций цифр можно составить? Первую цифру можно загадать десятью способами, вторую девятью и тд. И получаем 10*9*8*7 = 5040. Вот это общее количество комбинаций. А вариантов ответов может быть всего 14, они все показаны на рисунке.

В приведённой таблице рассмотрены все варианты ответов. Самый желанный и вкусный — это 4 быка, то есть сразу выигрыш. И такой вариант один. Самый вариативный это 1 корова — имеет 1440 вариантов расстановки цифр. По большому счёту наши дальнейшие шаги буде определять наш первый ход. А тут мы может положиться только на нашу удачу, расположение звёзд, расставленной мебели по фен-шую и наличию кофе. То есть любую комбинацию цифр. И по полученному ответу мы планируем дальнейшие шаги. Рассмотрим варианты, кроме 4быков:

  • 0 быков, 0 коров — это тоже вполне удачный ход! Эти цифры сразу исключаем из угадываемого числа, но можем использовать для выявления быков.
  • 1 бык или 1 корова — то есть мы нашли одну цифру, но какая она не ясно.
  • 1 бык и 1 корова, или 2 быка или 2 коровы — нашли 2 цифры.
  • 3 быка и 0 коров, 2 быка и 1 корова, 1 бык 2 коровы. Нашли 3 цифры, но самый желанный — это три быка, всего 24 комбинации! На практике 4 хода.
  • 2 быка и 2 коровы, 1 бык и 3 коровы, 4 коровы — то есть мы нашли все цифры. Здесь мы можем кричать ура, так как выигрыш считайте у нас в кармане! Самое большее 9 комбинаций!

Дальнейшую стратегию рассмотрим на примерах игры, так будет гораздо наглядней и проще.

Первый пример

На первый вопрос 1234 мы получили ответ одна корова. Вторым вопросом была комбинация 5678. И тут удача — два быка и одна корова. Логика третьего хода следующая: мы угадали три цифры, нужно определить их расположение. И мы точно знаем что цифра 9 и 0 отсутствуют в загаданном числе. Потому берём две цифры из второго вопроса, но ставим на другие места и доставляем 0 и 9.

Получаем такой вопрос: 7890, на который мы получили ответ 2 коровы. Поздравляем — мы точно определили 2 быка: 7 на третьем месте, 8 на четвёртом. Далее мы знаем что 5 или 6 точно есть в загаданном числе. Уберём одно и поставим на другое место. Последнее число возьмём из первого вопроса, тут без разницы какое — чистое везение. Получаем такой вопрос — 4578. И радуемся победе, мы отгадали, ответ четыре быка!

Второй пример

На первый вопрос 0123 мы получили ответ 1 бык, 2 коровы. Вторым вопросом задаём 4567. Получаем в ответе 1 корова. Всё, мы снова исключили две цифры — это 8 и 9. И теперь мы возьмём две цифры с первого вопроса и как обычно поставим на другое место, добавим 8 и 9.

Получился такой вопрос 2389, ответ на который был одна корова. Казалось бы результат так себе, но не тут-то было! Скомбинируем третий вопрос так — возьмём ноль с первого вопроса, но менять его место не будем, возьмём двойку с третьего и поставим на второе и разбавим несуществующими. Вот что получили: 0289. Ответом было два быка! Теперь тройку тоже вычеркнем, а это значит, что единичка точно в числе есть. Теперь осталось всего два варианта и мы выбираем 0215. И получаем 4 быка! Пятёрочка — это чистое везение.

Третий пример

В первый раз спросим 9012. Получаем 2 коровы. Второй вопрос — 3456 — тоже две коровы. Так, 7 и 8 исключаем. Теперь перетасовываем второй вопрос и уберём одну, заменив на семерку. Получаем такой вариант : 6573. Ответ — одна корова. Что мы поняли? Цифра 4 точно есть и получили расположения, где цифры 3, 5 и 6 точно не стоят.

Четвёртый вопрос формируем так — комбинируем третий и первый вопрос, меняя местами. Вот какую комбинацию мы получили — 1234. Ответ — три быка. 3 и 4 стоят на своих местах, проверяем только первые цифры. 9234 — ответом на него было 2 быка, одна корова. Всё, мы нашли число! 1934.

Читайте также:  Запуск этого устройства невозможен код 10 атол

Четвёртый пример

Первый вариант у нас 4590, ответ — один бык. Второй ход 1236 и ответ три коровы. Снова 7 и 8 вне игры. На третьем ходу тасуем цифры третьего вопроса и разбавляем 7. 7263, что даёт нам снова 3 коровы. Значит единичку выбрасываем.

Теперь нам нужно правильно расположить наших коров и найти быка с первого вопроса. Задаём такой вариант — 4623, ответ на него два быка и одна корова. Значит не четвёрка. Тройку мы не меняли и потому точно можем сказать, что именно тройка не на своём месте! Пробуем ещё раз — 3620. И бинго. Мы разгадали число!

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

Я старался в кратце описать ход своих мыслей при игре в быков и коров. Конечно, у каждого свой стиль игры. и многое зависит от везения. И на последок, удачи Вам и приятной игры.

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

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

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

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

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

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

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

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

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

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

Когда я поступил в институте, очень популярной была игра «Быки и коровы». Так совпало, что в это же время я прочитал математическую новеллу Альфреда Реньи «Дневник. — Записки студента по теории информации». Благодаря этой статье я познакомился с основами теории информации. И у меня родилась идея, как улучшить свои показатели в «Быках и коровах», опираясь на новые знания [1].

Кратко напомню правила. Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами (первой может быть и ноль). Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику в виде вопроса. Противник говорит в ответ, сколько цифр угадано с совпадением их позиций в тайном числе и сколько угадано без совпадения. Например: задумано тайное число 3219; попытка (вопрос) 2310; результат (ответ): один «бык» (цифра 1 из вопроса входит в тайное число и стоит на своем месте) и две «коровы» (цифры 2 и 3 из вопроса входят в тайное число, но стоят не на своем месте). Ответ сообщается в виде 2-значного числа. В нашем примере ответ — 12 (один «бык», две «коровы»). Игроки делают попытки по очереди. Побеждает тот, кто первым получит на свой вопрос ответ 40.

Читайте также:  Возникла ошибка код ошибки 0

Скачать заметку в формате Word или pdf, примеры в формате Excel, пример Неоптимальный второй вопрос в формате zip (внутри Excel-файл на 57МВ).

Рекомендую скачивать после прочтения соответствующего места заметки, и только если поймете, что вам хочется изучить детали.

Вот какие идеи теории информации мне показались полезными для улучшения показателей в игре (см. Введение в теорию информации):

  1. Вопрос нужно задавать так, чтобы ответ на него давал максимальное количество информации.
  2. Для этого вопрос нужно формировать так, чтобы вероятности различных ответов были по возможности близкими.
  3. Кроме того, вопрос должен быть таким, чтобы ответ на него не содержал информацию, полученную ранее из предыдущих вопросов.

Для лучшего понимания материала полезно также открыть Excel-файл.

1. Тайное число можно задумать 10*9*8*7 = 5040 способами (на первом месте может стоять любая из 10 цифр, на втором — любая из 9 оставшихся и т.д.). Для того, чтобы сформировать массив допустимых чисел я использовал простые алгоритмы в Excelе (см. листы «Подг1» и «Подг2»). Поскольку вероятность быть задуманным любого из 5040 чисел одинакова, неопределенность (Н) вычисляется по формуле Хартли: Н = log2N. Перед началом игры неопределенность составляет log25040 = 12,30 бит информации.

2. Понятно, что первый вопрос может быть любым, например, 0123. На него возможны 14 ответов (см. также лист «Вопрос1» Excel-файла):

Ответ Число ответов р H h
00 360 7,1% 8,49 3,81
01 1440 28,6% 10,49 1,81
02 1260 25,0% 10,30 2,00
03 264 5,2% 8,04 4,25
04 9 0,2% 3,17 9,13
10 480 9,5% 8,91 3,39
11 720 14,3% 9,49 2,81
12 216 4,3% 7,75 4,54
13 8 0,2% 3,00 9,30
20 180 3,6% 7,49 4,81
21 72 1,4% 6,17 6,13
22 6 0,1% 2,58 9,71
30 24 0,5% 4,58 7,71
40 1 0,02% 0,00 12,30
5040 100,0% 12,30 2,77

Здесь: р — вероятность ответа, Н — неопределенность, оставшаяся после соответствующего ответа, h — количество информации, полученное, если реализовался тот или иной ответ. Наиболее вероятный ответ — 01, означающий, что из вопроса в тайное число входит лишь одна цифра, причем стоит она не на своем месте. Ответ 01 подразумевает, что задуманным может быть одно из 1440 чисел, то есть неопределенность, оставшаяся после этого ответа, составляет log21440 = 10,49 бит, а информация, полученная при таком ответе 12,30 — 10,49 = 1,81 бит. Ответ 40 дает 12,30 бит информации, а неопределенности после него не остается J Поскольку вероятности ответов различны, количество информации, содержащееся в вопросе определяется по формуле Шеннона: Н(x) = p1log2(1/p1) + p2log2(1/p2) + … + pNlog2(1/pN). Первый вопрос приносит 2,77 бит информации.

3. При выборе второго вопроса следует руководствоваться тремя идеями сформулированными выше. На практике это означает, что вопрос должен допускать ответ 40.

Правило формирования второго вопроса. Пусть на первый вопрос (0123) мы получили ответ 01. Для второго вопроса возьмем одну цифру из первого вопроса, поставим ее на новое место и добавим три новые цифры. Получим, например, 4561. Если на вопрос1 был получен, например, ответ 11, надо взять две цифры из первого вопроса, одну оставить на своем месте, вторую поставить на новое место, и добавить две новые цифры; например, 0435.

На вопрос2 4561 также возможны 14 ответов (см. лист «Вопрос2»):

Ответ Число ответов р H h
00 54 3,8% 5,75 4,74
01 378 26,3% 8,56 1,93
02 369 25,6% 8,53 1,96
03 91 6,3% 6,51 3,98
04 6 0,4% 2,58 7,91
10 126 8,8% 6,98 3,51
11 222 15,4% 7,79 2,70
12 83 5,8% 6,38 4,12
13 6 0,4% 2,58 7,91
20 57 4,0% 5,83 4,66
21 31 2,2% 4,95 5,54
22 5 0,3% 2,32 8,17
30 11 0,8% 3,46 7,03
40 1 0,07% 0,00 10,49
1440 100,0% 10,49 2,86

Выбранный нами второй вопрос принес 2,86 бита информации. Посмотрим, сколько информации дадут другие вторые вопросы. Для этих целей я создал отдельный файл «Неоптимальный второй вопрос.xlsx» (он «весит» 58МВ, поэтому будьте с ним аккуратнее :)). Второй вопрос может быть одним из 5040 возможных чисел (в том числе и повторение первого вопроса). В итоге этого исследования я получил количество информации, которое дают те или иные вторые вопросы (напомню, что анализ сделан в предположении, что первый вопрос 0123 дал ответ 01). Например, вопрос2 — 0123 дает ноль битов информации, так как на него возможен только один ответ 01, а (для N = 1) log21 = 0. Вопрос2 0132 дает 0,65 бит информации, вопрос2 0148 — 2,53 бита информации. Максимальное количество информации дают 1440 вторых вопросов, сформированных по выше описанному правилу. Результаты исследования я перенес на лист «Разные вопросы2» файла «Быки-коровы.xlsx» и далее буду говорить только об этом файле.

Читайте также:  Значок вайбер для визитки

Как я уже сказал, максимальное количество информации — 2,859 — будет получено на вопрос2, подготовленный следующим образом: надо взять одну цифру из первого вопроса, поставить ее на новое место и добавить три новые цифры:

Информация от вопроса2, бит Число таких вопросов
0,000 1
0,650 6
0,811 8
0,918 9
1,899 24
2,104 72
2,258 144
2,268 72
2,365 216
2,372 48
2,530 180
2,624 360
2,664 720
2,756 360
2,766 480
2,767 720
2,774 180
2,859 1440
Итого 5040

Видно, что еще 180 вопросов дают почти столько же информации — 2,774 бита. Такое количество информации будет получено при ответе, например, на вопрос 1045 (см. лист «Вопрос2неопт»). Но этот вопрос не может дать ответа 40! То есть, вопрос подготовлен с нарушением сформулированного правила. Насколько велика разница в информации между 2,859 и 2,774 бита!? На первый взгляд она не выглядит большой. С другой стороны, при самом неблагоприятном ответе на вопрос2 4561 (01) останется 378 вариантов тайного числа, а при самом неблагоприятном ответе на вопрос2 1045 (также 01) — 408 вариантов. На 8% больше! Это и есть цена неоптимального вопроса.

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

Пример1. Первые два вопроса и ответа были следующими:

Вопрос1 0123 Ответ1 01
Вопрос2 4561 Ответ2 01

Первый вариант: входит единица, тогда не входят, ни 023, ни 456; то есть входят, не использовавшиеся в первых двух вопросах, цифры — 789. Получаем набор цифр тайного числа 1789 (порядок их расположения любой, удовлетворяющий ответам на первые два вопроса). Вариантов, отвечающих этому набору, 12.

Второй вариант: единица не входит, тогда входит одна цифра из 023, одна — из 456, и две — из 789. Записываю я это так:

Ориентировочное число вариантов набора цифр равняется 3 (одна из 023) * 3 (одна из 456) * 3 (две из 789) = 27. А с учетом мест расположения цифр вариантов существенно более 100. Для вопроса3 берем одну цифру из 023, одну из 456, две из 789. Располагаем цифры так, чтобы не было совпадений мест расположения с вопросом1 и вопросом2. Более того, располагаем цифры, которые ранее уже встречались (4 и 2) на совершенно новых местах, то есть на 2-м или 4-м. Например, вопрос3 7482 лучше, чем 2784. Так как в первом случае 4-ка и 2-ка стоят на местах, которые в вопросе1 и вопрос2 они не занимали. В то же время, в вопросе3 2784 цифра 2 стоит на месте 4-ки из вопроса2 (см. лист «Вопрос3»). Ответ на вопрос3 4782 содержит 2,958 бит информации, а ответ на вопрос 3 2784 — «только» 2,955.

Пример2. Первые два вопроса и ответа были следующими:

Вопрос1 0123 Ответ1 02
Вопрос2 3541 Ответ2 02

Первый вариант: входят 13, тогда не входят, ни 02, ни 45, а из оставшихся цифр входят две:

Количество тайных числе в варианте1 — 48.

Второй вариант: входит одна цифра из 13, тогда входит одна — из 02, одна — из 45, и одна — из 6789:

Ориентировочное количество тайных чисел в варианте2 — более 100.

Третий вариант: не входят 13, тогда входят и 02, и 45: 0245. Количество тайных чисел в варианте3 — 8.

Итак для вопроса3 выбираем число из варианта2, например, 1705.

5. Когда тайных чисел остается мало (от 4 до 10…20), я перехожу на полный перебор всех возможных вариантов.

Играйте с алгоритмом, построенным на основе теории информации, и выигрывайте!

Дополнение от 14 февраля 2015 г.

Нурым Кенжебеков написал программу, позволяющую играть с компьютером. Программа работает под Windows 7, 8, 8.1 с установленным Framework 4.5. Игра мне очень понравилась, но алгоритм явно далек от оптимального. Я сыграл трижды и все три раза выиграл.

Оцените статью
Adblock detector