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 could not come up with a tricky algorithm for the solution, so I wrote bruteforce. Wrote in C #.
In the first version, I went through the movements of the loader (robot). Sorted recursively in depth, to protect against looping, stored all the passed options in an array. He issued the decision in the form of a string indicating in which order to press the buttons in the game. I downloaded this sequence to the MacroExpress program, and it already sent clicks to the game window. By adjusting the pauses between sending clicks, you could watch the passage of levels at a convenient speed.
The bot decided the first few levels and at the next stuck for a couple of days. 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. Replaced the movements of the robot with the movements of the boxes, i.e. no longer need to store the moves of the robot path from one box to another. At each turn, I determined which boxes the robot can now reach and which way to push.
Then the bot decided the next few levels and got stuck again. Then there were several more versions:
- added a restriction on the depth of recursion, believing that most levels can be solved in less than 100 movements of the boxes;
- Marked static dead-end places on the map, for example, a corner or the first row along a flat wall, because then it will be impossible to pull out the box from there;
- added a simple analysis of the course and discarding obvious dynamic deadlocks such as shifting a square of 4 boxes;
- the storage of coordinates of all previous moves was replaced by the storage of their hashes, so that it would fit into the memory and be faster to search;
All this made it possible to advance several more levels, but it became clear that the complexity of the solutions greatly increased with each level. Then I chose the largest level - 86. Well, if the bot solves it, then the rest will be easily handled.
So, level 86.
It contains 46 boxes and 156 field cells. At the same time, 40 cells are static dead ends, a total of 116 cells on which you can move the box. Therefore, the number of different options will not exceed 116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Yes, this is a number of 95 digits. It is ~ = 9.2e + 94. In this case, the maximum number of moves does not make sense, since this estimate turned out to be even more: let's say the maximum of moves = 100, and on average each box can be pushed in at least one direction out of four, then the number of options will not exceed (46 * 1) ^ 100 ~ = 1.9e + 166 .
Heuristic Addition:
- 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 away from the wall to push it to the destination. I mark such places on the map in advance and the bot does not make such moves in the search process.
- dynamic dead ends
It is clear that if you move 4 drawers square (in various combinations with drawers and walls), then it will be impossible to tear them apart. The bot analyzes each move and does not make moves leading to such a square.
I have not yet come up with more complicated ones.
Of course, the real options will be much less than the first estimate due to the cutting off of dynamic dead ends, probably by several orders of magnitude. But even if you take half the orders of this number (92271483792519010208299118408158326223759549834) and store the state of each move in just one byte, you will need 83920425634022658603 terabytes.
It was then that I realized that "still wait and the bot will sort through all the moves" as at the first levels it will not work anymore. It is necessary to radically change something in the algorithm, carry out a more complex and lengthy analysis at each turn, but cut off the larger subtrees of the options. But I don’t know exactly how 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 (robot). Sorted recursively in depth, to protect against looping, stored all the passed options in an array. He issued the decision in the form of a string indicating in which order to press the buttons in the game. I downloaded this sequence to the MacroExpress program, and it already sent clicks to the game window. By adjusting the pauses between sending clicks, you could watch the passage of levels at a convenient speed.
The bot decided the first few levels and at the next stuck for a couple of days. 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. Replaced the movements of the robot with the movements of the boxes, i.e. no longer need to store the moves of the robot path from one box to another. At each turn, I determined which boxes the robot can now reach and which way to push.
Then the bot decided the next few levels and got stuck again. Then there were several more versions:
- added a restriction on the depth of recursion, believing that most levels can be solved in less than 100 movements of the boxes;
- Marked static dead-end places on the map, for example, a corner or the first row along a flat wall, because then it will be impossible to pull out the box from there;
- added a simple analysis of the course and discarding obvious dynamic deadlocks such as shifting a square of 4 boxes;
- the storage of coordinates of all previous moves was replaced by the storage of their hashes, so that it would fit into the memory and be faster to search;
All this made it possible to advance several more levels, but it became clear that the complexity of the solutions greatly increased with each level. Then I chose the largest level - 86. Well, if the bot solves it, then the rest will be easily handled.
So, level 86.
It contains 46 boxes and 156 field cells. At the same time, 40 cells are static dead ends, a total of 116 cells on which you can move the box. Therefore, the number of different options will not exceed 116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416. Yes, this is a number of 95 digits. It is ~ = 9.2e + 94. In this case, the maximum number of moves does not make sense, since this estimate turned out to be even more: let's say the maximum of moves = 100, and on average each box can be pushed in at least one direction out of four, then the number of options will not exceed (46 * 1) ^ 100 ~ = 1.9e + 166 .
Heuristic Addition:
- 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 away from the wall to push it to the destination. I mark such places on the map in advance and the bot does not make such moves in the search process.
- dynamic dead ends
It is clear that if you move 4 drawers square (in various combinations with drawers and walls), then it will be impossible to tear them apart. The bot analyzes each move and does not make moves leading to such a square.
I have not yet come up with more complicated ones.
Of course, the real options will be much less than the first estimate due to the cutting off of dynamic dead ends, probably by several orders of magnitude. But even if you take half the orders of this number (92271483792519010208299118408158326223759549834) and store the state of each move in just one byte, you will need 83920425634022658603 terabytes.
It was then that I realized that "still wait and the bot will sort through all the moves" as at the first levels it will not work anymore. It is necessary to radically change something in the algorithm, carry out a more complex and lengthy analysis at each turn, but cut off the larger subtrees of the options. But I don’t know exactly how to do this ... maybe you can advise me? Use some techniques from the field of graphs, ant algorithms, neural networks?
