The tale of how the tower robot collected

Immediately make a reservation that under the "towers" in the title of the post means the puzzle game "Sarov towers", located on the website bashni.org , the existence of which I learned from a 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 process of solving a puzzle, over the hands of which sometimes people used to beat the IQ going wild, and what came of it all.

Introduction

So, in October 2011, I came across the above article, and, by virtue of my craving for various puzzles, “hooked” on this game. He collected the towers little by little, with time getting better and better, but often he 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 you certainly have not had time to learn about it from the links I have 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 site keeps statistics of all assemblies, then all this is very clearly shown, and creates a completely competitive atmosphere.

And so, once again, having failed to overtake, or at least just catch up with the honored masters of sports in tower engineering, I decided to use “dope”, i.e. write a program to solve the problem. In the end, shouldn't robots work instead of humans in the progressive third millennium?

An additional incentive for me was that the creator of the game, notorious in the PapaBubaDiop Habré , repeatedly stated in the comments to that article that the number of turn options in complex layouts is very large, and you can programmatically select them for a very, very long time, while another volerog claimed that he already wrote a bot that can solve most of the towers in a matter of minutes.

In general, without delaying the case indefinitely, I began to write the code.

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

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

If the reader to this place has not yet at least fluently familiarized with the rules of the game, then it’s worth it on this wonderful page , where everything is very accessible, and even there is a vivid animation example. Fortunately, these rules are very simple and concise.
Have you read? Great, go ahead.

The first pancake - 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 alignment was taken, the first column was searched, which allowed the move to be allowed by the rules, the move was made (virtually), a recursive return to the first paragraph of the algorithm went on, only now it was not the initial position of the towers that was taken as a base, but what happened after the move.

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

One of the basic optimizations was cutting of branches of moves whose length exceeded the solutions already found, which is quite obvious, since no use of such branches.

The second optimization was the check for "blocks-neighbors", i.e. blocks of the same color with adjacent numbers, for example. 3 and 4. Since such blocks after folding are combined and can be moved at the same time, I decided that all the “neighbors” should be connected always, 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 top three on the four, and only then went through the search. This greatly reduced the time of the script, because the more blocks “stuck together” together, the fewer moves there were left.

The script quite tolerably worked on the "African" towers (the minimum level of complexity), finding a solution in 1-2 minutes, and sometimes less. However, on the “Hanoi” he was already late for 15-30 minutes, and I was even afraid to take on the “Sarov”.

In addition, a couple of times I noticed that the program, even sorting through all the possible options, cannot repeat the result achieved by the players, and lags behind him by 1-2 moves. As it turned out later, the reason for this was my optimization on “block-neighbors”, since 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 turn off this optimization, then the time to solve puzzles goes off scale, and even for African towers exceeded 15 minutes.

It was necessary to change something.

Bug work

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

After certain conclusions, I came to the conclusion that we can unconditionally glue together only blocks where the upper brick of the upper block is zero or one. Because only in this case we are guaranteed not to suffer from the loss of “seats” (on the block with a zero brick, you can’t put anything else on top, but you can only put zero on the 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 bypass options, because busting the tree from left to right was extremely inefficient in cases where the best option was just on the right side.

After each turn, 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. Weakly call intermediate moves that do not immediately lead to the desired result (for example, when we put the red three on the top five, because later we will still have to shift it to the four). Thus, the options with the least number of weak moves with respect to the overall progress of the decision had the best estimate.

Options are queued based on 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 meaningless, because to guarantee finding the best result, we still need to go through all the options, but in combination with discarding branches of solutions that are longer in length (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 very first seconds, after which huge branches of “long” solutions could be immediately thrown away, focusing on finding the optimum.

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

I began to make a text cast of each position after each move and put it into a hash table (which, as you know, underlies the work of objects in JS, which I used). It turned out that there are significantly more such duplicate branches than I had anticipated, and, discarding them, we managed 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 moving blocks from one empty space to another. All this is quite obvious and does not significantly affect the algorithm.

Glory to the robots! Kill all humans!

The final result exceeded all my expectations. The script was solved by most African towers in a matter of seconds (1-3 on average), Hanoi - within 10 seconds, Russian (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 of the towers of the middle and complex levels are not optimally solved by people, even taking into account the competitive element (that is, after the players tried several times to exceed each other’s results). Usually, the script finds a solution by 1-2, and sometimes by 3-5 moves shorter than the best result in humans.

Well, of course, iron brains are far ahead of human brains in terms of finding solutions.

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 this process became quite boring, as usually happens if you play with “cheats” .

To the result of the two-day brain effort did not disappear completely in vain, I decided to tell this story here in Habré, and put the program code in open access.

Let me explain why I am doing this.
The game itself is wonderful, and I want to once again express my gratitude to its creator PapaBubaDiop , for undying enthusiasm. However, the very same competitive element that was intended to be 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 relatively short time, and many can do this (although not everyone, of course). Once again, this is proved by the fact that the habrauser Rois recently created its own bot, no worse than mine (and perhaps better in terms of 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 can never know about it if the bot owner sets himself 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 will not reveal the bot, and you will not stop it.

One can only reconsider the very concept of the competition or the attitude to their results.

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

PPS I almost forgot :) pastebin.com/AJyR2E71 - that's the code