詞猜謎遊戲，使用什麼算法？

Question

我有一個號碼[1,2,3,4,5,6,7,8,9,10]的列表，現在我做出一些他們的組合。比方說[2,2,4,5,1,1]。

現在程序必須猜測我認爲什麼樣的組合。
然後該程序將生成一個與我的組合相同長度的隨機列表。比方說，它將是[1,2,5,5,4,3]。

現在我必須告訴在正確的位置有多少個數字，以及在正確的位置有多少個數字。所以，在這種情況下，正確的是兩個數字（2和5）。還有1和3在正確的地方，但在錯誤的地方。

最初，程序應該使用我的提示猜測密碼。有人可以幫助我弄清楚或給出一個用於解決這類問題的算法的提示。

Answer 1

那麼這應該有助於你開始做起。下面的代碼將幫助您生成從1由數字隨機組合，以10

from random import randrange 

# randrange will generate a random number between 1 and 11 
# the end value 11 is not included 

# for _ in range(0, 6) is used to iterate 6 times 
comb = [randrange(1, 11) for _ in range(0, 6)] 

Answer 2

免責聲明：該解決方案將不會與你的問題集大小工作，因爲你是10的6次方，且算法二次。二次部分是一個很容易解決的問題（如果您不關心最優解），您不必考慮所有可能的猜測，足以進行抽樣並測試樣本是否足夠好（例如：至少減少一半的狀態空間）。難以解決的一件事是狀態空間的初始大小。你可以硬編碼一些初步的猜測（例如，硬編碼前3個猜測），然後僅用有效組合產生初始狀態空間（例如：如果你發現板上沒有'1'，那麼不會產生猜測包含'1'）。

---

下面是使用Knuth's minmax solution來解決問題的代碼。

• 我們保留一組猜測，可以根據以前的猜測進行解決。
• 我們認爲它們中的每一個都是下一步，並且計算最壞的情況，也就是猜測後最大可能的大小。
• 從這些最壞的情況我們選擇最好的，也就是保證最大限度地減少集合大小的下一步。
• 我們玩這個猜測，根據答案我們從集合中消除不可能的解。
• 我們這樣做直到找到解決方案。

我做了一個小小的修改（主要是爲了代碼的簡單性和速度），這樣只有下一個猜測纔會考慮有效的答案。因此，該算法有時需要額外的步驟。

克努特也給顯示，在某些情況下，無S 的成員將是得分最高的猜測之中，因此猜測不能 贏得下一回合，但將需要在五個確保一個雙贏的例子。

這裏有這樣的病理例如：

Secret: [1, 1, 1, 0] 
(0, 0, 1, 1) -> (1, 2) 
(5, 1, 1, 0) -> (3, 0) 
(4, 1, 1, 0) -> (3, 0) 
(3, 1, 1, 0) -> (3, 0) 
(2, 1, 1, 0) -> (3, 0) 
(1, 1, 1, 0) -> (4, 0) 
Done in 6 steps 

它可以在更少的步驟很容易地找到了丟失的顏色，但因爲它試圖唯一有效的解決方案，它需要一個額外的步驟。

#!/usr/bin/python 

import random 
import itertools 
import collections 

COLORS, PEGS = 6, 4 

def random_secret(): 
    return [random.randrange(COLORS) for _ in range(PEGS)] 

def all_states(): 
    return list(itertools.product(*[range(COLORS) for _ in range(PEGS)])) 

def evaluate(secret, guess): 
    color_and_pos = 0 
    color = 0 
    colors = collections.defaultdict(int) 
    for i in range(len(secret)): 
     if secret[i] == guess[i]: 
      color_and_pos += 1 
     else: 
      colors[secret[i]] += 1 
    for i in range(len(secret)): 
     if secret[i] != guess[i]: 
      if colors[guess[i]] > 0: 
       colors[guess[i]] -= 1 
       color += 1 
    return (color_and_pos, color) 

def list_count(l): 
    #for python >= 2.7 you can use collections.Counter 
    return dict((x, l.count(x)) for x in set(l)) 

def dict_max_value(d): 
    return max(d.values()) 

def minmax(fun, actions): 
    min, choice = None, None 
    for action in actions: 
     max = fun(action) 
     if choice is None: 
      min, choice = max, action 
     elif max <= min: 
      min, choice = max, action 
    return choice 

class Algo(): 
    def __init__(self): 
     self.contenders = all_states() 
    def initial_guess(self): 
     return tuple([0] * (PEGS/2) + [1] * (PEGS - PEGS/2)) 
    def next_guess(self, qnas): 
     self.filter_contenders(qnas[-1]) 
     #print "contenders size: ", len(self.contenders) 
     return minmax(lambda (candidate): 
      dict_max_value(list_count(
       [evaluate(contender, candidate) for contender in self.contenders] 
      )), self.contenders) 

    def filter_contenders(self, qna): 
     self.contenders = [contender for contender in self.contenders 
            if evaluate(contender, qna[0]) == qna[1]] 

class Game(): 
    def __init__(self, algo): 
     self.algo = algo 
    def run(self): 
     secret = random_secret() 
     print "Secret:", secret 
     qnas = [] 
     n = 1 
     guess = self.algo.initial_guess() 
     while True: 
      answer = evaluate(secret, guess) 
      qnas.append((guess, answer)) 
      print guess, "->", answer 
      if answer == (PEGS, 0): 
       break 
      guess = self.algo.next_guess(qnas) 
      n += 1 
     print "Done in", n, "steps" 

Game(Algo()).run() 

Answer 3

「然後該程序將生成一個與我的組合相同長度的隨機列表」 - 這是問題的一部分嗎？你稍後說，該程序使用你的提示，所以我假設你正在生成隨機數字列表，試圖找出密碼，同時只使用隨機的數字列表，而不是使用你必須做的更好的猜測信息，可以縮小更快地取得成果。

在這種情況下，您需要跟蹤您的猜測，併爲每個人猜出您可以從中收集哪些信息。每次您從猜測中獲得新信息時，都可以返回之前猜測的結果並查看是否獲得任何新信息。對於你的榜樣，讓我們​​說這是這樣的，包括第一後​​我由猜測：

PASSWORD: [2,2,4,5,1,1] 
GUESS 1: [1,2,5,5,4,3] - 4 correct, 2 right position 
GUESS 2: [5,2,1,7,3,8] - 3 correct, 1 right position 
GUESS 3: [7,7,8,3,7,9] - 0 correct, 0 right position 
GUESS 4: [5,6,5,3,8,9] - 1 correct, 0 right position 
GUESS 5: [8,2,5,6,7,3] - 2 correct, 1 right position 

猜測3之後，你知道你有沒有3S，7S，8S或787-9。回到第二個猜測，你知道三個數字是1,2,5，因爲你沒有3,7,8。回到你的第一個猜測與知識，你知道答案有1,2,5以及4或5.看看第4猜你現在知道只有一個5，所以你的四個數字是1 ，2,4,5。繼續使用這個算法，直到找出所有6個數字，而不是關心他們位於什麼位置。

一旦你有全部6個數字，你就可以切換算法來找出數字的位置。猜測每次你學習新的信息，並繼續猜測隨機密碼，如果你卡住了。對於初始運行，由於猜測，你知道5不在位置1或3中。猜測2 - 你知道5不在位置1，所以2或1在正確的位置[X， 2,1，X，X，X]。猜測1你知道5不在位置3，因此以下2個位於正確的位置：[1,2，X，5,4，X]。猜測5告訴你，無論是2還是5都處於正確的位置，但由於猜測4，你知道5處於錯誤的位置，所以現在你知道2在位置2了。將這個信息與猜測2相結合你的1也不在位置3，所以你知道它必須是4或2.

表示你的知識的一種方法是將數組的最小和最大計數爲每個數字和一個布爾數組每個地方都告訴你哪些數字可以到達那裏。一旦獲得了猜測中的所有信息，就可以將其從列表中刪除，因此不必再次查看。因此，在猜測3之後，最大數量3,7,8,9爲0.您也可以將這些可能性設置爲每個位置爲假。這就是你可以得到的所有信息，所以你不必再看看猜測3.

你也可以改變猜測來簡化它，例如一旦你知道2進入位置2並且沒有3 ，7,8，你可以刪除那些「的已知，」你猜2點的變化：

GUESS 2: [5,2,1,7,3,8] - 3 correct, 1 right position 
NEW 2: [5,X,1,X,X,X] - 2 correct, 0 right position 

但是，一旦你知道所有的數字和已成立5爲false位置1和1爲false位置3，這樣可以給你更多的信息，你可以從你的列表中刪除這個猜測。