Быки и коровы

[Joker90]

Здравствуйте всем!

Простенькая игра:
Один из участников загадывает четырехзначное число. Цифры в нем повторяться не должны.

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

Результат отгадывания выражается в условных единицах - Быках и Коровах. Бык - цифра входит в число и стоит на своем месте. Корова - цифра входит в число, но находится не на своем месте.

Кто-нибудь считал? Какова вероятность определить число с 2-х попыток? с 3-х? с 4-х? с 5-и? с 6-и? Сколько попыток нужно, чтобы вероятность определения числа была равна 1?

Естественно, при оптимальной стратегии игры.

[Руст]

Число можеть начаться с 0?

[Joker90]

Руст писал(а):

Число можеть начаться с 0?

Да

[Руст]

Соответственно количество возможных расстановок 210*24=5040. Это достаточно много, для разбора стратегий в ручную. К тому же есть определённые приорететы у людей, т.е. не все варианты у них встречаются одинаково часто. Они могут приспособиться и к определённой стратегии угадывания. Соответственно требуется не единая стратегия, а некоторая минимаксная. Поэтому можно решать толко задачи попроще, искать не оптимальную стратегию, а некоторую, гарантирующую почти всегда достичь угадывания скажем за 15 ходов.

[Joker90]

Руст писал(а):

Соответственно количество возможных расстановок 210*24=5040. Это достаточно много, для разбора стратегий в ручную. К тому же есть определённые приорететы у людей, т.е. не все варианты у них встречаются одинаково часто. Они могут приспособиться и к определённой стратегии угадывания. Соответственно требуется не единая стратегия, а некоторая минимаксная. Поэтому можно решать толко задачи попроще, искать не оптимальную стратегию, а некоторую, гарантирующую почти всегда достичь угадывания скажем за 15 ходов.

Вроде формула есть, где-то на форуме болтается даже. Из нее следует, что явно меньше 15 ходов.
+
Вопрос-то не в этом.

[evgeny]

Эта игра очень хорошо и давно известна. По английски она называется MasterMind.
Только т.к. она для детей, то вместо цифр цвета.
в 70-е Кнут писал про стратегии для этой игры (4-х значные числа с цифрами 0..5)

Прежде чем искать оптимальную стратегию, надо определиться как сравнивать две стратегии.
Два наиболее типичных подхода - в средний и худший случай, т.е. сколько вопросов в среднем и сколько вопросов потребуется в худшем случае.
Чаще всего оптимальные стратегии при этих двух подходах различны.
Но даже выбрав способ сравнения, может возникнуть ситуация, когда сразу несколько стратегий оптимальны, в этом случае Ваш вопрос (про вероятность отгадать за k ходов) может быть некоректен - у разных оптимальных стратегий ответы могут отличаться.

Оптимальную стратегия (она очевидно есть в силу конечности игры) науке не известна, так что наличие каких-либо формул сомнительно
Например, Кнут предлагает стратегию с $4.478$ вопросов в среднем (для 6 цветов).

Вроде как для Вашей игры можно построить стратегию, с не более чем 8 вопросами в худшем случае

[Joker90]

evgeny писал(а):

Эта игра очень хорошо и давно известна. По английски она называется MasterMind.
Только т.к. она для детей, то вместо цифр цвета.
в 70-е Кнут писал про стратегии для этой игры (4-х значные числа с цифрами 0..5)

Прежде чем искать оптимальную стратегию, надо определиться как сравнивать две стратегии.
Два наиболее типичных подхода - в средний и худший случай, т.е. сколько вопросов в среднем и сколько вопросов потребуется в худшем случае.
Чаще всего оптимальные стратегии при этих двух подходах различны.
Но даже выбрав способ сравнения, может возникнуть ситуация, когда сразу несколько стратегий оптимальны, в этом случае Ваш вопрос (про вероятность отгадать за k ходов) может быть некоректен - у разных оптимальных стратегий ответы могут отличаться.

Оптимальную стратегия (она очевидно есть в силу конечности игры) науке не известна, так что наличие каких-либо формул сомнительно
Например, Кнут предлагает стратегию с $4.478$ вопросов в среднем (для 6 цветов).

Вроде как для Вашей игры можно построить стратегию, с не более чем 8 вопросами в худшем случае

Спасибо. И всё-таки?
Если максимум нужно 8 ходов, при этом р=1, то при 7-и ходах какова вероятность? При 6-и? При 5-и? И т. д. Хотя бы ориентировочно.

[незваный гость]

Я уже не помню подсчетов в точности, но, по-моему, было достаточно 6 ходов. Существует детали, связанные, например, с тем, можно ли в вопросе повторять цифры.

Ответ на вопрос дать затруднительно, поскольку он сильно зависит от стратегии угадывающего. Предположим угадывающий избирает стратегию, направленную на гарантированное угадывание за 6 ходов. Он сделал 3 хода. Дальше у него есть выбор -- сделать ли ход, оптимизирующий угаывание на следующем ходе, или сделать ход, гарантирующий угадывание за 6 ходов. Маловероятно, что эти варианты дадут один и тот же ход. Поэтому можно ставить вопрос о угадывании на $n$-ом ходу при конкретной стратегии угадывания. $P\{n \leqslant 1\} = \frac1{5040}$, $P\{n \leqslant 6\} = 1$

Сравнивая с Mastermind, полезно иметь в виду, что в Mastermind разрешены повторения. Поэтому там возможно 1296 вариантов.

А вообще считать неинтересно. Задача с полной информацией, доступным PC конечным перебором, и непонятной математической ценностью.

[Joker90]

незваный гость писал(а):

$P\{n \leqslant 1\} = \frac1{5040}$, $P\{n \leqslant 6\} = 1$
Сравнивая с Mastermind, полезно иметь в виду, что в Mastermind разрешены повторения. Поэтому там возможно 1296 вариантов.

??? Вроде при разрешенных повторах должно быть больше вариантов? Разве 1296>5040?

незваный гость писал(а):

твет на вопрос дать затруднительно, поскольку он сильно зависит от стратегии угадывающего. Если угадывающий избирает стратегию, направленную на гарантированное угадывание за 6 ходов. Он сделал 3 хода. Дальше у него есть выбор -- сделать ли ход, оптимизирующий угаывание на следующем ходе, или сделать ход, гарантирующий угадывание за 6 ходов. Маловероятно, что эти варианты дадут один и тот же ход. Поэтому можно ставить вопрос о угадывании на $n$-ом ходу при конкретной стратегии угадывания.
А вообще считать неинтересно. Задача с полной информацией, конечным перебором доступным PC, и непонятной математической ценностью.

Странно...Подсчитать полную вероятность при ВСЕХ стратегиях, т.е. не зависящую от стратегий - разве это тривиально?

[незваный гость]

Joker90 писал(а):

??? Вроде при разрешенных повторах должно быть больше вариантов? Разве 1296>5040?

В Mastermind традиционно 6 цветов, в Быках и коровах -- десять цифр.

Joker90 писал(а):

Подсчитать полную вероятность при ВСЕХ стратегиях

Интересно, как Вы это понимаете "вероятность при ВСЕХ стратегиях"? И я не сказал тривиально -- я сказал неинтересно.

[Joker90]

незваный гость писал(а):

Joker90 писал(а):

Подсчитать полную вероятность при ВСЕХ стратегиях

Интересно, как Вы это понимаете "вероятность при ВСЕХ стратегиях"? И я не сказал тривиально -- я сказал неинтересно.

Очевидно, что НАИБОЛЬШАЯ вероятность и будет вероятностью для вСЕХ стратегий.
Например, при стратегии 1 вероятность отгадать за n ходов будет Р1, для стратегии 2=Р2.
Какая больше - та и будет для ВСЕХ.

[незваный гость]

А-а-а-а. Так это называется не полная вероятность, а максимальная вероятность (по стратегиям).

[Someone]

незваный гость писал(а):

И я не сказал тривиально -- я сказал неинтересно.

"Тривиальный" означает "неоригинальный", "неинтересный".

[незваный гость]

Виноват-с, off-topic это.

Someone писал(а):

"Тривиальный" означает "неоригинальный", "неинтересный".

Быть может.
У нас (на Матмехе) в основном имело значение "имеющий короткое сразу приходящее на ум решение". То есть, например, длинное техническое решение не было тривиальным. Технически тривиальный корень (тривиальное решение) -- специальное решение, часто не отражающее свойств общего решения (в выражениях, подобных "$x(t) = 0$ -- тривиальное решение $x'(t) = a \, x(t)$").

[Joker90]

Есть прога, которая за 6 ходов решает. Правда ли?