What kind of programming pattern is appropriate for programming an algorithm with rules and exceptions?

Question

I'm interested in coming up with an algorithm to solve a guessing game. The player is attempting to guess a sequence of 4 unique numbers from 1 to 9. After a guess, they are told how many numbers of their guess are correct and in the correct position and how many are correct and in the wrong position.

The approach I'm taking is to have a starting collection of all of the possible guesses and a collection of all the possible numbers. The collection of guesses is used to give the player an idea of all valid guesses remaining. The collection of numbers stores information about each digit:

• whether it is definitely present or definitely not, and
• which position it is definitely in or definitely not in.

Then, as the player is given more clues, I remove all guesses that must be invalid and update assumptions about the digits. The idea is that, after a certain number of guesses, the algorithm should continue to improve their odds of choosing the correct sequence.

I want to accomplish the process of striking items off of the list and making assumptions about the digits by creating rules. Whenever a rule's conditions are met, the number collection and/or guess collection should update. Rules should include:

• if the current guess has no numbers in the correct position, all numbers in the sequence are definitely not in their current position,
• if 4 of the numbers in the sequence are present, then all guesses without all 4 of these numbers are invalid,
• if two guesses have 8 unique numbers between them and the sum of present numbers is only 3, then the 9th digit not guessed is definitely present,
• etc.

I like the idea that I, as the developer, can continue to add rules as I discover patterns that I have not noticed (or have not been able to formalize) without much hassle. The problem lies in implementation.

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

Answer 1

You might also look into expert systems, business rule engines, declarative programming, inference engines, A* search algorithm, Rete algorithm, Prolog, Datalog, CLIPS, metaknowledge, metaprogramming, reflection, etc...

J.Pitrat's blog has interesting entries, e.g. Know thyself etc...

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

Yes, it is called an expert system (and is probably more a programming paradigm, or even a buzzword, than a programming pattern), the set of rules and facts being called the knowledge base

Experts systems have been in vogue in the 1980s & 1990s. Then came the so called AI winter (where AI meant artificial intelligence - an expression whose meaning has varied a lot during time).

^{Off-topic: I believe that the next AI winter would be an Abstract Interpretation winter. Static analysis of source code is today also a buzzword, even if formal methods are very useful, but they are not the silver bullet that some people proclaim.}

AGI (artificial general intelligence) is however a very interesting research field.

Answer 2

Your problem is comparable to a program simulating a chess player. When in need of using a set of knowledge rules to produce the most suitable decisions, the logic programming seems to be the ideal solution. Using such a programming language (like Prolog), you can define the whole set of rules that govern your 'world', and finally you have to create a query regarding the ways in which a specific logical statement can become true. The program will execute all the possible paths from the initial condition to the final one, and it will output all the possible solutions. However, be aware that if the decision tree has too many branches, then this will be quite cpu-stressful.

On the other side, you can use a procedural language (like Java or perhaps R would be good, since it is focused on Machine Learning features). You can implement on your own one of the well-known Pathfinding algorithms (established by the AI community) to dynamically solve your problem. Each node in your graph will correspond to a decision state and the target node will be the final state. In the web you can find a lot of tutorials and demos of implementations of those algorithms.