Tale of how a tower robot assembled

I must say right away that under the “towers” ​​in the title of the post is meant the puzzle game “Sarov Towers”, located on the site bashni.org , the existence of which I learned from the Habrapost How to build a tower .

If you are familiar with this game and this site, then no further explanation is required, if not, you can go over both links to understand what it is about.

Well, or you can just read about how one lazy programmer wanted to automate the puzzle-solving process, over the layouts of which sometimes people with off-scale IQ fought for hours, and what came of it all.

Introduction

So, in October 2011, I stumbled upon the aforementioned article, and, due to my craving for various puzzles, “hooked” on this game. Slowly collecting towers, better and better over time, but often it turned out to be a bit more experienced opponents, or could not repeat the result they had already achieved.

Here is the time to mention the competitive element of the game, if of course you have not had time to learn about it from the links I provided. The bottom line is that the task is not just to solve the puzzle, but to do it in fewer moves than other players. Because each layout has a unique number, and the statistics of all assemblies are kept on the site, then all this is very clearly shown and creates a completely competitive atmosphere.

And now, once again failing to overtake, or even just catch up with the honored masters of sports in tower-building, I decided to use “doping”, i.e. write a program to solve the puzzle. After all, shouldn't robots work instead of humans in the progressive third millennium?

An additional incentive to me was the fact that the creator of the game, well-known Habré PapaBubaDiop , in the comments to the article repeatedly stated that the number of variants of moves in complicated hands, is very large, and software through them can be a very long time, while the other habrayuzer volerog claimed that he had already written a bot capable of solving most of the towers in a matter of minutes.

In general, without delaying the matter, I started writing code.

Because my main working tool is JavaScript, and the game is browser-based, then writing a program in this language became a natural solution. Of course, many may argue that the interpreted scripting language is not best suited for processing a large amount of information, and it would be better to write all this in C (or even Asm, “for truly”), but to me such efforts for the Just for fun task seemed excessive .

I was even too lazy to make something like a plug-in userscript for the browser from the program, and limited myself to just copy-paste the code to the dev console (the one that is called by the F12 button in FF and Chrome). Actually, it was Chrome, which has the fastest JavaScript engine that I know, and became my test site.

If the reader to this place has not yet at least fluently read the rules of the game, then you should do it on this wonderful page , where everything is very accessible painted, and even there is a clear animation example. Fortunately, these rules are very simple and concise.
Have you got acquainted? Great, move on.

The first pancake is lumpy

The first version of the program was very primitive, and simply checked all possible solutions from left to right (in the order of the columns). The initial layout was taken, the first column was searched for, which allowed making the move allowed by the rules, the move was made (virtually), then there was a recursive return to the first point of the algorithm, only now the base was not taken from the initial position of the towers, but what happened after the move made.

And so many, many times, a banal decision tree.
If at the next move the puzzle was solved (i.e. all the towers turned out to be assembled), then the decision was remembered indicating the number of moves spent on it. According to the results of the program, the solution with the least number of moves found was used.

One of the basic optimizations was the chopping off of branches of moves whose length exceeded the solutions already found, which is quite obvious, because no use from such branches.

The second optimization was the check for "neighbor blocks", i.e. blocks of the same color with adjacent numbers, e.g. 3 and 4. Since such blocks are combined after folding and can move at the same time, I decided that all the “neighbors” should always be connected as soon as the opportunity arises, and not create extra branches of options. As a result, if the program saw, for example, red 3 and 4, then it always first put the three on the four, and only then continued the search. This greatly reduced the running time of the script, as the more blocks “stuck” together, the fewer options left.

The script worked reasonably well on the "African" towers (the minimum level of difficulty), finding a solution in 1-2 minutes, and sometimes less. However, on the "Hanoi" he was already delayed for 15-30 minutes, and for the "Sarov" I was even scared to take.

In addition, a couple of times I noticed that the program, even after going through all the possible options, cannot repeat the result achieved by the players, and is 1-2 steps behind it. As it turned out later, the reason for this was my optimization for “block-neighbors”, because it was based only on my empirical assumption (I myself did this when I played with my “head”), and not on any objective arguments.

However, if you completely disable this optimization, then the time for solving puzzles went through the roof, and even for African towers it exceeded 15 minutes.

It was necessary to change something.

Error handling

Firstly, it was necessary to deal with the issue of gluing “neighboring blocks”. The problem was that when they merged, we lost a "seat" for smaller blocks. For example, having “not glued” 4 and 5 in different columns of the same color, we could put blocks with values ​​from zero to three on each of them and work with these two sets in parallel. Often this was critical for saving those 1-2 moves that led to the optimal solution.

After certain conclusions, I came to the conclusion that we can certainly only glue blocks where the top brick of the top block is zero or one. Because only in this case we are guaranteed not to suffer from the loss of “seats” (nothing else can be put on a block with a zero brick on top anyway, but only zero can be put on a block with a unit, and therefore there is no need to save 2 “seats”, having only one possible variant of the “landing block”).

Secondly, it was necessary to optimize the order of circumvention of options, because sorting the tree from left to right was extremely ineffective in cases where the best option was just on the right side.

After each move, I began to evaluate the “cost” of the current position of the towers as the difference between the total number of moves made at the moment and the number of “weak” moves. I call weak intermediate moves that do not immediately lead to the desired result (for example, when we put the red three on the five, because later we still have to shift it to four). Thus, the options with the least number of weak moves in relation to the overall progress of the solution had the best rating.

Options are queued taking into account their cost, and first of all, the options with the best rating are decided, because they are the ones most likely to turn into the optimal solution. By itself, this optimization is pointless. for guaranteed finding the best result, we still need to sort through all the options, but in combination with discarding the decision branches exceeding the lengths (and cost) already found, this allowed us to reduce the search time by orders of magnitude, because short (although not always the best) solutions were found very quickly, usually in the first seconds, after which it was possible to immediately discard huge branches of “long” solutions, focusing on finding the optimum.

Well, the third whale of success was the chance observation that different branches of options (even with a different number of moves) can lead to the same positions of the towers. Obviously, the further development of these options there is no reason to consider separately for each branch, because with the same initial position, the decision tree will be the same.

I began to make a text nugget of each position after each move and put it in a hash table (which, as you know, is the basis of the work of objects in JS, which I used). It turned out that there are much more such duplicate branches than I expected, and by discarding them, it was possible to reduce the search time by several times.

There were a number of minor optimizations that are hardly worth mentioning here, for example, protection against looping moves or from blocking blocks from one empty place to another. All this is quite obvious and does not significantly affect the algorithm.

Glory to the Robots! Kill all the people!

The final result exceeded all my expectations. The script solved most African towers in a matter of seconds (1-3 on average), Hanoi - within 10 seconds, Russians (Sarov) - from 30 seconds to 10 minutes in most cases, and 20-30 minutes for the most difficult layouts that I met, including the first hundred of the "complicated" layouts.

As it turned out, most medium and complex towers are not optimally solved by people, even taking into account the competitive element (i.e. after players tried several times to beat each other's result). Typically, a script finds a solution 1-2, and sometimes 3-5 moves shorter than the best result in humans.

Well, of course, in terms of the speed of finding a solution, iron brains are far ahead of human brains.

For some time I had fun posing as a mega-brain, but after a week or two of everyday victories from a previously unknown player, “the bees began to suspect something,” and the process became quite boring, as usually happens when playing with the “cheats” .

So that the result of two-day brain efforts does not disappear in vain, I decided to tell this story here on the hub, and put the program code in the public domain.

I will explain why I do it.
The game itself is wonderful, and I want to once again express gratitude to its creator PapaBubaDiop, for fading enthusiasm. However, the very competitive element that was called to become its highlight can also become its problem. It is quite obvious at the moment that a bot that quickly finds the best solution can be created, and this can be done in a fairly short time, and many (although certainly not all) can do it. This is once again proved by the fact that the Rois habraiser recently created its own bot, no worse than mine (or maybe better in speed), apparently in order to understand if I can be a bot.

I am writing this article and posting the code so that the guys who are serious about the competitive element in this game understand that yes - I can be a bot, Rois can be a bot, anyone can be a bot. And you may never know about it if the bot owner sets such a goal (there are a lot of ways to look like a person, even if you are a bot). And by purely technical means you won’t detect the bot, and don’t stop it.

You can only reconsider the very concept of the competition or the relation to their results.

PS Of course, I will not support the code, and if, for example, something is changed on the game’s website so that it cannot read the initial position of the towers, let those who want to fix it themselves.

PPS I almost forgot :) pastebin.com/AJyR2E71 - here is the code