Dagaz: Halfway

Just to the right, the slope - fall, disappear!
A little to the left slope - still not save!
But calm, it remains to pass
Just two-quarters of the way!

Vladimir Vysotsky " Tensioned rope "

When the front of work looks completely immeasurable, it has to be divided into small pieces. Slice, for the first iteration, I chose a very small one :
')

Even without ladies! The figures move forward and can "beat" the enemy, according to the usual rules of " Checkers " (jumping over the figure). Having reached the last line of the board, they do not turn into anything, but can take enemy pieces, since taking "back" is allowed. In this regard, the game being developed is similar to the “Ossetian checkers” described in a previous article . Taking is mandatory and, from all possible moves, the player must choose a move that takes the maximum number of pieces. The game ends when one of the players cannot complete the next move (locked or lost all the pieces).

Of course, this is not about “code the next checkers” (this could be done with less effort). I want to develop a "meta-game" system that allows you to describe fairly complex logic games using simple DSL and, ideally, not possessing advanced programming skills (that is, exactly what Zillions of Games does, but in a fully open and cross-platform project).

Crazy Russian Stack Machine

I was thinking about one question for a very long time. In fact, in order to make descriptions of games as declarative as possible, I need non-deterministic programming ! Just look at this snippet:

 (move (check (any nw ne)) (check is-empty?) ) 

This is a description of the “quiet” stroke of the figure. And it says that any shape can move to the "northwest" or "northeast", provided that the target cell is empty. We are not talking about parallel execution (this kind of “optimization” is premature at the current stage of development)! Simply, for each of the figures there are (at least) two possible variants of the move, each of which must be considered.

It is very important that the moment of choosing a direction (let's call it a point of non-determinism) precedes the subsequent checks of the correctness of the course. If any of the checks is not performed (for example, going off the board), the analysis of the selected option immediately stops. We roll back to the “point of non-determinism” and choose the next possible option. In fact, this is the well-known " search with return " algorithm expressed in the most declarative form. Similarly, for example, regular expressions can be interpreted.

The any form is not the only source of non-determinism in the game description. In checkers, several takeings can be performed "along the chain" (moreover, if the continuation of the capture is possible, it should be performed). Here is how it looks in code:

 (move (while true (let dir (any nw ne sw se)) (check dir) (check is-enemy?) (capture) (check dir) (check is-empty?) (end-move) ) ) 

Do not be confused by the "infinite" cycle! It will be interrupted by any of the check-checks (along with the analysis of the corresponding course option), if the relevant conditions are violated. This code is a bit more complicated than the previous one, but to understand it is quite realistic. Here is what is done (in steps) in each iteration of the loop:

1. We select one of the four directions (already known to us by the any operator) and save it to a variable
2. We are moving in the chosen direction (provided that this is possible)
3. On the field where we moved, there must be an enemy figure (otherwise we interrupt everything)!
4. Take the figure (now we are not considering measures to counter the " Turkish strike ")
5. And we continue to move in the same direction (checking what is where to go)
6. Target cell must be empty!
7. ...

Then the magic begins. The end-move form says that in this place the move can be completed, and the (infinite) cycle requires moving on! In fact, this is equivalent to the execution of the following pseudocode, in which the familiar any again comes out into the arena:

 (if (any true false) (execute post-actions) (generate-move) ) 

Moreover, any is so universal that, with its help, you can rewrite another participant of the performance, who still remained in the shadows. Here is what pseudo-code equivalent to the check statement looks like:

 (if (not <condition>) (any) ) 

Choosing a variant without the possibility of choice is an excellent metaphor for completing any sorting. Of course, this does not mean that check will be implemented in this way, but we can implement it in this way!


In general, what to do was clear, but how to do it? The operator any (as, however, and much more) can be implemented with the help of continuations , but in Java there are no continuations! For a while, I seriously thought about translating kernel development to Scheme (in which there are not only extensions, but everything is built upon them). When (after lengthy experimentation with screwing "extensions" to syntactic expression trees) I was already at the maximum depth of despair and was reading with small strides " Lisp in small pieces " (thanks, ilammy ), I realized that there is another way.


In general, the secret is simple. If we consider the program as a chain of commands (with the possibility of arbitrary transfer of control to them) - the implementation of the continuations becomes obvious. In fact, the continuation is nothing more than the address of the command, together with the saved state of all variables. This is much simpler than what you have to deal with when using AST expressions .

With the "processor" itself, there were no questions. Stack machines have proved their worth more than once, and besides, I had to deal with them. Their only drawback is that a very high qualification of the programmer is required in order to constantly monitor the correct order of the operands on the stack. For me, this is not a problem, since I do not plan to open access to commands at the DSL level. The stack machine commands will be used exclusively for internal representation.


Further - everything is simple. Executing a chain of commands is, for the most part, a sequential pass through it into the AbstractPorocessor . The If and Jump commands provide the ability to branch and loop. Any is full of magic, but the implementation of Check is rather trivial. CommandFactory provides a convenient interface for creating commands by name. Only one thing can darken the mood. To implement rollbacks to "points of non-determinism", it is necessary to learn how to memorize and restore the state of all variables that are changed during program execution. Let's do this!

Not ACID

Before we proceed further, we will determine what we are going to store in memory. The list is big, but I really need all this! In parentheses, there is a sign of data storage, the value of which I will decipher later:

1. Placement of figures (part of the state)
2. Attribute values ​​of figures (state part)
3. Position attribute values ​​(state part)
4. Positional values ​​(temporary)
5. Values ​​of local variables (temporary)

The shape placement information is not a value (it consists of several related scalar values). The remaining values ​​will be typed, but their names will not be permanently associated with any particular type. In addition, implicit type conversions will apply, whenever possible. Currently, three types of values ​​are supported:

• Line
• Integer
• Boolean value

Most likely, I will add support for list types (they will be needed to implement games such as Ordo and Go ). In addition, now, I do not consider issues related to the optimization of performance and use of RAM. If the prototype works as I plan, it will be possible, for example, to think about using bit masks to store a large number of Boolean values.





This diagram shows all types of storages used in calculating the course. It does not consider data about the loaded game (such as the topology of the board). They can be quite complex, but from the point of view of the move generator, they are constant. All information about the placement of figures, as well as all the previously listed values, except for local variables, are stored in State . Objects of the State type can be cloned, but only information about the state elements gets into the cloned object (positional values ​​are discarded).

The main task of the LocalEnvironment is the management of local variables. The IEnvironment interface provides all the necessary methods for this. In addition, the get method returns the corresponding value if, instead of the variable name, a constant is passed to it (a number, a string in quotes, and true and false literals). Values ​​corresponding to these strings cannot be changed with the set! or redefined with let .

From the DSL point of view, any mention of a “bare” name (a string without quotes) results in the execution of a get command. The consequences of executing this command depend on the environment in which it is processed. All environments are chained and if the LocalEnvironment does not know any name, it refers to the StateEnvironment . This is where the fun begins. This module provides access to “pseudo-variables” that control navigation and provide access to information on the placement of pieces on the board.

Here's what it looks like. Suppose a model determines the position of a regular chessboard. In this case, we can use the name of any position in DSL as if it were a variable name. The value of a “variable” (for example, ' a1 ') is requested in the LocalEnvironment , and then in the StateEnvironment . This environment is associated with State and has complete information about all positions defined by the model. If the requested position exists, it returns true , and, as a side effect, the name of the position received is stored in a variable that determines the current position in State . Otherwise, false is returned and no side effects are performed. Names of directions are processed in the same way (with the difference that at the time of the request, the “current position” in the State must be defined). In addition to pseudo-variable navigation, StateEnvironment defines several more names that provide access to extremely useful information:

• position - the name of the current position
• is-empty? - true if current position is empty
• not-empty? - false if current position is empty
• is a friend - true if there is a friendly figure on the field
• not-friend? - true if there is no friendly figure on the field
• is-enemy? - true if there is a hostile figure on the field
• not-enemy? - true if there is no hostile figure on the field
• player - the name of the player holding the figure located at the current position
• piece - the type of figure located at the current position

If StateEnvironment does not know any name, it is accessed down the chain to PlayersEnvironment . The task of this environment is to clarify the relationship of the players. In the current iteration, everything is simple - if the requested player name does not match the name of the player performing the current turn, then he is the enemy. Subsequently, the logic of checks can be complicated (for example, coalitions of players will be added). Accepting the name specified in the player list, PlayerEnvironment compares it with the name of the current player and returns false if there is a mismatch ( does StateEnvironment use this when calculating is-friend? And is-enemy? ). Other names processed by this environment:

• current-player — ,
• next-player — ,
• turn-number — '' ( — )
• turn-order — ''

If the requested name is not known to PlayersEnvironment , it is even lower, but I’m going to talk about why GlobalEnvironment is needed and how it works in the next section (this is really a complex topic). Now the main thing, and where does ACID ? In general, absolutely nothing to do with, but I could not think of a more suitable name for the ITransactional interface . I don't even need transactions , per se. All that is required is to be able to define savepoints and perform a full rollback of the state to them. Thus, you have to roll back LocalEnvironment (the state of local variables) and State (the state of the board). StateEnvironment- just a wrapper over the State and does not own any data, and the state of PlayersEnvironment does not change in the course of calculating the progress. In addition, the Processor should be able to roll back the state of the data stack, but this is its internal matter.

Beyond “Transactional”

Above, I have already said that, according to the rules of most varieties of checkers , if taking is possible, it must be fulfilled (this is called taking priority). In some variants of the game, for example, in International Checkers , an even stricter rule applies (usually called the “majority rule”). According to him, from all possible moves, the player must choose a move that takes the maximum number of opponent's pieces. It is the “taking priority” that turns checkers into a positional, strategic game. Without it, the game would have been much less interesting! But how is this rule reflected in DSL?

 (piece (name Man) (pre ... (let captured 0) ) (post (check (<= max-captured captured)) (set! max-captured captured) ... ) ... (move (while true (let dir (any nw ne sw se)) ... (check is-enemy?) (capture) (inc! captured) ... ) ) ) 

A tricky check in the post I call a "broken invariant". How does he work?For example, during the parsing process, a move was generated that takes one piece. The check in the post was successful and the unit was saved to the max-captured variable . Now all moves that do not take a take will be rejected, since the condition in check will be violated. It is clear that the max-captured variable should be stored in a very special place. It should not be affected by any state rollbacks and, most importantly, it should be accessible to all variants of the calculated moves (almost to different realities). GlobalEnvironment is the place. This environment does not know how to create local variables with the let command , but creates global variables for anyset! or get- request! If the variable name is not declared with the attribute or let construction , the variable is created automatically, when it is first used, and its value is divided between the various options for calculating the course.

But, in themselves, global variables are only part of the story! Usually, there is a completely different case. We find some move, taking one piece, and then, for example, continuing the chain of takes, take the second, third, fourth ... A simple check does not help here! We have to repeat all the checks performed earlier, each time the global variable max-captured changes., and reject the corresponding moves, when violations are detected. The invariant for these moves was performed at the time of their generation, but was broken by changing max-captured ! This is a really tricky place and I’m not sure yet that it works. To manage all this "magic" should MoveGenerator .


Well, well, with the "rule of the majority" figured out (I hope that all this will really work), but what about other options for games? In some of them, it is not required to take the maximum number of pieces, only the capture itself is mandatory (the exception is “Ossetian checkers”, in which the priority of capture does not work). The “majority rule” itself is also understood in very different ways . Sometimes it is required to take the greatest number of ladies (if there is such an opportunity), in other cases, the taking of the lady is the priority. All this can be described in terms of “broken invariants”, but there is a more subtle point.

In almost all games of the family of checkers (from among the traditional games, the only exception is Fanoron"), starting the chain of taking, the player must go through to the end! At the same time, for example, in Russian Checkers , you do not need to take the maximum number of pieces. This is a more complicated restriction than a simple" majority rule "(in any case, until I came up with how to express it through a “broken invariant") and another type of deferred check will be used for it. The no-moves predicate will check if there are no possible continuations. If the continuation is detected, the previous (shorter) variant of the move will be canceled. I will not to occupy I implementation of this predicate in the current iteration.

About unit tests

The main thing you need to know about unit tests is that unit tests help! No, seriously, I am not a supporter of the TDD methodology , but the usefulness of the unit tests themselves, it is in this project, it is difficult to overestimate! Here (so far) there is no database or any network components (respectively, one does not have to wrestle with mock-wrappers for them), but the project itself is rather complicated. The idea that you can simply write it from scratch, run it entirely and debug it in this form - it scares me. Unit tests help to perform this debugging in parts, starting with simple things, like a system of commands , going higher and higher to more complex concepts.. This approach really works! In the process of writing tests, I have already found and corrected several serious errors. Similar corrections, at the stage of debugging the entire project, would have cost me much more.

When moving to a higher layer, unit tests give confidence (sometimes false, but it all depends on the coverage) that all underlying layers work as intended. Moreover, if something seriously changes in the project (and this happens), unit tests immediately signal what and how it fell apart. In a sense, unit-tests document the project's API (this of course does not cancel the usual documentation), while focusing on the most delicate and complex cases. In general, at the moment, I am working on unit tests and intend to continue moving in this direction until it is possible (up to the moment when the goal of the first iteration of the project itself becomes one of the tests). This is half the way and I hope to go all the way.