Slashdot Mirror

← Back to Stories (view on slashdot.org)

World's First Game-Playing DNA Computer

Posted by simoniker on from the why's-the-enzyme-always-allowed-to-go-first? dept.

An anonymous reader writes "NewScientist.com posted an article today about the first game-playing 'computer' powered by DNA logic. An interesting read, although not at all a practical alternative for those looking to replace their PlayStation2 with the next great platform." The machine is "...an enzyme-powered tic-tac-toe machine that... uses a complex mixture of DNA enzymes to determine where it should place its nought or cross, and signals its move with a green glow."

6 of 166 comments (clear)

  1. CNN article by kaan · · Score: 5, Informative

    here's a similar article titled "DNA basis for new generation of computers"

  2. Naught or cross? by YetAnotherName · · Score: 1, Informative

    That's O or X in the US of A, baby. :-)

    Crosses and naughts...sheesh.

  3. Re:Smart enough to make a DNA computer but not to. by stienman · · Score: 5, Informative

    from http://www.wikipedia.org/wiki/Tic-tac-toe

    "In a normal 3x3 tic-tac-toe game, both players have a strategy to draw the game. In fact, any move by the first player leads to a draw with best play.

    "Statistically the best opening move is in one of the corners, after this move has been made if the opponent takes any square other than the centre one, then the first player can play in such a way that a win is certain, as shown in the above game. "

    -Adam

  4. Re:Silly Human! by Dudio · · Score: 2, Informative

    Indeed. The Tropicana in Las Vegas used to have a chicken trained to play tic-tac-toe, with cash prizes for anybody who could beat it. I didn't see it when I was just out there for Defcon though, so maybe the novelty wore thin.

  5. Re:DNA based computer used to solve TSP by rebelcool · · Score: 2, Informative
    Yes and no. It may indeed be true that you can't solve it in less than O(N!). Theres alot of problems similar enough to travelling salesman that if you can provide such a proof that you can't do it in less than N! (or a proof that shows you can), then those problems will fall in line as well.

    If indeed it can be shown the problem may not be solved in less than N!, then the problem becomes hardware to solve. This is why DNA and quantum computing will be handy because of their inherent parallel nature, in very tiny sizes.

    --

    -

  6. Re:DNA based computer used to solve TSP by Anonymous Coward · · Score: 1, Informative

    Ehm ... Sorry but I would like to point out a couple of things. Finding a path which goes through all cities is of course trivial if you assume that you have connections between each pair of cities (i.e. you are on a complete graph). If the graph is not complete, then the problem gets difficult (ie this is the so called hamiltonian cycle problem, which is in its decision version a well known NP-complete problem).

    On the other hand, the TSP problem is a NP-Hard problem, and a well known one. This does not mean the best algorithm goes like n!. Indeed, this is the most stupid approach (i.e. try them all), there are better (still not polynomial) algorithms using eg dynamic programming. There are even much better approaches based on branch and bound and cutting plane techniques, which, although of course not polynomial, perform quite well for reasonable size.

    The problem is well studied in the field of heuristics in combinatorial optimization. Nice methods which perform very well are based on genetic algorithms and (recently) on ant colonies. The problem is so well known that it is widely used as a (serious) toy example for new heuristics, as well as in DNA computing. I recently attended a conference on the subject where the TSP problem was shown as an example.