An interesting game for the family regardless of age. The enthusiasm to break the game logic; solve by machine (Only) was very compelling.
Apart from having a Live notes place, I would like programmers, mathematicians and AI enthusiast to participate and help solve it collectively.
Solving Heuristic problems is itself Heuristic and we may have to go back and forth to finally achieve the solution :)
Note: One can always use a Rule Engine to solve such problems. Drools Planner is a great tool for these things so maybe other simulators. However for any rule engine, one must be clear on the Hard & Soft Constraints. One cannot run away from studying the nature of the problem and expressing it properly before using any tool or methodology to solve it.
AI Backdrop
While it seemed that Brute force is certainly one way to handle the problem (since the nature seems NP-Complete). Studying how humans make a decision and if at a superficial level can we train machines to think similar is very much associated with solving puzzles like these (Also towers of Hanoi, Sudoku etc). Although there is a lot of research and literature on the subject, the process of learning this subject is perhaps more fun and time consuming when it is experimental and observational.
This blog represents an experiment and the path to solving the problem via machines.
Critical take away's will be added to this article while discussions will be maintained in the thread of the blog.
Brute Force Strategy
Computers today are fast, but AI problems are very demanding. As the combinatorial space grows, brute force needs to be replaced by any advantage of finding the optimal path to the solution or solution with the least Error Possible(Technically speaking the Mean Square Error). Theoretical filtration can drastically improve your chances of finding solutions faster.
The lesser money you have to spend on processors (literally or even a computational unit on some grid); the better your approach should be :)
So when is an alternative worth trying compared to the Brute Force?
To answer that we have to technically evaluate what Brute force means for a problem. Refer to: Wiki definition
This basically means to attempt to try every combination to find the solution. If the problem cannot state the number of solutions before hand, you have to exhaust all possible options. In this case Brute Force is the worst case.
Brute Force : What happens the number of required outcomes is pre-specified?
This means that you may reach the required solutions before having to search through every possible combination. The questions are:
- Does the Law of Large Numbers apply here?
- How do we determine on an average what is the worst case number of combination's one has to try to be successful, even with Brute Force?
Whatever algorithm or approach is chosen to solve the problem must beat its Brute Force counter part. For this reason we must search for a good evaluation criteria for our algorithms. I think this would boil down to defining a good biased estimator for selection.
[Coming : Analysis of the Set Problem, Statistical inferences, patterns etc.]
Draw Inferences from a Solved Puzzle (Training Phase):
PICTURE OF PUZZLE SOLVED
Rough Notes
Particular Sample Puzzle composition
Number: 8 (twos), 3 (threes), 1 (one) = 12 [High variance least combination's]
Colour: 4 of each = 12 [No variance, most combination's] ----> Intuitively this means that each successful result combination 'MUST HAVE' one of each colour! = A Hard Constraint for THIS problem (not the game mind you), derived by probability. Valuable in reducing the search space.
Fill : 5X (Stripe), 4Y (Solid), 3Z (Filled) = 12 [v little variance, Lots of combination's]
Shape : 6A (Diamond), 3B (Oval), 1C (Squiggle) = 12 [less combination's]
...we can see how statistical observations can help in having good selectors or filtering redundant combination's more quickly (no need to even pick them).
For example: We know that any combination that has the same colour repeated is useless for this particular experiment.
Swap Space
1. 6 (possible results) x 3 (Result Size) = 18 : The number of elements to be used across the solutions. There are 12 elements. This means some have to be repeated.
Q) Are they repeated twice or more, biased by composition?
A) Biased by composition. Some repeat 3 (1), some don't even occur once in the final outcome (1). Standard is 2.
Another Game / Experiment Sample Result
[Coming : The approach that can beat Brute Force to solve the Sets problem]
TODO:
- Mathematically evaluate if searching by Brute Force for a sample constrained by Number of Solutions pre-specified vs un-specified is any different?
- Use a rule Engine like Drools to solve the problem. Measure its efficiency on average case to solve the experiments.
- Build a Tool: Scriptable Simulator for defining Constraints, Seed values, Evaluation Functions and graph Plotter. Possibly define parallel threads and asynchronous behavior/external points in Java + Scala + Processing / SVG.imo Defining Rules in Rule Engines is still Clunky!
- Search/Define a a Biased Estimator that reduces the search space
References / Related Reading
- Employee Shift Rostering
- Automated Planning problems
- Drools Planner
- Brilliant Classroom Planner
- Interesting & Not Rleated : Nash Equilibrium
- Conditional Probability : The probabilities of events in games keep changing ad are dependent on events that have already occurred.
- Markov Chains : Given the present selected events/variables, the future is conditionally independent of the past. (Not applicable for this particular problem imo but worth understanding.)
- How Spell Check Works
