Читать книгу Handbook of Intelligent Computing and Optimization for Sustainable Development - Группа авторов - Страница 67

Tic-tac-toe (noughts and crosses), which is one of the world’s oldest games, is played by two players. The playing board is a 3 × 3 grid of 9 squares. It is displayed first, showing all slots empty. Each player is assigned a mark, either × or 0. The × player usually goes first. Two players alternatively places × and 0 on the board until it satisfies either of the two conditions listed below:

1 i. one player succeeds to place three respective marks in a row horizontally/ vertically/diagonally; the player is the winner;

2 ii. all nine squares are filled; the game is a tie.

In 1840s, Charles Babbage invented an automaton that is capable of playing tic-tactoe. It was one the first games which has been electronically coded on computer. In 1952, A. S. Douglas developed this video game on the Electronic Delay Storage Automatic Calculator (EDSAC) at the University of Cambridge.

A group of researchers from Columbia University and the University of New Mexico designed an interactive molecular machine with series of wells which are filled with hairpin-shaped DNA strands [12]. These nano-device is capable of playing tic-tac-toe game but with restricted moves. The molecular device is named as molecular array of YES and ANDANDNOT gates, or MAYA. This system is four times more complex than any previously designed DNA computer and the most powerful demonstration of DNA computing till date. It is also the first interactive use of programmable DNA enzymes.

MAYA I, which has been designed in 2003, contains 3×3 wells corresponding to the nine squares of the tic-tac-toe grid. The automaton is made up with 2 YES gates, 2 AND gates, and 19 ANDANDNOT gates. The solution of each well contains a specific set of DNA logic gates. The wells are designed in such a way that the enzymes of all the gates can cleave the same substrate DNA strand. The cleaving operation needs the cofactor Mg₂₊ ions to initiate its activity. The addition of the cofactor ions to all wells starts the game. According to the design strategy of this molecular device, MAYA is playing first and the first move is in the center well of the nine wells. The move of MAYA can be recognized from the increase in fluorescence from the central well as the enzymes in this well have no stem-loop structure to control the enzyme activity. Hence, the enzyme starts to cleave the DNA substrate immediately. The human opponent can give any one of the other eight possible inputs (move) which are represented by specific oligonucleotides. In MAYA I, this choice is constrained to square 1 or 4 to simplify the programming. As the board is symmetric, the human opponent moves somewhere else, the board could be rotated to make it a move in either square 1 or 4. The input oligonucleotides have complementary sequences to the sequences of the stem-loops that control the DNA gates of each well.

Let us assume that the human opponent gives his /her move to square 1. The DNA strand representing this move is added to all of the nine wells. Next, MAYA signals its move by the increment in fluorescence of another well. Each well has all input strands which represent all the moves of the human opponent during the onward movement of the game. The input strands are processed by the set of gates in each well.

In 2006, the research group reports the next generation, i.e., MAYA II, which is unrestricted and displays both players’ moves in two different fluorescent colors [13]. It is quadruple the size of its predecessor, i.e., MAYA I. The more user-friendly version, MAYA II combines 128 logic gates, 32 input molecules, and 8 two-channel florescent outputs. The green color signals the move of the human opponent and red color indicates the move by the automaton. The input oligonucleotides not only encode the position of the move but also represent the order of the move. It is not a fast process; it takes about 30 minutes for game fluorescence to overcome background levels.

The researchers suggest that the automaton for any symmetrical game strategy can be encoded by 152 gates using 32 inputs and allowing for subsequent additional activation in already played wells. The later provision still needs to be worked out.

One obstacle to translating the tic-tac-toe logic circuit to a biomedical setting is that it can be played only once. If the inputs and substrates have bound and stay in the well, then there is no way in this closed system to start again. So, the researchers have done simulations of DNA oscillators and flip-flop devices in an open system, which would enable the gates to be reset as old inputs and products are washed away and new ones enter a reaction chamber. Unfortunately, as the DNA oligonucleotides are expensive, the cost of actually carrying out an experiment in a typical 50-ml reactor is extremely high.