Automata are self-operating machines, or robots, that are able to analyze a series of "inputs" in a meaningful fashion. We are exploring DNA (deoxyribonucleic acid) as a medium for building automata on a molecular scale. Beginning with automata that can perform molecular computation, we are initially focussing on the construction of molecular automata to play tic-tac-toe (also known as noughts and crosses). Game playing is often used as an unbiased test of new computation media, and the game of tic-tac-toe is one of the simplest games of perfect information and yet a surprisingly complex combinatorial problem.
To date, we have constructed two tic-tac-toe playing molecular automata, known as MAYA (a m_olecular a_rray of Y_ES and A_NDNOT gates):
MAYA-I (published 17 August 2003
) plays a symmetry-pruned restricted game of tic-tac-toe. The automaton always goes first in the middle well, and the human player can respond by moving in only two wells.
MAYA-II (published 07 October 2006
) plays a non-symmetry-pruned complete game of tic-tac-toe. The automaton still always goes first in the middle well, however the human player may move in any remaining square. MAYA-II is also more user-friendly than it's original counterpart, as it displays both human and automaton moves using a two-color fluorogenic output system.
- 01 Apr 2006