| Genetic Algorithms | hught
Kwon-Tom Obsessive
Puzzles: 1967
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: 2080
Best Total: 32m 53s | 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: 6396
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: 1967
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: 2080
Best Total: 32m 53s | 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.. |
|
