Evodoku?

Hi everyone. I think we’re collectively at our best when we explore new things. As things seem we’re a little fractious right now let me offer up my idea for what might be a pleasant diversion.

Sodoku: http://www.sudoku.com/

It kind of has a genome and fitness criteria, right?

 

Let’s take just one 3×3 grid. It could have a genome of 9 digits, and competing fitness functions: (sum or product, max or min) for 3 rows, 3 columns, 2 diagonals and of course some rule about using all the digits (or not if we want better mutations). Each of the 9 genes would affect 2 or 3 (or 4 for gene number 5, in the middle of the square) of the fitness functions. Can we create a simulation, with drifting fitness functions and see how organisms evolve. Will this show islands of function and a path to traverse between them?  This might be fun because a mutation can help in one regard whilst hurting in another. I’ll leave this here for now, let me know if anyone is interested…

 

 

21 thoughts on “Evodoku?”

  1. Neil Rickert

    I’ll be interested if you can make something of this. However, to me, evolution and sudoku seem to be polar opposites.

    Sudoko is a logic problem. It is logic all the way. Pragmatics are of little use.

    Evolution is pragmatics all the way. We can describe it in such a was that it might look like logic, but that isn’t how it really works.

    Sudoku might be a good example of “irreducible complexity”.

  2. keithskeiths

    Neil,

    Sudoko is a logic problem. It is logic all the way.

    Rich is proposing modifications to Sudoku so that it isn’t merely a logic problem. Take a look at his last paragraph.

  3. petrushka

    Grid Weasel. Not that there’s anything wrong with that.

    That’s two dimensions. You could make it three, four, or N, for even more fun. Biology has many dimensions of fitness.

    I’m betting that when you increase the number of fitness dimensions, an evolutionary algorithm will outperform a human. Just as with the Travelling Salesman problem.

  4. Tom EnglishTom English

    The first “evolutionary” approach that comes to mind is to make the problem into one of multiobjective optimization. Define 9 \times 9 \times 9 = 27 “fitness” functions, one for each row, column, and 3-by-3 grid. The fitness of a region might be the number of distinct digits that it contains. There’s a slew of ways to handle selection in multiobjective evolutionary optimization. I generally would not sum the values of the multiple objective functions, i.e., to produce a scalar fitness, but it might be best here to start with just that, and see what happens.

  5. Tom EnglishTom English

    Rich, I hate seeing you with no takers. I’ve been going hard at something else, and don’t have many sparks left that will jump synapses.

    Evolutionary computation is really not the way to do this sort of problem. But it would be interesting to see what happens. Recombination would be fun, because there are three reasonable ways to do it, and no reason I can see (when brain dead) to exclude any of them: exchange columns or exchange rows or exchange 3×3 regions of parents. That is, generate 6 offspring by recombination of 2 parents in 3 different ways.

  6. RichardthughesRichardthughes Post author

    Tom English,

    No worries, Tom (& Keiths) – they can’t all be winners, or maybe its time is not yet.

    I enjoy the point at which evolution meets games people understand and the solutions are too complicated to be solved intuitively but is not so complicated that it can’t be followed. My hope is that “show me” doubters will be able to follow along and see evolution in action.

  7. MungMung

    Intelligent Design can produce games like sudoku.

    Which games have been produced by un-intelligent non-design?

  8. keithskeiths

    Intelligent Design can produce games like sudoku.

    Which games have been produced by un-intelligent non-design?

    The games you play. Mung.

  9. Tom EnglishTom English

    Mung: Intelligent Design can produce games like sudoku.

    Which games have been produced by un-intelligent non-design?

    If I had the time to spend on giving you a dose of your own medicine, I’d produce a bunch of quotations regarding applications of game theory to evolution, and add emphasis to all occurrences of the word game. I mean, game theory wouldn’t work if evolution were not a game — right?

  10. Tom EnglishTom English

    Richardthughes: I enjoy the point at which evolution meets games people understand and the solutions are too complicated to be solved intuitively but is not so complicated that it can’t be followed. My hope is that “show me” doubters will be able to follow along and see evolution in action.

    Arguments from improbability (including those that express improbability on a log scale, and refer to it as information) are rooted in the misconception of evolution as a problem solver. The fundamental reason that Marks, Dembski, and Ewert are wrong is that they treat models of evolution as problem solvers.

  11. PatrickPatrick

    keiths:

    Which games have been produced by un-intelligent non-design?

    The games you play. Mung.

    I’ve got to disagree with you there. Mung’s games are carefully designed to achieve his goals — any response whatsoever.

  12. PatrickPatrick

    Richard,

    I’ve been swamped at work but I do find your idea interesting. I wrote a Sudoku solver that was based on the algorithms people use rather than the usual constraint satisfaction approaches. That was an interesting exercise.

    Using an EA would be interesting as well. I’ll see if my GA engine can be used for that.

  13. fifthmonarchyman

    Neil Rickert: Sudoku might be a good example of “irreducible complexity”.

    I think I might agree.
    It definitely would be interesting to explore

    peace

  14. keithskeiths

    Patrick,

    I’ve got to disagree with you there. Mung’s games are carefully designed to achieve his goals — any response whatsoever.

    It might cut down on Mung’s seagull commenting if we gave him a dedicated thread in which people dropped by occasionally to say ‘hi’ and validate his existence.

  15. Tom EnglishTom English

    It might be fun to propagate constraints in a genotype-to-phenotype map, and to treat constraint violations in the phenotype as lethal. I’m tempted to chew through the leather straps (restraints are constraints), and give it a try.

  16. MungMung

    Patrick: Mung’s games are carefully designed to achieve his goals — any response whatsoever.

    That make you what, yet another sucker?

  17. PatrickPatrick

    Mung:

    Mung’s games are carefully designed to achieve his goals — any response whatsoever.

    That make you what, yet another sucker?

    Possibly, depending on what my goals are. Clearly I need to rethink them.

  18. Tom EnglishTom English

    Richardthughes,

    See what it leads to? (See that I don’t have time for Sudoku?)

    3.7.3 A man-in-the-loop sneaks in active information

    Computer programs, including evolutionary search, are invariably iteratively designed through debugging and tweaking.

    3.7.3.1 Evolving Tic-Tac-Toe to checkers to chess

    An interesting take on iterative design with a man-in-the-loop starts in 1993 when an evolutionary program “taught itself” to play tic-tac-toe. 32 The same researchers who developed the tic-tac-toe program published a paper eight years later in 2001 where a different evolutionary program they wrote learned to play checkers. 33 The skill of evolutionary programs they wrote had, in a sense, evolved to a higher level. Then in 2004 the team announced they had taught a computer using evolution to play chess. 34 Tic-tac-toe to checkers to chess is the type of information increase proponents of Darwinian evolution would celebrate. But the programming ability got better and better not because of evolution but primarily because of the increasing skill of the programmers.

    This evolution in the capability of evolutionary programs would clearly not have happened without a man-in-the-loop.

    Robert J Marks II; William A Dembski; Winston Ewert. Introduction to Evolutionary Informatics (Kindle Locations 1418-1428). World Scientific Publishing Company. Kindle Edition.

  19. PatrickPatrick

    Tom English:

    3.7.3 A man-in-the-loop sneaks in active information

    Computer programs, including evolutionary search, are invariably iteratively designed through debugging and tweaking.
    . . .

    Robert J Marks II; William A Dembski; Winston Ewert. Introduction to Evolutionary Informatics (Kindle Locations 1418-1428). World Scientific Publishing Company. Kindle Edition.

    Therefore the weather is designed because weather simulations are created through iterative debugging and tweaking.

    This is yet another example of how intelligent design creationism is scientifically vacuous.

Leave a Reply