Как решить игру "Угадывание"?

Ответ 1

Ключевые инструменты: энтропия, жадность, ветка и граница; Python, генераторы, itertools, decorate-undecorate pattern

Отвечая на этот вопрос, я хотел создать язык полезных функций для изучения проблемы. Я буду выполнять эти функции, описывая их и их намерения. Первоначально у них были обширные документы, с небольшими встроенными модульными тестами, проверенными с использованием doctest; Я не могу высоко оценивать эту методологию как блестящий способ реализации тестовой разработки. Тем не менее, он не хорошо переводится в StackOverflow, поэтому я не буду представлять его таким образом.

Во-первых, мне понадобятся несколько стандартных модулей и будущий импорт (я работаю с Python 2.6).

from __future__ import division # No need to cast to float when dividing
import collections, itertools, math

Мне нужна функция подсчета очков. Первоначально это возвращало кортеж (черные, белые), но я нашел вывод немного яснее, если я использовал namedtuple:

Pegs = collections.namedtuple('Pegs', 'black white')
def mastermindScore(g1,g2):
  matching = len(set(g1) & set(g2))
  blacks = sum(1 for v1, v2 in itertools.izip(g1,g2) if v1 == v2)
  return Pegs(blacks, matching-blacks)

Чтобы сделать мое решение общим, я передаю все, что связано с проблемой Mastermind, как аргументы ключевого слова. Поэтому я создал функцию, которая создает эти аргументы один раз, и используйте синтаксис ** kwargs, чтобы передать его. Это также позволяет мне легко добавлять новые атрибуты, если они мне понадобятся позже. Обратите внимание, что я допускаю, чтобы догадки содержали повторы, но препятствовали оппоненту выбирать разные цвета; Чтобы изменить это, мне нужно только изменить G ниже. (Если бы я хотел разрешить повторы в секретности противника, мне также нужно было бы изменить функцию подсчета очков.)

def mastermind(colours, holes):
  return dict(
    G           = set(itertools.product(colours,repeat=holes)),
    V           = set(itertools.permutations(colours, holes)),
    score       = mastermindScore,
    endstates   = (Pegs(holes, 0),))

def mediumGame():
    return mastermind(("Yellow", "Blue", "Green", "Red", "Orange", "Purple"), 4)

Иногда мне нужно разбить набор на основе результата применения функции к каждому элементу в наборе. Например, числа 1..10 можно разбить на четные и нечетные числа функцией n% 2 (коэффициенты дают 1, evens дают 0). Следующая функция возвращает такой раздел, реализованный как карта из результата вызова функции в набор элементов, которые дали этот результат (например, {0: evens, 1: odds}).

def partition(S, func, *args, **kwargs):
  partition = collections.defaultdict(set)
  for v in S: partition[func(v, *args, **kwargs)].add(v)
  return partition

Я решил исследовать решателя, который использует жадный энтропийный подход. На каждом шаге он вычисляет информацию, которая может быть получена из каждой возможной догадки, и выбирает наиболее информативное предположение. По мере роста числа возможностей это будет сильно ухудшаться (квадратично), но давайте попробуем! Во-первых, мне нужен метод вычисления энтропии (информации) набора вероятностей. Это просто -Σp log p. Для удобства, однако, я разрешу ввод, который не нормализуется, т.е. Не складывается до 1:

def entropy(P):
  total = sum(P)
  return -sum(p*math.log(p, 2) for p in (v/total for v in P if v))

Итак, как я буду использовать эту функцию? Ну, для данного набора возможностей, V и заданного предположения, g, информация, которую мы получаем от этой догадки, может исходить только из функции подсчета очков: более конкретно, как эта функция подсчета разделяет наш набор возможностей. Мы хотим сделать предположение, что лучше всего отличает оставшиеся возможности - делит их на самое большое количество небольших множеств, потому что это означает, что мы гораздо ближе к ответу. Именно это означает, что функция энтропии выше числа: большое количество маленьких множеств будет набирать больше, чем небольшое количество больших множеств. Все, что нам нужно сделать, это включить его.

def decisionEntropy(V, g, score):
  return entropy(collections.Counter(score(gi, g) for gi in V).values())

Конечно, на любом данном шаге мы действительно будем иметь набор оставшихся возможностей V и набор возможных догадок, которые мы могли бы сделать, G, и нам нужно будет выбрать предположение, которое максимизирует энтропию. Кроме того, если несколько догадок имеют одинаковую энтропию, предпочитайте выбирать ту, которая также может быть действительным решением; это гарантирует, что подход прекратится. Для этого я использую стандартный шаблон python decorate-undecorate вместе со встроенным максимальным методом:

def bestDecision(V, G, score):
  return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2]

Теперь все, что мне нужно сделать, многократно вызывает эту функцию до тех пор, пока не будет догадаться правильный результат. Я прошел через ряд реализаций этого алгоритма, пока не нашел тот, который казался правильным. Некоторые из моих функций захотят подойти к этому по-разному: некоторые перечисляют все возможные последовательности решений (по одному на догадку, который мог сделать противник), в то время как другие интересуются только одним путем через дерево (если противник уже выбрал секрет, и мы просто пытаемся достичь решения). Мое решение - это "ленивое дерево", где каждая часть дерева является генератором, который может быть оценен или нет, что позволяет пользователю избежать дорогостоящих вычислений, которые им не понадобятся. Я также закончил использование еще двух именованных вершин, снова для ясности кода.

Node = collections.namedtuple('Node', 'decision branches')
Branch = collections.namedtuple('Branch', 'result subtree')
def lazySolutionTree(G, V, score, endstates, **kwargs):
  decision = bestDecision(V, G, score)
  branches = (Branch(result, None if result in endstates else
                   lazySolutionTree(G, pV, score=score, endstates=endstates))
              for (result, pV) in partition(V, score, decision).iteritems())
  yield Node(decision, branches) # Lazy evaluation

Следующая функция оценивает один путь через это дерево на основе предоставленной функции подсчета очков:

def solver(scorer, **kwargs):
  lazyTree = lazySolutionTree(**kwargs)
  steps = []
  while lazyTree is not None:
    t = lazyTree.next() # Evaluate node
    result = scorer(t.decision)
    steps.append((t.decision, result))
    subtrees = [b.subtree for b in t.branches if b.result == result]
    if len(subtrees) == 0:
      raise Exception("No solution possible for given scores")
    lazyTree = subtrees[0]
  assert(result in endstates)
  return steps

Теперь это можно использовать для создания интерактивной игры Mastermind, где пользователь оценивает догадки компьютера. Игра с этим раскрывает некоторые интересные вещи. Например, наиболее информативное первое предположение имеет вид (желтый, желтый, синий, зеленый), а не (желтый, синий, зеленый, красный). Дополнительную информацию можно получить, используя половину доступных цветов. Это также справедливо для 6-цветного 3-луночного Mastermind - (желтого, синего, зеленого) и 8-цветного 5-луночного Mastermind - (желтый, желтый, синий, зеленый, красный).

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

def allSolutions(**kwargs):
  def solutions(lazyTree):
    return ((((t.decision, b.result),) + solution
             for t in lazyTree for b in t.branches
             for solution in solutions(b.subtree))
            if lazyTree else ((),))
  return solutions(lazySolutionTree(**kwargs))

Поиск наихудшего случая - это простой вопрос нахождения самого длинного решения:

def worstCaseSolution(**kwargs):
  return max((len(s), s) for s in allSolutions(**kwargs)) [1]

Оказывается, этот решатель всегда будет завершен на 5 шагов или меньше. Пять шагов! Я знаю, что, когда я играл с Учителем как ребенок, я часто занимал больше времени. Однако, создав этот решатель и играя с ним, я значительно улучшил свою технику, и 5 шагов действительно достижимая цель, даже если у вас нет времени, чтобы вычислить энтропически идеальное предположение на каждом шаге;)

Насколько вероятно, что решатель выполнит 5 шагов? Будет ли он когда-либо закончить в 1 или 2 шага? Чтобы найти это, я создал еще одну небольшую функцию, которая вычисляет распределение длины решения:

def solutionLengthDistribution(**kwargs):
  return collections.Counter(len(s) for s in allSolutions(**kwargs))

Для жадного энтропийного подхода, с разрешенными повторами: 7 случаев принимают 2 шага; 55 дел занимают 3 ступени; 229 дел занимают 4 ступени; и 69 случаев занимают максимум 5 шагов.

Конечно, нет никакой гарантии, что жадный энтропийный подход минимизирует наихудшее количество шагов. Заключительная часть моего языка общего назначения - это алгоритм, который решает, существуют ли какие-либо решения для данной наихудшей оценки. Это скажет нам, является ли жадная энтропия идеальной или нет. Для этого я принимаю стратегию с веткой и границей:

def solutionExists(maxsteps, G, V, score, **kwargs):
  if len(V) == 1: return True
  partitions = [partition(V, score, g).values() for g in G]
  maxSize = max(len(P) for P in partitions) ** (maxsteps - 2)
  partitions = (P for P in partitions if max(len(s) for s in P) <= maxSize)
  return any(all(solutionExists(maxsteps-1,G,s,score) for l,s in
                 sorted((-len(s), s) for s in P)) for i,P in
             sorted((-entropy(len(s) for s in P), P) for P in partitions))

Это определенно сложная функция, поэтому немного больше объяснений в порядке. Первый шаг заключается в разделении оставшихся решений на основе их оценки после угадывания, как и раньше, но на этот раз мы не знаем, какую догадку мы собираемся сделать, поэтому мы сохраняем все разделы. Теперь мы можем просто перечислить каждую из них, фактически перечислив всю вселенную возможных деревьев решений, но это займет ужасно долгое время. Вместо этого я замечаю, что если на данный момент нет раздела, который делит оставшиеся решения на более чем n наборов, то на любом будущем шаге тоже не может быть такого раздела. Если у нас осталось k шагов, это означает, что мы можем различать не более n ^k-1 решений до того, как мы закончим гадать (на последнем шаге мы должны всегда правильно гадать). Таким образом, мы можем отбросить любые разделы, содержащие оценку, сопоставленную с большим количеством этих решений. Это следующие две строки кода.

В последней строке кода рекурсия, использующая Python для всех функций для ясности, и, прежде всего, для решения наивысшей энтропии, мы надеемся, что это минимизирует время выполнения в положительном случае. Он также сначала переписывается в самую большую часть раздела, так как это скорее всего не удастся быстро, если решение было неправильным. Еще раз, я использую стандартный узор украшать-undecorate, на этот раз, чтобы обернуть сортированную функцию Python.

def lowerBoundOnWorstCaseSolution(**kwargs):
  for steps in itertools.count(1):
    if solutionExists(maxsteps=steps, **kwargs):
      return steps

Вызывая неоднократное обращение к решениюExists с увеличением числа шагов, мы получаем строгую нижнюю границу числа шагов, необходимых в худшем случае для решения Mastermind: 5 шагов. Жадный энтропийный подход действительно оптимален.

Из любопытства я придумал еще одну угадающую игру, которую я прозвал "twoD". В этом вы пытаетесь угадать пару чисел; на каждом шаге вы узнаете, правильно ли ваш ответ, если числа, которые вы догадались, не меньше соответствующих в тайне, и если числа не больше.

Comparison = collections.namedtuple('Comparison', 'less greater equal')
def twoDScorer(x, y):
  return Comparison(all(r[0] <= r[1] for r in zip(x, y)),
                    all(r[0] >= r[1] for r in zip(x, y)),
                    x == y)
def twoD():
  G = set(itertools.product(xrange(5), repeat=2))
  return dict(G = G, V = G, score = twoDScorer,
              endstates = set(Comparison(True, True, True)))

Для этой игры жадный энтропийный подход имеет худший случай из пяти шагов, но есть лучшее решение, возможное с худшим случаем из четырех шагов, подтверждающим мою интуицию, что близорукость жадности является только совпадающей идеей для Mastermind. Что еще более важно, это показало, насколько гибким является мой язык: все те же методы работают для этой новой игры угадывания, как и для Mastermind, позволяя мне исследовать другие игры с минимальным количеством дополнительного кодирования.

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

Одна дешевая оптимизация заключается в том, чтобы заметить, что на первом ходу большинство догадок в основном идентичны: (желтый, синий, зеленый, красный) на самом деле не отличается от (синий, красный, зеленый, желтый) или (оранжевый, желтый, красный, фиолетовый). Это значительно уменьшает количество догадок, которые нам нужно рассмотреть на первом шаге - в противном случае это самое дорогое решение в игре.

Однако из-за большого темпа роста этой проблемы я не смог решить проблему 8-цветного 5-луночного Mastermind даже при такой оптимизации. Вместо этого я портировал алгоритмы на С++, сохраняя общую структуру одинаковой и используя побитовые операции для повышения производительности в критических внутренних циклах, для ускорения на многие порядки. Я оставляю это как упражнение для читателя:)

Ответ 2

Я как-то написал " Jotto" решатель, который по сути является "Master Mind" со словами. (Мы каждый выбираем слово, и мы по очереди угадываем друг другу слово, забиваем "правильные" (точные) совпадения и "в другом месте" (правильная буква/цвет, но неправильное размещение).

Ключом к решению такой проблемы является осознание симметричной функции подсчета.

Другими словами, если score(myguess) == (1,2), то я могу использовать ту же функцию score(), чтобы сравнить мое предыдущее предположение с любой другой возможностью и исключить любые, которые не дают точно такой же балл.

Позвольте мне привести пример: скрытое слово (цель) - это "оценка"... текущая догадка "дураки" --- оценка 1,1 (одна буква "o", "справа" ", другое письмо" s "," находится в другом месте "). Я могу исключить слово" угадать ", потому что" оценка ( "догадка" ) (против "дураков" ) возвращает (1,0) (финальные "совпадения", но ничего не делает). Таким образом, слово "догадка" не соответствует "дуракам", а счету против неизвестного слова, которое дало результат (1,1).

Итак, теперь я могу пройти через каждое пять буквенных слов (или комбинацию из пяти цветов/букв/цифр и т.д.) и устранить все, что не набирает 1,1 против "дураков". Сделайте это на каждой итерации, и вы очень быстро сходите на цель. (Для пяти буквенных слов я смог получить в течение 6 попыток каждый раз... и обычно только 3 или 4). Разумеется, всего 6000 слов, и вы убираете почти 95% для каждой догадки.

Примечание: для следующего обсуждения я говорю о пяти буквенных "комбинациях", а не о четырех элементах шести цветов. Используются те же алгоритмы; однако проблема на порядок меньше для старой игры "Мастер-Разум"... в классической программе "Мастер разума" есть только 1296 комбинаций (6 ** 4) цветных колышек, предполагая, что дубликаты разрешены. Линия рассуждений, которая приводит к конвергенции, включает в себя некоторую комбинаторика: для пяти целевых элементов (n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5] есть 20 необоснованных оценок), чтобы увидеть их все, если вам интересно. Поэтому мы ожидаем, что любые случайные действительный выбор будет иметь примерно 5% -ный шанс сопоставить наш счет... другие 95% не будут и, следовательно, будут устранены для каждого набранного догадки. Это не учитывает возможную кластеризацию в шаблонах слов, но поведение в реальном мире достаточно близко для слов и определенно еще ближе к правилам "Мастер-Разум". Однако, только с 6 цветами в 4 слотах у нас есть только 14 возможных необоснованных баллов, поэтому наше сближение не так быстро).

Для Jotto две второстепенные задачи: создание хорошего мирового списка (awk -f 'length($0)==5' /usr/share/dict/words или аналогичного в системе UNIX) и что делать, если пользователь выбрал слово, которое не в нашем словаре (генерирует каждую буквенную комбинацию, aaaaa 'через' zzzzz '--- это 26 ** 5... или ~ 1,1 миллиона). Тривиальный генератор комбинации в Python занимает около 1 минуты, чтобы генерировать все эти строки... оптимизированный должен быть намного лучше. (Я также могу добавить требование, чтобы каждое "слово" имело хотя бы одну гласную... но это ограничение не очень помогает --- 5 гласных * 5 возможных мест для этого, а затем умножено на 26 ** 4 других комбинаций).

Для Master Mind вы используете один и тот же генератор комбинации... но только с 4 или 5 буквами (цветами). Каждая 6-цветная комбинация (15 625 из них) может быть сгенерирована в течение секунды (с использованием того же генератора комбинации, что и я использовал выше).

Если бы я писал эту программу "Jotto" сегодня, например, в Python, я бы "обманул", создав поток, генерирующий все буквенные комбо в фоновом режиме, в то время как я все еще удалял слова из словаря (в то время как мой противник был забив меня, догадываясь и т.д.). Поскольку я сгенерировал их, я бы также устранил все догадки. Таким образом, после того, как я уничтожу все известные слова, у меня будет относительно небольшой список возможностей и против человека, который я "скрыл" большую часть моего отставания в вычислении, делая это параллельно с их вводом. (И, если бы я написал версию веб-сервера такой программы, у меня был бы мой веб-движок, чтобы поговорить с местным демоном, чтобы спросить последовательности, совместимые с набором баллов. Демон будет содержать локально сгенерированный список всех комбинаций букв и будет использовать модель select.select() для возврата возможностей каждому из запущенных экземпляров игры - каждый из них будет кормить мои пары демона/пар баллов, которые мой демон будет применять в качестве фильтра для возможностей, которые он передает обратно этому клиенту).

(Для сравнения я написал свою версию "Jotto" около 20 лет назад на XT с использованием Borland TurboPascal... и он мог бы выполнять каждую итерацию исключения --- начиная с ее скомпилированного в списке нескольких тысяч слов - - в хорошо под вторым. Я строю свой список слов, написав простой генератор комбинаций букв (см. ниже)... сохраняя результаты в умеренно большой файл, а затем запустив проверку текста в текстовом процессоре, используя макрос, чтобы удалить все это было "неправильно написано". Затем я использовал другой макрос, чтобы обернуть все оставшиеся строки в правильной пунктуации, чтобы сделать их действительными статическими назначениями для моего массива, который был #include файлом для моей программы. Все, что позволило мне построить автономная игровая программа, которая "знала" почти каждое действующее английское 5-буквенное слово, а программа была .COM --- менее 50 КБ, если я правильно помню).

По другим причинам я недавно написал простой генератор произвольной комбинации в Python. Это около 35 строк кода, и я опубликовал это в своей "банальной фрагментации" wiki на bitbucket.org... это не "генератор" в смысле Python... но класс, который вы можете создать для бесконечной последовательности "числовая" или "символическая" комбинация элементов (по существу, подсчитывается в любой положительной целочисленной базе).

Вы можете найти его по адресу: Trite Snippets: Генератор комбинаций произвольных последовательностей

Для точной части соответствия нашей функции score() вы можете просто использовать это:

def score(this, that):
    '''Simple "Master Mind" scoring function'''
    exact = len([x for x,y in zip(this, that) if x==y])
    ### Calculating "other" (white pegs) goes here:
    ### ...
    ###
    return (exact,other)

Я думаю, что это иллюстрирует некоторую красоту Python: zip() до двух последовательностей, вернуть любое совпадение и взять длину результатов).

Поиск совпадений в "других" местах обманчиво усложняется. Если повторений не было разрешено, вы можете просто использовать наборы, чтобы найти пересечения.

[В моем предыдущем редактировании этого сообщения, когда я понял, как использовать zip() для точных совпадений, я ошибочно думал, что мы могли бы уйти с other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact... но было уже поздно, и я устал. Когда я спал, я понял, что этот метод был испорчен. Плохо, Джим! Не отправляйте сообщения без надлежащего тестирования! * (Протестировано несколько случаев, когда это случилось).

В прошлом подход, который я использовал, состоял в сортировке обоих списков, сравните головы каждого из них: если главы равны, увеличьте количество и поп новых элементов из обоих списков. иначе добавьте новое значение в меньшее из двух головок и повторите попытку. Перерыв, как только список пуст.

Это работает; но он довольно многословный. Лучшее, что я могу придумать с помощью этого подхода, - это всего лишь несколько десятков строк кода:

other = 0
x = sorted(this)   ## Implicitly converts to a list!
y = sorted(that)
while len(x) and len(y):
    if x[0] == y[0]:
        other += 1
        x.pop(0)
        y.pop(0)
    elif x[0] < y[0]:
        x.pop(0)
    else:
        y.pop(0)
other -= exact

Используя словарь, я могу обрезать это примерно до девяти:

other = 0
counters = dict()
for i in this:
    counters[i] = counters.get(i,0) + 1
for i in that:
    if counters.get(i,0) > 0:
        other += 1
        counters[i] -= 1
other -= exact

(Используя новый класс "collections.Counter" (Python3 и планируется для Python 2.7?), я мог бы, вероятно, уменьшить это немного больше, три строки здесь инициализируют коллекцию счетчиков).

Важно, чтобы "счетчик" уменьшался, когда мы находим совпадение, и очень важно проверить, что счетчик больше нуля в нашем тесте. Если заданная буква/символ появляется в "this" один раз и "это" дважды, то она должна учитываться только как совпадение один раз.

Первый подход определенно немного сложнее писать (нужно быть осторожным, чтобы избежать границ). Также в нескольких быстрых тестах (тестирование миллион случайно генерируемых пар буквенных шаблонов) первый подход занимает около 70% дольше, чем тот, который использует словари. (Сгенерирование миллиона пар строк с использованием random.shuffle() заняло в два раза больше, чем замедление функций подсчета очков, с другой стороны).

Формальный анализ эффективности этих двух функций будет сложным. Первый метод имеет два типа, так что это будет 2 * O (nlog (n))... и он выполняет итерацию по крайней мере из одной из двух строк и, возможно, должен перебирать все пути до конца другой строки ( лучший случай O (n), наихудший случай O (2n)) - сила, которую я неправильно использую здесь, но это просто приблизительная оценка. Второй случай полностью зависит от характеристик исполнения словаря. Если бы мы использовали b-деревья, тогда производительность была бы примерно равной O (nlog (n) для создания и нахождения каждого элемента из другой строки в нем была бы другой операцией O (n * log (n)). Однако словари Python очень и эти операции должны быть близки к постоянному времени (очень мало хэш-коллизий). Таким образом, мы ожидаем производительность примерно O (2n)... что, конечно, упрощает O (n). Это примерно соответствует моим результатам тестов.

Взгляд на статью Википедии " "Мастер-разум "" Я вижу, что Дональд Кнут использовал подход, который начинается аналогично моей (и 10 лет ранее), но он добавил одну значительную оптимизацию. После сбора каждой оставшейся возможности он выбирает, какой из них удалит наибольшее количество возможностей в следующем раунде. Я рассматривал такое усовершенствование своей собственной программы и отверг идею по практическим соображениям. В его случае он искал оптимальное (математическое) решение. В моем случае я был обеспокоен возможностью воспроизведения (на XT, желательно с использованием менее 64 КБ ОЗУ, хотя я мог переключиться на формат .EXE и использовать до 640 КБ). Я хотел сохранить время отклика в области одной или двух секунд (что было легко с моим подходом, но с гораздо более сложным с дальнейшим спекулятивным подсчетом). (Помните, что я работал в Pascal, под MS-DOS... без потоков, хотя я реализовал поддержку сырого асинхронного опроса пользовательского интерфейса, который оказался ненужным)

Если бы я писал такую ​​вещь сегодня, я бы добавил поток, чтобы сделать лучший выбор. Это позволило бы мне дать лучшее предположение, которое я нашел в течение определенного временного ограничения, чтобы гарантировать, что моему игроку не нужно слишком долго ждать моей догадки. Естественно, мой выбор/исключение будет выполняться в ожидании моего оппонента.

Ответ 3

Вам кажется, что Raymond Hettingers попытался? Они, безусловно, соответствуют некоторым вашим требованиям.

Интересно, как его решения сравниваются с вашими.

Ответ 4

Существует отличный сайт о стратегии MasterMind здесь. Автор начинает с очень простых проблем MasterMind (используя цифры, а не буквы, игнорируя порядок и повторение) и постепенно наращивает до полной проблемы MasterMind (используя цвета, которые можно повторять в любом порядке, даже с возможностью ошибок в подсказках).

Представленные семь обучающих программ:

• Учебное пособие 1 - Простейшая настройка игры (без ошибок, фиксированного порядка, без повторения)
• Учебное пособие 2 - Код может содержать пробелы (без ошибок, фиксированный порядок, без повторения)
• Учебное пособие 3 - Советы могут содержать ошибки (фиксированный порядок, без повторения)
• Учебник 4 - Игра началась с середины (без ошибок, фиксированного порядка, без повторения)
• Учебное пособие 5 - Цифры/цвета могут повторяться (ошибок нет, фиксированный порядок, каждый цвет повторяется не более 4 раз)
• Учебник 6 - Цифры/цвета, упорядоченные в случайном порядке (без ошибок, случайного порядка, без повторений)
• Учебное пособие 7 - Объединить все это (нет ошибок, случайный порядок, каждый цвет повторяется не более 4 раз)

Ответ 5

Просто подумал, что я внес бы свои 90 нечетных строк кода. Я основывался на ответе @Jim Dennis, в основном убирая намек на симметричный подсчет очков. Я реализовал минимаксный алгоритм, описанный в статье авторской статьи Википедии от Knuth, за одним исключением: я ограничиваю свой следующий переход на текущий список возможные решения, поскольку я обнаружил ухудшение производительности при принятии всех возможных решений на каждом шаге. Текущий подход оставляет меня в худшем случае из 6 догадок для любой комбинации, каждый из которых находится в скважине под второй.

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

from itertools import product, tee
from random import choice

COLORS = 'red ', 'green', 'blue', 'yellow', 'purple', 'pink'#, 'grey', 'white', 'black', 'orange', 'brown', 'mauve', '-gap-'
HOLES = 4

def random_solution():
    """Generate a random solution."""
    return tuple(choice(COLORS) for i in range(HOLES))

def all_solutions():
    """Generate all possible solutions."""
    for solution in product(*tee(COLORS, HOLES)):
        yield solution

def filter_matching_result(solution_space, guess, result):
    """Filter solutions for matches that produce a specific result for a guess."""
    for solution in solution_space:
        if score(guess, solution) == result:
            yield solution

def score(actual, guess):
    """Calculate score of guess against actual."""
    result = []
    #Black pin for every color at right position
    actual_list = list(actual)
    guess_list = list(guess)
    black_positions = [number for number, pair in enumerate(zip(actual_list, guess_list)) if pair[0] == pair[1]]
    for number in reversed(black_positions):
        del actual_list[number]
        del guess_list[number]
        result.append('black')
    #White pin for every color at wrong position
    for color in guess_list:
        if color in actual_list:
            #Remove the match so we can't score it again for duplicate colors
            actual_list.remove(color)
            result.append('white')
    #Return a tuple, which is suitable as a dictionary key
    return tuple(result)

def minimal_eliminated(solution_space, solution):
    """For solution calculate how many possibilities from S would be eliminated for each possible colored/white score.
    The score of the guess is the least of such values."""
    result_counter = {}
    for option in solution_space:
        result = score(solution, option)
        if result not in result_counter.keys():
            result_counter[result] = 1
        else:
            result_counter[result] += 1
    return len(solution_space) - max(result_counter.values())

def best_move(solution_space):
    """Determine the best move in the solution space, being the one that restricts the number of hits the most."""
    elim_for_solution = dict((minimal_eliminated(solution_space, solution), solution) for solution in solution_space)
    max_elimintated = max(elim_for_solution.keys())
    return elim_for_solution[max_elimintated]

def main(actual = None):
    """Solve a game of mastermind."""
    #Generate random 'hidden' sequence if actual is None
    if actual == None:
        actual = random_solution()

    #Start the game of by choosing n unique colors
    current_guess = COLORS[:HOLES]

    #Initialize solution space to all solutions
    solution_space = all_solutions()
    guesses = 1
    while True:
        #Calculate current score
        current_score = score(actual, current_guess)
        #print '\t'.join(current_guess), '\t->\t', '\t'.join(current_score)
        if current_score == tuple(['black'] * HOLES):
            print guesses, 'guesses for\t', '\t'.join(actual)
            return guesses

        #Restrict solution space to exactly those hits that have current_score against current_guess
        solution_space = tuple(filter_matching_result(solution_space, current_guess, current_score))

        #Pick the candidate that will limit the search space most
        current_guess = best_move(solution_space)
        guesses += 1

if __name__ == '__main__':
    print max(main(sol) for sol in all_solutions())

Если кто-нибудь обнаружит какие-либо возможные улучшения вышеприведенного кода, я бы очень интересовался вашими предложениями.

Ответ 6

Чтобы выработать "худший" случай, вместо использования энтропии я смотрю на раздел с максимальным количеством элементов, затем выберите попытку, которая является минимальной для этого максимума = > Это даст мне минимальное число оставшейся возможности, когда мне не повезло (что происходит в худшем случае).

Это всегда разрешает стандартный случай в 5 попытках, но это не полное доказательство того, что 5 попыток действительно необходимы, потому что может случиться так, что для следующего шага большие возможности набора дали бы лучший результат, чем меньший (потому что проще чтобы различать).

Хотя для "стандартной игры" с 1680 я имею простое формальное доказательство: Для первого шага попытка, которая дает минимум для раздела с максимальным числом, равна 0,0,1,1: 256. Воспроизведение 0,0,1,2 не так хорошо: 276. Для каждой последующей попытки есть 14 результатов (1 не помещается и 3 помещается не представляется возможным), а 4 помещается в раздел 1. Это означает, что в лучшем случае (все одинаковые размеры раздела) мы получим максимальный раздел, который является минимум (количество возможностей - 1)/13 (округляется, потому что у нас есть целое число, поэтому обязательно некоторые будут меньше и другие, так что максимум округляется вверх).

Если я применил это:

После первой игры (0,0,1,1) я получаю 256 слева.

После второй попытки: 20 = (256-1)/13

После третьей попытки: 2 = (20-1)/13

Тогда у меня нет другого выбора, кроме как попробовать один из двух слева для 4-й попытки.

Если мне не повезло, нужна пятая попытка.

Это доказывает, что нам нужно не менее 5 попыток (но не этого достаточно).

Ответ 7

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

Вы можете свободно использовать любое целое или часть этого алгоритма, если кредит предоставляется соответственно.

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

Независимо отсюда, код:

import random


def main():

    userAns = raw_input("Enter your tuple, and I will crack it in six moves or less: ")
    play(ans=eval("("+userAns+")"),guess=(0,0,0,0),previousGuess=[])

def play(ans=(6,1,3,5),guess=(0,0,0,0),previousGuess=[]):

    if(guess==(0,0,0,0)):
       guess = genGuess(guess,ans)
    else:
        checker = -1
        while(checker==-1):
            guess,checker = genLogicalGuess(guess,previousGuess,ans)

    print guess, ans


    if not(guess==ans):
        previousGuess.append(guess)

        base = check(ans,guess)

        play(ans=ans,guess=base,previousGuess=previousGuess)

    else:
        print "Found it!"





def genGuess(guess,ans):
    guess = []
    for i in range(0,len(ans),1):
        guess.append(random.randint(1,6))

    return tuple(guess)

def genLogicalGuess(guess,previousGuess,ans):
    newGuess = list(guess)
    count = 0

    #Generate guess

    for i in range(0,len(newGuess),1):
        if(newGuess[i]==-1):
            newGuess.insert(i,random.randint(1,6))
            newGuess.pop(i+1)


    for item in previousGuess:
        for i in range(0,len(newGuess),1):
            if((newGuess[i]==item[i]) and (newGuess[i]!=ans[i])):
                newGuess.insert(i,-1)
                newGuess.pop(i+1)
                count+=1

    if(count>0):
        return guess,-1
    else:
        guess = tuple(newGuess)
        return guess,0


def check(ans,guess):
    base = []
    for i in range(0,len(zip(ans,guess)),1):
        if not(zip(ans,guess)[i][0] == zip(ans,guess)[i][1]):
            base.append(-1)
        else:
            base.append(zip(ans,guess)[i][1])

    return tuple(base)

main()

Ответ 8

Здесь ссылка на чистый решатель Python для Mastermind (tm): http://code.activestate.com/recipes/496907-mastermind-style-code-breaking/ В нем есть простая версия, способ экспериментировать с различными стратегии угадывания, измерение производительности и дополнительный ускоритель C.

Ядро рецепта короткое и сладкое:

import random
from itertools import izip, imap

digits = 4
fmt = '%0' + str(digits) + 'd'
searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)])

def compare(a, b, imap=imap, sum=sum, izip=izip, min=min):
    count1 = [0] * 10
    count2 = [0] * 10
    strikes = 0
    for dig1, dig2 in izip(a,b):
        if dig1 == dig2:
            strikes += 1
        count1[dig1] += 1
        count2[dig2] += 1
    balls = sum(imap(min, count1, count2)) - strikes
    return (strikes, balls)

def rungame(target, strategy, verbose=True, maxtries=15):
    possibles = list(searchspace)
    for i in xrange(maxtries):
        g = strategy(i, possibles)
        if verbose:
            print "Out of %7d possibilities.  I'll guess %r" % (len(possibles), g),
        score = compare(g, target)
        if verbose:
            print ' ---> ', score
        if score[0] == digits:
            if verbose:
                print "That it.  After %d tries, I won." % (i+1,)
            break
        possibles = [n for n in possibles if compare(g, n) == score]
    return i+1

def strategy_allrand(i, possibles):
    return random.choice(possibles)

if __name__ == '__main__':
    hidden_code = random.choice(searchspace)
    rungame(hidden_code, strategy_allrand)

Вот как выглядит результат:

Out of   10000 possibilities.  I'll guess (6, 4, 0, 9)  --->  (1, 0)
Out of    1372 possibilities.  I'll guess (7, 4, 5, 8)  --->  (1, 1)
Out of     204 possibilities.  I'll guess (1, 4, 2, 7)  --->  (2, 1)
Out of      11 possibilities.  I'll guess (1, 4, 7, 1)  --->  (3, 0)
Out of       2 possibilities.  I'll guess (1, 4, 7, 4)  --->  (4, 0)
That it.  After 5 tries, I won.