Qual è l'algoritmo ottimale per giocare al gioco di parole dell'impiccato?

Question

Supponiamo di stare giocando boia.Sia io che il mio avversario abbiamo accesso al dizionario durante il gioco.Il mio avversario sceglie una parola dal dizionario conoscendo l'algoritmo che userò per indovinare la sua parola segreta.Una volta che il mio avversario ha scelto una parola, mi viene data solo la lunghezza della parola.Posso indovinare una lettera che penso sarà nella parola, e se è nella parola il mio avversario identifica tutte le posizioni di quella lettera in quella parola.Se indovino una lettera che non è nella parola, viene conteggiato come un errore.Se riesco a indovinare la parola prima di fare troppi errori vinco.

L'obiettivo del mio avversario dovrebbe essere quello di scegliere una parola che massimizzi il numero di errori (ipotesi errate) che faccio prima di poter indovinare la parola.Il mio obiettivo è minimizzarli.(Tradizionalmente, se il numero di errori è > un certo numero, allora perdo la partita, ma possiamo allentare questo vincolo.)

Considera tre algoritmi per indovinare le lettere.Queste sono le principali a cui ho pensato, ma probabilmente ce ne sono altre e accolgo con piacere idee alternative.In tutti e tre gli algoritmi, il primo passo sarà raccogliere l'elenco delle parole che hanno la stessa lunghezza della parola segreta.Quindi, per ogni lettera dell'alfabeto, conta il numero di parole del dizionario che contengono quella lettera.Ad esempio, forse 5000 contengono "a", 300 contengono "b" e così via.Eccolo in Python:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

Successivamente è dove i tre algoritmi divergono.

1. Nel primo algoritmo, indoviniamo la lettera che contiene il maggior numero di parole rimanenti.Quindi, se le 5000 parole rimanenti contengono "a" e non ci sono altre lettere in così tante parole, sceglieremo "a" ogni volta.Se "a" è corretto, questo ci fornisce informazioni sulla posizione che possiamo filtrare ulteriormente l'elenco.Ad esempio, potremmo filtrare l'elenco in base a tutte le parole che corrispondono a ".a...".(I punti sono lettere sconosciute.) Se "a" non è corretta, filtriamo tutte le parole che contengono "a".Nel caso in cui vi sia parità e si trovino due lettere in un numero uguale di parole, le lettere vengono scelte in ordine alfabetico.Quindi, se sappiamo che la parola corrisponde a ".ays", indovineremo semplicemente le parole in ordine alfabetico.

2. Questo è solo leggermente diverso dal primo algoritmo.Invece di scegliere sempre l'ordine alfabetico, in caso di parità scegliamo le lettere in modo casuale.Questo ha il vantaggio che il nostro avversario non sa cosa sceglieremo.Nella prima strategia, "raggi" è sempre migliore di "giorni".Questo evita questo problema.

3. In questo caso scegliamo le lettere con una probabilità proporzionale al numero di parole che contengono quella lettera.All'inizio, quando abbiamo contato il numero di parole che contengono "a" e il numero di parole che contengono "b" e così via, poiché "a" si trovava nel maggior numero di parole, nelle strategie 1 e 2 abbiamo scelto " a" il 100% delle volte.Invece, sceglieremo ancora "a" una pluralità di volte, ma un piccolo numero di volte sceglieremo "z" anche se a potrebbe essere trovato in 10 volte più parole.Ho i miei dubbi sul fatto che questa strategia sia ottimale ma è stato utilizzato nella ricerca nel 2010.

Quindi ho due domande:

1. Qual è la strategia ottimale per indovinare le lettere che dovrei usare supponendo che il mio avversario sappia che utilizzerò questa strategia?In questo caso vogliamo ridurre al minimo il numero medio di tentativi necessari per indovinare la parola segreta.
2. Per una data parola, ad esempio "paga", qual è il numero medio di errori M che dovrei fare?Esiste un modo in forma chiusa per calcolare M, invece di eseguire questa simulazione molte volte e calcolare la media dei risultati?

Chiarimenti

• È possibile utilizzare qualsiasi dizionario inglese.Per esempio, questo dizionario inglese con 84.000 parole..Anche sottoinsiemi di dizionari scelti con cura per l'ambiguità potrebbero essere interessanti ma esulano dall'ambito di questa domanda.
• Non vi è alcun vincolo sulla dimensione della parola finché la parola è nel dizionario.L'indovino conoscerà la dimensione della parola prima di iniziare a indovinare.
• Conta solo il numero totale degli errori, che è indipendente dalla dimensione della parola.Non hai più possibilità per le parole più lunghe, o meno possibilità per quelle più brevi.
• Mi interessa solo ridurre al minimo il numero medio di errori.Se esistono due algoritmi ottimali che hanno un numero medio di errori altrettanto piccolo, entrambi sono accettabili.
• In linea di principio è possibile che si verifichi una situazione in cui la scelta di una lettera (ad esempio "b") porta a più informazioni di un'altra (ad esempio "a") anche se "a" ricorre in più parole possibili di "b".Sono aperto a questa possibilità anche nella pratica.I tre algoritmi sopra illustrati presuppongono che ciò non accada perché un'ipotesi corretta tende a fornire più informazioni di una errata (ad es.le informazioni sulla posizione di una lettera corretta sono generalmente migliori di "questa lettera non è nella parola").Ma un algoritmo ottimale non ha bisogno di fare questa ipotesi.

Answer 1

È possibile calcolare la strategia ottimale, ma il calcolo potrebbe essere piuttosto impegnativo e non sono sicuro che ti darà un grande vantaggio rispetto alla semplice euristica.Di seguito ti spiegherò come.L'idea principale è quella di utilizzare la programmazione dinamica.

Strategie deterministiche

Vorrei iniziare innanzitutto con il caso speciale delle strategie deterministiche per scegliere quale lettera indovinare successivamente, poiché sono più facili da analizzare.Questo ci darà un po’ di riscaldamento prima di passare alle strategie randomizzate (che probabilmente saranno superiori).

Lo stato del gioco in qualsiasi momento può essere riassunto dalla coppia $(g,r)$, Dove $g$ è l'insieme delle lettere finora indovinate, e $r$ sono le risposte (cioè la sequenza di spazi e lettere da $g$ visibile al giocatore).L'ordine delle ipotesi passate non ha importanza (motivo per cui è sufficiente avere un set $g$ delle ipotesi passate).Diremo questa parola $w$ è coerente con $(g,r)$ se rimane possibile, cioè se lo è la parola dell'avversario $w$ e tu fai le ipotesi $g$, quindi otterresti la risposta $r$.

Permettere $p(g,r)=1$ se è possibile vincere da qui, se partendo dallo Stato $(g,r)$.Ciò significa che esiste una strategia per vincere:dove non importa quale parola stia pensando l'avversario (purché sia ​​coerente con $(g,r)$), il numero di ipotesi sbagliate che hai fatto finora, più il numero che farai in futuro con questa strategia, non supererà il limite superiore.Altrimenti definisci $p(g,r)=0$.

Ora puoi calcolare $p(g,r)$ con programmazione dinamica, utilizzando la relazione di ricorrenza

$$p(g,r) = \bigvee_a \bigwedge_{(g',r')} p(g',r'),$$

Dove $a$ spazia su tutte le lettere non presenti $g$ (vale a dire, tutte le possibilità su quale lettera indovinare successivamente), e $(g',r')$ spazia su tutte le possibili risposte se indovini $a$ successivo (cioè $g'=g azza \{a\}$, e spaziamo su tutte le parole $w$ che sono coerenti con $(g,r)$ e calcolare la risposta $r'$ alle ipotesi $g'$ se la parola è $w$).

In particolare, ti suggerisco di calcolare $p(g,r)$ utilizzando la ricerca approfondita e la memorizzazione.Poi, $p(\emptyset, - - \cdots -)$ ti dirà se è possibile vincere entro il limite massimo, indipendentemente dalla parola scelta dall'avversario.Ripercorrendo il calcolo a ritroso è possibile ricostruire la strategia ottimale.

È fattibile?Immagino che lo sia.Penso al numero di stati possibili $(g,r)$ non è troppo grande.(In particolare, puoi ignorare gli stati $(g,r)$ dove hai già fatto troppe ipotesi errate e qualsiasi stato in cui solo una parola è coerente con quello stato è automaticamente una vittoria, quindi non necessita di ulteriori analisi.) Come ottimizzazione, dato uno stato $(g,r)$, puoi provare a enumerare tutte le parole $w$ che sono coerenti con loro e simulano alcune euristiche fisse e controllano se vincerà per ogni parola;in tal caso non è necessario effettuare ulteriori traversate in profondità e si può marcare immediatamente $p(g,r)=1$.Inoltre, devi solo considerare le ipotesi $a$ che compaiono in almeno una parola coerente con $(g,r)$.

Quindi dovrebbe essere abbastanza semplice calcolare la strategia deterministica ottimale.

Strategie randomizzate

Possiamo seguire un metodo simile per gestire strategie randomizzate, ma diventa un po’ più complicato.Adesso molla $p(g,r)$ denotano la probabilità di vincere da qui in poi, se utilizziamo le strategie ottimali da qui in poi.Possiamo ancora calcolarlo utilizzando la programmazione dinamica.

La differenza fondamentale sta nella relazione di ricorrenza in cui calcoliamo $p(g,r)$ dalle quantità $p(g',r')$ Dove $(g',r')$ spazia su tutti gli stati che potrebbero verificarsi dopo aver indovinato un'altra lettera.Qui abbiamo un semplice gioco a due giocatori.Per prima cosa scegliamo una distribuzione di probabilità sulle lettere non presenti $g$.Quindi l'avversario vede la nostra distribuzione e sceglie una distribuzione sulle parole $w$ che sono coerenti con $(g,r)$.La nostra vincita (e l'importo che l'avversario perde) è pari alla probabilità che vinceremo da qui in poi date quelle scelte.Si noti che questo può essere calcolato da $p(g',r')$ valori.Si scopre che poiché agiamo per primi e l'avversario vede la nostra scelta, l'avversario non ha bisogno di una strategia randomizzata;possono farlo altrettanto bene con una strategia deterministica, cioè scegliendo una singola parola $w$ in base alla nostra distribuzione.Quindi se formiamo una matrice $M$ Dove $M_{w,i}$ contiene la probabilità di vincere se scegliamo la lettera $i$ successivo e l'avversario sceglie la parola $w$;possiamo compilare $M_{w,i}$ COME $p(g',r')$ Dove $g'=g \coppa \{i\}$ E $r'$ è la risposta a indovinare $g'$ se la parola è $w$.Cerchiamo quindi di risolvere il problema di ottimizzazione $$\max_v \min_w (Mv)_w = -\min_v \max_w -(Mv)_w = -\min_v \|-Mv\|_\infty.$$ Questo può essere risolto utilizzando la programmazione lineare.Quindi, possiamo calcolare $p(g,r)$ utilizzando la programmazione lineare dai valori $p(g',r')$ Dove $g'$ è uno più grande di $g$.

Mettendo tutto insieme, utilizzeremo l'attraversamento approfondito con memoizzazione (o programmazione dinamica), utilizzando la programmazione lineare in ogni passaggio per risolvere il gioco a 2 giocatori.Questo ci dà la strategia randomizzata ottimale per giocare all'impiccato.

Il calcolo risultante potrebbe essere molto costoso, poiché richiede miliardi o trilioni di passaggi, in cui si risolve un programma lineare in ogni passaggio.Quindi, non so se sia realistico usarlo nella pratica.

Sono possibili alcune ottimizzazioni, come suggerito da @j_random_hacker.Puoi prima calcolare $p(g,r)$ per strategie deterministiche;allora devi solo considerare le strategie randomizzate per gli stati $(g,r)$ Dove $p(g,r)=0$.

Strategie euristiche

Hai elencato alcune euristiche ragionevoli per la scelta di una strategia.Ecco un'altra euristica.Dato lo stato $(g,r)$, enumerare tutte le possibilità per l'ipotesi successiva $a iente$.Concentriamoci su una singola lettera $a$.Quindi, per ciascuno $(g',r')$ ciò potrebbe verificarsi come stato successivo dopo aver indovinato $a$ (COSÌ $g'=g azza \{a\}$), contare il numero di parole $w$ consistente con $(g',r')$;prendi il massimo su questi numeri e usalo come conteggio associato $a$.La strategia euristica è scegliere la lettera $a$ il cui conteggio è minimo.

Calcolo del numero previsto di errori

È possibile calcolare il numero previsto di errori di una particolare strategia randomizzata utilizzando la programmazione dinamica.I dettagli sono simili a quelli sopra, ma la relazione di ricorrenza diventa più semplice:diventa

$$p(g,r) = \min_w \mathbb{E}[p(g',r')],$$

Dove $w$ spazia su tutte le parole coerenti con $(g,r)$, E $(g',r')$ è la distribuzione sullo stato successivo se la parola è $w$ e la prossima lettera indovinata viene scelta dalla tua strategia.Data la tua strategia e la parola $w$, è facile calcolare la distribuzione sulle ipotesi e quindi ottenere la distribuzione sugli stati successivi, quindi è facile calcolare $\mathbb{E}[p(g',r')]$.