[competition experience sharing] a problem-solving summary of the whole DFS (internal track)

TL;DR: The main idea is based on “ Endgame ”（ The foundation ） Heuristics dfs. For the first edition python Realization (GUI+solver) Probably 70W+, Back handle solver Some of them are transplanted to rust On , Some performance optimizations and various constraints are combined to achieve 100W+, It is difficult to improve the feeling of re optimization . The final score is 1060356, The inner race track No 8 name .

On

The first thing is to determine how the block sequence is generated , Looked at the js Have a very friendly source file address , Random number generation core ： return (v * a + C) % M;`, The seeds are also fixed , Gave up RL Ideas .

And then use pygame according to js First, I wrote a simple local client-side auxiliary debugging , Functionally, it can make the square not drop actively , You can go up , You can repent （ But at this time, repentance moves through the replay sequence to the penultimate N Realized ）, Print debugging information, etc , At the same time, the sequence can be generated according to the process of playing .

At this time, I probably played manually 500 Multiple squares ,3.8W about , In proportion, if it is all completed, it will be 70 many W.（ Worship the front TAS The boss of the method ）

So I decided to implement the solver . I used to give Shenzhen IO Card games solitaire and Opus Magnum Of minigame sigmar's garden Realization bot They are based on heuristics DFS Method , It is realized in the same way . The core idea is to sort the actions through the evaluation function ,“ guide ”、“ inspire ” Program to search . Several implementation details ：

• At this time, it has been found that you can directly pass "N" Let the square hang in the air , But generate possible moves Considering the large space , Just consider " to ground " The situation of . The method of generation is to generate each shape first （0~3 The shape of the state, Repeated without consideration ） List the target locations on the ground , adopt bfs Find the way to see if it can be achieved through operation , Get what is actually reachable moves
• to possible moves Sort (heuristic score), That is to say “ Evaluation function ”, Priority search “ Better ” Of move. At the beginning, the height and are used as the evaluation criteria .
• Progress is slow from scratch , So instead “ Endgame ” Pattern , Played manually 30~40 Block or so , Let the solver continue to execute on this basis . This is not good move It will soon fall back because the game is over

UI Example

The two red numbers on the picture are brick_count( Block serial number ), Here are the scores . At the time of submission, another script generates the corresponding... For the sequence file js Code , Copy to browser console Submitted in .

It's easy to play in this way 10000 A piece will never die , Probably 70W about

Optimize

It took 2 Later, the solver was transplanted to rust（ The coordinates of a shape were copied incorrectly , It was also adjusted for nearly one night bug）, Combined with other optimizations ：

• Before dfs The exploration uses the method of copying the whole game state , Change it to in-placed The way , And change the implementation method of fallback from “ Replay sequence ” For the real ” Back off “（ Directly restore the state of the previous square ）, Significantly reduce a large number of allocation Consume
• Before optimization , The state seen is of type HashMap<u32, HashSet<String>> preservation (String Is the current game “ The board ” A coding form of ),key For the current brick_count, In this way, some memory can be released when the memory is too large brick_count smaller entry. The runtime found that the memory was too large , Realize that because only judge the existence or not , Changed to HashMap<u32, HashSet<u64>> The type of , Significantly reduces memory requirements ( Calculation hash Used fxhash)
• use hashbrown Of HashSet Method replaced std Of HashSet To save some memory
• modify heuristic score The evaluation function returns Option, That is, in other languages Optional or Maybe type . In this way, the evaluation function can return None Tell the upper level to give up the unwanted state

In addition, I also played some good games manually ” Endgame “, Only one hole per row in the lower layer . At the same time, it has been adjusting heuristic score The strategy of . Tried to use PD Algorithm , But it doesn't seem to have any effect , Some other strategies have been added ：

• Give up the one line solution ( The last sequence is basically elimination 2 That's ok , minority 3 Row sum 4 That's ok , A big promotion ）
• Give up the scheme that only needs two lines （ A little improvement ）

Limit the number of rows to be eliminated

• Judge the total number of existing blocks when there is elimination , Less than 164 Give up （168 I tried several rounds , Will soon fail ）
• Less than 168 Probabilistic abandonment of

Limit the number of squares left

At this time, I think 103W

The last small optimization

Because the sequence is fixed , Some large intervals are generated "I" and "J" List of serial numbers for (HashSet), Judge in the evaluation function if... Is not reached in these blocks 3 Eliminate or 4 eliminate , Give up on probability . This change significantly increases the running time ( The feeling of the body is that it will take 1 God ), But in the end it only improved 3W+ about , arrive 106W+

summary

• There is still a big gap with the top several , To make a significant improvement, you may have to change some methods with higher search efficiency （ Combine better pruning schemes ）
• Currently, the global score calculation of the evaluation function is still based on the height 、 Weighted sum of voids, etc （ Bad ）, I feel there is still room for optimization by introducing other ideas
• Thanks to the Organizing Committee for this competition , Learn a lot and see a lot , The process is also very interesting . Looking forward to the next game .