Dagaz: evolution instead of revolution

In this world of what we would like NO!
We believe in the power to change it YES!

Yuri Shevchuk


')
Those of you who have read my articles should be aware that I have been studying the Zillions of Games metagame system for quite some time. For all this time, I developed a little less than fifty games and learned this platform up and down. My goal is to develop a similar (and preferably more functional) open source system. On the progress of this work and I want to tell.

In the image and likeness

As I said, I understand very well how Zillions of Games works. The absence of its source codes does not bother me, since I am not going to engage in the porting of this product. We are talking about the development of a new system from scratch, taking into account the merits (and even more deficiencies) of all the metagame platforms that I know at the moment. I will list them:

• Zillions of Games - the most famous metagame system, about which I wrote a lot
• Axiom Development Kit is a rather interesting project, implemented as a Zillions of Games expansion module, but also capable of operating autonomously.
• The LUDÆ project - A fun system designed for the automated development of new board games.
• Jocly - Modern and very interesting development (unfortunately, the quality of the games implemented for it leaves much to be desired)

All these products work and do exactly what they are intended for - they help, with the expenditure of more or less effort, to create computer implementations of various board games. It's not just about Checkers and Chess! The number and (most importantly) the variety of games already created exceeds all expectations. This is the main advantage of metagame systems - a working prototype of a new and rather complicated board game can be created in just a couple of hours!


Acquaintance with Jocly prompted me to revise some decisions. For further development, I firmly decided to use JavaScript, since this is obviously the easiest way to create an extensible and cross-platform system with a modern interface. The single-threading is a bit scary, but in fact this moment is important only for AI (and it’s not easy to use multithreading), and we have (for ourselves) found out that AI is not the strongest side of metagame systems.

On the other hand, the need for a certain DSL to describe the most routine moments of board games is quite obvious to me. Directly using JavaScript to develop the entire gaming model gives the process unprecedented flexibility, but requires diligence and concentration (and, as experience has shown, even their presence does not help much). Ideally, I would like to ensure compatibility with the base ZRF, in order to be able to run in the new system, if not all two and a half thousand games , then at least a significant part of them. Here is what Jocly developers write about it:

In ZoG, games are described in a lisp-based language called ZRF. This is where the ZRF has been defined. The Jocly Approach It is a good idea.

In theory, it would be possible to write a ZRF interpreter in Javascript. If you are willing to develop that kind of tool, let us know.

I decided to move along this path, concentrating, however, not on interpretation, but on a kind of “compilation” of the ZRF file in the game description for Jocly. Constant parsing of a text file, even if it contains a very simple description of the game, in a language resembling Lisp is not a task that I would like to engage in JavaScript.


Jocly is built according to the classic MVC scheme. To develop a new game, you need to write its model and presentation. The model determines the rules of the game, and the presentation - how the game will be shown to the user. The controller, written by the developers, takes care of the rest (including the bots wired into it).


The architecture of the universal model implemented by Z2J is also not very complicated. The basis is the Design component, which contains an immutable description of the rules of the game. The state of the game (placement of pieces on the board) is stored in instances of the Board class. The data of these components also do not change. By executing a move (applying the Move object to the Board ), we create a new state. The old remains the same!


To generate a move (create a Move object), the current state of the Board is used , but it alone is not enough to realize all the capabilities of the ZRF. In the process of generating a turn, ZRF can use variables (flags and position flags) that are not part of the game state. All this, as well as the logic of the execution of the stack machine commands, is handled by the Move Generator . In short, this is the architecture of the zrf-model.js module .

The devil is in the details

So, I was going to embed my model (zrf-model.js), configured by the compilation of Turkish Checkers , instead of the Jocly model , and try to run all this without making any changes to the game view . Looking back, I understand that the idea was adventurous (why - I’ll tell you below), but that’s what I started from. It was required a little from the model:

1. Keeping the current state of the game
2. Generation of all moves allowed for the current game state
3. Changing the state of the game by applying one of the generated moves to it

The difficulty was that the move, far from always, boils down to a simple movement of one of the pieces on the board. In the most general form, a move consists of a sequence of the following elementary actions:

• move - Moving a shape from one position to another
• capture - Deleting a piece from one of the positions on the board
• drop - Add (reset) a new piece to the board

For example, taking a piece in checkers consists of one moving one's own figure and taking an opponent's piece (in this case, the taking is not “chess”, since the position with which it is performed does not coincide with the final position of the piece's movement), but moves in such games as " Renju "consist of single drops of figures on the board. One should not think that when performing a move only one figure can move! So, when casting in chess, the rook and the king move simultaneously, within the same indivisible move.


But all this is only part of the problem! In checkers, the figure can (and moreover, is obliged) to perform several takes "along the chain." Until all captures are completed, the move is not transferred to another player. From the point of view of the model and for AI, this is one move! With the controller and the presentation is a little more complicated. In the user interface of the game, each checker take (partial move) must be performed separately. The user (player) must be able to choose one or another partial move at each stage of the execution of a long composite move.


Compound stroke generation is the simplest application of the ZrfMoveGenerator. Each copy of the generator forms its partial stroke, and the partial moves themselves concatenate into a “chain” of the composite stroke. Unfortunately, this is not the only way ZRF can use to determine moves. Consider a very simple case describing a piece moving through empty fields in one direction (such as Elephant , Rook and Queen in Chess ):


You can see that the add command, completing the formation of the move, is used in the body of the loop. This means that the figure can stop on any empty field, on the way to the enemy figure (and this will be considered a correct move). Of course, such a cycle can be eliminated by rewriting the definition:


The add command, executed in the body of the loop, leads to the formation of a non-deterministic move. The figure may stop or go further. For ZrfMoveGenerator, this means the need for cloning. The generator creates a complete copy of its state and pushes it onto the stack for subsequent generation, after which the current copy completes the formation of the turn. Here's what it looks like:



The FORK command clones the progress generator along with its entire current state and works as a conditional transition. In the generated generator, the control will go to the next command, and the parent will transfer control to the number of steps specified by the parameter (yes, this is very much like creating a process in Linux).


Using these two methods (alignment of move generators into a “chain” and cloning), you can implement any constructions of the ZRF language. Of course, the implementation is not simple and, due to the need to ensure compatibility with the ZRF semantics, is rather confusing. This is not a big problem if the code works. The problem is that ZRF itself is far from perfect!

Open your fingers

This year began with disappointments. To begin with, I was stumped by my attempts to create a universal DSL suitable for the simple description of all the board games I know. Universally, in principle, it turned out, “understandable” - no. Even relatively simple games, such as Fanoron , were keen to write about in some kind of horror.



With Jocly, the matter also somehow didn’t immediately set. I did not like her architecture. Let's start with the fact that to store the state of the board it uses a mutable Model.Board singleton. How to work with this AI-bot - I'll never know. But the main thing is not even that. One model in it is completely different from the other (just has nothing to do). At the same time, “magical” members, like mWho or mMoves , are actively used , and the presentation should “know” how the model works , since it uses it on a par with the controller!

My hopes to “replace” the model were doomed to failure in advance! That is, it is quite possible for me and it will be possible to replace the model of " Turkish drafts"so that the appropriate presentation worked with her , but for any other game (even for English Drafts ) you would have to start everything from the beginning, because her model differs very significantly from Turkish Drafts. I realized that I was not ready, in addition to the model, engage in more and developing presentation and was in a deep depression. and then, the work involved jonic and on the horizon a little brightened.

We decided to give up trying to integrate with Jocly and elaborate missing controllers (for network and local games, as well as utility autoplay ), presenter Supports (2D and 3D), as well as bots (in stock) independently. Moreover, he agreed to do all this work jonicso I can focus on working on the model. First, I got rid of Jocly's stupid inherited restrictions. Yes, now the model supports games for more than two players! And then I got a taste ...


I told you that I don’t like the restrictions of ZRF either? A smaller part of these options are the inherited Zillions of Games settings, which must be supported. The rest is extensions that have not been seen in ZRF before. So all the zrf-advanced options (you can enable them all together, with one team) expand the ZRF semantics, making it more convenient (I tried to accommodate the wishes of Zillions of Games users ), and the board-model options introduce new types of boards.


The options themselves are implemented as loadable JavaScript modules. For example, if the game (as in “International checkers”) requires you to take the maximum number of pieces, you need to load the corresponding module after loading the zrf-model . Module connection is performed by the checkVersion function:



The model will check the compatibility of versions of the requested modules and enable the appropriate options. This expanding mechanism gave me an interesting thought. In some games, there are rules that are devilishly difficult to implement using only ZRF. In most cases, these rules are reduced to additional checks that affect the ability to perform a particular move. Putting checks into loadable options will relieve me of the need to extend the base language to implement them (which would not be easy at all).


Let me explain by example.There is a kind of "Turkish drafts", which I learned about recently. The only difference between the “Bahraini checkers” and the Turkish ones is that they are not allowed to respond with an attack on an enemy attack. You can eat the attacked figure or get out from under the blow, but you can not attack another figure in return! Taking into account the fact that the rule also applies to ladies, the implementation of this game on ZRF turned out to be quite complex and, most importantly, not very “transparent”. But if I use extensible options, I have no need to complicate the code in ZRF!


I can take the " Turkish checkers " and connect the option that performs the necessary checks. The loadable module replaces the method of post-processing a move and, if necessary, can prohibit a previously generated move! The verification logic itself can be arbitrarily complex, it will still be more understandable than a similar implementation on ZRF! The case is not limited to the additional validation of already generated moves. The option can "enrich" the course! For example, performing a move in “ Go ”, you must do the following:

• Check 4 adjacent stones (3 at the border of the board or 2 in the corner).
• If the neighboring stone belongs to the enemy, build a "connected" group of stones into which it enters, and count the number of its dame (free points with which the group borders).
• If the enemy group does not border on free points - remove all its stones.
• If none of the enemy groups are removed, build a group containing the stone you just added.
• If the constructed group does not have a dame, prohibit the move (Strictly speaking, not always. Inga rules allow suicide for groups consisting of more than one stone).

All this can be “hidden” in a JavaScript extension ! It not only performs the necessary checks, but also completes the course by removing enemy stones. ZRF-description of the game becomes elementary ! Moreover, the extension is also suitable for other games! For example, for " Multicolor Go ".

More than one move ...

Expandable options allowed me to look at the project in a new way, but one small task still haunted me. In some games, under certain conditions, it is allowed to take any opponent's piece from the board . For example, in " Mill ":

• Players put on the board and move their pieces, trying to put 3 pieces in a row.
• If this succeeds, the player gets the right to remove any opponent from the board.
• At the same time, preference should be given to figures not standing "in a row" (figures constituting a number are taken as the last).
• If a player has 3 pieces left, he gets the opportunity to move them to any place on the board (not only along the marked lines).
• Loses a player who has less than 3 pieces left.

This is not to say that this is unrealizable on ZRF, but the code is very complicated. Well, in general, generating a set of moves that are the same in almost everything except for the piece to be taken is a rather dull decision. I thought it would be much more convenient if you could use arrays of positions in the actions of the moves :

 ZrfMove.prototype.capturePiece = function(pos, part) { - this.actions.push([ pos, null, null, part]); + this.actions.push([ [pos], null, null, part]); } 

It was quite a global alteration of the code, but unit tests , once again, helped. So far, such non-deterministic moves are planned to be generated only from JavaScript extensions, as part of the “enrichment” of the moves generated by the simplest ZRF description of the game. If we talk about the " Mill ", then we are talking about all the same addition to the course of taking the pieces. Just instead of a set of single takes, one non-deterministic is added:


But this is a broader concept. Not only taking can be non-deterministic! Remember that in the "Mill" there is a rule according to which the three remaining pieces of the player can jump "anywhere." In fact, this is a non-deterministic move to any free position:


The moving figure can also be an array! According to the rules of transformation in Chess, a pawn, reaching the last rank, can turn into any of 4 pieces (Knight, Elephant, Rook, Queen), at the player’s choice. This is nothing more than a non-deterministic transformation performed when the figure is moved. In the ZRF code, the pawn can be turned into a queen, for example, and in a JavaScript extension :


For the controller changes a little. Having received a move from the model that is valid for the current state of the board, he must check the size of the arrays in each of the actions. If more than one element is transmitted, the controller must go through all possible options, forming deterministic moves. I think it is not necessary to say that one should be careful with such non-determinism. The Cartesian product of several independent positions is capable of generating an incredible number of different moves!

Subtotals

In general, I can say that I like the direction of the project development. I abandoned the idea of ​​creating something revolutionary new (although it was not easy) and focused on achievable, but not less interesting goals. It can be said that of the two famous birds, I prefer the “crane in hand”. Work on the project helps to master a new language for me, and joining a new, more experienced developer to the project carries the hope that the work will still be crowned with success. I refused the “revolution”, but the project continues to evolve!