Bot for playing Sokoban brute force
When I started playing BoxWorld (a game like Sokoban), the first 20-30 levels were interesting, but then the complexity and monotony began to outweigh and I decided to write a bot. I couldn’t come up with any tricky solution algorithm, so I wrote to brute force. Wrote in C #.
In the first version I went through the movements of the loader itself (the robot). Went through recursively in depth, to protect against looping, he kept all passed options in the array. He gave the solution in the form of a string indicating the order in which to press the buttons in the game. I downloaded this sequence into MacroExpress, and it already sent clicks to the game window. By adjusting the pause between sending clicks you could watch the passage of the levels at a convenient speed.
The bot decided the first few levels and was stuck for a couple of days at the next. This level was 2 times more than the previous one, but the time for finding solutions grew exponentially. So without waiting for an answer, I began to write the second version. The movements of the robot replaced the movements of the boxes, so It is no longer necessary to store the moves of the robot path from one box to another. At each turn, I determined which boxes the robot could now reach and which way to push.
')
Then the bot decided the next few levels and got stuck again. Then there were some more versions:
- added restriction of the recursion depth, assuming that most levels can be solved in less than 100 drawer movements;
- marked on the map static dead ends, such as a corner or the first row along a flat wall, because then it will be impossible to pull out the drawer;
- added a simple analysis of the course and discarding obvious dynamic deadlocks such as shifting a square of 4 boxes;
- the storage of the coordinates of all previous moves was replaced by the storage of their hashes, so that more memory would be stored and it would be faster to search
All this made it possible to advance even at several levels, but it became clear that the complexity of the decisions greatly increased with each level. Then I chose the largest level - 86. If the bot decides it, it will cope with the rest easily.
So, level 86.
It contains 46 boxes and 156 cells of the field. At the same time 40 cells are static dead-end places, a total of 116 cells to which the box can be moved. This means that the number of different options will not exceed 116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Yes, this is a 95-digit number. It is ~ = 9.2e + 94. The maximum number of moves in this case makes no sense to take into account since such an assessment turned out to be even more: let's assume a maximum of moves = 100, and on average each move can push each box in at least one direction out of four, then the number of options will not exceed (46 * 1) ^ 100 ~ = 1.9e + 166 .
Supplement about heuristics:
- static dead ends
It is clear that if you slide the box to any place marked with a red marker, then it will be impossible to tear it from the wall to push it to its destination. Such places I pre-mark on the map and the bot does not make such moves in the process of iteration.
- dynamic deadlocks
It is clear that if you move 4 drawers with a square (in various combinations with drawers and walls), then it will be impossible to tear them apart from each other. The bot analyzes each move and does not make moves leading to such a square.
More difficult yet did not invent.
Of course, the real options will be much less than the first estimate due to the cutting off of dynamic deadlocks, probably by several orders of magnitude. But even if you take half the orders of this number (92271483792519010208299118408158326223759549834) and store the status of each move in just one byte, you will need 83920425634022658603 terabytes.
It was then that I realized that “it’s still to wait and the bot will go through all the moves” as at the first levels it will not work. It is necessary to change something drastically in the algorithm, to carry out a more complex and lengthy analysis at each turn, but to cut off more subtrees of options. But I don’t know how exactly to do this ... maybe you can advise me? Use some techniques from the field of graphs, ant algorithms, neural networks?
In the first version I went through the movements of the loader itself (the robot). Went through recursively in depth, to protect against looping, he kept all passed options in the array. He gave the solution in the form of a string indicating the order in which to press the buttons in the game. I downloaded this sequence into MacroExpress, and it already sent clicks to the game window. By adjusting the pause between sending clicks you could watch the passage of the levels at a convenient speed.
The bot decided the first few levels and was stuck for a couple of days at the next. This level was 2 times more than the previous one, but the time for finding solutions grew exponentially. So without waiting for an answer, I began to write the second version. The movements of the robot replaced the movements of the boxes, so It is no longer necessary to store the moves of the robot path from one box to another. At each turn, I determined which boxes the robot could now reach and which way to push.
')
Then the bot decided the next few levels and got stuck again. Then there were some more versions:
- added restriction of the recursion depth, assuming that most levels can be solved in less than 100 drawer movements;
- marked on the map static dead ends, such as a corner or the first row along a flat wall, because then it will be impossible to pull out the drawer;
- added a simple analysis of the course and discarding obvious dynamic deadlocks such as shifting a square of 4 boxes;
- the storage of the coordinates of all previous moves was replaced by the storage of their hashes, so that more memory would be stored and it would be faster to search
All this made it possible to advance even at several levels, but it became clear that the complexity of the decisions greatly increased with each level. Then I chose the largest level - 86. If the bot decides it, it will cope with the rest easily.
So, level 86.
It contains 46 boxes and 156 cells of the field. At the same time 40 cells are static dead-end places, a total of 116 cells to which the box can be moved. This means that the number of different options will not exceed 116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Yes, this is a 95-digit number. It is ~ = 9.2e + 94. The maximum number of moves in this case makes no sense to take into account since such an assessment turned out to be even more: let's assume a maximum of moves = 100, and on average each move can push each box in at least one direction out of four, then the number of options will not exceed (46 * 1) ^ 100 ~ = 1.9e + 166 .
Supplement about heuristics:
- static dead ends
It is clear that if you slide the box to any place marked with a red marker, then it will be impossible to tear it from the wall to push it to its destination. Such places I pre-mark on the map and the bot does not make such moves in the process of iteration.
- dynamic deadlocks
It is clear that if you move 4 drawers with a square (in various combinations with drawers and walls), then it will be impossible to tear them apart from each other. The bot analyzes each move and does not make moves leading to such a square.
More difficult yet did not invent.
Of course, the real options will be much less than the first estimate due to the cutting off of dynamic deadlocks, probably by several orders of magnitude. But even if you take half the orders of this number (92271483792519010208299118408158326223759549834) and store the status of each move in just one byte, you will need 83920425634022658603 terabytes.
It was then that I realized that “it’s still to wait and the bot will go through all the moves” as at the first levels it will not work. It is necessary to change something drastically in the algorithm, to carry out a more complex and lengthy analysis at each turn, but to cut off more subtrees of options. But I don’t know how exactly to do this ... maybe you can advise me? Use some techniques from the field of graphs, ant algorithms, neural networks?
Source: https://habr.com/ru/post/130417/
All Articles