On the issue of virt and chains

Algorithms + data structures = programs - Virt N.

“We had a wonderful opportunity to conduct a small but extremely instructive tactical exercise”

Despite the first epigraph to this post, I will allow myself to disagree with the author and try to show that in some cases the correct choice of data structure may be more significant than the correct choice of algorithms. To illustrate such a seditious thesis, let us consider the simple but promising task of investigating the game “Chain”.

First, about the rules of the game - two players play, the starting position consists of H adjacent objects. The next move is to remove any one or two adjacent objects (you can try to give a formal definition of "near location", but it is understandable at an intuitive level). The player who wins away the last object wins - a direct game, or the one who has to lose (it is impossible to skip a move) to pick up the last object wins - an inverse game. Since in this version of the rules, the direct game will simply be uninteresting (more on this later), they introduce an additional restriction - in the first move you can only delete one object.

First of all, we will determine that the game is finite, because with each move the number of objects strictly decreases and the game ends when the number of objects, calculated as zero, is reached, so we can count on success in the study of this game. Moreover, it is obvious that the game can not last more than H moves, remember this fact.

The study of the game consists in determining whether for a particular initial number of objects the player making the first move wins (since this is a zero-sum game, otherwise it is a losing player) with optimal play of both sides and at what minimum number of moves does the gain reach (or What is the maximum number of moves the loss moves away).

For some of H, the answer is obvious - with one object, the first one wins in one move in a direct game and loses in one move in an inverse (П1 = 1, И1 = -1). With two objects, the first player loses in two moves in a direct game and wins in two moves in an inverse (П2 = -2, И2 = 2), which may give rise to a hypothesis about the simplicity of the evaluation of this game, which is confirmed by the case of three objects (П3 = 3, I3 = -3). Fortunately (otherwise this post would not have been published), a game with four objects changes the picture somewhat (A4 = -4, but I4 = -3), so research of the game is really required.

For some of the H and for a certain type of game there are heuristic algorithms that give a guaranteed win. For example, for a direct game with an odd initial H, it is guaranteed to win, if you remove the central object by the first move and then repeat the opponent's moves using the central place as the axis of symmetry, then we are guaranteed to take the last object and win. The same strategy would have worked with an even number of objects, if not for the restrictions on the first move, which makes the game not so trivial. Generally speaking, the use of symmetric strategies is quite a frequent occurrence in a counting game, but not a panacea, because, for example, in our inverse game this strategy succumbs. It should be noted that heuristics provide an algorithm for winning but do not give an accurate assessment of the position, since there may be strategies

How we can evaluate the game - exactly as I received previous estimates for 1-4 objects - the method is called brute force from top to bottom - we must consider the complete game tree, that is, all possible moves for both sides and evaluate each position, including the original, according to certain rules. It should be noted that the existence of successful heuristics does not guarantee us an accurate assessment, since it answers only the first half of the question - who wins, but does not give the minimum required number of moves.

So, we have to build a complete tree of the game, but before we start building, we need to create a model of the object being studied, in our case, the game.

Why I am focusing attention at this stage - because we cannot explore the object in its material embodiment. No, theoretically it is possible (“in the world there is very little that is impossible theoretically”) and I can imagine a picture where a very large number of robots play a lot of games in the real world, but the material costs for such a solution to the game evaluation problem are reasonably representable values, so we are forced to embark on the path of modeling real objects with their software counterparts. And here it is very important to go along a thin line that combines a sufficient level of model adequacy and the necessary simplification.

But first, a bit of mathematics to assess the complexity of the task - we need to go through all possible moves in the game (attention is not all possible positions, this is a topic of another method, namely, moves) and we would like to evaluate the required amount of resources before starting work - to determine the order of the problem. On the first move, we have the opportunity to remove any piece (I will continue to call objects) from the H available, on the next move - any of the remaining H-1 or two adjacent chips (there will be no more such pairs than H-2) that gives the total number of Hx variants (H-1 + H-2). It is easy to see that after the third move we have Hx (H-1 + H-2) x (H-2 + H-3 + Δ) and so on.

If we restrict ourselves in each bracket to only the first terms of the sum, we obtain an estimate of the total number of moves, like H !, which gives us an estimate in quadratures H ^ H.

This is a very unpleasant result, which claims that we will have very big problems with significant H, so most likely head-in-front modeling will entail significant computational costs. For example, for 16 chips in the initial position, we will have to consider approximately 16! = 10E13 moves, and if performing one move is 10E-9 seconds (quite an optimistic estimate), then the total time will be about 10E4 seconds or almost 3 hours, which is a bit too much , but acceptable, but for only 20 chips the expected settlement time will be 77 years, which is clearly unacceptable. Factorial is growing very quickly and nothing can be done about it.

Let us pay attention to the fact that the number of moves significantly exceeds the number of possible positions, which is only 2 ^ N, and it is obvious that for 16 chips we will fall into a separate position 10E (13-5) = 10E7 times, which is pretty commonplace for reboring tasks. Remember this fact, it will be useful to us later.

Nevertheless, let's start writing the program, for which we will determine the model. To begin with, let's number the chips from 1 to H, then create an array with the number of elements H, and determine that the number 1 in the array element with the index n means the presence of the chip number n, and the number 0 - its absence in a specific position. Such a model is adequate, simple, intuitive, and allows you to make effective operations of removing the chips, as well as determining the condition “near location”.

Now that we have a model (data structure), we can proceed to stringing (owls on the globe) the algorithm on this model. The algorithm of complete enumeration with return is simple in the block diagram and consists of two independent parts - the actual enumeration and evaluation of positions, for the beginning we will implement the first part. Let's pay attention to the fact that this algorithm is not best implemented in the framework of the structural programming paradigm and would be somewhat more efficient if we allow ourselves to use the transition or code repetition, but without these deviations from the style, the implementation is not at all arty (cyclomatic complexity is quite acceptable) . Since we have not yet introduced the assessment, but I would like to get the result from the program, for the time being we simply derive the positions under consideration and examine them with our eyes to assess the correctness of the implementation and see

Now we will add a position estimate - of course, well-written code is self-documenting (although there are different opinions regarding this statement), but this part is better described with words. The idea is that we give an unambiguous assessment of the final positions (in our case, it is unique and consists of zero chips), based on the rules of the game, and all other positions are given a preliminary neutral assessment, and then we begin to refine it by transferring the estimates up the tree . The evaluation of the current position when moving backwards is changed by one from zero, then inverted and transferred to the previous position, where it is combined with the previous estimate according to the following rules:

1. the neutral score changes to a new one,
2. positive score changes to less positive
3. a negative score changes to a large negative or a positive one.

After we have completely gone through all the moves, the assessment of the initial position is final.

We add estimates to our procedure for generating all positions and we can admire the results of the analysis, which we display in the form of a table, add another stroke counter and a time meter spent on the analysis. I have a gcc compiler (in optimization mode -O2) on a machine with a processor that has turned out a table that fully confirms our initial assumptions about the factorial order of the complexity of the problem. From the same table, we see that I stopped expecting results with H exceeding 11, since the computation time became unacceptable (for me, it is possible, you are ready to wait half an hour) and our assumption about the progress and the nanosecond does not correspond to reality (average time consideration of the position is 100 ns). The question arises - what do we do if we want to have an estimate for more than 11,

We could take the path of small optimizations, play with transitions and flags, go into assembly inserts, apply tricky vector operations from the system of our processor’s commands, and we can win several times in this way, by an order of magnitude - maybe two orders of magnitude - highly unlikely, but we need a gain of many orders of magnitude, since the order (and even more) we will eat an increase of N per unit over 10. By the way, if you just turn on the optimization of the compiler, then it will do something for us and the execution time reduces I have 4 times - not bad at all and in line with our expectations.

Therefore, we must first try to improve the applied algorithms, and the first of these (and the main) improvement is the brute force method with clipping or the “alpha-beta procedure”. Its main idea looks quite sensible and consists in the fact that if we evaluate a certain position as a winning one, we stop improving the estimate for this one and go back through the tree. Such an approach can greatly increase the speed of the algorithm, especially if we examine the successful moves (leading to the gain) in the first place. But it can also increase the time, because checking the current assessment is added and the procedure for choosing the course is complicated, it is very difficult to estimate the effect of this method in advance, it is necessary to conduct an experiment. And one more consideration - we should not forget that in the case of busting with pruning, in the case of a fatty position, we give an estimate that is correct, but not accurate, since some of the options are not considered, and they could give a gain in a smaller number of moves. If we are satisfied with such a decrease in accuracy, then why not apply this method, but for an accurate assessment, nothing but complete enumeration does not work.

The results of the implementation of brute force with clipping are shown in the following table, and we see that there is a performance boost, and the gain is significant, but not sufficient for the study of large values ​​of N. In which direction we will continue our research - first consider another data structure, and then, As you may have guessed (it's nice to deal with a thoughtful audience) another algorithm.

Note that the data structure we have adopted makes the chips unique and, for example, a single (not having nearby) chip in a position is not equivalent to a single chip in the position n + 2, which is completely wrong. Select the key element of the game position - a group of adjacent chips and determine its main characteristic - the number of chips in the group. It is this information that uniquely identifies any position in the game and we must present it in a convenient form for programming. We choose the simplest and most obvious data structure — we start an array on H elements and in the n element of the array we store the number of groups with exactly n chips in it. Then, for example. For the initial position with 3 chips, we will have the representation {0,0,1}. The procedure for performing a move with this representation is still simple and effective, although, of course, harder than the first version. After the first move (which was two instead of three), we get the positions {0,1,0} and {2,0,0}.

Let us try to estimate the expected gain in the number of moves for a given data structure. For the first move, we have (H-1) / 2 + 1 options, for the second (we have broken the group H into m and Hm-1) (m-1) / 2 + (Hm-1-1) / 2 (take 1 chip) + (m-2) / 2 + (H-m-1-2) / 2 (take 2 chips) = (H-3) / 2 + (H-5) / 2 and by analogy , we conclude that at each step we save at least half of the moves. Then our gain should be at least 2 ^ H, which for large H is very, very good. In fact, the gain will be even greater, for example, for the position {8.0 ...} in the first variant, 8 moves must be enumerated, and in the second only 1 and the gain in this case will be 8 times. So we can firmly count on 2 ^ H, but expect much more, which we will check. And exactly, for the program for such a presentation, we get Table 4, The last line shows the increase in performance when switching to the second version of the data structure (calculated by hands). The increase is simply enormous and we are confident (have reached the bottom) have broken the ceiling of the possibility of analyzing up to 20 chips in the initial position at reasonable time costs.

Next, we can tackle the fine optimization of the algorithm with this data structure and get another performance gain, but we will not get such a dramatic (by orders of magnitude) growth, which means that Wirth was wrong. For example, in the program above, the procedure of creating the next candidate in the course was deliberately not optimal and its obvious correction (we leave it to the inquisitive reader) leads to an increase in the speed of work 3 times, but this is a trifle, albeit a pleasant one.

Pay attention to the results and see some not obvious things. For example, the program claims that a guaranteed win in a direct game for 9 chips is achieved not at all in 9 moves, as follows from the heuristic symmetric algorithm, but in only 7, with the first move coinciding with the heuristic one (and moreover, it is the only winning ), but the third and subsequent ones should not at all repeat the moves of the opponent, as follows from the naive algorithm, and the key position here is {1,0,0,1}, which has an estimate of +4. Now that we have given an accurate assessment of the game, we can ask interesting questions about the presence of positions with a stable assessment (in which we can allow the enemy to walk for himself), the presence of key positions in the search tree,

Here is the final rating table.

Chips	Straight	Feedback	Positions / Time	Positions / Time
one	one	-one	ten	ten
2	-2	2	4/0	20
3	3	-3	17/0	7/0
four	-four	-3	82/0	20/0
five	five	four	463/0	71/0
6	five	-five	3032/0	263/0
7	7	6	22693/0	1107/0
eight	-eight	-7	191422/0	4945/0
9	7	-7	1798427 / 0.1	24283/0
ten	9	eight	18634228 / 0.8	125419/0
eleven	eleven	-9	211177537 / 10.4	699165 / 0.1
12	-ten	-9	*** / 127	4057686 / 0.6
13	eleven	ten		25056975 / 3.84
14	-12	-eleven		160643971/28
15	13	12		1082854607/213
sixteen	-14	-13		*** / 1698

Nevertheless, we see that the estimate of the time of work remained factorial, albeit with a significant decrease in the growth rate. Look for other ways to explore the game tree.

We have brought the perfection algorithm from top to bottom (well, of course, in that ugly form that I sketched on the back of the envelope, we didn’t finish it; you can significantly improve the speed by carefully rewriting the basic procedures, and this is sure to be done, but the problem is not decides), then let's go the other way - from the bottom up. The idea of ​​this method is intuitively simple and understandable, but it is very difficult for a person to use - we start from the final position, the assessment of which is given according to the rules of the game, and begin to transfer the assessment up the tree using the same rules as for going from top to bottom. Of course, in this case, we are not considering possible moves down from the current position, but considering all positions from which we could get into the current one in one move. The assessment is transferred according to the rules given earlier. Further, we apply this procedure iteratively and when it ceases to produce results, that is, in the next round no position has changed the assessment, the task is completed and the assessment of the initial position is correct and accurate. This approach allows you to greatly reduce the search time, especially if you make some improvements, but it has a strong drawback (and this is a classic - we change time for memory), which significantly limits its scope - high memory requirements, since we must keep estimates for all possible positions at the same time, so the limit is the amount of RAM available to us (taking into account our ability to save it). In the case of the game in question, a bit representation method for the first data structure is suggested, there are other methods, allowing to reduce the amount of required memory (storing only three considered levels of the tree with the exception of the lower layer), but, naturally, by deteriorating performance, since the search becomes very nontrivial. However, for N not greater than 20, the total number of positions will be no more than 2 ^ 20, and an array of this size in memory for elements containing a number from -20 to 20, that is, an 8-bit number, I am quite a way to present and its implementation will not be difficult. So it is possible to write a program for such an algorithm and evaluate the resulting performance, but let's not hurry and make estimates. What memory we will have to allocate, is easy to determine, but with a temporary parameter is somewhat more difficult. Suppose we immediately create all possible positions, they will be M, then the average number of moves from one position can be estimated as no more than 2 * N (a very rough estimate). Then, at each iteration, we will need to perform no more than M * 2 * N transfer estimates, and, since in each cycle we will improve the estimate of at least one position, then the total work time will be of the order M * 2 * H * M.

Then, for the first way of presenting data, we get 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (we emphasize once again that this estimate is very strong from above) and, for example, for H = 20, the search time estimate from above -down will be 20! ~ 10E18, and for bottom-up search we have 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14, that is, for 20 chips we gain at least 10–6 times in time, which is very good. We also calculate for 9 initial chips, getting 9 for an enumeration from above! ~ 10E6, and for an iteration from below 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6, that is, starting with this number, the enumeration from the bottom wins. The last statement is somewhat hasty, since the procedure for evaluating the next position has become significantly longer - we will have to look for it among the already generated ones, but for this particular representation in the form of a bit array, this procedure is performed in O (1).

For the second representation, it is necessary to estimate the number of different positions, which is a task from the field of combinatorics. As an example, we can consider a game with 9 initial chips, for which the total number of different positions will be: 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39
Then the estimate using the same methodology will lead to the value H * M * M = 39 * 39 * 9 ~ 10E4, which is two orders of magnitude better in speed than the first representation, and as H grows, the gain will only increase. Compared with the search from above for the second view, we should also expect a significant improvement in performance, but it is more difficult to evaluate, so it's easier to try.

Therefore, if and to do the program parsing bottom-up, then for the second presentation. I will not bring the program, it is necessary to leave something for home analysis by readers. We must get results for significant H in a perfectly reasonable time. Another advantage of searching from the bottom is that we can save a lot by fixing the estimate for the lower half of positions (which has fewer chips than H / 2), since the lower half of the estimated half is transferred unchanged for the next number of chips, which will give us an additional gain in 2 times.

The necessary remark - earlier this paragraph was written quite differently, but in the process of programming one very unpleasant circumstance came to light, which called into question the results obtained. So I don’t have the right program, maybe I don’t want to show the wrong one, so I turned my laziness (I'm tired of this task) into a didactic method.

And finally, the necessary explanation for those who took my post too seriously and burns with (fair) indignation - I’m not at all sure that specifying the algorithms as the first term in the formula for defining the program confirms their greater significance, I completely agree that in some specific situations, a correctly chosen algorithm can give an ordinal increase in productivity, and I was not at all going to incriminate Dijkstra (whom I treat with respect) as errors. This was all a phrase for attracting attention, and posting something completely different - that the data structure is also extremely important from a performance point of view and we would like it not to be forgotten in the design process.

Ps. I am prompted here from the audience (hello, Max) that there is another method for studying the game - mathematical, and, given the hypothesis with a double last name, that most counting games are reduced to playing Him, so all we need to do is to calculate the sum The initial position (in my opinion, the statement is dubious), and you can also convert the original game to games on the graph (there are no objections here), for which you can expect an estimate of 1.878 ^ H over the time of work (although a specific number has puzzled me a little). Probably, these considerations have the right to life, at least, the articles of this content look convincing, but I have a special practice and leave these options again for inquisitive readers (ars longa, vita brevis).