DNA computer unbeaten at tic tac toe.

DNA computer unbeaten at tic tac toe.

Post by Ken Kubo » Sat, 23 Aug 2003 08:46:01



      DNA computer unbeaten at tic tac toe

      Noughts and crosses automaton heralds medical robots.
      21 August 2003
      HELEN PEARSON

      A DNA computer called MAYA has won every game of tic tac toe it has
played against human opponents - over 100 in all.

      In the classic puzzle, also called noughts and crosses, two players
take turns to bag squares of a three-by-three grid, battling to complete the
first line. MAYA has a three-by-three array of wells in a plastic laboratory
dish, each filled with a unique*tail of enzymes1. Feeding it a
particular combination of DNA fragments triggers enzymes in one well to
generate a glowing dye.

      A game begins when a human player adds magnesium to all of the wells.
This fires up the enzymes to play their first move - always the centre
square.

      Current rules dictate that the human then has to play either the top
left corner or left middle, by adding the appropriate DNA fragment to every
well - he or she has eight DNA pieces, each corresponding to the eight
remaining places on the board. The DNA causes enzymes in another of the
squares to glow, and so the game goes on.

      MAYA never slips up - it is unbeatable even if its human opponent
plays perfectly, in which case there is a draw. It was invented by Milan
Stojanovic, of Columbia University in New York, and Darko Stefanovic, of the
University of New Mexico in Albuquerque.

      A similar approach might be used to create other logic-puzzle
computers, says Stefanovic, such as one to solve the '*s and
missionaries' conundrum. Here players figure out how to ferry three
*s and three missionaries across a river, never allowing the hungry
to outnumber their prey.

      Molecular automatons might one day find medical uses. Injected into
the *, they could recognize molecules on cancerous or healthy cells to
deliver a drug accurately. "We don't want to go too deep into games or the
[medical] community will not take us seriously," says Stojanovic.

      References
        a.. Stojanovic, M. N. & Stefanovic, D. A deoxyribozyme-based
molecular automaton. Nature Biotechnology, published online,
doi:10.1038/nbt86 (2003).

--
Ken

"Iran would be dangerous if they have a nuclear weapon."

- Washington, D.C., June 18, 2003
 - President Bushisms

begin 666 spacer_trans.gif
M1TE&.#EA`0`!`)$``````/_______P```"'Y! $```(`+ `````!``$```("
$5 $`.P``
`
end

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Randall R Schul » Sat, 23 Aug 2003 09:50:10


That's not particularly impressive in itself.

Tic-tac-toe is decidable. It's eminently tractable to examine the game
tree fully at each move and reliably play to no worse than a draw.

Randall Schulz


>       DNA computer unbeaten at tic tac toe


 
 
 

DNA computer unbeaten at tic tac toe.

Post by Kent Paul Dola » Sat, 23 Aug 2003 15:48:04


Lest this plague of cute announcements off topic for the newsgroups
targeted continue, these are by design low traffic newsgroups, which go
occasionally for months with no articles at all between flurries of
postings.  This is exactly as intended and wanted.

Peace and quiet here is not "a problem", nor are you required to provide
some "solution" which in your case is simply undesirable noise compared
to the group charters.

Stop showing off your ability to browse the net. All of us can do that
for ourselves. I don't care how clever you think you are, nor probably
do other readers: your contributions are unwelcome.

Newsgroups exist elsewhere for nanotechnology, biotechnology, "hardware"
computational mechanism innovations.  None of those are artificial life,
none of those are application of evolutionary algorithms to search of
complex fitness landscapes.  Those are the topics of interest in the
groups you are spamming.

xanthian.

--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Anthony Bucc » Sun, 24 Aug 2003 01:24:08


Quote:> Newsgroups exist elsewhere for nanotechnology, biotechnology, "hardware"
> computational mechanism innovations.  None of those are artificial life,
> none of those are application of evolutionary algorithms to search of
> complex fitness landscapes.  Those are the topics of interest in the
> groups you are spamming.

Game-playing falls squarely within the realm of AI.  The fact that a
newcomer to the computational-substrate arena (DNA) could implement a
strategy to play a game is inherently interesting and relevant to AI.  AI
is also concerned with problems like automatic programming.  Personally,
I'd really like to see a setup which could automatically discover how to
play tictactoe (versus being told how to do it by a smart person, which is
what has been done thus far).  If DNA computing happens to crack that one,
then great!

That said: please stop spamming the board with press releases.  I don't
want to see them here for the 5th time either.

Anthony

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Tim Tyle » Sun, 24 Aug 2003 02:46:45



: Game-playing falls squarely within the realm of AI.  The fact that a
: newcomer to the computational-substrate arena (DNA) could implement a
: strategy to play a game is inherently interesting and relevant to AI.  AI
: is also concerned with problems like automatic programming.  Personally,
: I'd really like to see a setup which could automatically discover how to
: play tictactoe (versus being told how to do it by a smart person, which is
: what has been done thus far).  If DNA computing happens to crack that one,
: then great!

It's not a very difficult problem, though - since the number of
possible games is so small.
--
__________

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Anthony Bucc » Sun, 24 Aug 2003 05:41:52


Quote:> It's not a very difficult problem, though - since the number of
> possible games is so small.

Playing tictactoe is easy.  *Learning* to play tictactoe from scratch is
not.  It's important not to confuse the two problems.  People have had a
remarkably hard time with the latter problem.

Anthony

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Tim Tyle » Sun, 24 Aug 2003 19:37:48



:> It's not a very difficult problem, though - since the number of
:> possible games is so small.

: Playing tictactoe is easy.  *Learning* to play tictactoe from scratch is
: not.  It's important not to confuse the two problems.  People have had a
: remarkably hard time with the latter problem.

It depends on what you mean by "from scratch".

Building a machine that can learn to play /any/ deterministic game that
consists of two players alternately adding monochrome counters to an empty
3x3 board is not terribly difficult - even if the machine has to be
constructed before the rules of the game it has to learn are specified.

If we have some rocks and an ammonium-nitrogen atmosphere to start
from, though - then things can get tricky ;-)
--
__________

 
 
 

DNA computer unbeaten at tic tac toe.

Post by SeeBe.. » Mon, 25 Aug 2003 01:48:26


<snip>

Quote:> Building a machine that can learn to play /any/ deterministic game that
> consists of two players alternately adding monochrome counters to an empty
> 3x3 board is not terribly difficult - even if the machine has to be
> constructed before the rules of the game it has to learn are specified.

Can you elaborate on that?  Please explain in detail, so that I can write the
program, how to make a computer learn to play perfect tic-tac-toe, without
programming any strategy about how to play the game.  (or send me the source
code of such a program)

I suspect it may not be nearly as easy as you think.

Thank You,

Mitchell Timin

m

--
http://sourceforge.net/projects/annevolve is what I'm into nowadays.
Humans may write to me at this address: zenguy at telus dot net

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Anthony Bucc » Mon, 25 Aug 2003 06:59:56


Quote:> It depends on what you mean by "from scratch".

> Building a machine that can learn to play /any/ deterministic game that
> consists of two players alternately adding monochrome counters to an empty
> 3x3 board is not terribly difficult - even if the machine has to be
> constructed before the rules of the game it has to learn are specified.

To set up such a thing, you need to:

a) Decide how to represent a player.  There is a lot of danger of
including human knowledge at this stage.  Do you give it knowledge of the
symmetries of the board (rotations, mirror images...)?  If so, you've
helped it tremendously, given it a much simpler problem to learn (in ttt,
there are ~5,500 board configs w/o symmetries, ~800 with).

Do the players build models of one another?  Or do they simply look at the
current board state and make a move?  If you make a choice here, you've
also helped.

b) Decide how to represent the board.  Is it just an array with marks, or
does it give the players further information.  E.g., in ttt: "there are
two x's in a row on the third column".  Info like that helps a lot, too.

But you're right.  On a board that size, you can simply expand the entire
game tree to the leaves and store the game tree in RAM.  But the fact you
can do that is human knowledge, too.  Expand the realm of games to 8x8
boards, and it no longer applies.  Human knowledge is quite wily in how it
infiltrates your ML system.

So really, I want a system that does not use such brute force methods.  I
want a system that can examine the board state and decide what to do, but
comes upon *how* it does that analysis of the board on its own, without
help from me.  And when I say "without help," I mean it!  Other than
rudimentary impls of a) and b), the computer gets nothing.

Anthony

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Tim Tyle » Mon, 25 Aug 2003 07:48:08


:> Building a machine that can learn to play /any/ deterministic game that
:> consists of two players alternately adding monochrome counters to an empty
:> 3x3 board is not terribly difficult - even if the machine has to be
:> constructed before the rules of the game it has to learn are specified.

: Can you elaborate on that?  Please explain in detail, so that I can write the
: program, how to make a computer learn to play perfect tic-tac-toe, without
: programming any strategy about how to play the game.  (or send me the source
: code of such a program)

: I suspect it may not be nearly as easy as you think.

It appears that similar tasks have been performed by others - e.g.:
http://satirist.org/learn-game/systems/sal.html

Basically, TTT is small enough for a LUT of all the possible positions to
be created.  *Assuming* you can tell when a game has been won by you, you
can label the winning positions, as desirable, then label all the nodes
that lead immediately to a (previously-marked) winning position, as desirable
and then work backwards up the game tree until the board is in the
starting position.

You then repeat the procedure for a win by your opponent - only this time
you mark the game positions as *un*desirable.

Note that the term "game position" is defined as including information
about who is to move.

Then you have the game's rule book.  All the possible moves from any
position will be labelled, either "desirable" (win) or
"undesirable" (lose) - or not labelled at all
(representing "draw"/"unreachable" states).

With this book, when faced with any position, you can simply examine the
possible moves - and play the least undesirable one.

This is enough for Tic Tac Toe.  A very similar strategy (which deals
with the possibility that won states may be beyond drawn or lost ones
by checking for that) should always result in a perfect player -
**if** the game tree is of a "managable" size.
--
__________

 
 
 

DNA computer unbeaten at tic tac toe.

Post by Tim Tyle » Mon, 25 Aug 2003 07:56:02


:> Building a machine that can learn to play /any/ deterministic game that
:> consists of two players alternately adding monochrome counters to an empty
:> 3x3 board is not terribly difficult - even if the machine has to be
:> constructed before the rules of the game it has to learn are specified.

: But you're right.  On a board that size, you can simply expand the entire
: game tree to the leaves and store the game tree in RAM.  But the fact you
: can do that is human knowledge, too. [...]

It was mentioned in the (carefully worded) premise:

``deterministic game that consists of two players alternately adding
  monochrome counters to an empty 3x3 board''

All such games have tractable rule books - that information was given.

: Expand the realm of games to 8x8 boards, and it no longer applies.

I made no claims about 8x8 boards, though.  I said the board size was 3x3.

: So really, I want a system that does not use such brute force methods.  I
: want a system that can examine the board state and decide what to do, but
: comes upon *how* it does that analysis of the board on its own, without
: help from me. [...]

Sounds like you want a miracle! ;-)
--
__________

 
 
 

1. Tic tac toe

Hi!

I'm looking for a source code of the tic-tac-toe game for prolog.
Please send it to me if you happen to have any.
Thanks.

--
*******************************************
Francois Dreyfuss

WEB: http://www.hj.se/~is96drfr/
*******************************************

2. Internal Zip Drive

3. tic-tac-toe w/ GA's

4. what does it mean Open_files?

5. tic-tac-toe

6. "Dec offers sneak peak at Alpha" Computerworld article

7. tic tac toe em prolog

8. Strange behaviou between debug and runtime

9. matchbox tic-tac-toe in C? (machine learning)

10. Tic-tac-toe AI

11. Help with Tic-Tac-Toe algorithm

12. help with minimax and alpha-beta pruning [tic tac toe]..

13. Tic-Tac-Toe with AI