Wednesday, 18th July 2018
Puzzles Solved Yesterday: 128
Home | Register | Login | Current Puzzle | Archives | Leaderboard | Forum | Tutorial | FAQ
Forum Index
 
Genetic Algorithms
hught
Kwon-Tom Obsessive
Puzzles: 1966
Best Total: 30m 27s
Posted - 2008.09.16 18:49:13
Here's a thought: it should be possible to create a genetic algorithm for solving these puzzles. That is, start with a population of "creatures" whose genomes are encodings of puzzle rules (as discussed passim). Give them puzzles, and compare their answers against the solutions, rating the creatures accordingly, and ranking them in order. Those in the top quarter of the list get to "breed" - those in the bottom quarter are replaced by some combination of breeders' and others' genomes. Now and again a cosmic ray zaps a bit somewhere, to represent random mutation. After many generations, you may get a creature that can solve not just puzzles it has seen, but also puzzles it hasn't seen.

So my question is: how could you encode rules, essentially as strings of numbers/characters? Would you do it as straight pattern-matching, or are there more subtle and elegant ways of doing it? What data would be needed?
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 930
Best Total: 38m 37s
Posted - 2008.09.16 20:17:34
Quote:
Originally Posted by hught
Here's a thought: it should be possible to create a genetic algorithm for solving these puzzles. That is, start with a population of "creatures" whose genomes are encodings of puzzle rules (as discussed passim). Give them puzzles, and compare their answers against the solutions, rating the creatures accordingly, and ranking them in order. Those in the top quarter of the list get to "breed" - those in the bottom quarter are replaced by some combination of breeders' and others' genomes. Now and again a cosmic ray zaps a bit somewhere, to represent random mutation. After many generations, you may get a creature that can solve not just puzzles it has seen, but also puzzles it hasn't seen.

So my question is: how could you encode rules, essentially as strings of numbers/characters? Would you do it as straight pattern-matching, or are there more subtle and elegant ways of doing it? What data would be needed?

I think that genetic algorithms aren't suitaible for this type of puzzle (mainly in term of speed). Encoding rules is not so difficult, but I don't understand how you will rank your "creatures" if the solution for the current puzzle is still unknown.. Each puzzle is different so I think it will doesn't work.. Also many of important aspects of this puzzle can't be implemented in such way - such as closing loop too early, locks, coloring... Maybe you will be able to implement this (but i have no idea about your evalution function), but it should be terrible slow... I am trying to implement the fastest algorithm for this type of puzzle and genetic algorithm is not the proper way...
pqg
Kwon-Tom Obsessive
Puzzles: 4072
Best Total: 15m 37s
Posted - 2008.09.17 01:18:36
I don't think genetic algorithms are a great idea for creating a solver, but if used alongside a decent solver they are potentially a very powerful way of creating new high-difficulty puzzles. (Start with a puzzle, introduce random variations, discard those that are insoluble, selectively breed for those with the longest solving time/most explorations needed for solution, repeat...)
hught
Kwon-Tom Obsessive
Puzzles: 1966
Best Total: 30m 27s
Posted - 2008.09.17 07:11:44
To be fair, I wasn't expecting GAs to work very quickly, I was more interested in seeing whether this could be done at all. Being able to use primitives in the genome which represent such operations as "examine next line in chain" and "have we examined this line already?" may be enough to deal with loops, for instance. So what primitives would be needed?
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 930
Best Total: 38m 37s
Posted - 2008.09.17 09:25:55
Quote:
Originally Posted by hught
To be fair, I wasn't expecting GAs to work very quickly, I was more interested in seeing whether this could be done at all.

I'm not sure whether this could be done. The main reason is how to estabilish fitness function (if you don't know the solution yet - in time of solving) which will assign value to you creatures and make new ones from strong creatures. Maybe you have an idea.

Quote:
Originally Posted by hught
Being able to use primitives in the genome which represent such operations as "examine next line in chain" and "have we examined this line already?" may be enough to deal with loops, for instance. So what primitives would be needed?

Examinig next line in chain looks like classical backtrack. Maybe I didn't understand your idea well and I am wrong, then I apologize..

Forum Index