[competition experience sharing] Tencent's internal track - goose Rose Square race notes

Preface

I'm in the past , I have written many games AI, So I'm glad to see that the company has such a competition . Unfortunately, the two weeks of the competition were just right, and the project team was very busy , But I still hope to do better in my limited time .

Mining rules

stay chrome View in browser js file , Found that there is a link to the complete source code before compilation , And the notes inside are particularly detailed .

I mainly focused on core.js and game.js. From this, we can get the key information in the rules

1. The sequence in which the squares appear is completely fixed , And for 10000 block
2. There are two key factors in the final score , Rich and noble insurance should be combined to encourage multiple lines to eliminate

in other words , We can set two small goals , One is to finish 10000 A square , Second, finish 10000 Get more points on the basis of blocks .

Algorithm to choose

It's easy to think , Tetris is a classic game , It must have a lot of previous experience to learn from . So I can easily find a feasible algorithm on the Internet , namely Pierre Dellacherie’s Algorithm

El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm | imake

This algorithm through the situation 6 Features to construct the evaluation function , It has good immortality , It even gives a set of adjusted parameters . In this way, the first small goal should be achieved , That is to eliminate 10000 Square block , Basically, there's no problem .

Language choice

PD The algorithm looks good , And what we have to do , It's running 10000 Higher scores for blocks at the same time . If you want to pursue perfection , Calculate more points , It must require strong computing power . In addition, directly use JS It's also a way , Because we can get the most accurate source code of the game rules directly .

Language	performance	cost
C++	high	Complete implementation of the rules of the game +AI Algorithm
JS	low	Modify the rules of the game a little +AI Algorithm

Considering the cost of time , If I use C++ To write the , It is likely that it will take a lot of time to make the rules of the game exactly the same as the official rules , And I have very little time , Use it directly JS Add some optimizations , Perhaps from the completion of the game , It's a better choice .

Implementation process

1. Modify the original game rules , Let time forbid

The first thing we have to do is change the falling speed into 0, This will play a key role in the later debugging . It's easy to change it , Just remove the timer for each fall .

2. Complete the basic state enumeration + Random evaluation function

We simulate game keyboard events directly ,DFS The enumeration can be completed by listing all termination states . The States to be saved include , The location of the squares , Direction of rotation , Sequence of operations and other information . be aware , Due to the final decision of a block falling, the average is about 20 Kind of , All roads lead to Rome , We can make a status record , Let each block access only in the state of a certain coordinate 1 Time . such , thus , We have completed the most basic AI The main process of automatic game , Although it will die soon in the beginning .

3. complete PD Algorithm

PD The algorithm implementation is not complicated , Each time the DFS When you find a landing point , Fill the current box into the panel , according to PD Algorithm 6 Calculate the score for each feature . this 6 Features include the following ：

Landing Height: The height where the piece is put (= the height of the column + (the height of the piece / 2)) Rows eliminated: The number of rows eliminated. Row Transitions: The total number of row transitions. A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa. Column Transitions: The total number of column transitions. A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa. Number of Holes: A hole is an empty cell that has at least one filled cell above it in the same column. Well Sums: A well is a succession of empty cells such that their left cells and right cells are both filled.

Optimize

Just finished PD Algorithm time , The result was not as good as I expected . It doesn't finish as scheduled 10000 Square block , There will be a lot of continuity in the middle of the game s and z, Or occasionally a few in a row I, So almost every time in 1000 About a block died , No matter how you adjust the parameters , Always stuck in 3W about . The other thing that I found , The box goes to the back , The slower the computation , And more and more slowly . In theory, the amount of computation during the game will not change much , It's hard for me to understand .

1. Operation sequence backtracking strategy

It is a big problem that the game is getting slower and slower from the early stage to the middle stage , In the 1000 The speed dunka is especially outstanding , Even if I can write good algorithms , I can't hold it out 10000 block . Through Google browser's performance detector , I focused on DFS Save the state of .DFS The most calls are state saving and backtracking . Because I saved the sequence of operations , And it's a deep copy . The sequence of operations is a very long string , It will grow with the development of the game ！ In fact, we don't have to copy the whole sequence every time . According to the sequence N Incremental backtracking to the location of the occurrence , So even in the middle of the game , The running speed can be almost the same as that at the beginning .

2. Rotating pruning

stay dfs In the process , Because the square can rotate ,4 A state is a cycle . But actually not every square needs to be rotated 3 Time , For example, a square has no rotation at all , and Z and S and I The model has only two rotation states . This can reduce a lot of intermediate decision-making overhead and final decision-making overhead .

3. Fast fall

be aware dfs The process was originally a simulation of keyboard operation , But we can still improve a little . If a square is in the air , In fact, it doesn't need to do a lot of fancy spins in the middle , Just rotate it at the end . So we DFS When searching the status below , You can go straight down “ jump ” To a space above the touchable position . This saves a lot of saving and backtracking of intermediate paths .

4. The number of decision-making levels increases

In fact, no matter how you adjust the parameters , There is only one square , What we are looking at is not long-term . Our search needs to search more blocks at a time , That is, increase the number of decision-making levels . In the process of increasing the number of layers , State saving also needs more , For example, when one more square falls each time , Grid information of the previous step . however JS The computing performance of is limited , If there is no front 3 An optimization ,2 Layers will be very slow , I can't wait 10000 Block elimination complete . Joined the front 3 After optimization , To calculate 2 Layer or 3 layer .

In the case of two floors , You can finish it 10000 A square , The effect is considerable , Can get T-shirt 了 .

5. Add the scene square

Because of the rules of wealth insurance , If there are more squares in the scene , Higher scores . I find , Can calculate 2 In the case of layers , It only takes half the height to stabilize the whole situation . So if the situation is safe , You can search 1 Layer strategy increases height , When the situation is dangerous , Search with 2 Layer strategy to stabilize the situation .

such , You can finish typing 10000 More squares at the same time .

summary

The final score 35w, ranking 48, There is still a long way to go compared with the big man who scores millions . But for me , This competition has learned a lot , And when time is limited , To complete a AI, Look at AI After automatic brushing 10000 Square block , It was a good experience . Last , Thank you for hosting such an event ~ great