Разработка оптимальной стратегии игры «Быки и коровы» на основе теории информации

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

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

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

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

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

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

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

1. Тайное число можно задумать 10*9*8*7 = 5040 способами (на первом месте может стоять любая из 10 цифр, на втором – любая из 9 оставшихся и т.д.). Для того, чтобы сформировать массив допустимых чисел я использовал простые алгоритмы в Excelе (см. листы «Подг1» и «Подг2»). Поскольку вероятность быть задуманным любого из 5040 чисел одинакова, неопределенность (Н) вычисляется по формуле Хартли: Н = log₂N. Перед началом игры неопределенность составляет log₂5040 = 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 чисел, то есть неопределенность, оставшаяся после этого ответа, составляет log₂1440 = 10,49 бит, а информация, полученная при таком ответе 12,30 – 10,49 = 1,81 бит. Ответ 40 дает 12,30 бит информации, а неопределенности после него не остается J Поскольку вероятности ответов различны, количество информации, содержащееся в вопросе определяется по формуле Шеннона: Н(x) = p₁log₂(1/p₁) + p₂log₂(1/p₂) + … + p_Nlog₂(1/p_N). Первый вопрос приносит 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) log₂1 = 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. Игра мне очень понравилась, но алгоритм явно далек от оптимального. Я сыграл трижды и все три раза выиграл.

Скачать программу в формате архива.

---

[1] http://slovesnov.narod.ru/articles/bullcow.pdf. Сказать по правде, мне не удалось ее осилить 🙂 Но упоминаний теории информации при беглом просмотре я в ней не нашел…