Che tipo di schema di programmazione è appropriato per programmare un algoritmo con regole ed eccezioni?

4

Sono interessato a inventare un algoritmo per risolvere un gioco di ipotesi. Il giocatore sta tentando di indovinare una sequenza di 4 numeri univoci da 1 a 9. Dopo un'ipotesi, viene loro indicato quanti numeri della loro ipotesi sono corretti e nella posizione corretta e quanti sono corretti e nella posizione sbagliata.

L'approccio che sto prendendo è quello di avere una raccolta iniziale di tutte le possibili ipotesi e una raccolta di tutti i numeri possibili. La raccolta di ipotesi è usata per dare al giocatore un'idea di tutte le ipotesi valide rimanenti. La raccolta di numeri memorizza le informazioni su ciascuna cifra:

  • se è sicuramente presente o no, e
  • in quale posizione è decisamente dentro o sicuramente non presente.

Quindi, dato che al giocatore vengono dati altri indizi, rimuovo tutte le ipotesi che devono essere non valide e aggiorna le ipotesi sulle cifre. L'idea è che, dopo un certo numero di tentativi, l'algoritmo dovrebbe continuare a migliorare le probabilità di scegliere la sequenza corretta.

Voglio completare il processo di eliminazione degli elementi dall'elenco e fare ipotesi sulle cifre creando regole. Ogni volta che vengono soddisfatte le condizioni di una regola, la raccolta di numeri e / o la raccolta di congetture devono essere aggiornate. Le regole dovrebbero includere:

  • se l'ipotesi corrente non ha numeri nella posizione corretta, tutti i numeri nella sequenza non sono sicuramente nella posizione corrente,
  • se sono presenti 4 numeri nella sequenza, allora tutte le ipotesi senza tutti e 4 questi numeri non sono valide,
  • se due ipotesi hanno 8 numeri univoci tra loro e la somma dei numeri presenti è solo 3, quindi la nona cifra indovinata è sicuramente presente,
  • ecc.

Mi piace l'idea che io, come sviluppatore, possa continuare ad aggiungere regole mentre scopro schemi che non ho notato (o che non sono stato in grado di formalizzare) senza troppi problemi. Il problema sta nell'implementazione.

Esiste un modello di programmazione che mi consente di creare un insieme di regole estendibili per testare e reagire a?

    
posta Koviko 27.02.2015 - 16:02
fonte

2 risposte

4

Potresti anche consultare sistemi esperti , motori di regole aziendali , programmazione dichiarativa , motori di inferenza , Algoritmo di ricerca A * , Algoritmo di rete , Prolog , Datalog , CLIPS , metaknowledge , metaprogramming , reflection , ecc ...

Il blog di J.Pitrat ha voci interessanti, ad es. conosci te stesso ecc ...

Is there a programming pattern that allows me to make an extendable set of rules to test for and react to?

Sì, si chiama un sistema esperto (ed è probabilmente più un paradigma di programmazione, o anche una parola d'ordine, che un modello di programmazione), l'insieme di regole e fatti chiamato il knowledge base

I sistemi di esperti sono stati di moda negli anni '80 & 1990. Poi è arrivato il cosiddetto AI inverno (dove AI significava intelligenza artificiale - un'espressione il cui significato è variato molto nel tempo).

Off-topic: Credo che il prossimo inverno AI sarebbe un Interpretazione astratta inverno. L'analisi statica del codice sorgente è oggi anche una parola d'ordine, anche se metodi formali sono molto utili, ma non sono il proiettile d'argento che alcuni la gente proclama.

AGI (intelligenza artificiale generale) è comunque un campo di ricerca molto interessante.

    
risposta data 24.03.2015 - 10:21
fonte
2

Il tuo problema è paragonabile a un programma che simula un giocatore di scacchi. Quando si ha bisogno di utilizzare un insieme di regole della conoscenza per produrre le decisioni più adatte, la programmazione logica sembra essere la soluzione ideale. Usando un tale linguaggio di programmazione (come Prolog), puoi definire l'intera serie di regole che governano il tuo "mondo", e infine devi creare una query sui modi in cui una specifica affermazione logica può diventare vera. Il programma eseguirà tutti i possibili percorsi dalla condizione iniziale a quella finale e produrrà tutte le possibili soluzioni. Tuttavia, tieni presente che se l'albero decisionale ha troppi rami, questo sarà piuttosto cpu-stressante.

Dall'altro lato, è possibile utilizzare un linguaggio procedurale (come Java o forse R sarebbe buono, poiché si concentra sulle funzionalità di Machine Learning). È possibile implementare da soli uno dei noti algoritmi Pathfinding (stabiliti dalla comunità di intelligenza artificiale) per risolvere dinamicamente il problema. Ogni nodo nel tuo grafico corrisponderà a uno stato decisionale e il nodo di destinazione sarà lo stato finale. Nel web puoi trovare molti tutorial e demo di implementazioni di questi algoritmi.

    
risposta data 24.03.2015 - 09:42
fonte

Leggi altre domande sui tag