A project made up and written during Oded Ben Dov's bachelor degree in Computer Science.
This project uses common AI techniques in order to search a formula that produces specific values in a specific order.
Computer Science deals, among other things, with combinatorial problems such as "How many possibilities do I have to position 5 people in a row?" (5! = 120) or "How many tetris shapes are there with 4 squares?" (7, without counting rotations).
Some of these problems are still unsolved. One example of such is what started this project - "How many tetris shapes are there with
n
squares?" (Known as the
Counting Polyominoes problem
). We know the answer for 1 square - that's easy - it's just 1 shape. For 2 squares we can still only create 1 shape (both options are the same if disregarding rotation). For 3 squares we can compose 2 different shapes, for 4 squares 7 shapes, and so on.
Yet, the formula for the number of diffrent shapes given n squares, is still unknown. And this is where the AI comes in. Our agent builds a formula like it's building a puzzle. It just tries to compose a formula by appending different operators with different operands, and checks whether the resulting formula produces the required series.
Thus, in the example above, the agent will try billions of different formulas, until it finds one that will produce 1,1,2,7 for n=1,2,3,4 respectively. The resulting formula can produce the wrong number for n=5, but from our experiments 4 values were usually enough for the agent to find the correct formula.
Currently the agent uses the Best First algorithm, and tries the following operators: +, -, *, /, !, choose, power, sigma (set addition) and pi (set multiplication). It iterates some hundred thousands formulas a second, and has found the formula for the
Catalan Series
in about a minute and a half.
We are working on finalizing the project, so researchers could put it to real use. So far it is yet to find formulas for open problems, but hopefully in the hands of other researches it might still stumble upon some great discovery. There is also a paper due on this research, but it's hard to say when it will come out.
Keep posted to see when it becomes available for public use.
