AI In Tetris

In recent years AI is very active area of research, and that the games AI research is an important branch of the field. RPG involved in the game to be one of the NPC's decision-making, the optimal route search, the man-machine chess game, such as a chessboard.Currently, the game AI research has entered a period of prosperity. David M. Bourg and Glenn Seemann in their book "AI Techniques for Game Programming", a book, discussed in detail how to create a true act of artificial role, and to enable them to respond intelligently, including modern AI technology (such as neural networks, decision trees, genetic classifier), the standard control mechanisms (such as rule-based system and the finite state machine).Now the Tetris AI research has entered a mature stage, many researchers both at home and abroad to a number of different algorithms, such as Erik D. Demaine, Susan Hohenberger, David Liben-Nowell wrote Tetris is Hard, Even to Approximate. Frenchman Pierre Dellacherie developed in 2003 had been Colin fahey think it is the best single-level intelligence block search box AI Russia, the average Consumers box lines up to 650,000.The first design prepared by the Tetris game itself, and then the preparation of AI module, will be the final two parts linked together.Main program not only determine the keyboard events and refresh, the district will be displayed. If there is information on the keyboard, is scheduled to determine whether the control buttons, according to the keyboard control to determine whether the successful operation sent rapid elosEx object whereabouts, and overturned, the news about mobile in the final set, and District.In this game automatically on the basis of the Russian box, which is automatically AI procedures under Russian control box game. From Grade () function call to search the dll file in the Evaluate function score. If there are multiple dll file from the menu option called one of them.When the search procedures to the best of the current box positioned, it needs to calculate the movement of the box path and rotation step and then sent to the mobile messaging elos objects, the box can be moved to make provisions of the position. However, the Robot class function and the operation has not ended the internal procedures call very quickly, if the order immediately sent mobile so easily lead to instant mobile box can not be seen clearly in place and observers mobile steps, resulting in the "rapid run" effect.Based on the above considerations, the need to separate the control box as a thread running in the control box in each flip and whereabouts of the man-made process dormant for a period of time, two threads running interludes, this can simulate the operation of a manual effect. MoveTo function to be called to be placed on a new thread.According to the known conditions, preliminary view is that human thinking can be used similar to the way placing box: in the box during the whereabouts of the box and comprehensive judgment will be the next to the box placed in the containers in a situation is good or bad, manipulation of the current box will be placed in its "best current judgment" position. Because theoretically the best available method for the determination of the NP-complete problems, it can only display of a relatively good position.This procedure adopted retroactive law, the search algorithm uses real-time strategy, that is, in the box during the whereabouts of the real-time search box and a box placed in all combinations of each situation and a score. Specific steps are as follows:Judging the present and a box placed in the optimal location is in fact a height of 5 N-tree depth-first traversal conducted (if it is a standard Tetris games, Nmax = 10). Tree layer 0 that began traversing the state, a layer of four nodes, each a box that overturned the current state of each inversion has 10 sub-node status, they formed a Layer 2, each node that current box placed in the containers in a situation of third and fourth floors of an enumeration of the state and location of the box. Thus, the current box and the box under a combination of emissions from all the trees are a leaf node.Using depth-first traversal of the recursive method can be judged under the current box and a box overturned state and location information, simplifying the code of editing and logical.In the above algorithm, the valuation function Evaluate very important, it determines the merits of the judgment of the current situation, is the basis for the optimal decision. Therefore, the valuation function optimization of the process is efficient and intelligent level of AI has a great effect. Formal valuation algorithm can be described as follows:Formula represents a valuation function, the parameter is an n-dimensional vector , each of which represents a known input parameters, such as the width.It is not difficult to see a situation was selected as the best situation if and only if such a situation can make the function to maximize, or to choose a situation, making .Based on the above description, in the selection of the transition matrix of different weights vector A and , they can design different valuation function, that the input vector :Return value: the evaluation of the situation of . Vector is value.Vector will eventually be set at 8-dimensional, they are: bound by these conditions are as follows:Experiment shows that the algorithm substantial increase in the level of AI intelligent, automated procedures Tetris game possible.Theoretically, multidimensional vector than low-dimensional vector outstanding. However, we discuss this process, taking into account factors such as the efficiency of procedures, temporary vector dimension as 8-dimensional, and its appropriate weight vector choice is difficult. But the general view, the former should be positive for 4D, after 4D should be negative. Specific numerical could be considered the best use of genetic algorithm to determine the limited scope of the study of this topic, by artificial many tests tentatively scheduled for Retrospective of the algorithm to achieve a reasonable Tetris AI part of the core - elected optimal positioned, as a result of the predicate the optimal situation has been recorded, as long as the manipulation of the box moved to the position can be, it should be said that AI procedures part of the core has been designed.Each box under the worst-case scenario four kinds of state, from left to right followed by a 10 positioned. Therefore, it is estimated that each box worst decentralization 40, the current box and the next box exhaustive combination of the placing of a total of 1,600 kinds of display methods. Under the worst-case scenario is when the box on the whereabouts of 1,600 kinds of needs may be followed by a state in accordance with the highest score and the state display. Score of because it is fixed, and therefore time constants.In the solution space also can be seen, the number of leaf node is fixed as mentioned above, all the decision-making time in the 1600×O(1).The optimization of the decision-making procedures of the running time is fixed.Rows 13 to 17 million lines between objectively speaking, has been achieved despite a relatively good results, compared Colin fahey Standard Tetris procedures, such as the millions of lines of the above there is a great gap, that the right procedures in the selection, parameter estimation, and so there is still a considerable aspects of the room.The Tetris AI research and the preparation of the Tetris to achieve automatic control of the game, in the practical aspects of AI algorithms better meet the needs of the plane, such as a battlefield. This time, study the algorithm is relatively clear framework to facilitate future upgrade algorithm performance. Search algorithm and the valuation function of intelligent design to meet the requirements of relatively high degree of the situation, based on the above valuation function can be the follow-up to become more powerful and more reasonable judgment logic algorithms, to apply demanding occasions.